Morpion Solitaire - Score Limits

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:

Game ⁽¹⁾		Minimum score	≤	Current record score ⁽²⁾	≤	Upper bound ⁽³⁾ of maximum score
5	T	20	≤	172	≤	704 or 324
5	D	20		82		141 or 138
4	T	22		62		~~192~~ 62
4	D	16		35		48 35

Notes:
(1) The 5T, 5D, 4T, 4D games are respectively called G'₄(A₄), G₄(A₄), G'₃(A₃), G₃(A₃) in the Demaine et al paper.
(2) Or also "Lower bound of maximum score", proved by the record grid.
(3) For the 4T and 4D games, it is not an upper bound. Thanks to the enumeration of Michael Quist, we know now that any 4T game has 62 moves maximum and that any 4D game has 35 moves maximum.

Demaine-Demaine-Langerman-Langerman mathematically proved these 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. Before, in March 2003, Achim Flammenkamp (University of Bielefeld, Germany) announced an upper bound of 324 moves only, but Demaine et al were "unable to verify his proof sketch". I am pleased to give this proof sketch:

Download Flammenkamp's proof of the 5T upper bound of 324 moves (PDF file of 231Kb)
Send me your comments on Flammenkamp's proof, confirmation of the proof, or error in the proof.

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

540 by Daniel Goffinet and Pierre Berloquin, June 1974 (Daniel Goffinet is the inventor of the "potential" notion, reused by Berloquin, then by Demaine et al)
556 by P. Bertin, June 1974
1021 by Robert Féron, M. Colmard, and Pierre Berloquin, November 1974
144² = 20,736 by Daniel Goffinet and Pierre Berloquin, May 1975
probably 500 or 600 estimated by Pierre Berloquin, November 1975

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:

Download Karjalainen's proof of the 5D upper bound of 138 moves (PDF file of 67Kb)
Send me your comments on Karjalainen's proof, confirmation of the proof, or error in the proof.

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:

worst 5T = 20 moves (39 distinct terminal positions)
worst 5D = 20 moves (51 distinct terminal positions)
worst 4T = 22 moves (6 distinct terminal positions)
worst 4D = 16 moves (12 distinct terminal positions)