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!)

Advertisements
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:
      1. start with a randomly completed grid, M
      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.

  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
      243. 90 (8.36) IqwrU3cRsst5jgTRaO9+ffWax+eg
      342. 91 (11.66) IqwrU3cRsst5jgTRaO99e7+ax+eg
      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
      737. 98 (24.02) 1KJbTmbRwh/ArHtljcbJfGadz53fuw
      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!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s