**Morpion Solitaire - Record Grids (5D game)**

August 21st, 2010: new 5D record
with a grid of 82 moves by **Christopher D. Rosin,**
USA, only 5 days after his 5T record!!! Two more moves than the previous
5D record by Tristan Cazenave. Chris Rosin got his result after only one
hour of computation, reusing the same software that produced his 5T record.
A very powerful algorithm and software!

- Download the text file of the 82 moves, which you can use directly in Pentasol, a freely downloadable Windows software

Look at his grid below or see the animated GIF file (2.1Mb, created by C. Rosin) showing the game, move by move.

*August
2010: Grid of 82 moves done by computer by
Chris Rosin (click on the image to enlarge it)*

In May 2011, **Chris Rosin** announced
that the new enhanced version of his program, able to produce a new
5T record, has unfortunately been unable to produce a new 5D record.
However, good results because, after 82 runs of his app, one hour for each
run, 25 of them produced grids of 82 moves, which equals 25 times his previous record!

Here are 19 grids, Chris does not have images of the 6 missing grids. After rotations/symmetries, I have oriented these images in the same direction as his first record of 2010, we can better see that they are extremely close... See the Powerpoint presentation (2.1Mb), or its equivalent PDF file (2.3Mb). Quite the same, including the same strange "hole" in the Greek cross. What I thought below on Cazenave's grid of 80 moves was wrong: finally not so rare to have a hole in a good grid...

*May 2011: New grids of 82 moves
by Chris Rosin, compared to the grid of 2010 (click on the images to enlarge them)*

Two grids
of 82 moves were found in 2012 by **Tristan Cazenave** using his new
Monte-Carlo algorithm called "Beam search". He also reused, separately,
the NRPA
(Nested Rollout Policy Adaptation) algorithm of Chris Rosin
inspired by his works of 2009, but improved with this beam search: he
did not obtain a better score, but this improved algorithm is interesting for the traveling salesman problem with time windows, a very
difficult version of the old classical salesman problem. Look at papers
published from 2009 to 2012 by Chris Rosin, and by Tristan Cazenave (and Fabien
Teytaud).

2012:
Two grids of 82 moves by Tristan
Cazenave.

For a better comparison, grids are here oriented after rotations/symmetries
in the same direction as Rosin's grids.

The first one is the same as
Rosin's 82e, and the second one is very close to
Rosin's 82d and 82i.

**
****Tristan Cazenave** (Paris 1968 - )** **in 2008

Before 82 moves, the previous record was a grid
of 80 moves by **Tristan Cazenave**, obtained by computer February 1st, 2008. Tristan
Cazenave, a well-known specialist of the Go game, had already written papers
on Morpion Solitaire and had already been the record-holder with his grids
of 76 and 78 moves. He
was assistant professor at the LIASD (*Laboratoire d'Informatique Avancée
de Saint-Denis, University of Paris 8*), http://www.ai.univ-paris8.fr

November 3rd, 2008: another grid
of 80 moves found by Tristan Cazenave. He is now professor at the LAMSADE
(*Laboratoire d'Analyse et Modélisation de Systèmes pour l'Aide à la Décision,
University of Paris-Dauphine*). His home page is http://www.lamsade.dauphine.fr/~cazenave

*
2008 (February on the left, November on the right): Grids of 80 moves done by computer by Tristan Cazenave*

My own feeling is that Cazenave's records above can still be improved. Look at the 4 unused potentials of the November 2008 grid: 20-24-26, 38-32-41, 75-67-65 and 77-70-66. And look at those in the south-west corner of the February 2008 grid: alignments 71-76-73, 63-70-79 and 72-68-75. Leaving so many unused potentials in so small a zone usually offers, after slight modifications in the moves, a better solution. And it is rare to see a record grid with a hole, here on the left of move 18. But after my own tries, I am unable to improve his grid. I succeeded in using his 63-70-79 potential adding one move in the south-west corner... but only if I suppress one move on the opposite north-east corner. 80 + 1 - 1 = again 80 moves...

**Zbigniew Galias**, Poland, has computed
at the end of February 2010 that the last 47 moves of both of Cazenave's grids are optimal.

*February
2008: Another grid of 80 moves by Christian
Boyer, after some modifications of the Cazenave's grid*

The previous record
was set 8 months earlier also by computer by the Finnish team **Heikki Hyyrö**
and **Timo Poranen**, *University of Tampere*. They used a simulated
annealing algorithm described in their "New Heuristics for Morpion Solitaire"
paper. For this kind of algorithm, look at http://en.wikipedia.org/wiki/Simulated_annealing
or http://mathworld.wolfram.com/SimulatedAnnealing.html.

*June 2007: Grid of 79 moves done by computer by Heikki
Hyyrö and Timo Poranen*

In his "Reflexive
Monte-Carlo Search" paper at CGW 2007 (*Computer Games Workshop*),
**Tristan Cazenave** published this grid of 78 moves.

*May 2007: Grid of 78 moves done by computer by Tristan
Cazenave*

For the previous records
of the 5D game, look
at http://slef.org/jeu
page by **Stefan Langerman**. Some old records were found by hand,
without computer.

Analyzing
the symmetrical grids by computer, **Michael Quist**, USA, found this grid of 68 moves
in April 2008. He thinks that it should be the best possible score of all symmetrical
5D grids (inversion symmetry
like this one, but also diagonal reflection,
horizontal reflection, 90-degree rotation, ...).

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

© Christian Boyer, www.morpionsolitaire.com