Almost optimal solution of three-dimensional 4x4x4 noughts and crosses
Everyone knows the game tic-tac-toe 3x3. With the right game at the first move of the crosses, the result is a draw. You can manually create a tree of moves, where on any move of zeroes, there is a move of crosses, which leads to the best result (for crosses), that is, to a draw or win. This tree of moves exhausts all the options, so they say that the game is “solved”. There is a three-dimensional type of 4x4x4 tic-tacs for which the answer to the question of who will win in the first move of the crosses is not obvious. Moreover, the question arises whether it is possible to construct such a minimal tree that will solve this problem.
The answer to this question under the cut.
Let me remind you that it is a 4x4x4 tic-tac-toe game (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 contour lines and verticals, 24 diagonals and 4 main diagonals. Given this, you can see 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? It can be roughly estimated as 2 to the degree of 64 variants, which is quite a lot. Of course, not all of these options are realized in the game and many branches of the tree are cut off quite quickly, but in this case it is not possible to build such a tree by simple enumeration. How can we reduce the bust in order to solve this problem? It can be noted 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 placing three crosses or zeroes 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 in the next move. Such moves with the 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, zeroes. If such a chain of moves leads to a situation in which there are two lines with three crosses or zeroes, then the corresponding player loses. This is called a forced win.
Let us number all the fields with numbers from 0 to 63 starting from the top edge and going by horizontal lines from left to right.
We illustrate this with the example of one game:
0-3-60-21-15-51-12-63 4x8x5x10x20x40x28x44x24x16x36x52x48
Here the crosses make the first move to the left far corner on the upper face (0), then the toes respond to the right far corner on the same face (3). Crosses go to the left near corner on the bottom face (60), the toe is answered in the field on the second from the top face, etc. After moving the zeros into 63, the crosses begin a sequence of forced moves: 4 - check. The toe is forced to answer at 8, the cross is 5 check, the toe is answered at 10, etc. until a cross has two lines with three crosses. The toe lost.
To solve this game, it is necessary to find such sequences for all possible moves of zeros. For an optimal solution, such sequences should be minimal.
The first who decided this game was Patashnik (Patashnik) in the early 80s. He manually picked up the initial combinations, and then searched for a winning move using a computer. He showed that if the crosses go into a corner, they always win when played correctly. The next step was taken by Victor Allis. In his dissertation in the mid-90s, he showed that the solution can be obtained completely on a computer. However, he did not check all the options with which the crosses could come to win, but only the first ten, the most promising ones. Therefore, his decision was not optimal and he left this task to other researchers.
The solution to this problem in an optimal way, that is, I decided to find the minimum tree. Obviously, for this you need to use the search in width, as opposed to the depth search in Allis. First of all, the search of the forced gain for an arbitrary situation was implemented. It turned out, however, that it turned out to be rather slow, since the search in depth for the forced gain for long combinations is rather expensive. The solution was found by adding a repository of already calculated options to std :: unordered_set. It is worth saying that the playing field was encoded as 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. This caching gave a significant acceleration. However, the main problem was finding a wide for unforced moves. In a typical 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 the subtree calculation for this variant of the arrangement of crosses and zeros. In this case, the encoding of the playing field began to occupy 17 bytes. Thus, when searching in width and gradually increasing the depth of the tree, it was possible to discard already calculated subtrees. With this, I was able to calculate the minimum trees.
for the first move of the cross in the corner (square 0) and the responses of the zeros in all the fields that control four lines.
Difficulties arose if the zeros in the first reciprocal move occupied the field that controlled seven lines. In this case, the amount of memory occupied by the cache began to exceed 32 gigabytes of RAM, and my Linux went into a swap. It was necessary to look for another solution.
Here 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 turns and reflections will also have a solution. It should be noted here that thanks to these automorphisms, the first move of the crosses has only two options - one in the field 0 (controlling 7 lines) and one in the field 1 (controlling 4 lines). Therefore, in my case, the first move of the crosses is always done in field 0. But this is true only for an empty field.
Let us return, however, to automorphisms for an arbitrary playing field. How to find them all?
I used the following method: since the cube has a dimension of three, it is possible to rearrange the coordinates (there will be 6 such permutations) and make reflections (there will be 8 of them). Therefore, the total spatial automorphism will be 48. However, the cube has two more internal automorphisms. One swaps the coordinates of the fields in the first and second pair in each line,
and the second leaves the first and last field in place, and rearranges only the coordinates for the second and third field. These two automorphisms can also be applied simultaneously. Thus, for each of the 48 spatial automorphisms, there are four
(including trivial) inner automorphisms. Otherwise for the whole cube there are 192 automorphisms. This gives hope for a significant reduction in the number of stored fields already calculated.
However, another problem arises: if we check all 192 automorphisms, then we must quickly transform the playing field by shifting the bits. If this transformation is not done fast, then all the time will go to him, there will be no gain in performance and the whole idea of automorphisms will fly into the tube. Therefore, 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 create a table in advance and select a ready-made solution in it with the current playing field as the index. For me, this method did not work, since it was necessary to have an array of 2 to the extent of 64 sixty-bit words.
I already really wanted to leave this idea, however, it occurred to me that it was not necessary to have one big table, but you could have several small ones. In principle, it was possible to choose a different number of such tables, but I stopped at 8 tables of 256 words (for each automorphism). Thus, to rearrange the bits, I take one byte from the 64-bit field and, in a pre-calculated table, select a pattern where the bits are already in place (if they are, of course, not null in the original field). Then I take the next byte from the 64-bit field and in the next pre-calculated table I select another template and do a logical “or” with the first one. And so 8 times. Since these operations do not contain conditional transitions, they must be performed fairly quickly without disturbing the pipeline in the processor.
All this looks quite good, but it is quite problematic to encode all these automorphisms and quick bit permutations manually and without errors. Therefore, an additional program was created that generates C code, which, in turn,
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 tic-tac-toe 4x4x4. Why "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 4x4x4 tic-tac-toe game is fully calculated, the crosses always win and can this topic be closed? Not really. The fact is that since the crosses go first, they have an advantage. What if you try to compensate for this advantage? I propose the following idea - to prohibit the crosses with the first move to put a cross in the field that controls 7 lines, limiting them only to the 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 zeroes will be able to reduce the game to a draw, and maybe win. So, what is there to explore.
The answer to this question under the cut.
Let me remind you that it is a 4x4x4 tic-tac-toe game (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 contour lines and verticals, 24 diagonals and 4 main diagonals. Given this, you can see 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? It can be roughly estimated as 2 to the degree of 64 variants, which is quite a lot. Of course, not all of these options are realized in the game and many branches of the tree are cut off quite quickly, but in this case it is not possible to build such a tree by simple enumeration. How can we reduce the bust in order to solve this problem? It can be noted 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 placing three crosses or zeroes 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 in the next move. Such moves with the 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, zeroes. If such a chain of moves leads to a situation in which there are two lines with three crosses or zeroes, then the corresponding player loses. This is called a forced win.
Let us number all the fields with numbers from 0 to 63 starting from the top edge and going by horizontal lines from left to right.
We illustrate this with the example of one game:
0-3-60-21-15-51-12-63 4x8x5x10x20x40x28x44x24x16x36x52x48
Here the crosses make the first move to the left far corner on the upper face (0), then the toes respond to the right far corner on the same face (3). Crosses go to the left near corner on the bottom face (60), the toe is answered in the field on the second from the top face, etc. After moving the zeros into 63, the crosses begin a sequence of forced moves: 4 - check. The toe is forced to answer at 8, the cross is 5 check, the toe is answered at 10, etc. until a cross has two lines with three crosses. The toe lost.
To solve this game, it is necessary to find such sequences for all possible moves of zeros. For an optimal solution, such sequences should be minimal.
Historical excursion
The first who decided this game was Patashnik (Patashnik) in the early 80s. He manually picked up the initial combinations, and then searched for a winning move using a computer. He showed that if the crosses go into a corner, they always win when played correctly. The next step was taken by Victor Allis. In his dissertation in the mid-90s, he showed that the solution can be obtained completely on a computer. However, he did not check all the options with which the crosses could come to win, but only the first ten, the most promising ones. Therefore, his decision was not optimal and he left this task to other researchers.
The solution to this problem in an optimal way, that is, I decided to find the minimum tree. Obviously, for this you need to use the search in width, as opposed to the depth search in Allis. First of all, the search of the forced gain for an arbitrary situation was implemented. It turned out, however, that it turned out to be rather slow, since the search in depth for the forced gain for long combinations is rather expensive. The solution was found by adding a repository of already calculated options to std :: unordered_set. It is worth saying that the playing field was encoded as 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. This caching gave a significant acceleration. However, the main problem was finding a wide for unforced moves. In a typical 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 the subtree calculation for this variant of the arrangement of crosses and zeros. In this case, the encoding of the playing field began to occupy 17 bytes. Thus, when searching in width and gradually increasing the depth of the tree, it was possible to discard already calculated subtrees. With this, I was able to calculate the minimum trees.
for the first move of the cross in the corner (square 0) and the responses of the zeros in all the fields that control four lines.
Difficulties arose if the zeros in the first reciprocal move occupied the field that controlled seven lines. In this case, the amount of memory occupied by the cache began to exceed 32 gigabytes of RAM, and my Linux went into a swap. It was necessary to look for another solution.
Here 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 turns and reflections will also have a solution. It should be noted here that thanks to these automorphisms, the first move of the crosses has only two options - one in the field 0 (controlling 7 lines) and one in the field 1 (controlling 4 lines). Therefore, in my case, the first move of the crosses is always done in field 0. But this is true only for an empty field.
Let us return, however, to automorphisms for an arbitrary playing field. How to find them all?
I used the following method: since the cube has a dimension of three, it is possible to rearrange the coordinates (there will be 6 such permutations) and make reflections (there will be 8 of them). Therefore, the total spatial automorphism will be 48. However, the cube has two more internal automorphisms. One swaps the coordinates of the fields in the first and second pair in each line,
and the second leaves the first and last field in place, and rearranges only the coordinates for the second and third field. These two automorphisms can also be applied simultaneously. Thus, for each of the 48 spatial automorphisms, there are four
(including trivial) inner automorphisms. Otherwise for the whole cube there are 192 automorphisms. This gives hope for a significant reduction in the number of stored fields already calculated.
However, another problem arises: if we check all 192 automorphisms, then we must quickly transform the playing field by shifting the bits. If this transformation is not done fast, then all the time will go to him, there will be no gain in performance and the whole idea of automorphisms will fly into the tube. Therefore, 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 create a table in advance and select a ready-made solution in it with the current playing field as the index. For me, this method did not work, since it was necessary to have an array of 2 to the extent of 64 sixty-bit words.
I already really wanted to leave this idea, however, it occurred to me that it was not necessary to have one big table, but you could have several small ones. In principle, it was possible to choose a different number of such tables, but I stopped at 8 tables of 256 words (for each automorphism). Thus, to rearrange the bits, I take one byte from the 64-bit field and, in a pre-calculated table, select a pattern where the bits are already in place (if they are, of course, not null in the original field). Then I take the next byte from the 64-bit field and in the next pre-calculated table I select another template and do a logical “or” with the first one. And so 8 times. Since these operations do not contain conditional transitions, they must be performed fairly quickly without disturbing the pipeline in the processor.
All this looks quite good, but it is quite problematic to encode all these automorphisms and quick bit permutations manually and without errors. Therefore, an additional program was created that generates C code, which, in turn,
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 tic-tac-toe 4x4x4. Why "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 4x4x4 tic-tac-toe game is fully calculated, the crosses always win and can this topic be closed? Not really. The fact is that since the crosses go first, they have an advantage. What if you try to compensate for this advantage? I propose the following idea - to prohibit the crosses with the first move to put a cross in the field that controls 7 lines, limiting them only to the 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 zeroes will be able to reduce the game to a draw, and maybe win. So, what is there to explore.
All Articles