Morpion Solitaire - Enumeration

Morpion Solitaire - Enumeration

Michael Quist in 2008 (New-York 1974 - )

In March-April 2008, Michael Quist computed the numbers of distinct possible grids for the first moves, and for each game: 5D, 5T, 4D, 4T. Look also at his 3D/3T and finite 3D enumerations. Because he computed the 4D and 4T games up to the last possible grids, these games are now fully solved: look at the 4D and 4T record grids. Michael Quist, Ph.D., is a Research Scientist at Soar Technology, Michigan, USA.

In December 2011, Michael added the number of 5D distinct grids of 24 moves, also recomputing and confirming his enumeration of previous moves. His code is written in Java, and took around 5 days using a Macbook Pro (2.4GHz quad-core) at half capacity.

In the following table, all the numbers come from his computation, but for the 5T game the 20 first numbers were already known, and are confirmed by Michael. As mentioned by Jean-Charles Meyrignac at http://euler.free.fr/morpion.htm, they were first computed by:

Eric Bainville, in July 2000 (moves 1 - 12)
Edward Brisse, in November 2002 (moves 13 - 14)
Pascal Zimmer, December 2002 - February 2003 (moves 15 - 20)

The 5D, 5T, 4D, 4T enumerations are referenced respectively under the numbers A204107, A204108, A204109 and A204110 in the On-Line Encyclopedia of Integer Sequences, OEIS Foundation.

*Morpion Solitaire: number of distinct grids*
Move No	5		4
Move No	D	T	D	T
1	4	4	5	5
2	55	56	106	107
3	404	428	1174	1212
4	2462	2741	10608	11307
5	11196	13247	73709	82008
6	41135	52059	419916	492459
7	122897	167502	1991917	2488802
8	307319	453377	8027941	10810906
9	652286	1047750	27842848	40954087
10	1199755	2112634	84184659	137334461
11	1950378	3808004	224072711	412834554
12	2885188	6369041	528129333	1123737371
13	4043706	10436597	1104419319	2789937671
14	5718245	18107008	2050193527	6354724457
15	8888485	36365073	3377728678	13348667549
16	16594082	90462493	4926536570	25978331545
17	39074532	282733629	6324442265	47005248571
18	115646521	1074838721	7094518159	79292133202
19	414852909	4716194782	6907808080	125052789966
20	1714717418	22663033612	5798009340	185063311252
21	7743579586	114269420056	4159280242	258100163444
22	36521752030	586835167740	2529867930	340693659166
23	174522348856	Unknown ~ 3 x 10^12	1303170244	427231510805
24	832180499844	Unknown ≠ 0	577789811	510573991860
25	Unknown ~ 4 x 10^12	Unknown ≠ 0	233092437	583199573552
26	Unknown, but ≠ 0		95176181	638498530949
27			42457190	671704764622
28			19421547	680361927366
29			7779370	664506187444
30			2318997	626592321191
31			441660	570974319683
32			65620	503018045238
33			10542	428268445219
34			1139	351981574359
35			4	278851125995
36			0	212685481171
37				156060385490
38				110147139843
39				74812560627
40				48944753049
41				30875383909
42				18784093173
43				11004908127
44				6187172765
45				3322534859
46				1697664286
47				824285244
48				380730137
49				167670236
50				70480255
51				28308310
52				10909843
53				4040927
54				1427437
55				466917
56				132561
57				31740
58				7045
59				1573
60				405
61				108
62				12
63				0

Graphics of numbers of distinct grids

Using the above numbers, here are graphics of the two fully enumerated games, 4D and 4T, really looking like bell curves, Gaussian functions:

If we now compare the common logarithms of 5D/5T/4D/4T enumerations, the 5D/5T curves (or more exactly their available beginning) show an inflexion point, not in 4D/4T curves:

The two first unknown numbers of distinct grids should be around 8e+11 (move number 24 at the 5D game) and 3e+12 (move number 23 at the 5T game).
The true number 8.32e+11 of move 24 at 5D, later computed in 2011 by Michael Quist, confirmed this estimate. Now the next unknown number, move 25 at 5D, should be around 3.9e+12.