Morpion Move Encoding

For instructions on how to play the game visit: Morpion Solitaire

Each move consists of a point where the move was made, a point where the line begins and the line direction.

The most basic way of storing a collection of moves is to indicate the x and y coordinates of the move, the starting x and y coordinates of the line and the line direction. Eg. 3,4,5,6,e. A delimiter makes it easier to separate the moves.

The following is a basic string representation of a morpion configuration for a 160 solution:

Basic move encoding:

0,2,0,2,s|2,2,0,4,ne|4,6,0,6,e|5,6,4,6,e|2,0,2,0,e|6,4,6,0,s|6,5,6,4,s|-1,3,-1,3
,e|1,5,-1,3,se|9,7,9,3,s|3,4,3,0,s|3,5,3,4,s|2,4,0,2,se|2,1,2,0,s|4,2,0,6,ne|1,2
,0,2,e|4,5,1,2,se|4,-1,0,3,ne|2,5,0,5,e|7,2,4,-1,se|5,3,2,0,se|4,3,4,3,e|5,4,2,1
,se|4,4,2,4,e|4,1,4,-1,s|4,7,4,3,s|2,9,2,9,ne|1,9,1,9,e|1,4,0,3,se|1,1,1,1,s|5,5
,1,1,se|-2,4,-2,4,ne|-1,4,-2,4,e|2,7,-1,4,se|1,8,1,8,ne|1,7,1,5,s|5,1,2,1,e|-1,6
,-1,6,ne|0,8,0,8,ne|8,4,4,0,se|0,7,0,7,ne|-1,7,-1,7,e|5,7,5,3,s|7,7,3,7,e|-1,5,-
1,3,s|2,8,-2,4,se|2,10,2,6,s|4,8,2,10,ne|5,8,2,8,e|8,5,4,9,ne|7,5,5,5,e|8,2,8,2,
s|5,2,4,2,e|5,-1,5,-1,s|10,2,6,6,ne|7,1,5,-1,se|8,0,4,4,ne|7,4,3,0,se|7,8,7,4,s|
10,4,6,4,e|11,3,7,7,ne|3,11,-1,7,se|4,10,3,11,ne|4,11,4,7,s|3,10,0,7,se|3,12,3,8
,s|5,10,3,12,ne|6,10,2,10,e|5,11,5,7,s|6,12,2,8,se|7,11,3,7,se|6,11,6,8,s|8,11,4
,11,e|7,10,4,7,se|7,12,3,8,se|7,9,7,8,s|8,8,5,11,ne|9,9,5,5,se|8,9,5,9,e|9,10,5,
6,se|8,10,4,6,se|10,8,6,12,ne|9,8,6,8,e|10,7,6,11,ne|8,7,8,6,s|10,9,6,5,se|11,7,
7,7,e|9,11,9,7,s|11,8,7,12,ne|10,10,6,10,e|11,9,7,5,se|12,9,8,5,se|13,9,9,9,e|0,
10,0,10,ne|10,6,10,6,s|12,8,8,4,se|13,7,9,11,ne|7,0,7,0,s|8,-1,4,3,ne|0,9,0,6,s|
9,1,5,5,ne|7,-1,7,-1,se|6,-1,4,-1,e|7,-2,3,2,ne|8,-2,4,2,ne|8,1,8,-2,s|10,1,6,1,
e|9,2,6,5,ne|10,3,6,-1,se|10,5,10,2,s|11,4,7,8,ne|12,3,8,3,e|9,0,5,4,ne|11,2,7,-
2,se|10,0,6,0,e|12,2,8,2,e|12,1,8,5,ne|9,-1,9,-1,s|11,1,8,-2,se|11,5,11,1,s|11,6
,11,5,s|12,7,8,3,se|12,6,8,6,e|12,5,12,5,s|13,5,9,5,e|14,4,10,8,ne|12,4,12,1,s|1
4,8,10,4,se|13,8,10,8,e|13,6,13,5,s|14,7,10,3,se|15,7,11,7,e|14,6,11,3,se|14,5,1
4,4,s|15,4,11,8,ne|13,4,10,4,e|15,6,11,2,se|14,3,10,7,ne|16,5,12,9,ne|13,2,12,1,
se|16,6,12,6,e|17,5,13,9,ne|15,5,13,5,e|15,3,15,3,s|13,3,12,2,se|16,3,12,3,e|14,
2,10,6,ne|13,1,13,1,s|16,4,13,1,se|16,2,16,2,s|15,2,12,2,e|14,1,10,1,e|14,0,14,0
,s|15,-1,11,3,ne|17,3,13,7,ne|15,0,11,4,ne|15,1,15,-1,s|18,4,14,0,se|17,4,14,4,e
|18,5,14,1,se

Character count: 1854

Pentasol, a windows base program for playing morpion, makes the encoding more efficient by indicating an offset from the move point to indicate the starting point. Eg. 3,3,-3,s. This decreases the encoding slightly.

I was considering making a genetic algorithm for morpion and decided that it would be best to have some kind of binary representation of a morpion move configuration.

To encode the move configuration above we begin with an empty playing board. We take the initial possible moves, 28 of them, and sort them. Consistent sorting is very important when encoding/decoding.

possible_moves.sort_by { |move| [move.x, move.y, move.line.x, move.line.y, DIRECTION_INDEX[move.line.dir]] }

We iterate over all the moves and add a 0 for all the moves that were not used and a 1 for the move that were used. This is continued until all the moves are encoded.


@taken_moves.each do |move|
morpion.possible_moves.sort_by { |move| [move.x, move.y, move.line.x, move.line.y,DIRECTION_INDEX[move.line.dir]] }.each do |possible_move|
bin = (move == possible_move) ? bin + '1' : bin + '0'
end
morpion.make_move move
end

Binary encoding:

00100000000000000000000000000001000000000000000000000000000000001000000000000000
00000000010000000000000010000000000000000000000000000010000000000000000001000000
00100000000000000010000000000000000000000000010000100000000001000000000100000000
00100000000000000100000001000000000000000010000000000000100000000100000000000000
00100000001000000000010000000000000001000000000001000000000000001000000000000000
00001000000000000000000100000000000000000000100000000000000100000000000000000010
00000000000000000000000001000000100000000000000000000100000000000000000000000100
00000000000000000100000000000000000001000000000000000000000000001000000000010000
00000000000000000000100000000000000000000000000000000000101000000000000000010000
00000000000000000001000000000010001000000000001000000000000010000000000000100000
00000001000000000010000000001000000000000010000000000100000000000001000000000000
00000000000100000000010000000000000000000001000000000010000000000000001000000000
00010000000000010000100000010000001000000100001000010000001000010000010000000100
00100000001000010000010000100001000000010001000000010001000000000010000000100000
00000100001000000000001000000000010000000100000000001000010000000100000010000011
00000001000010000010100101011010101101010010001001001100010010000101110110001101
00010010100010010010010010010010010100010010000101000100101001001001011010100010
10100100011101101

Character count: 1378

This can be further reduced by base64 encoding the binary string.


BASE64_ENC_TABLE = “ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/”

bin.scan(/.{1,6}/).each do |sextuplet|
sextuplet = sextuplet.ljust(6,’0′)
base64_enc += BASE64_ENC_TABLE[sextuplet.to_i(2)]
end

Base64 encoding:

IAAAAQAAAACAAABAAIAAAAIAAEAgACAAAAQgBAEAIABAQAAgAIBAACAgBAAEAEAAgAAIAAEAAAgAEAAC
AAAAQIAABAAABAAAQAAEAAAAgBAAAAgAAAAAoAAQAAAQAiACAAgAIAEAIAgAIAQAEAAAEAQAABACAAIA
EAEIECBCECEEBCAhBCEBEBEAICAEIAIAQEAIQECDAQgpWrUiTEhdjRKJJJJRIUSklqKkdo

Character count: 231

For decoding you just reverse the process.

Advertisements
This entry was posted in Uncategorized and tagged , , . Bookmark the permalink.

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