Archive for chess

monomial representations on Netflix

Posted in Books, Kids, pictures, Travel with tags , , , , , , , , , , , , on February 16, 2021 by xi'an

When watching the first episode of Queen’s Gambit, following the recommendations of my son, I glimpsed the cover of a math thesis defended at Cornell by the mother of the main character..! Prior to 1957, year of her death. Searching a wee bit further, I found that there exists an actual thesis with this very title, albeit defended by Stephen Stanley in 1998 at the University of Birmingham. that is, Birmingham, UK [near Coventry]. Apart from this amusing trivia piece, I also enjoyed watching the first episodes of the series, the main actor being really outstanding in her acting, and the plot unfolding rather nicely, except for the chess games that are unrealistically hurried, presumably because watching people thinking is anathema on TV! The representation of misogyny at the time is however most realistic (I presume|!) and definitely shocking. (The first competition game when Beth Hamon loses is somewhat disappointing as failing to predict a Queen exchange is implausible at this level…) However, the growing self-destructive behaviour of Beth made me cringe to the point of stopping the series. The early episodes also reminded me of the days when my son had started playing chess with me, winning on a regular basis, had then joined a Saturday chess nearby, was moved to the adult section within a few weeks, and … stopped altogether a few weeks later as he (mistakenly) thought the older players were making fun of him!!! He never got to any competitive level but still plays on a regular basis and trashes me just as regularly. Coincidence or not, the Guardian has a “scandalous” chess story to relate last week,  when the Dutch champion defeated the world top two players, with one game won by him having prepared the Najdorf Sicilian opening up to the 17th round! (The chess problem below is from the same article but relates to Antonio Medina v Svetozar Gligoric, Palma 1968.)

Le Monde puzzle [#1141]

Posted in Kids, pictures, R, University life with tags , , , , , , , , on May 4, 2020 by xi'an

The weekly puzzle from Le Monde is in honour of John Conway, who just passed away, ending up his own game of life:

On an 8×8 checker-board, Alice picks n squares as “infected”. She then propagates the disease by having each square with least two infected neighbours to become infected as well. What is the minimal value of n for the entire board to become infected? What if three infected neighbours are required?

A plain brute force R random search for proper starting points led to n=8 (with a un-code-golfed fairly ugly rendering of the neighbourhood relation, I am afraid!) with the following initial position

With three neighbours, an similar simulation failed to return anything below n=35 as for instance:

oops, n=34 when running a little longer:

which makes sense since an upper bound is found by filling one square out of two (32) and adding both empty corners (2). But this upper bound is only considering one step ahead, so is presumably way too large. (And indeed the minimal value is 28, showing that brute force does not always work! Or it may be that forcing the number of live cells to grow at each step is a coding mistake…)

value of a chess game

Posted in pictures, Statistics, University life with tags , , , , , , , , , , , , on April 15, 2020 by xi'an

In our (internal) webinar at CEREMADE today, Miguel Oliu Barton gave a talk on the recent result his student Luc Attia and himself obtained, namely a tractable way of finding the value of a game (when minimax equals maximin), result that got recently published in PNAS:

“Stochastic games were introduced by the Nobel Memorial Prize winner Lloyd Shapley in 1953 to model dynamic interactions in which the environment changes in response to the players’ behavior. The theory of stochastic games and its applications have been studied in several scientific disciplines, including economics, operations research, evolutionary biology, and computer science. In addition, mathematical tools that were used and developed in the study of stochastic games are used by mathematicians and computer scientists in other fields. This paper contributes to the theory of stochastic games by providing a tractable formula for the value of finite competitive stochastic games. This result settles a major open problem which remained unsolved for nearly 40 years.”

While I did not see a direct consequence of this result in regular statistics, I found most interesting the comment made at one point that chess (with forced nullity after repetitions) had a value, by virtue of Zermelo’s theorem. As I had never considered the question (contrary to Shannon!). This value remains unknown.

Death won the last chess game [but it took a while]

Posted in Statistics with tags , , , , , , , , on March 30, 2020 by xi'an

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…]