## Morpion DNA Encoding Revisited

Each move consists of two parts; a grid point where the move was made and a line that passes through the point.

Let’s consider the line universe of discourse. Each point on the grid can be the beginning of four possible lines. These possibilities per point encompass all the possible lines that can be formed.

Encoding

To store the possible lines for a 40×40 grid one would need an array of size 40x40x4.

The correspondence is defined by:

def dna_line_index (line)
line.x * 40 * 4 + line.y * 4 + DIRECTION_INDEX[line.dir]
end

The direction index is a consistent arbitrary ordering of the possible directions. I use:

DIRECTION_INDEX = {
:ne => 0,
:e => 1,
:se => 2,
:s => 3
}

Given a move’s line we can now get a corresponding value from the array.

The goal is to encode a completed grid into this array.

The array is initialized to a random real between 0 and 1 (needed for later).

dna = Array.new(40*40*4){rand}

We then run the following loop.

@taken_moves.each_with_index do |move, index|
dna[dna_line_index move.line] = (@taken_moves.length + 1) - index
end

Iterate over the taken moves of the grid and set the corresponding position in the array to a descending move numbering. For example if the completed grid has a score of 90 then the value stored in the array at the corresponding position of the first move’s line is 90. The second move’s line is 89 and so on.

Evaluation

The array can now be evaluated deterministically with the following method:

At each stage of the algorithm consider the set of possible moves. Rank each move using the value of the array index corresponding to the move’s line. Make that move. Continue the process until there are no possible moves.

This is a complete encoding. Evaluating the dna string will generate a consist grid.

Move Black Listing

The strength of this encoding is it’s resiliency to change. Consider the black listing of a move. A black listed move is a move that can only be made if it is the only possible move at an evaluation stage. This is accomplished quite easily with:

dna[morpion.dna_line_index morpion.taken_moves.sample.line] = -1

Since all the values in the array are positive this move will never be ranked higher than an available move. Also any undisturbed structures are preserved in their line preferences. A move that has been made will always be ranked higher than a move that was not made. If a situation occurs that all possible moves are not part of the original grid then a random move is taken. This is accomplished by initializing unused array indices to rand.

I find black listing three of the taken moves works really well.

related:

Coming soon…
How to efficiently identify two grids that have the same move positions (could have different lines)

End Search: Using loose moves, random completions and move index timeouts to generate similar solutions (hopefully better ones!)

This entry was posted in Uncategorized. Bookmark the permalink.

### 8 Responses to Morpion DNA Encoding Revisited

1. Henryk says:

Thanks for this interesting description! What you mean by “blacklisting three of the taken moves”?

• Dimitri Tishchenko says:

Black listing three moves works like this:

first we generate an array corresponding to a morpion grid (I have a method in my morpion object)

dna = morpion.generate_dna

Then I select three moves that are part of the grid and set their indeces in the array to -1. This is accomplished by the following:
(this beautiful one-liner is why I love ruby!)

3.times do
dna[morpion.dna_line_index morpion.taken_moves.sample.line] = -1
end

Now we can re-evaluate the modified dna array and hopefully get a good neighbor to the current configuration. This can be done with the process above of starting with an empty grid and ranking the possible moves and making the highest ranked moves using the modified dna.

This isn’t the only modification technique I’ve tried but one that is pretty good. Removing one move seems to be too limiting in terms of creating good selection of neighbors.

Put together it looks like this:
dna = morpion.generate_dna

3.times do
dna[morpion.dna_line_index morpion.taken_moves.sample.line] = -1
end

eval_morpion = Morpion2::Morpion.new
eval_morpion.eval_dna dna

So for a basic algorithm try this:
2. generate dna D for M
3. black list three moves in D
4. evaluate D and get a new grid NM
5. if NM’s score is greater or equal to M, set M to equal NM
6. go to 2

This algorithm is surprisingly good at getting decent scores. But as you can imagine it get’s stuck at peaks.

For any further clarification, please let me know.

2. Henryk says:

Is it correct that in 2. you want to do

go to 2

With go to 1 the algorithm starts from a random grid in each run.

• Dimitri Tishchenko says:

Ah yes, thanks Henryk. Goto 2. (I will update the comment)

3. Henryk says:

I have a preliminary implementation of the pseudocode above (I am still in the process of correcting bugs) and ran it for various iterations:

1. 10000 iterations, time 10s, result 91
2. 100000 iterations, time 100s result 95
3. 1000000 iterations, time 1004s result 100.

Does it agree with your experience and how to improve on it?

• Dimitri Tishchenko says:

It seems we might have a different definition of iteration. By sixty seconds I usually do about 1000 iterations. But the scores given the time are pretty consistent.

