October 26, 2017 at 16:51Almost optimal solution for three-dimensional 4x4x4 tic-tac-toe
Everyone knows the game tic-tac-toe 3x3. With the correct game, the first move of the crosses results in a draw. You can manually create a tree of moves, where for any move of zeros, there is a move of crosses, which leads to the best result (for crosses), that is, to a draw or a win. This tree of moves exhausts all the options, so they say that the game is “solved”. There is a three-dimensional variety of tic-tac-toe 4x4x4 for which the answer to the question of who will win the first move of the tic tacs is not obvious. Moreover, the question arises whether it is possible to build such a minimal tree that will solve this problem.
The answer to this question is under the cut.
Let me remind you what the game is tic-tac-toe 4x4x4 (it is also called Qubic).
This is a cube consisting of 64 fields in which to win, you must put 4 consecutive crosses or zeros, and they can go along any line, including the main diagonals. In total there are 76 such lines - 48 contours and verticals, 24 diagonals and 4 main diagonals. Given this, it can be noted that not all fields are the same: there are 8 angular and 8 central fields that control 7 lines and 48 other fields that control 4 lines. Therefore, it makes sense to try to take positions that control more lines.
What is the difficulty of building a decision tree for this game? Roughly can be estimated as 2 in a degree of 64 options, which is quite a lot. Of course, not all of these options are implemented in the game and many branches of the tree are cut off quickly enough, but even in this case, the construction of such a tree by simple enumeration is not possible. How can we reduce the search in order to solve this problem? You may notice that after several moves of crosses and zeros, a situation may arise in which it is possible to create a threat to the enemy by putting three crosses or zeros in one line. With such a threat, the enemy is forced to make his next move to the remaining empty space in this line, otherwise he will lose on the next move. Such moves with a threat can be done several in a row, if there are a sufficient number of lines, on which there are only two crosses or, respectively, a zero. If such a chain of moves leads to a situation in which there are two lines with three crosses or zeros, then the corresponding player loses. This is called a forced win.
We number all the fields with numbers from 0 to 63 starting from the top face and going with horizontal lines from left to right.
We illustrate this with an example of one game:
0-3-60-21-15-51-12-63 4x8x5x10x20x40x28x44x24x16x36x52x48
Here, the crosses make the first move to the far left corner on the upper face (0), then the zeroes respond to the right far corner on the same face (3). The crosses go to the left near corner on the lower edge (60), the zeros correspond in the field to the second from the top edge, etc. After the toe move in 63, the crosses begin a sequence of forced moves: 4 - check. Tac-toe are forced to answer at 8, the cross is 5 check, tac-toe is answered at 10, etc. until two lines with three crosses form at the crosses. Tac toe lost.
To solve this game, you need to find such sequences for all possible moves of the tac toe. For an optimal solution, such sequences should be minimal.
The first to solve this game was Patashnik in the early 80s. He manually selected the initial combinations, and then searched for a winning move using a computer. He showed that if the crosses go to the corner, then they always win with the right game. The next step was taken by Victor Allis. In his dissertation in the mid-90s, he showed that a solution can be obtained entirely on a computer. However, he did not check all the options that crosses can win, but only the first ten, the most promising. Therefore, his solution was not optimal and he left this task to other researchers.
I decided to solve this problem in an optimal way, that is, finding a minimal tree. Obviously, for this it is necessary to use the breadth-first search, as opposed to the Allis depth search. First of all, the search for forced winnings for an arbitrary situation was implemented. It turned out, however, that it turned out to be rather slow, since the in-depth search for the forced payoff for long combinations is quite expensive. The solution was found by adding a repository of already calculated options in std :: unordered_set. It is worth saying that the playing field was encoded in the form of two 64 bit variables, one for crosses, one for zeros, where 1 means the presence of a cross or a zero in the corresponding field. Such caching provided significant speedup. However, the main problem was a breadth-first search for unforce moves. In a normal search without optimization, the calculation did not end in a reasonable time.
I had to turn to caching again. Another byte was added to the calculated game field with the result of calculating the subtree for this option of arranging tic tac toe. At the same time, the encoding of the playing field began to occupy 17 bytes. Thus, when searching in width and gradually increasing the depth of a tree, already calculated subtrees could be discarded. With the help of this, I was able to calculate the minimum trees
for the first move of the cross to the corner (cell 0) and the answers of the zeros to all the fields that control four lines.
Difficulties arose if the tac toe took the field that controlled seven lines in the first retaliatory move. In this case, the cache occupied by the cache exceeded 32 gigabytes of RAM, and my Linux went into a swap. It was necessary to look for another solution.
Then I turned to the fact that the playing field has many automorphisms, that is, if you find a solution for one combination of crosses and zeros, then combinations corresponding to different rotations and reflections will also have a solution. It should be noted that thanks to these automorphisms, the first move of the crosses has only two options - one in field 0 (controlling 7 lines) and one in field 1 (controlling 4 lines). Therefore, in my case, the first move the crosses always make in the field 0. But this is true only for an empty field.
We return, however, to automorphisms for an arbitrary playing field. How to find them all?
I used the following method: since the cube has three dimensions, you can rearrange the coordinates (there will be 6 such permutations) and make reflections (there will be 8 of them). Therefore, there will be 48 spatial automorphisms in total. However, the cube has two more internal automorphisms. One permutes the coordinates of the fields in the first and second pairs in each line,
and the second leaves the first and last field in place, and only permutes the coordinates for the second and third fields. These two automorphisms can also be applied simultaneously. Thus, for each of the 48 spatial automorphisms, there are four
(including trivial) internal automorphisms. Otherwise for the whole cube there are 192 automorphisms. This gives hope for a significant reduction in the number of fields already calculated.
However, another problem arises here: if you check all 192 automorphisms, then you need to quickly transform the playing field by interchanging bits. If this transformation is not made fast, then it will go all the time to it, there will be no gain in productivity, and the whole undertaking with automorphisms will fly into the pipe. So I started searching the Internet for a quick way to swap bits. To be honest, I did not find anything suitable. The only acceptable quick way to rearrange the bits is to pre-compile the table and select a ready-made solution in it having the current playing field as an index. For me, this method did not fit, because it was necessary to have an array of 2 to the power of 64 sixty-bit words.
I already really wanted to leave this idea, however, the idea came to my mind that it is not necessary to have one large table, but you can have several small ones. In principle, it was possible to choose a different number of such tables, but I settled on 8 tables of 256 words (for each automorphism). Thus, to swap bits, I take one byte from a 64 bit field and, in a pre-calculated table, I select a template where the bits are already in place (unless, of course, they are zero in the source field). Then I take the next byte from the 64 bit field and in the next pre-calculated table I select another template and make a logical “or” with the first. And so 8 times. Since these operations do not contain conditional jumps, they should be performed quickly enough without violating the pipeline in the processor.
All this looks good enough, however, to code all these automorphisms and quick permutations of bits manually and without errors is quite problematic. Therefore, an additional program was created that generates C code, which, in turn, is
included in the main program.
After creating the above program, it became possible in a few days to find an almost optimal tree for playing 4x4x4 tic-tac-toe. Why is it "almost optimal"? Because the total length of the forced moves is not taken into account and it may happen that there is a tree for unforced moves of the same depth, but with a smaller total depth of the forced moves. But I think this is not a very big drawback.
Thus, the game of tic-tac-toe 4x4x4 is completely calculated, the crosses always win and you can close this topic? Not really. The fact is that since crosses go first, they have an advantage. What if you try to compensate for this advantage in some way? I propose the following idea - to prohibit the crosses from putting the cross in the field that controls 7 lines with the first move, restricting them to fields controlling only 4 lines. Despite the fact that this seems to be a small change, in fact, the result of the game can change significantly and zeros will be able to reduce the game to a draw, or maybe win. So, there is something to explore.
The answer to this question is under the cut.
Let me remind you what the game is tic-tac-toe 4x4x4 (it is also called Qubic).
This is a cube consisting of 64 fields in which to win, you must put 4 consecutive crosses or zeros, and they can go along any line, including the main diagonals. In total there are 76 such lines - 48 contours and verticals, 24 diagonals and 4 main diagonals. Given this, it can be noted that not all fields are the same: there are 8 angular and 8 central fields that control 7 lines and 48 other fields that control 4 lines. Therefore, it makes sense to try to take positions that control more lines.
What is the difficulty of building a decision tree for this game? Roughly can be estimated as 2 in a degree of 64 options, which is quite a lot. Of course, not all of these options are implemented in the game and many branches of the tree are cut off quickly enough, but even in this case, the construction of such a tree by simple enumeration is not possible. How can we reduce the search in order to solve this problem? You may notice that after several moves of crosses and zeros, a situation may arise in which it is possible to create a threat to the enemy by putting three crosses or zeros in one line. With such a threat, the enemy is forced to make his next move to the remaining empty space in this line, otherwise he will lose on the next move. Such moves with a threat can be done several in a row, if there are a sufficient number of lines, on which there are only two crosses or, respectively, a zero. If such a chain of moves leads to a situation in which there are two lines with three crosses or zeros, then the corresponding player loses. This is called a forced win.
We number all the fields with numbers from 0 to 63 starting from the top face and going with horizontal lines from left to right.
We illustrate this with an example of one game:
0-3-60-21-15-51-12-63 4x8x5x10x20x40x28x44x24x16x36x52x48
Here, the crosses make the first move to the far left corner on the upper face (0), then the zeroes respond to the right far corner on the same face (3). The crosses go to the left near corner on the lower edge (60), the zeros correspond in the field to the second from the top edge, etc. After the toe move in 63, the crosses begin a sequence of forced moves: 4 - check. Tac-toe are forced to answer at 8, the cross is 5 check, tac-toe is answered at 10, etc. until two lines with three crosses form at the crosses. Tac toe lost.
To solve this game, you need to find such sequences for all possible moves of the tac toe. For an optimal solution, such sequences should be minimal.
Historical excursion
The first to solve this game was Patashnik in the early 80s. He manually selected the initial combinations, and then searched for a winning move using a computer. He showed that if the crosses go to the corner, then they always win with the right game. The next step was taken by Victor Allis. In his dissertation in the mid-90s, he showed that a solution can be obtained entirely on a computer. However, he did not check all the options that crosses can win, but only the first ten, the most promising. Therefore, his solution was not optimal and he left this task to other researchers.
I decided to solve this problem in an optimal way, that is, finding a minimal tree. Obviously, for this it is necessary to use the breadth-first search, as opposed to the Allis depth search. First of all, the search for forced winnings for an arbitrary situation was implemented. It turned out, however, that it turned out to be rather slow, since the in-depth search for the forced payoff for long combinations is quite expensive. The solution was found by adding a repository of already calculated options in std :: unordered_set. It is worth saying that the playing field was encoded in the form of two 64 bit variables, one for crosses, one for zeros, where 1 means the presence of a cross or a zero in the corresponding field. Such caching provided significant speedup. However, the main problem was a breadth-first search for unforce moves. In a normal search without optimization, the calculation did not end in a reasonable time.
I had to turn to caching again. Another byte was added to the calculated game field with the result of calculating the subtree for this option of arranging tic tac toe. At the same time, the encoding of the playing field began to occupy 17 bytes. Thus, when searching in width and gradually increasing the depth of a tree, already calculated subtrees could be discarded. With the help of this, I was able to calculate the minimum trees
for the first move of the cross to the corner (cell 0) and the answers of the zeros to all the fields that control four lines.
Difficulties arose if the tac toe took the field that controlled seven lines in the first retaliatory move. In this case, the cache occupied by the cache exceeded 32 gigabytes of RAM, and my Linux went into a swap. It was necessary to look for another solution.
Then I turned to the fact that the playing field has many automorphisms, that is, if you find a solution for one combination of crosses and zeros, then combinations corresponding to different rotations and reflections will also have a solution. It should be noted that thanks to these automorphisms, the first move of the crosses has only two options - one in field 0 (controlling 7 lines) and one in field 1 (controlling 4 lines). Therefore, in my case, the first move the crosses always make in the field 0. But this is true only for an empty field.
We return, however, to automorphisms for an arbitrary playing field. How to find them all?
I used the following method: since the cube has three dimensions, you can rearrange the coordinates (there will be 6 such permutations) and make reflections (there will be 8 of them). Therefore, there will be 48 spatial automorphisms in total. However, the cube has two more internal automorphisms. One permutes the coordinates of the fields in the first and second pairs in each line,
and the second leaves the first and last field in place, and only permutes the coordinates for the second and third fields. These two automorphisms can also be applied simultaneously. Thus, for each of the 48 spatial automorphisms, there are four
(including trivial) internal automorphisms. Otherwise for the whole cube there are 192 automorphisms. This gives hope for a significant reduction in the number of fields already calculated.
However, another problem arises here: if you check all 192 automorphisms, then you need to quickly transform the playing field by interchanging bits. If this transformation is not made fast, then it will go all the time to it, there will be no gain in productivity, and the whole undertaking with automorphisms will fly into the pipe. So I started searching the Internet for a quick way to swap bits. To be honest, I did not find anything suitable. The only acceptable quick way to rearrange the bits is to pre-compile the table and select a ready-made solution in it having the current playing field as an index. For me, this method did not fit, because it was necessary to have an array of 2 to the power of 64 sixty-bit words.
I already really wanted to leave this idea, however, the idea came to my mind that it is not necessary to have one large table, but you can have several small ones. In principle, it was possible to choose a different number of such tables, but I settled on 8 tables of 256 words (for each automorphism). Thus, to swap bits, I take one byte from a 64 bit field and, in a pre-calculated table, I select a template where the bits are already in place (unless, of course, they are zero in the source field). Then I take the next byte from the 64 bit field and in the next pre-calculated table I select another template and make a logical “or” with the first. And so 8 times. Since these operations do not contain conditional jumps, they should be performed quickly enough without violating the pipeline in the processor.
All this looks good enough, however, to code all these automorphisms and quick permutations of bits manually and without errors is quite problematic. Therefore, an additional program was created that generates C code, which, in turn, is
included in the main program.
Conclusion and subsequent development
After creating the above program, it became possible in a few days to find an almost optimal tree for playing 4x4x4 tic-tac-toe. Why is it "almost optimal"? Because the total length of the forced moves is not taken into account and it may happen that there is a tree for unforced moves of the same depth, but with a smaller total depth of the forced moves. But I think this is not a very big drawback.
Thus, the game of tic-tac-toe 4x4x4 is completely calculated, the crosses always win and you can close this topic? Not really. The fact is that since crosses go first, they have an advantage. What if you try to compensate for this advantage in some way? I propose the following idea - to prohibit the crosses from putting the cross in the field that controls 7 lines with the first move, restricting them to fields controlling only 4 lines. Despite the fact that this seems to be a small change, in fact, the result of the game can change significantly and zeros will be able to reduce the game to a draw, or maybe win. So, there is something to explore.