Morpion Solitaire - Records Grids (5T game)

Christopher D. Rosin in 2009 (Milwaukee, Wisconsin 1971 - )

August 16, 2010: new record with 172 moves! With his grid obtained with computer, Chris Rosin is the first to have succeeded to beat the old record of 170 moves done 34 years earlier by C.-H. Bruneau without computer! And this is tremendous progress with his new algorithm, the previous record obtained by computer having only 146 moves. Five days later, he also beats the 5D record. Chris has lived in San Diego, California for the past 18 years, and is a cofounder of Parity Computing where he is Chief Algorithmist. His personal home page is www.chrisrosin.com.

August 2010: Chris Rosin's grid of 172 moves
(click on the image to enlarge it)

I notice that the road to his 172 moves is very tight: for the moves 132, 134, 135, 136, 144, 145, 150, 168, 170, 171 and 172, there is no other choice. It is the opposite of common sense: we may think that a record should offer several possible moves at each step. In Bruneau’s grid, only the last moves 169 and 170 were unique. Two files detailing Rosin's grid:

• See the animated GIF file (7.5Mb, created by C. Rosin) showing the game, move by move
• Download the text file of the 172 moves, file that you can directly use in Pentasol, a Windows software freely downloadable

Here are some details on the search that Chris Rosin sent me:

Monte-Carlo search has had some recent success in the game of Go (for example: www.lri.fr/~teytaud/mogo.html), and also in other domains (including some of the recent Morpion Solitaire results by others). Monte-Carlo search methods operate by performing randomized "playouts" and then making moves which worked well in these playouts. In Morpion Solitaire, a "playout" consists of a randomized sequence of legal moves that proceeds until no further legal moves are available. An important factor for the success of Monte-Carlo search is the choice of playout policy, for biasing the randomized move choices during the playout. I spent several months developing and fine-tuning a playout policy for Morpion Solitaire, combined with some modified Monte-Carlo search techniques. This got me as far as 166 on the 5T game, but I could get no further. So I then threw out my fine-tuned playout policy, and tried instead to apply machine learning techniques to learn playout policies from scratch. This general idea has been tried in Go as well (D. Silver & G. Tesauro, "Monte-Carlo simulation balancing." ICML 2009). I combined this policy learning with nested search (somewhat like: T. Cazenave, "Nested Monte-Carlo Search." IJCAI 2009), and this succeeded in producing the result with 172 lines on August 16, 2010.

