Archive for chess

a grim knight [cont’d]

Posted in Books, Kids, pictures, R, Statistics with tags , , , , , , , on October 20, 2016 by xi'an

As discussed in the previous entry, there are two interpretations to this question from The Riddler:

“…how long is the longest path a knight can travel on a standard 8-by-8 board without letting the path intersect itself?”

riddlerechckas to what constitutes a path. As a (terrible) chess player, I would opt for the version on the previous post, the knight moving two steps in one direction and one in the other (or vice-versa), thus occupying three squares on the board. But one can consider instead the graph of the moves of that knight, as in the above picture and as in The Riddler. And since I could not let the problem go I also wrote an R code (as clumsy as the previous one!) to explore at random (with some minimal degree of annealing) the maximum length of a self-avoiding knight canter. riddlerechkThe first maximal length I found this way is 32, although I also came by hand to a spiralling solution with a length of 33.

riddlerechckRunning the R code longer over the weekend however led to a path of length 34, while the exact solution to the riddle is 35, as provided by the Riddler (and earlier in many forms, including Martin Gardner’s and Donald Knuth’s).

[An unexpected side-effect of this riddle was ending up watching half of Bergman’s Seventh Seal in Swedish…]

grim knight [a riddle]

Posted in Kids, pictures, R with tags , , , on October 14, 2016 by xi'an

The Riddler of this week had a riddle that is a variation of the knight tour problem, namely

“…how long is the longest path a knight can travel on a standard 8-by-8 chessboard without letting the path intersect itself?”

the riddle being then one of a self-avoiding random walk [kind]… As I could not get back to sleep last night, I spent a couple hours (!) on this riddle, programming a random walk [or more accurately, a random canter]. This is a brute-force approach in that I pick any acceptable move with the same probability and stop when there is no further move available. [The title refers to the recommendation to avoid the rim of the chessboard with a knight: “a knight on the rim is grim”…]

board=rep(1,64)
curr=sample(1:64,1)
board[curr]=0
cont=0
stop=TRUE
while (stop){
  mov=nexx(curr,board)
  curr=mov$mov;board=mov$boa
  stop=(curr>0);cont=cont+stop}

with my function nexx a rather clumsy 50 lines business of selecting one acceptable move from the current position curr. This function returns the proposed move as well as the updated board with zeros in squares already visited by the knight. Which highlights the ambiguity in the question, namely how one defines the path of a knight? For an acceptable knight move from A to B, there are two possible paths: either take two steps in one direction and one in the orthogonal direction or the opposite. I thus pick one of the two (at random) and prohibit further visits to those squares. An alternative meaning of the question could be that the line joining A to B cannot be crossed ever again, which excludes less moves (but is more cumbersome to code). Anyway, with the former interpretation of a path, repeating the self-avoiding moves led to a maximum of 19 moves, with one solution exhibited below. (Since (64-1)/3=21, it is conceivable that the true maximum is 20 or even 21. In the path representation below, it seems possible to include yet another move by going to (4,1) instead of (4,5). But this is apparently excluded by the square representation on the right. Why is why the path representation is somewhat confusing!)

riddlerchk

Today, namely on October 15, I received a solution of length 21, hence covering the entire board without ever using the same square twice. It was sent to me by Paul-Henry Cournède (a geographical neighbour!) and is “obvious” once you see it. Which may be why the alternative interpretation of “path” was chosen in The Riddler. And why my rhs representation is clearly misleading!

knight_21_moves

Einvígið [book review]

Posted in Books, Kids, Mountains, pictures, Travel with tags , , , , , , , , on August 17, 2015 by xi'an

Reykjavik2In Roissy (De Gaulle) airport, prior to catching my flight to Seattle, I noticed a “new” Indriðason‘s novel, Le Duel (Einvígið), that has not yet been translated into English. But just translated into French! This is a most unusual novel in the Erlendur series, in that the central character of the series only appears as a young cop in the final lines of the novel. Instead, the mentor of Erlendur, Marion Biem, is conducting an inquiry as to who had killed a young man in an almost empty Reykjavik cinema. Where almost all spectators seemed to have something to hide, if not always a murder… A classical whodunnit?! Not really because this happens in 1972, during the famous Fisher-Spassky duel, and that duel is unrelated to the murder, while the Icelandic police seems overwrought by the event and the presence of Russian and American double-agents in Reykjavik…

I found the whole exercise interesting, creating a sort of genealogy in the Erlendur series, with Marion’s mentor playing a side role and his early training in Glasgow (of all places!), with the re-creation of a 1972 Iceland and the chess match between Fisher and Spassky at the height of the Cold War. Plus a reminder about the tuberculosis epidemics of the 1930’s, where  The detective side of the novel is however less convincing than usual, with clues and fingerprints appearing at the most convenient times. And a fairly convoluted resolution. Still worth reading, especially on a long flight!

the signal and the noise

Posted in Books, Statistics with tags , , , , , , , , , , , on February 27, 2013 by xi'an

It took me a while to get Nate Silver’s the signal and the noise: why so many predictions fall – but some don’t (hereafter s&n) and another while to read it (blame A Memory of Light!).