With the modification method above I get:
representation: iteration. score (elapsed_seconds) grid_pack
1. 71 (0.05) bqKnm3NXDIMbGAMUOJ7n/X2
3. 72 (0.17) LqankzlgimTXiBRMLuf5tP/
11. 73 (0.45) bqKnm3NmhKPGASmLtf16f/
54. 74 (1.73) bqKnG3NmhJYjSh1bzNH18m3g
64. 76 (2.08) b6KmW3NjQlWhCoT15uNbva/g
67. 77 (2.22) b6KmW3NjQgsTRPXm6VZy+/+
129. 78 (4.17) LqynVbUqKVBPkWHcKpyuv9/z
135. 79 (4.44) LqyHVWqVwKCk+RYdwq0tW4v+2c
146. 80 (4.84) LqyHUXUrQmzWKzCUvjlOq37e+
158. 81 (5.19) JqyPUXZWkhmnYSzGUv783f7f
160. 82 (5.28) JqyLUXahMqLZ2EszlL+/juf7q
161. 86 (5.36) JqwrU3cQqi2dhLM5S/v1zy+/Ow
167. 88 (5.61) JqwrU3cQqi2dhLM5S/v1z068f9
216. 89 (7.38) JqwrU3cRsoWzcJNTkp+t2n7l4/6
580. 92 (20.13) JqwqQvlWIMRmPog0xtn9t1+nfX+Pg
589. 94 (20.45) JqwqQvlWIMRmPog0ytn9t1+nXd29e
649. 95 (22.39) JiwqRu40BRCJ4eEVpFu/9t1+v3dq64
752. 97 (26.2) FiwqTaokMAxIvACcxLvvZ9bu/z7371o
1233. 98 (41.98) FqxqRa0RAxJYKp1ITv2dWzeTN7O91vv
1253. 99 (42.73) FqxrDdRFCsFQVTq0Q+ydi2/bPnvbq+8
1334. 100 (45.8) FqxLR1NCIGKUTU6fI+aXt/t6dO/a/Pg
———————————-
0. 76 (0.03) 7qJWXrEm5cehKKmUHI5m3vtb
3. 81 (0.16) 7qJXXrShWi2IjSyg+hejzdfteg
33. 82 (1.16) 7qBXfrVOillDspaJqmPN97P/
38. 83 (1.34) 7qBXfrVOilnDxxdamvO99v+
70. 84 (2.27) 5qBffTU6LSAhyOdgtWcvm+3d/g
72. 85 (2.38) 5qBffXU6KmcOEkwJqzl5vvu/+
74. 86 (2.47) 5qBffXU6KmcOUk5FauMv339/Y
201. 87 (6.3) 1qJfTmlsYRgo4BU9B1rNre/0998
205. 88 (6.44) 1qJfTmlsYRgh6E+CVkONmm9/p774
310. 90 (9.69) 1KJfTmlo8S+wCXhSeNmxx+/z76X
317. 93 (9.98) 1KJfTmlo8Q+DCdLNm+7evV/Z8y+
376. 95 (11.8) 1KJbTmrRwx0gtj5hOZMeOnr/uvpt2
408. 96 (12.92) 1KJbTmrRwx0gtj5pNisx+Pz3+X1b4
680. 97 (22.16) 1KJbTmbRwh/AiPbNG42d4Xz/1fnXs
825. 100 (27.16) 1KJbTmbRwh/ArHtmjcbJvC+dz7r57s
———————————-
4. 70 (0.13) 3UFGqZzl1UQpkiFaKuzv99w
5. 71 (0.19) 12FOqxxwtCRZgdROQ7t3X/w
11. 72 (0.39) 12FOr6ElCDg5FKOcRavfb/5
13. 73 (0.48) 16FOrakqHNCjlOuH/xJbEL/
16. 76 (0.59) 16FOra0lDmhRy9dPyY2RWf3g
20. 79 (0.77) x6NOjajBQySaknlHbEs5RLf/P0
50. 81 (1.73) x6NOhaYKGSQ2sQs0jskP+ux97/A
65. 82 (2.27) x6MuhOYKGSQ28EI01Hpi/7T73eo
76. 83 (2.64) 56MuhPMuEAOZahUUqR9OTveLb9yg
79. 84 (2.8) 56MuhPMuQDuLwM0FX5ooyV9G33sg
80. 86 (2.86) 56MuhPMuQBs+KwWINzTbpT+f/7I
95. 88 (3.38) 56NuhOZcgDLix6FJC5p7pH+f/7O
119. 90 (4.14) 46NuhOZyFBrix6FJC1p7pH+f/r7Q
140. 91 (4.81) w6NuhOZyFBrix6FLAl7S7qV73s8fs
162. 92 (5.53) w6NugOZyFGuLHoUwu0rRU9v5m1/9o
628. 93 (21.44) k6NOi5mcg7BbyMPEZA5PXl+//z/s
702. 94 (24.05) k5NOjpk6A2diZLI31wRQ/8nU3/2Pz
718. 95 (24.64) k5NOjpk6A2diZLIn14Iof+Tqf97fMw
1649. 96 (56.17) k5NujVJ4jObC5UkK9ZdVk/F2Y/730g

Very dependent on the starting position.

In the next couple of days I will write a technique I use to “lateralize” the search. The problem here is that it gets stuck. If you run this algorithm over night it should get a pretty good result. This algorithm also doesn’t know when to drop back when it gets stuck.

Would it help if I published some runnable code? Would you be able to install ruby?

4. Henryk says:

By one iteration I mean going once through steps 2,3,4,5,6. In practive it means creating a heuristic playing one complete game according to the current heuristic offered by the dna matrix.

Regarding installation, I can do whatever setup is required. Running code indeed would be helpful. Thanks for a quick reply!