The code was written in C++. For the final version, I did 10 runs (each with a different random seed), with each run taking about 3 days on a single CPU core of a 3GHz Intel CPU. Two of these runs yielded 170 (not the same as Bruneau's grid), and one yielded the result with 172 lines.

And here are his two previous grids of 170 moves, equaling the score got in 1976 by C.-H. Bruneau (but different from Bruneau's grid):

The two first images are Rosin's grids A and B of 170 moves. I notice that these two grids are very close:
the third image C comes from the image B after rotation and symmetry, now looking like the image A (click on the images to enlarge them).

Bruneau's grid of 170 moves: the world record from 1976 to 2010

Charles-Henri Bruneau in 2008 (Perpignan 1953 - )

April 1976: Science & Vie published a Morpion Solitaire grid done by Charles-Henri Bruneau, without any computer. With its 170 moves, it was for 34 years, up to August 2010, the world record at the original 5T game! Charles-Henri Bruneau is now professor at the I.M.B. (Institut de Mathématiques de Bordeaux, University of Bordeaux 1). His home page is http://www.math.u-bordeaux.fr/~bruneau. Two astonishing facts described below:

Story of the Bruneau's grid: Charles-Henri Bruneau, student at that time, learnt only in 2008 that his grid had been published!
5T grids done by computer: before Rosin's grid, the computers were strangely far from matching or beating his record with their maximum at 146 moves.

Bernard Helmstetter, in his thesis of February 2007 ("Analyses de dépendances et méthodes de Monte-Carlo dans les jeux de réflexion"), studied Bruneau's grid, and found it optimal for its last 109 moves. If his computing is correct, it is impossible to get a better score for any play starting from the 61st move of this grid! An impressive result for a grid created by hand.

Download the Bernard Helmstetter's thesis, PDF file of 2.3Mb, written in French: see more particularly the chapter 5, "Morpion Solitaire", pp. 83-100.
• Download the text file of the 170 moves, file that you can directly use in Pentasol, a Windows software freely downloadable

C.-H. Bruneau's grid of 170 moves as published by Pierre Berloquin in Science & Vie, April 1976, page 130.
Slight errors made by the magazine: the horizontal lines between 155-165-164 moves should not be drawn
and the vertical line between 159-154 moves should be drawn.

Denis Excoffier copied Bruneau's grid in 2000, from the 1st to the 170th move. There is another grid of 170 moves, apparently done in January 1982 by J.-B. Bonté, never published in a magazine. This grid, very close to Bruneau's grid, was sent by Pierre Berloquin to Jean-Charles Meyrignac in 2003:

J.-B. Bonté's grid of 170 moves

Before Bruneau's grid, the previous records were done in 1975 independantly by Joseph Martin, Michel Szeps and Yoland Strehl with grids of 164 moves.

Story of the Bruneau's grid

Incredible! Charles-Henri Bruneau did not know that his own grid had been published!

More than 30 years after its publication, I was very pleased to send him the information in my email of January 23, 2008.... Of course, he remembered that he had reached this score of 170 moves and to have sent the grid to Science & Vie, but he thought (and was disappointed) that his grid had never been published... He only knew that his name with his score had been mentioned -without the grid- in some websites and papers (for example in Jeux & Stratégie). Here is Pierre Berloquin's column that he had never seen, presenting his grid:

Science & Vie, April 1976: publication of the Bruneau's grid of 170 moves, by Pierre Berloquin
(click on the images to enlarge them, or download the PDF file, 2.4Mb)

Asking Charles-Henri Bruneau to tell me the history of his grid, here is what he remembers (translated in English):

Charles-Henri Bruneau in 1970s

When I was a teenager, I knew the Morpion game like other schoolboys. And also Solitaire with its two versions (cross and octogon) that I liked very much, mainly the octogon because it is more difficult and for which I had solutions without starting from the center. I learned later that we could demonstrate that there is no solution starting from the center! And one day I came across an article in Science & Vie on Morpion Solitaire. I found this game interesting and I remember having played it a lot during my spare time when I was a bachelor's student at Perpignan, during the school year 1974-1975. Being inspired by the previous records (*) published by S&V, I first got 166 moves, then I kept on playing with the hope of improving my score and got 170 in the spring of 1975. Because I progressed, I continued to search again; the summer passed and I left Perpignan for my master's studies in Nice in October 1975 and never played again.

I remember being greatly disappointed by the article with the record of 164 (**) because I already had a much better record... and that's what prompted me to release my own record. When I returned to my parent's home at Perpignan for Christmas, I found my grids and sent in my best one. My grid was handwritten; at that time I had drafts, and I made a good copy on cross-ruled paper from a ring binder that I sent to S&V without even keeping a copy! I did not hear whether it was received, and thought that my grid had not been published. Much later, I met somebody who, learning my name, asked me if I was the Morpion Solitaire player and told me that he had seen my name in S&V. At long intervals, I had some news from other persons interested in this game, then in 2003 Jean-Charles Meyrignac contacted me, and now you tell me that my grid had finally been published in April 1976!

Notes
(*) Probably the grid of 162 moves by Rémy Daubié published by Pierre Berloquin in Science & Vie, November 1974
(**) Grid of 164 moves by Joseph Martin published in November 1975

During the summer of 2008, Pierre Berloquin honoured me by entrusting his archives to me: I was very happy to find Bruneau's original letter, including his grid which has been during 34 years the world record! Here is this "historic" letter which was written on January 2nd 1976 (the author C.H. Bruneau, happy that his writing has been found, authorize me to publish it here):

   
Original letter of Charles-Henri Bruneau sent to Science & Vie, Pierre Berloquin's column
(click on the images to enlarge them)

5T grids done by computer

Before Rosin's grid, computers were unable to reach very big scores at this 5T game. The first big computed grids, 117 then 122 moves, were published by Hugues Juillé in his papers of 1995 then 1999, for his PhD thesis at Brandeis University, USA. Later, in January 2003, Pascal Zimmer reached 143 moves. Then in December 2007, Tristan Cazenave, LIASD, University of Paris 8, reached 144 moves:

December 2007: Grid of 144 moves done by computer by Tristan Cazenave

Haruhiko Akiyama in 2010 (Tokyo 1987 - )

The computing record became 145 moves, reached February 4th 2010 by Haruhiko Akiyama, a student of TUAT (Tokyo University of Agriculture and Technology). Using a modified "nested Monte-Carlo search" (see Cazenave's two papers of 2009), during 21 days he ran his own program written in C on a PC, Intel Core2Duo E8400 at 3.00GHz.

I notice, looking at the grid, that this record by computer can be improved by hand. For example (maybe among other possible improvements), it is easy to get 149 moves:

• move 23, instead of X-20-X-X-23, it would be better to play X-X-23-X-8, because then there is a new possible move with 48-146-X-20-X.
• move 18, instead of 5-6-18-X-10, it would be better to play 16-5-6-18-X (or X-16-5-6-18), because then there is a second new possible move with X-10-90-110-147.
• move 108, instead of 65-108-57-107-81, it would be better to play 82-65-108-57-107, because then there is a third new possible move with 107-81-99-148-147.
• renumber move 44 by a new move 32 (still obtained by 32-9-X-25-26), then instead of the old move 32 with X-32-20-X-27, play a new move 33 with 32(=old 44)-22-X-33-20, renumber old moves 33 to 43 by new moves 34 to 44, do not modify moves 45 to 148, and there is a fourth new possible move with 20-X-27-51-149.

Zbigniew Galias, Poland, has computed at the end of February 2010 that the last 71 moves of this grid improved at 149 moves are optimal.

February 16th 2010, Haruhiko Akiyama reached 146 moves: his program finally saw my last remark above and ended after 33 days of running. Renumbering the moves, my three other remarks can be again applied and allow to get 149 moves. With his professor Yoshiyuki Kotani, he published a paper in Japanese, reporting his grid of 145 moves (paper submitted before his new grid of 146 moves).

• Download the text file of the 145 moves, and of the 146 moves, files that you can directly use in Pentasol, a Windows software freely downloadable

February 2010: Grids of 145 and 146 moves done by computer by Haruhiko Akiyama

Analyzing the symmetrical grids by computer, Michael Quist, USA, found this excellent and very nice grid of 136 moves, only 10 moves less than the above record! He thinks that it should be the best possible score of all symmetrical 5T grids (inversion symmetry like this one, but also diagonal reflection, horizontal reflection, 90-degree rotation, ...).

April 2008: symmetrical grid of 136 moves done by computer by Michael Quist

Jean-Jacques Sibilla, IPGP (Institut de Physique du Globe de Paris), http://www.ipgp.fr/~sibilla, is doing an interesting search: since 2007, his computer has generated more than 800 million grids (status in February 2010), where the moves are done at random. His main results:

extremely difficult to get random grids of more than 100 moves, his best grid having 102 moves
two peaks at 21 and 64 moves
impossible to get fewer than 20 moves, as mentioned in the worst possible grids

Scores after 34,300,000 random grids, computed by Jean-Jacques Sibilla

© Christian Boyer, www.morpionsolitaire.com