# Morpion Solitaire

Go down for the high scores (The best solution is now 79).

Here is a game that my father plays from time to time.
Try it: it's very simple, and fun when you have nothing
else to do.
You start with a cross formed by 36 points on a grid as shown below
(images were generated by a script from
Stefan
Schmieta, further improved by
Erik D. Demaine):

At each step, add a line in any of the 4 directions : | - / \, passing
thru 5 adjacent points of the grid, 4 of which already exists, and one
that you add. For example, from the starting position above, you could
add a line and obtain:

Moreover, two lines in the same direction cannot touch each other,
i.e. cannot share a point, and each line has to have exactly five
points.

The goal is to draw as many lines as possible.

### Question:

What is the maximum number of lines you can draw? One can easily find
an upper bound of - say - 141, can you prove a better bound?

After several years of intensive search, my father has never been able
to exceed 64 lines (see below). Is there a better solution?

If you can improve those upper and lower bounds of the optimal
solution, send me an
email, and I'll include your result in this page.

Stefan
Schmieta's program found a better solution: the number to beat is
now 65

### Oct 15, 1996

Stefan
Schmieta's program found an even better solution: the number to beat is
now 66
He used a simple random walk algorithm!

The human mind proved once more its supremacy over the machine (but
for how long??). My dad raised the high score to 67, and then 68.
Here is the 68 solution:

Machines win this new round with a new high score of 69, 72, then 74.
The solutions were constructed by
Heikki Hyyro and
Timo Poranen
using a simulated annealing algorithm.
Here is 74 (click for an animated gif, also available in
xfig and
eps).

A new record of 76 appears in the paper "Reflexive Monte-Carlo Search" by
Tristan Cazenave
that was recently accepted in CGW 2007 in Amsterdam. He
further improved his result to 78:

After matching the score of 78 using their simulated annealing algorithm,
the Hyyro-Poranen team just improved the score to 79: