Morpion Move Layering and Encoding Improvement

Morpion Move Layering Model:

Linear Move Model:
The linear model is the common approach to thinking about how moves are made on the Morpion board. A list of ordered moves defines the path to the end of the configuration.

Move Layering Model:
Move layering is another approach to making moves on the Morpion board where ordering among the layers is unimportant. A Morpion move layer consists of a set of moves taken (TKM) at that layer and a set of moves not taken (TBM). At any layer there are TKM! ways complete the taken moves of that layer.

Example: 160 – First Move Layer
Consider the 160 solution from my previous blog post on encoding. Start a brand new board. You will have 28 possible moves. Take the intersection of the 160’s taken moves and the possible moves that exist currently on the board. In this configuration there were eight moves that mark the used moves at the first layer. We can say that eight moves were used and 19 moves were not used. It is also important to note that the eight moves used can be taken in any order since they cannot conflict (one move removes another). The first eight moves of the first layer of the 160 can be made in 8! ways (40320)

Using the linear move model it can be shown that any configuration can be made in an astronomical linear combination of moves.

Example: 160 – Move Layer Analysis
The numbers below represent the moves taken at each layer
8! * 4! * 1! * 2! * 2! * 3! * 4! * 3! * 2! * 2! * 3! * 2! * 2! * 2! * 1! * 1! * 2! * 1! * 1! * 2! * 3! * 2! * 2! * 3! * 4! * 2! * 3! * 4! * 4! * 4! * 3! * 4! * 4! * 4! * 5! * 1! * 2! * 4! * 4! * 3! * 3! * 3! * 1! * 1! * 2! * 2! * 3! * 2! * 2! * 2! * 1! * 1! * 2! * 2! * 2! * 1! * 2! * 3! * 2! * 4! * 2! * 1! * 1! * 1! * 1!
= 6.45314718 × 10 39

Application of Morpion Move Layer to Encoding:
In my previous post on encoding I was able to encode a 160 configuration using 231 characters. Here I will show how that same 160 can be encoded using 45 characters.

Binary encoding:
The first step is to build the first layer. As described above you take the intersection of the taken moves and the possible moves and get TKM. You then subtract TKM from the possible moves to get a list of taboo moves (moves we will not be making, TBM).

Take the possible moves and order them (previous post describes how to order moves). At this point it is important to remove moves from possible moves that appear in the taboo moves. These moves are known not to be used and do not need to appear in the encoding. If the move is used put a 1 into the binary string, 0 otherwise. If the move is not used, add it a set of taboo moves. Taboo moves are never used and can be removed from the set of possible moves at later layers to decrease the size of the binary encoding.

A new board is used to evaluate the possible moves at each layer. Continue this process for all moves.

In the end a binary string will be generated:

101011000100010001000000010011011100101101001010111010110001100000010001011000110110011000010100110000010111010011001111010110101100110011001100101111110111101111011101111011110111011100111101110011101111010101111010110110111011110111111101110110111110111111110111101101

Character count: 270

Base64 encoding:
rERATctK6xgRY2YUwXTPWszMv3vd73c9zvV627392+/3t

Character count: 45

Decoding:
The process is very similar. Consider the possible moves at each layer of a new board. Look at the binary string. If a 1 appears make the move, if a 0 appears don’t make the move and add it to TBM. At each layer remove the taboo moves from the possible moves. Continue until new board does not have any more possible moves.

Advertisements
This entry was posted in Uncategorized. 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