Morpion Solitaire - Score Limits


It is impossible to have an infinite number of moves at Morpion Solitaire. Any game has a number of moves within these limits:

We can also note than, by definition of their rules, a 5T record score CAN'T be better than 5T+/5T#/5T++ record scores (games with more free rules), themselves limited by the same upper bound:


Mathematical proofs

Demaine-Demaine-Langerman-Langerman mathematically proved 5D (141), 4T (192) and 4D (48) upper bounds in their "Morpion Solitaire" paper. For the 5T game, they proved an upper bound of 838 moves in their 2004 version, improved to 704 moves in their 2006 version. However, two small errors in their 2006 paper:



March 2003: Grids of 288 moves claimed to be upper bounds by Achim Flammenkamp
(image created in Oct. 2011 by Christian Boyer, click to enlarge)

    Before, in March 2003, Achim Flammenkamp (University of Bielefeld, Germany) found exactly the same upper bound of 705 moves and this tighter upper bound of 288 moves only, but Demaine et al. were "unable to verify his proof sketch" (page 8 above). Here is this proof sketch:

    The grids of 324 dots described at the end of his proof are saided to be upper bounds. However, even if they correctly contain 324 dots, they can't include the needed 324 - 36 = 288 lines as you can check in my nearby image of his two limit octagons: the first one with b1 = 14, b2 = 26, d1 = d2 = 31 can contain a maximum of 264 lines of five dots, and the second one with b1 = 13, b2 = 28, d1 = d2 = 32 can contain a maximum of 270 lines of five dots.

    Below my final 5T grid of 317 moves correctly contains the needed 317 lines and, because this number is greater than his 288 moves, this proves that his result is not an upper bound: his proof of 288 moves is wrong, why is it self-limited to octagonal shapes? But the proof of 705 moves, found both by him (= 741 - 36) and by Demaine et al. (= 704 + 1), seems correct.

    November 2011, new version of Flammenkamp proposing, page 10, a 5T upper bound of 665 moves.

In the columns of Science & Vie, various attempts to find 5T upper bounds were reported, but without detailed and/or valid proof:

There is another 5T upper bound obtained in the 70's:

In August 2010, Pekka Karjalainen, Oulu, Finland, sent me a proof of a 5D upper bound of 138 moves, three fewer moves than the Demaine et al. upper bound.

  Conference by Yushi Uno on his new upper bound, at CCCG 2013

In July 2013, Akitoshi Kawamura (University of Tokyo, Japan), Takuma Okamoto, Yuichi Tatsu, Yushi Uno, and Masahide Yamato (all four from Osaka Prefecture University, Japan) proved a new 5D upperbound of 121 moves. This proof, version 1 published in arXiv, was announced at CCCG 2013, the 25th Canadian Conference on Computational Geometry held in August 2013 in Waterloo, Ontario, Canada.

In January 2014, they published in arXiv a version 2 of their paper, retaining the upperbound of 121 moves, but correcting a small flaw (part 4.2, new lemma 2 replacing old lemmas 2 & 3), and specifying that Peter Bartsch was the first author of a grid of 102 moves (figure 3, partie 4.3).


5T++ Record Grid (best known 5T final grid): 317 moves

Because at each move of the game we simultaneously add one dot and one line, any 5T (and also 5T+ and 5T#) grid of n moves always has, during the game or at the end of the game:

What is the largest possible number of moves in a final grid respecting these rules? "Final grid" means that we do not check if it is possible or impossible to really play this grid move by move from the initial cross.

Here is my best result, a 5T / 5T+ grid of 317 moves. It could be the best possible 5T and 5T+ final grid, and in consequence also an upper bound for maximum score, but difficult to prove... This is anyway the record for the 5T++ game. And this is also a counterexample to Flammenkamp's "proof" above of 288 moves.


November 2011: Record grid 5T++, best know 5T final grid, 317 moves, by Christian Boyer
 i.e. 317 lines (82 horizontal + 81 vertical + 77 diagonal/ + 77 diagonal\) , and 317 + 36 = 353 dots

The number of initial dots has a big influence on the best possible final grid. With only six supplemental dots (36 + 6 = 42 initial dots), we can obtain 535 moves, i.e. more than two hundred supplemental moves! And with twelve more supplemental dots (42 + 12 = 54 initial dots), we can obtain 829 moves! I think that these two grids are the best possible for these numbers of initial dots, but again difficult to prove. In the three grids, the trick is the same: if you look at the four sides as stairs, each stair has a 2x2 size, except one larger stair 4x2. With this trick, almost all diagonal lines, but also horizontal and vertical lines, are multiples of four segments, fully filling the inside without leaving unused spaces.

   
November 2011: 5T final grid of 535 moves with 42 initial dots, i.e. 535 lines and 577 dots
 and 5T final grid of 829 moves with 54 initial dots, i.e. 829 lines and 883 dots, by Christian Boyer
Filling the grids is left as an exercice of patience for the reader :-)

As you can see, my final grids looks like diamonds... I mean the shape, not the gem... even if it is the trade of Arthur Langerman ;-)
Flammenkamp used octagons only.
But maybe somebody will construct better 5T final grids, more moves with the same numbers of initial dots? And maybe with one more different shape?


Minimum scores

After the maximum scores, what about the minimum scores? I have never seen any mention of them. Strange... because it is a lot of fun to construct bad grids! Here are my worst possible grids (other examples with the same numbers of moves are possible):

       
January 2008: Examples of worst possible Morpion Solitaire games, by Christian Boyer.
Respectiveley 5T/5D game with 20 moves, 4T game with 22 moves, 4D game with 16 moves.
(click on the images to enlarge them)

Look at the 22 moves of the worst possible 4T game: it is strangely impossible to get a grid as bad as the 5T and 5D games (20 moves).

During his enumeration, Michael Quist confirmed in March 2008 that my scores are the worst possible, and computed the number of different possible grids:


© Christian Boyer, www.morpionsolitaire.com