“Bayes and Price are telling Hume, don’t blame nature because you are too daft to understand it.” s&n, p.242

I find s&n highly interesting and it is rather refreshing to see the Bayesian approach so passionately promoted by a former poker player, as betting and Dutch book arguments have often been used as argument in favour of this approach. While it works well for some illustrations in the book, like poker and the stock market, as well as political polls and sports, I prefer more decision theoretic motivations for topics like weather prediction, sudden epidemics, global warming or terrorism. Of course, this passionate aspect makes s&n open to criticisms, like this one by Marcus and Davies in The New Yorker about seeing everything through the Bayesian lenses. The chapter on Bayes and Bayes’ theorem (Chapter 8) is a wee caricaturesque in this regard. Indeed, Silver sees too much in Bayes’ Essay, to the point of mistakenly attributing to Bayes a discussion of Hume’s sunrise problem. (The only remark is made in the Appendix, which was written by Price—like possibly the whole of the Essay!—, and  P.S. Laplace is the one who applied Bayesian reasoning to the problem, leading to Laplace’s succession rule.) The criticisms of frequentism are also slightly over-the-levee: they are mostly directed at inadequate models that a Bayesian analysis would similarly process in the wrong way. (Some critics argue on the opposite that Bayesian analysis is too much dependent on the model being “right”! Or on the availability of a fully-specified  model.) Seeing frequentism as restricted to “collecting data among just a sample of the population rather than the whole population” (p.252) is certainly not presenting a broad coverage of frequentism.

“Prediction serves a very central role in hypothesis testing, for instance, and therefore in all of science.” s&n, p.230

The book is written in a fairly enjoyable style, highly personal (no harm with that) and apart from superlativising (!) everyone making a relevant appearance—which seems the highest common denominator of all those pop’sci’ books I end up reviewing so very often!, maybe this is something like Rule #1 in Scientific Writing 101 courses: “makes the scientists sound real, turn’em into real people”—, I find it rather well-organised as it brings the reader from facts (prediction usually does poorly) to the possibility of higher quality prediction (by acknowledging prior information, accepting uncertainty, using all items of information available, further accepting uncertainty, &tc.). I am not sure the reader is the wiser by the end of the book on how one should improve one’s prediction tools, but there is a least a warning about the low quality of most predictions and predictive tools that should linger in the reader’s ears…. I enjoyed very much the chapter on chess, esp. the core about Kasparov’s misreading the computer reasons for a poor move (no further spoiler!), although I felt it was not much connected to the rest of the book.

In his review, Larry Wasserman argues that the defence Silver makes of his procedure is more frequentist than Bayesian. Because he uses calibration and long-term performances. Well… Having good calibration properties does not mean the procedure is not Bayesian or frequentist, simply that it is making efficient use of the available information. Anyway, I agree (!) with Larry on the point that Silver somehow “confuses “Bayesian inference” with “using Bayes’ theorem”. Or puts too much meaning in the use of Bayes’ theorem, not unlike the editors of Science & Vie a few months ago. To push Larry’s controversial statement a wee further, I would even wonder whether the book has anything to do about inference. Indeed, in the end, I find s&n rather uninformative about statistical modelling and even more (or less!) about model checking. The only “statistical” model that is truly discussed over the book is the power law distribution, applied to earthquakes and terrorist attack fatalities. This is not an helpful model in that (a) it does not explain anything, as it does not make use of covariates or side information, and (b) it has no predictive power, especially in the tails.  On the first point, concluding that Israel’s approach to counter-terrorism is successful because it “is the only country that has been able to bend” the power-law curve (p.442) sounds rather hasty. I’d like to see the same picture for Iraq, say. Actually, I found one in this arXiv paper. And it looks about the same for Afghanistan (Fig.4). On the second point, the modelling is poor in handling extreme values (which are the ones of interest in both cases) and cannot face change-points or lacks of stationary, an issue not sufficiently covered in s&n in my opinion. The difficulty with modelling volatile concepts like the stock market, the next presidential election or the move of your poker opponents is that there is no physical, immutable, law at play. Things can change from one instant to the next. Unpredictably. Esp. in the tails.

There are plenty of graphs in s&n, which is great, but not all of them are at the Tufte quality level. For instance, Figure 11-1 about the “average time U.S. common stock was held” contains six pie charts corresponding to six decades with the average time and a percentage which could be how long compared with the 1950s a stock was held. The graph is not mentioned in the text. (I will not mention Figure 8-2!) I also spotted a minuscule typo (`probabalistic’) on Figure 10-2A.

Maybe one last and highly personal remark about the chapter on poker (feel free to skip!): while I am a very poor card player, I do not mind playing cards (and loosing) with my kids. However, I simply do not understand the rationale of playing poker. If there is no money at stake, the game does not seem to make sense since every player can keep bluffing until the end of time. And if there is money at stake, I find the whole notion unethical. This is a zero sum game, so money comes from someone else’s pocket (or more likely someone else’s retirement plan or someone else’s kids college savings plan). Not much difference with the way the stock market behaves nowadays… (Incidentally, this chapter did not discuss at all the performances of computer poker programs, unexpectedly, as the number of possibilities is very small and they should thus be fairly efficient.)