For this example I will use a very interesting 135 configuration. It appears to be a peak.
Our goal is encode these moves into a binary string.
Lets begin by considering the 28 possible moves that are available when starting a new game. Out of these initial 28 moves some are going to be used and some will be removed as a consequence of making some other moves. Taking the intersection of the possible moves and the taken moves from the configuration above we see that eight moves were made and 20 moves not made.
For each of the eight moves that were taken we are going to add a 1 to the binary encoding and a 0 for the moves not taken.
In order to be able to decode this binary encoding it is important to consistently order the possible moves. I chose [move.x, move.y, move.line.x, move.line.y, Morpion2::DIRECTION_INDEX[move.line.dir]]. Since all attributes are included I am guaranteed a unique ordering.
For the 20 moves that were not taken, we are explicitly stating that at no point should any of these moves be made. These are added to a list of ‘taboo’ moves. Also we no longer need to encode these moves if they appear as possible moves later on.
Okay, lets take a look at the first layer:
layer 0
1. -1, 3 – (-1,3,e): 0
2. -1, 6 – (-1,6,e): 0
3. 0, 2 – (0,2,s): 0
4. 0, 7 – (0,3,s): 0
5. 2, 0 – (2,0,e): 0
6. 2, 2 – (0,4,ne): 1
7. 2, 7 – (0,5,se): 0
8. 2, 9 – (2,9,e): 0
9. 3, -1 – (3,-1,s): 0
10. 3, 4 – (3,0,s): 0
11. 3, 5 – (3,5,s): 0
12. 3, 10 – (3,6,s): 1
13. 4, 3 – (0,3,e): 0
14. 4, 6 – (0,6,e): 1
15. 5, 3 – (5,3,e): 1
16. 5, 6 – (5,6,e): 0
17. 6, -1 – (6,-1,s): 0
18. 6, 4 – (6,0,s): 0
19. 6, 5 – (6,5,s): 1
20. 6, 10 – (6,6,s): 0
21. 7, 0 – (3,0,e): 1
22. 7, 2 – (5,0,se): 0
23. 7, 7 – (5,9,ne): 1
24. 7, 9 – (3,9,e): 0
25. 9, 2 – (9,2,s): 1
26. 9, 7 – (9,3,s): 0
27. 10, 3 – (6,3,e): 0
28. 10, 6 – (6,6,e): 0
We see the 28 possible moves sorted by the given criteria. The eight taken moves are marked with a 1. The moves that aren’t taken are marked with a 0 and added to a taboo list (this will come into play in the later layers).
We now make our first eight moves on a grid. After making the moves consider the set of possible moves available to us. There are 18 possible moves. Out of those 18 moves, 14 moves are in our taboo list. We have already stated that these moves will not be used. That means we can ignore them.
We are left with four possible moves. Just like in the first layer we now want to take the intersection of the possible moves and the taken moves. This shows that three moves were taken and one not. Note: Moves shown in [] are tabooed.
layer 1
29. 4, 3 – (1,3,e): 1
30. 5, 6 – (4,6,e): 1
31. 5, 8 – (3,10,ne): 0
32. 6, 4 – (6,1,s): 1
[3, -1 – (3,-1,s)]
[6, -1 – (6,-1,s)]
[3, 4 – (3,0,s)]
[7, 2 – (5,0,se)]
[6, 4 – (6,0,s)]
[0, 2 – (0,2,s)]
[-1, 3 – (-1,3,e)]
[4, 3 – (0,3,e)]
[0, 7 – (0,3,s)]
[2, 7 – (0,5,se)]
[5, 6 – (5,6,e)]
[10, 6 – (6,6,e)]
[2, 9 – (2,9,e)]
[7, 9 – (3,9,e)]
This process is continued until there are no possible moves left on the board.
layer 2
33. 5, 4 – (3,2,se): 0
34. 5, 5 – (3,7,ne): 1
35. 7, 4 – (5,6,ne): 1
[3, -1 – (3,-1,s)]
[3, 4 – (3,0,s)]
[7, 2 – (5,0,se)]
[0, 2 – (0,2,s)]
[0, 7 – (0,3,s)]
[2, 7 – (0,5,se)]
[2, 9 – (2,9,e)]
[7, 9 – (3,9,e)]
[5, 8 – (3,10,ne)]
layer 3
36. 4, 4 – (2,2,se): 1
37. 4, 4 – (3,3,se): 0
38. 7, 5 – (7,3,s): 0
[3, -1 – (3,-1,s)]
[3, 4 – (3,0,s)]
[7, 2 – (5,0,se)]
[0, 2 – (0,2,s)]
[0, 7 – (0,3,s)]
[2, 7 – (0,5,se)]
[2, 9 – (2,9,e)]
[7, 9 – (3,9,e)]
[5, 8 – (3,10,ne)]
[5, 4 – (3,2,se)]
layer 4
39. 3, 5 – (2,6,ne): 1
[3, -1 – (3,-1,s)]
[3, 4 – (3,0,s)]
[7, 2 – (5,0,se)]
[0, 2 – (0,2,s)]
[0, 7 – (0,3,s)]
[2, 7 – (0,5,se)]
[2, 9 – (2,9,e)]
[7, 9 – (3,9,e)]
[5, 8 – (3,10,ne)]
[5, 4 – (3,2,se)]
[7, 5 – (7,3,s)]
layer 5
40. 3, 4 – (3,1,s): 0
41. 3, 4 – (3,2,s): 1
[3, -1 – (3,-1,s)]
[3, 4 – (3,0,s)]
[7, 2 – (5,0,se)]
[0, 2 – (0,2,s)]
[0, 7 – (0,3,s)]
[2, 7 – (0,5,se)]
[2, 9 – (2,9,e)]
[7, 9 – (3,9,e)]
[5, 8 – (3,10,ne)]
[5, 4 – (3,2,se)]
[7, 5 – (7,3,s)]
layer 6
42. 4, 5 – (2,3,se): 0
43. 5, 2 – (3,4,ne): 1
44. 5, 4 – (3,4,e): 0
[7, 2 – (5,0,se)]
[0, 2 – (0,2,s)]
[0, 7 – (0,3,s)]
[2, 7 – (0,5,se)]
[2, 9 – (2,9,e)]
[7, 9 – (3,9,e)]
[5, 8 – (3,10,ne)]
[5, 4 – (3,2,se)]
[7, 5 – (7,3,s)]
layer 7
45. 4, 1 – (3,0,se): 0
46. 4, 2 – (2,2,e): 1
47. 5, 4 – (5,2,s): 1
48. 8, 5 – (5,2,se): 0
[7, 2 – (5,0,se)]
[0, 2 – (0,2,s)]
[0, 7 – (0,3,s)]
[2, 7 – (0,5,se)]
[2, 9 – (2,9,e)]
[7, 9 – (3,9,e)]
[5, 8 – (3,10,ne)]
[5, 4 – (3,2,se)]
[7, 5 – (7,3,s)]
[5, 4 – (3,4,e)]
[4, 5 – (2,3,se)]
layer 8
49. 2, 0 – (2,0,se): 0
50. 2, 1 – (2,1,se): 0
51. 2, 4 – (2,4,e): 0
52. 4, 1 – (4,0,s): 0
53. 4, 5 – (4,2,s): 1
54. 7, 5 – (3,1,se): 0
55. 7, 5 – (4,2,se): 0
56. 8, 4 – (4,4,e): 1
57. 8, 4 – (5,4,e): 0
58. 8, 7 – (4,3,se): 0
[7, 2 – (5,0,se)]
[0, 2 – (0,2,s)]
[0, 7 – (0,3,s)]
[2, 7 – (0,5,se)]
[2, 9 – (2,9,e)]
[7, 9 – (3,9,e)]
[5, 8 – (3,10,ne)]
[7, 5 – (7,3,s)]
[4, 5 – (2,3,se)]
[4, 1 – (3,0,se)]
[8, 5 – (5,2,se)]
layer 9
59. 1, 2 – (1,2,se): 0
60. 2, 5 – (2,5,e): 1
61. 2, 7 – (2,7,ne): 0
62. 5, 1 – (4,0,se): 0
63. 5, 1 – (5,1,se): 0
64. 7, 2 – (3,6,ne): 1
65. 7, 5 – (3,5,e): 0
66. 7, 8 – (3,4,se): 0
67. 10, 6 – (6,2,se): 0
[7, 2 – (5,0,se)]
[0, 2 – (0,2,s)]
[0, 7 – (0,3,s)]
[2, 7 – (0,5,se)]
[2, 9 – (2,9,e)]
[7, 9 – (3,9,e)]
[5, 8 – (3,10,ne)]
[7, 5 – (7,3,s)]
[4, 1 – (3,0,se)]
[8, 5 – (5,2,se)]
[2, 0 – (2,0,se)]
[7, 5 – (3,1,se)]
[7, 5 – (4,2,se)]
[2, 1 – (2,1,se)]
[8, 7 – (4,3,se)]
layer 10
68. 2, 4 – (2,2,s): 1
69. 4, -1 – (4,-1,se): 0
70. 7, 1 – (7,0,s): 1
71. 7, 5 – (7,2,s): 0
72. 10, 5 – (6,1,se): 0
[0, 2 – (0,2,s)]
[0, 7 – (0,3,s)]
[2, 7 – (0,5,se)]
[2, 9 – (2,9,e)]
[7, 9 – (3,9,e)]
[5, 8 – (3,10,ne)]
[7, 5 – (7,3,s)]
[4, 1 – (3,0,se)]
[8, 5 – (5,2,se)]
[2, 0 – (2,0,se)]
[7, 5 – (3,1,se)]
[7, 5 – (4,2,se)]
[2, 1 – (2,1,se)]
[8, 7 – (4,3,se)]
[1, 2 – (1,2,se)]
[7, 8 – (3,4,se)]
[5, 1 – (4,0,se)]
[5, 1 – (5,1,se)]
[10, 6 – (6,2,se)]
layer 11
73. 0, 2 – (0,2,se): 1
74. 1, 4 – (0,4,e): 0
75. 1, 5 – (0,6,ne): 0
76. 5, 1 – (2,4,ne): 1
77. 5, 7 – (1,3,se): 0
78. 5, 7 – (2,4,se): 0
[0, 2 – (0,2,s)]
[0, 7 – (0,3,s)]
[2, 7 – (0,5,se)]
[2, 9 – (2,9,e)]
[7, 9 – (3,9,e)]
[5, 8 – (3,10,ne)]
[4, 1 – (3,0,se)]
[8, 5 – (5,2,se)]
[2, 0 – (2,0,se)]
[7, 5 – (3,1,se)]
[7, 5 – (4,2,se)]
[2, 1 – (2,1,se)]
[8, 7 – (4,3,se)]
[1, 2 – (1,2,se)]
[7, 8 – (3,4,se)]
[5, 1 – (4,0,se)]
[5, 1 – (5,1,se)]
[10, 6 – (6,2,se)]
[4, -1 – (4,-1,se)]
[10, 5 – (6,1,se)]
layer 12
79. 0, 1 – (0,1,s): 1
80. 3, -1 – (3,-1,se): 1
81. 4, 1 – (3,1,e): 1
[0, 7 – (0,3,s)]
[2, 7 – (0,5,se)]
[2, 9 – (2,9,e)]
[7, 9 – (3,9,e)]
[5, 8 – (3,10,ne)]
[4, 1 – (3,0,se)]
[8, 5 – (5,2,se)]
[2, 0 – (2,0,se)]
[7, 5 – (3,1,se)]
[7, 5 – (4,2,se)]
[2, 1 – (2,1,se)]
[8, 7 – (4,3,se)]
[1, 2 – (1,2,se)]
[7, 8 – (3,4,se)]
[10, 6 – (6,2,se)]
[4, -1 – (4,-1,se)]
[10, 5 – (6,1,se)]
[1, 4 – (0,4,e)]
layer 13
82. 1, 2 – (0,1,se): 1
83. 1, 4 – (0,5,ne): 0
84. 1, 4 – (1,4,ne): 1
85. 2, -1 – (2,-1,se): 1
86. 3, -2 – (3,-2,s): 1
87. 6, -1 – (2,3,ne): 0
88. 8, 5 – (4,1,se): 0
[2, 7 – (0,5,se)]
[2, 9 – (2,9,e)]
[7, 9 – (3,9,e)]
[5, 8 – (3,10,ne)]
[8, 5 – (5,2,se)]
[2, 0 – (2,0,se)]
[7, 5 – (3,1,se)]
[7, 5 – (4,2,se)]
[2, 1 – (2,1,se)]
[8, 7 – (4,3,se)]
[1, 2 – (1,2,se)]
[7, 8 – (3,4,se)]
[4, -1 – (4,-1,se)]
[10, 5 – (6,1,se)]
[1, 4 – (0,4,e)]
layer 14
89. -1, 2 – (-1,2,se): 1
90. -1, 4 – (-1,4,e): 1
91. 1, 5 – (1,2,s): 1
92. 4, -1 – (3,-2,se): 1
93. 4, 7 – (0,3,se): 0
[2, 7 – (0,5,se)]
[2, 9 – (2,9,e)]
[7, 9 – (3,9,e)]
[5, 8 – (3,10,ne)]
[2, 0 – (2,0,se)]
[7, 5 – (3,1,se)]
[7, 5 – (4,2,se)]
[2, 1 – (2,1,se)]
[8, 7 – (4,3,se)]
[4, -1 – (4,-1,se)]
[10, 5 – (6,1,se)]
layer 15
94. -2, 2 – (-2,2,e): 0
95. -1, 3 – (-1,3,se): 0
96. 1, 0 – (-1,2,ne): 1
97. 2, 1 – (-1,4,ne): 0
98. 2, 1 – (0,3,ne): 0
99. 2, 7 – (-1,4,se): 0
100. 4, -2 – (4,-2,s): 1
101. 4, 8 – (0,4,se): 0
102. 4, 8 – (1,5,se): 0
[2, 7 – (0,5,se)]
[2, 9 – (2,9,e)]
[7, 9 – (3,9,e)]
[5, 8 – (3,10,ne)]
[2, 0 – (2,0,se)]
[7, 5 – (3,1,se)]
[7, 5 – (4,2,se)]
[2, 1 – (2,1,se)]
[8, 7 – (4,3,se)]
layer 16
103. 2, 1 – (1,0,se): 1
[2, 7 – (0,5,se)]
[2, 9 – (2,9,e)]
[7, 9 – (3,9,e)]
[5, 8 – (3,10,ne)]
[2, 0 – (2,0,se)]
[7, 5 – (3,1,se)]
[7, 5 – (4,2,se)]
[2, 1 – (2,1,se)]
[8, 7 – (4,3,se)]
[-2, 2 – (-2,2,e)]
[2, 7 – (-1,4,se)]
[2, 1 – (-1,4,ne)]
[-1, 3 – (-1,3,se)]
[4, 8 – (0,4,se)]
[4, 8 – (1,5,se)]
[2, 1 – (0,3,ne)]
layer 17
104. -2, 5 – (-2,5,ne): 0
105. 5, -2 – (1,2,ne): 1
[2, 7 – (0,5,se)]
[2, 9 – (2,9,e)]
[7, 9 – (3,9,e)]
[5, 8 – (3,10,ne)]
[2, 0 – (2,0,se)]
[7, 5 – (3,1,se)]
[7, 5 – (4,2,se)]
[-2, 2 – (-2,2,e)]
[2, 7 – (-1,4,se)]
[-1, 3 – (-1,3,se)]
[4, 8 – (0,4,se)]
[4, 8 – (1,5,se)]
layer 18
106. 5, -1 – (5,-2,s): 1
[2, 7 – (0,5,se)]
[2, 9 – (2,9,e)]
[7, 9 – (3,9,e)]
[5, 8 – (3,10,ne)]
[2, 0 – (2,0,se)]
[7, 5 – (3,1,se)]
[7, 5 – (4,2,se)]
[-2, 2 – (-2,2,e)]
[2, 7 – (-1,4,se)]
[-1, 3 – (-1,3,se)]
[4, 8 – (0,4,se)]
[4, 8 – (1,5,se)]
layer 19
107. 1, -1 – (1,-1,e): 1
108. 3, -3 – (3,-3,se): 0
109. 6, -1 – (2,-1,e): 0
110. 8, 2 – (4,-2,se): 1
111. 8, 2 – (5,-1,se): 0
[2, 7 – (0,5,se)]
[2, 9 – (2,9,e)]
[7, 9 – (3,9,e)]
[5, 8 – (3,10,ne)]
[2, 0 – (2,0,se)]
[7, 5 – (3,1,se)]
[7, 5 – (4,2,se)]
[-2, 2 – (-2,2,e)]
[2, 7 – (-1,4,se)]
[-1, 3 – (-1,3,se)]
[4, 8 – (0,4,se)]
[4, 8 – (1,5,se)]
layer 20
112. 2, 0 – (1,-1,se): 1
113. 8, 5 – (8,2,s): 1
114. 10, 2 – (6,2,e): 1
[2, 7 – (0,5,se)]
[2, 9 – (2,9,e)]
[7, 9 – (3,9,e)]
[5, 8 – (3,10,ne)]
[2, 0 – (2,0,se)]
[7, 5 – (3,1,se)]
[7, 5 – (4,2,se)]
[-2, 2 – (-2,2,e)]
[2, 7 – (-1,4,se)]
[-1, 3 – (-1,3,se)]
[4, 8 – (0,4,se)]
[4, 8 – (1,5,se)]
layer 21
115. 1, 1 – (0,2,ne): 0
116. 2, -2 – (2,-2,s): 1
117. 5, 8 – (4,9,ne): 0
118. 5, 8 – (5,8,ne): 1
119. 7, 5 – (6,6,ne): 1
120. 10, 3 – (6,7,ne): 0
121. 10, 7 – (6,3,se): 1
[2, 7 – (0,5,se)]
[2, 9 – (2,9,e)]
[7, 9 – (3,9,e)]
[5, 8 – (3,10,ne)]
[-2, 2 – (-2,2,e)]
[2, 7 – (-1,4,se)]
[-1, 3 – (-1,3,se)]
[4, 8 – (0,4,se)]
[4, 8 – (1,5,se)]
layer 22
122. 1, -2 – (1,-2,e): 1
123. 6, -2 – (2,-2,e): 0
124. 7, 8 – (7,4,s): 1
125. 9, 7 – (5,3,se): 1
126. 10, 5 – (6,5,e): 1
[2, 7 – (0,5,se)]
[2, 9 – (2,9,e)]
[7, 9 – (3,9,e)]
[-2, 2 – (-2,2,e)]
[2, 7 – (-1,4,se)]
[-1, 3 – (-1,3,se)]
[4, 8 – (0,4,se)]
[4, 8 – (1,5,se)]
[1, 1 – (0,2,ne)]
layer 23
127. 1, 1 – (1,-2,s): 1
128. 4, 8 – (3,8,e): 0
129. 8, 7 – (6,7,e): 0
130. 8, 7 – (6,9,ne): 1
131. 8, 9 – (4,5,se): 1
132. 11, 6 – (7,2,se): 1
[2, 7 – (0,5,se)]
[2, 9 – (2,9,e)]
[7, 9 – (3,9,e)]
[-2, 2 – (-2,2,e)]
[2, 7 – (-1,4,se)]
[-1, 3 – (-1,3,se)]
[4, 8 – (0,4,se)]
[4, 8 – (1,5,se)]
[1, 1 – (0,2,ne)]
layer 24
133. -1, 1 – (-1,1,e): 1
134. -1, 3 – (-1,3,ne): 1
135. 5, -3 – (1,1,ne): 0
136. 5, 7 – (5,7,e): 0
137. 7, 9 – (4,9,e): 0
138. 9, 8 – (5,4,se): 1
139. 11, 7 – (7,7,e): 1
[2, 7 – (0,5,se)]
[2, 9 – (2,9,e)]
[7, 9 – (3,9,e)]
[-2, 2 – (-2,2,e)]
[2, 7 – (-1,4,se)]
[-1, 3 – (-1,3,se)]
[4, 8 – (0,4,se)]
[4, 8 – (1,5,se)]
[4, 8 – (3,8,e)]
layer 25
140. -2, 2 – (-2,2,se): 1
141. -1, 0 – (-1,0,s): 0
142. -1, 5 – (-1,1,s): 1
143. 7, 10 – (7,10,ne): 1
144. 8, 8 – (5,8,e): 1
145. 10, 6 – (7,3,se): 1
146. 12, 5 – (8,9,ne): 0
[2, 7 – (0,5,se)]
[2, 9 – (2,9,e)]
[7, 9 – (3,9,e)]
[-2, 2 – (-2,2,e)]
[2, 7 – (-1,4,se)]
[4, 8 – (0,4,se)]
[4, 8 – (1,5,se)]
[4, 8 – (3,8,e)]
[7, 9 – (4,9,e)]
layer 26
147. -3, 2 – (-3,2,e): 1
148. -2, 5 – (-2,5,e): 1
149. 0, 0 – (-2,2,ne): 1
150. 4, 7 – (3,6,se): 1
151. 8, 10 – (8,6,s): 1
152. 12, 6 – (8,6,e): 1
[2, 7 – (0,5,se)]
[2, 9 – (2,9,e)]
[7, 9 – (3,9,e)]
[2, 7 – (-1,4,se)]
[7, 9 – (4,9,e)]
layer 27
153. -3, 6 – (-3,6,ne): 1
154. -2, 3 – (-3,2,se): 1
155. -1, 0 – (-1,0,e): 1
156. 5, 7 – (3,7,e): 1
[2, 7 – (0,5,se)]
[2, 9 – (2,9,e)]
[7, 9 – (3,9,e)]
[2, 7 – (-1,4,se)]
[7, 9 – (4,9,e)]
layer 28
157. -3, 3 – (-3,3,e): 1
158. 5, 10 – (5,6,s): 0
159. 7, 9 – (4,6,se): 1
[2, 9 – (2,9,e)]
[7, 9 – (3,9,e)]
[7, 9 – (4,9,e)]
layer 29
160. 6, 10 – (6,10,ne): 1
161. 9, 9 – (5,9,e): 1
162. 11, 5 – (7,9,ne): 0
[2, 9 – (2,9,e)]
[5, 10 – (5,6,s)]
layer 30
163. 4, 8 – (2,6,se): 1
164. 9, 10 – (9,6,s): 1
165. 10, 8 – (8,10,ne): 1
166. 10, 10 – (6,6,se): 1
[5, 10 – (5,6,s)]
layer 31
167. 2, 10 – (2,10,ne): 1
168. 4, 10 – (4,6,s): 1
169. 5, 10 – (5,10,e): 1
170. 10, 4 – (10,4,s): 1
171. 10, 9 – (10,5,s): 0
172. 10, 9 – (10,6,s): 0
173. 11, 10 – (7,10,e): 0
[5, 10 – (5,6,s)]
layer 32
174. 1, 10 – (1,10,e): 1
175. 2, 7 – (1,6,se): 1
176. 5, 11 – (5,7,s): 1
177. 11, 5 – (8,2,se): 1
layer 33
178. 2, 9 – (1,10,ne): 1
layer 34
179. 1, 9 – (1,9,e): 1
180. 2, 8 – (2,6,s): 1
layer 35
181. 1, 7 – (-1,5,se): 0
182. 1, 7 – (0,6,se): 0
183. 1, 7 – (1,7,se): 1
184. 1, 8 – (1,8,e): 0
185. 6, 12 – (2,8,se): 0
layer 36
186. -2, 4 – (-3,3,se): 1
187. 1, 8 – (1,6,s): 1
[1, 8 – (1,8,e)]
layer 37
188. -2, 1 – (-2,1,s): 0
189. -2, 6 – (-2,2,s): 1
190. 0, 8 – (0,8,e): 1
layer 38
191. -1, 7 – (-2,6,se): 1
layer 39
192. -2, 8 – (-2,8,ne): 1
193. 0, 7 – (-1,7,e): 1
layer 40
194. -1, 6 – (-2,5,se): 0
195. -1, 6 – (-1,6,se): 1
196. -1, 8 – (-1,8,ne): 1
197. 0, 9 – (0,5,s): 1
198. 4, 11 – (0,7,se): 0
layer 41
199. -4, 6 – (-4,6,e): 0
200. -2, 7 – (-3,6,se): 1
201. -1, 9 – (-1,5,s): 0
202. -1, 10 – (-1,10,ne): 1
layer 42
203. -3, 8 – (-3,8,ne): 1
204. -1, 9 – (-1,6,s): 1
[-4, 6 – (-4,6,e)]
[-1, 9 – (-1,5,s)]
layer 43
205. -4, 8 – (-4,8,e): 1
206. -2, 10 – (-2,10,ne): 1
[-4, 6 – (-4,6,e)]
layer 44
207. -3, 7 – (-4,8,ne): 1
208. -2, 9 – (-2,6,s): 1
[-4, 6 – (-4,6,e)]
layer 45
209. -3, 9 – (-3,9,e): 1
[-4, 6 – (-4,6,e)]
layer 46
210. -3, 5 – (-3,5,s): 0
211. -3, 10 – (-3,6,s): 1
[-4, 6 – (-4,6,e)]
layer 47
212. 0, 10 – (-3,10,e): 1
[-4, 6 – (-4,6,e)]
layer 48
213. -4, 6 – (-4,6,se): 1
214. -1, 11 – (-1,11,ne): 1
215. 1, 11 – (-3,7,se): 0
[-4, 6 – (-4,6,e)]
layer 49
216. -5, 6 – (-5,6,e): 1
217. -5, 7 – (-5,7,se): 0
218. 0, 12 – (-4,8,se): 0
layer 50
219. -4, 7 – (-5,6,se): 1
[-5, 7 – (-5,7,se)]
[0, 12 – (-4,8,se)]
layer 51
220. -5, 7 – (-5,7,e): 1
[-5, 7 – (-5,7,se)]
[0, 12 – (-4,8,se)]
layer 52
221. -6, 6 – (-6,6,se): 1
222. -3, 5 – (-5,7,ne): 1
[0, 12 – (-4,8,se)]
layer 53
223. -3, 4 – (-3,2,s): 1
layer 54
224. -4, 5 – (-5,6,ne): 1
layer 55
225. -4, 4 – (-4,4,s): 1
226. -4, 9 – (-4,5,s): 0
layer 56
227. -5, 4 – (-5,4,e): 1
228. -5, 5 – (-6,6,ne): 1
layer 57
229. -6, 5 – (-6,5,e): 1
230. -5, 3 – (-5,3,s): 1
231. -5, 8 – (-5,4,s): 0
layer 58
232. -6, 2 – (-6,2,se): 1
Our binary encoding now looks like:
0000010000010110001010101000110101110010101001100000100100010001000101001001001111011100111100010001001011100101110101101101111001111100011101111011111111111011101111111100011111110010011011111011100101111111101111010011111110111101
I then base64 encode this string to:
BBYqjXKmCREUk9zxEuXW3nx3v/u/x/JvuX+9P70
In summary each successive layer is just the moves that were created from the layer below.
Please let me know if any part requires further explanation.
Descent into Mathness 
Hi again. You mention using a 40×40 grid in the last article and here I notice what look like negative positions. So I was wondering where the origin is, or what the negatives mean. Thanks.
David
I’m guessing the intersection of the upper and left sides of the cross are 0,0. I’m also guessing that using that facilitates changing the grid size more easily.
David
That’s correct. So the first move is made at 2,2. I originally was thinking of having a dynamic board size but then decided against it because of the added complexity. I have never run off of the edge of a 40×40 grid.
What board we can implemented. I know 3 types: fixed (for example 40×40), dynamic (1 field bigger then last placed point from each side – changed and recalculated during searching) and unlimited. And what board is most effective for faster searching??? I impress you! – it unlimited board!!! For unlimited board we can’t search all board to find new possible moves – for that type board we must think like human – after moves we must check our move list and remove from it moves not possible longer and now we must check how moves are possible to add. Checking for remove is fast, checking for new moves after added move it need analysing only 80 possible position. So it much faster then checking any big fixed or dynamic board. Well – I only have 143 as my record but some my ideas are good – so try implementing it in your programs…
Dimtri,
I am working through this in bits as I have only small chunks of time. I like the approach. I’m going to have more questions. Would it be possible to discuss this off-blog? I believe you have my email.
David
Dimitri,
Again this is a very interesting idea.
Thanks for your time and discussion. I thought I share a couple of my observations in case it helps others.
I found reading this that I initially had the wrong big picture of what was happening. That generated lots of distracting questions/thoughts like why the taboo moves were being left on the table and were they not still possible. I got mentally caught up until I broke the link between actually playing the game and just reconstructing a particular game. It also helped to think of the pool as a single list with dead/taboo entries.
I’d describe the big picture I was looking for as: The compressed bit sequence represents an index into a structure of possible unique moves in a morpion game. Reconstructing the game involves reconstructing the possible new moves from the initial position in a series of internally ordered layers. As each layer is constructed the indexed moves become available and are played adding possible moves until the game is exhausted. Once a new layer is added all moves in previous layers are inaccessible either because they were played or not played in that particular game. Additionally, this method of recording is equivalent to the game played but often will not match the order of moves played.