Magic beatboards and Russian checkers
This article is an illustration of how bit tricks can be used not only in tasks for interviews, but also in solving real problems. The article describes one method of quickly generating moves in Russian checkers based on magic bitboards. Bitboards - position representation in the form of several unsigned integers, each bit of which is responsible for the state of a certain element of the game, for example, a cell. Usually the use of bitboards gives a gain in performance and in terms of the amount of memory used, but is associated with more sophisticated programming. In this case, the problem often arises of obtaining the value of certain bits in a bitboard, for example, for subsequent reference to a table. There are two main approaches to solving this problem. The first is the use and support of redundant submission in the form of additional bitboards with bit renumbering. Such bitboards are often called rotate. The second way is multiplication by the magic constant, shift and reference to the table. About these magical bitboards and will be discussed in this article.
Representing a position in the game is a crucial step that affects all subsequent ones. When I was a student, without hesitation, I chose the most obvious presentation in the form of an array of 32 bytes, one for each cell. This turned out to be an ineffective solution. And if at least it worked on checkers, in the case of chess, the results were deplorable.
Later I learned that one of the fastest algorithms for getting a list of all moves uses bitboards. In the case of chess, this is a representation of the position in the form of 64-bit numbers, where each bit is responsible for one cell of the board. A total of several bitboards are used, one for storing the disposition of white pawns, the other for storing the arrangement of black knights, etc. To generate all moves in chess, two main methods are used: “rotating bitboards” and “magic beatboards”. The use of the “rotated bitboards” method is described in the article “ Rotated bitboards: a new round of the old idea ”. The use of the magical beatboard method can be found in English on the chessprogramming wiki site. Who is interested in implementation in the C programming language, I advise you to watch the code of the Crafty chess engine, which is available on craftychess.com . The author of the engine, Professor Robert Hyatt (Robert Hyatt) paid much attention to the readability of the code, many places are provided with explanations. He is also the author of several interesting articles on chess programming.
In the case of chess, the use of bitboards looks natural. 64 cells - 64 bits. There is no question about the numbering of bits. Suppose we go to generate all the movements of the white pawns on one field. To do this, we need to take the bit mask of all pawns, move eight bits to the left (black pawns move, respectively, to the right), make AND with the bitboard of all free cells, and we immediately get a bit field mask, where I can move the pawns. It remains only to form a list of moves.
')
With Russian checkers, everything is a little more complicated. What should be the correspondence between bits and fields of the board? One of the options to get as much as possible from chess is to use the board representation in the form of a 64-bit integer number, where only 32 bits, which are responsible for black fields, are used. Yes, an option, but the fact that exactly half of all bits will not be used depresses me. If only 32 black cells are used for the game, then why not use 32-bit numbers as beatboards?
So, the position in Russian checkers is described by an integer number, which will show the turn of the turn, and four 32-bit bitboards. The question about the correspondence of fields and bits will be left until later. What are four bitboards you need to choose to represent the board? I stopped at the option when for each side two bitboards are used: all simple checkers, and all checkers, both simple and ladies. In this case, we can get all the bitboards we are interested in in one operation. So,
An important issue is the numbering of bits. The easiest way is to consider the problem of generating moves of simple checkers. For each method of numbering bits, we need to find a simple expression that would allow us to get a bit mask of possible displacements simple. Let's start with the most obvious way for numbering bits:
It looks beautiful, but somewhat uncomfortable. The fact is, the number of bits by which we need to move the simple bit mask depends on the parity of the series. What makes us write a more complex expression.
For now, we will keep this option as a reserve parachute, and try to find a numbering in which the numbers of bits on one diagonal form an arithmetic progression. After playing a little, this numbering appears:
If you take the diagonals going up and left, then everything is fine, to generate simple moves, you can use a simple left shift [to the right] for whites [black]. If we take the diagonals that run parallel to the a1-h8 diagonal (bolshaku), then we have an arithmetic progression using modulo-32 addition, which corresponds to the cyclic shift operation. This operation must be sufficiently effective, as it is contained in the instruction set of some processors, in particular the x86 family. On this and stop.
In reality, not all simple can go forward-left. Therefore, in a real program, you will have to perform another AND operation before the shift, leaving only those checkers that have this capability. If we eliminate the technical difficulty with the fact that in one move you can take several enemy checkers, then taking simple primes is treated the same way, only we will need to perform two consecutive shifts, the first of which is to make AND with the enemy's beatboard and the second are free fields . Below is an example for the case of a take-up check:
We got a fairly effective solution, but it only works for an 8x8 board. In the case of international checkers (board 10x10) on a board of 50 black cells. Using a similar type of numbering, we step on a rake that we need to perform a cyclic shift for 50 bits. There is no such one instruction, so you will have to perform the bit mask acquisition for three operations: left shift, right shift and OR. In the case of the Sparintseti checkers, which are no different from the Russian checkers, except that the 8x10 board is used, it is difficult to come up with even an analogue of such numbering, so most likely you will have to use the board representation in the form of a 10x10 subset.
Now consider the issues relating to the capture of the ladies. Can a lady make a capture, which piece will be killed, where can a lady get after taking? It seems that to answer these questions can not do without a tedious cycle. But if you look closely, only the bits of the same diagonal are used to answer these questions. Diagonals that are parallel to the twin (diagonals g1-a7 and h2-b8) have a consecutive numbering of bits. Which leads us to a rather simple idea: all the checkers' beatboards must be shifted to the right so that all the bits of the diagonal occupy the youngest positions. And then just turn to some predetermined table. And this is a minimum of operations!
For diagonals that are parallel to a large one, getting answers to these questions is somewhat more difficult. One of the ways is to support two numbers at the same time, one of which would be more convenient for checking the captures on the diagonals parallel to the big one, and the other on the diagonals parallel to the twin. This numbering looks like it is rotated at a 90Âş angle. Hence the name - rotated bitboards. When I once implemented a generator of moves in chess based on this idea, every time I read bitboards in hexadecimal form, rotated 90Âş degrees, involuntarily turned my head myself. Here is a possible numbering for rotated beatwords:
But there is also a more beautiful idea! So, consider the big. In our bitboard, these are bits 0, 7, 14, 21, 28, 3, 10, 17. We need to come up with a function that would move these bits to places from zero to seventh, in any order. Then we could use the table prepared in advance.
As for me, such an operation would be very useful in the instruction set of the processor, especially which is designed to implement logic in different games. The instruction itself could have the form SUBBITS a, v , where a is a certain number, v is a bitmask, which indicates which bits should be left and moved to the lower digits. For example, SUBBITS 0xFF00FF, 0x111111 should output 110011 2 at the output: leave bits with numbers 0, 4, 8, 12, 16, 20 and transfer the zero bit to the zero position, the fourth - to the first, eighth - to the second, ...
Well, this is a lyrical digression. In most cases, such an operation is easy to implement efficiently with existing commands. Moving the bits to the right is a division. In practice, it turned out that it is easier to move all the bits to the leftmost positions (multiplication), and then make a big shift to the right. How?
Consider one bit. Suppose we have the number x, and we want the 10th bit of this number to the 31st position, which is uninteresting to the rest of the bits. This is a rather simple task, since 31 - 10 = 21, we get x << 21. Suppose that we have not only the 10th bit, but also the 20th bit, which we would like to move to the 30th position. This is not difficult to do:
And now let's try to look at this sequence in a different way. First of all, we can replace the OR operation in the last line with the addition by the addition: no overflow will spoil our life. Secondly, after replacing the OR sign with a plus sign, the expression in the last line suspiciously resembles multiplication. Really,
mask10 and mask20 are obtained from the same x, so we can bring our example to the form:
If you don’t pay attention that there may be garbage left in other bits, this will work.
Let's sum up. If the stars in the sky are successful, then you can move the specified bits to higher positions by the AND operation and multiplication. Or maybe not. In our case, bits 10 and 20 are located far from each other, and the result of addition can in no way affect the 31st and 30th bits of the result.
When will our method fail? Suppose we want to move the 4th bit to the 7th place, the 2nd bit to the 6th, and the 0th to the 5th. In this case, our magic constant will look like 0x38, it has three bits set: the fifth (shift by five), the fifth and the third. But the problem is that when we try to implement our multiplication, the bits will overlap one another:
How to get around this trouble? The way out is that we can try another bit permutation. For example, 4 → 6, 2 → 7, 0 → 5. In this case, our magic constant will look like 0x24, only two bits are set in it, because the second and zero bits must move to the same value.
What does this mean in relation to bitboards in checkers? We have seven diagonals, and if we are lucky, but we can find such a permutation of bits that multiplying by a magic constant takes every bit to the right place and doesn’t spoil anything. But for this we will need to write a separate search program that would not only find such constants, form magical arrays storing answers to the questions whether it is possible to take a take, which checker is being killed, what fields a woman can go after taking (or continue the fight ).
Of course, there may still be technical difficulties in generating a list of moves. For example, we must not forget about the Turkish strike , when the dead drafts are removed from the board only after the completion of the strike. But they are all technical. For this article, I implemented a small learning example that presents the implementation of a move generator using magic bit masks. It can be said on the link checkers-0.1.tar.bz2 .
Position representation
Representing a position in the game is a crucial step that affects all subsequent ones. When I was a student, without hesitation, I chose the most obvious presentation in the form of an array of 32 bytes, one for each cell. This turned out to be an ineffective solution. And if at least it worked on checkers, in the case of chess, the results were deplorable.
Later I learned that one of the fastest algorithms for getting a list of all moves uses bitboards. In the case of chess, this is a representation of the position in the form of 64-bit numbers, where each bit is responsible for one cell of the board. A total of several bitboards are used, one for storing the disposition of white pawns, the other for storing the arrangement of black knights, etc. To generate all moves in chess, two main methods are used: “rotating bitboards” and “magic beatboards”. The use of the “rotated bitboards” method is described in the article “ Rotated bitboards: a new round of the old idea ”. The use of the magical beatboard method can be found in English on the chessprogramming wiki site. Who is interested in implementation in the C programming language, I advise you to watch the code of the Crafty chess engine, which is available on craftychess.com . The author of the engine, Professor Robert Hyatt (Robert Hyatt) paid much attention to the readability of the code, many places are provided with explanations. He is also the author of several interesting articles on chess programming.
In the case of chess, the use of bitboards looks natural. 64 cells - 64 bits. There is no question about the numbering of bits. Suppose we go to generate all the movements of the white pawns on one field. To do this, we need to take the bit mask of all pawns, move eight bits to the left (black pawns move, respectively, to the right), make AND with the bitboard of all free cells, and we immediately get a bit field mask, where I can move the pawns. It remains only to form a list of moves.
')
With Russian checkers, everything is a little more complicated. What should be the correspondence between bits and fields of the board? One of the options to get as much as possible from chess is to use the board representation in the form of a 64-bit integer number, where only 32 bits, which are responsible for black fields, are used. Yes, an option, but the fact that exactly half of all bits will not be used depresses me. If only 32 black cells are used for the game, then why not use 32-bit numbers as beatboards?
So, the position in Russian checkers is described by an integer number, which will show the turn of the turn, and four 32-bit bitboards. The question about the correspondence of fields and bits will be left until later. What are four bitboards you need to choose to represent the board? I stopped at the option when for each side two bitboards are used: all simple checkers, and all checkers, both simple and ladies. In this case, we can get all the bitboards we are interested in in one operation. So,
typedef int square_t; typedef uint32_t bitboard_t; typedef int side_t; enum side_t { WHITE, BLACK }; enum position_bitboard_index_t { IDX_ALL_0 = 0, // IDX_ALL_1 = 1, // IDX_SIM_0 = 2, // IDX_SIM_1 = 3 // . }; struct position { bitboard_t bitboards[4]; side_t active; }; // : uint32_t /* */ all_bb = bitboards[IDX_ALL_0] | bitboards[IDX_ALL_1]; uint32_t /* */ empty_bb = ~all_bb; uint32_t /* */ mam_bb = bitboards[IDX_ALL_0] ^ bitboards[IDX_SIM_0]; Bit numbering
An important issue is the numbering of bits. The easiest way is to consider the problem of generating moves of simple checkers. For each method of numbering bits, we need to find a simple expression that would allow us to get a bit mask of possible displacements simple. Let's start with the most obvious way for numbering bits:
+ - + - + - + - + - + - + - + - + | | 28 | | 29 | | 30 | | 31 | eight + - + - + - + - + - + - + - + - + | 24 | | 25 | | 26 | | 27 | | 7 + - + - + - + - + - + - + - + - + | | 20 | | 21 | | 22 | | 23 | 6 + - + - + - + - + - + - + - + - + | 16 | | 17 | | 18 | | 19 | | five + - + - + - + - + - + - + - + - + | | 12 | | 13 | | | 14 | | 15 | four + - + - + - + - + - + - + - + - + | 8 | | 9 | | 10 | | 11 | | 3 + - + - + - + - + - + - + - + - + | | 4 | | 5 | | 6 | | 7 | 2 + - + - + - + - + - + - + - + - + | 0 | | 1 | | 2 | | 3 | | one + - + - + - + - + - + - + - + - + abcdefgh
It looks beautiful, but somewhat uncomfortable. The fact is, the number of bits by which we need to move the simple bit mask depends on the parity of the series. What makes us write a more complex expression.
// , , — : uint32_t up_right_bb = 0 | ((bb & RANK_1357) >> 4 | ((bb & RANK_2468) >> 5 ; For now, we will keep this option as a reserve parachute, and try to find a numbering in which the numbers of bits on one diagonal form an arithmetic progression. After playing a little, this numbering appears:
+ - + - + - + - + - + - + - + - + | | 31 | | 5 | | 11 | | 17 | eight + - + - + - + - + - + - + - + - + | 24 | | 30 | | 4 | | 10 | | 7 + - + - + - + - + - + - + - + - + | | 23 | | 29 | | 3 | | 9 | 6 + - + - + - + - + - + - + - + - + | 16 | | 22 | | 28 | | 2 | | five + - + - + - + - + - + - + - + - + | | 15 | | 21 | | 27 | | 1 | four + - + - + - + - + - + - + - + - + | 8 | | 14 | | 20 | | 26 | | 3 + - + - + - + - + - + - + - + - + | | 7 | | 13 | | | 19 | | 25 | 2 + - + - + - + - + - + - + - + - + | 0 | | 6 | | 12 | | 18 | | one + - + - + - + - + - + - + - + - + abcdefgh
If you take the diagonals going up and left, then everything is fine, to generate simple moves, you can use a simple left shift [to the right] for whites [black]. If we take the diagonals that run parallel to the a1-h8 diagonal (bolshaku), then we have an arithmetic progression using modulo-32 addition, which corresponds to the cyclic shift operation. This operation must be sufficiently effective, as it is contained in the instruction set of some processors, in particular the x86 family. On this and stop.
In reality, not all simple can go forward-left. Therefore, in a real program, you will have to perform another AND operation before the shift, leaving only those checkers that have this capability. If we eliminate the technical difficulty with the fact that in one move you can take several enemy checkers, then taking simple primes is treated the same way, only we will need to perform two consecutive shifts, the first of which is to make AND with the enemy's beatboard and the second are free fields . Below is an example for the case of a take-up check:
all = bitboards[IDX_ALL_0] | bitboards[IDX_ALL_1]; enemy = bitboards[IDX_ALL_1 ^ active]; bitboard_t empty = ~all; bitboard_t singles = bitboards[IDX_SIM | active]; bitboard_t try_left_up = ((((singles & possible_left_up) << 1) & enemy) << 1) & empty; We got a fairly effective solution, but it only works for an 8x8 board. In the case of international checkers (board 10x10) on a board of 50 black cells. Using a similar type of numbering, we step on a rake that we need to perform a cyclic shift for 50 bits. There is no such one instruction, so you will have to perform the bit mask acquisition for three operations: left shift, right shift and OR. In the case of the Sparintseti checkers, which are no different from the Russian checkers, except that the 8x10 board is used, it is difficult to come up with even an analogue of such numbering, so most likely you will have to use the board representation in the form of a 10x10 subset.
Magic
Now consider the issues relating to the capture of the ladies. Can a lady make a capture, which piece will be killed, where can a lady get after taking? It seems that to answer these questions can not do without a tedious cycle. But if you look closely, only the bits of the same diagonal are used to answer these questions. Diagonals that are parallel to the twin (diagonals g1-a7 and h2-b8) have a consecutive numbering of bits. Which leads us to a rather simple idea: all the checkers' beatboards must be shifted to the right so that all the bits of the diagonal occupy the youngest positions. And then just turn to some predetermined table. And this is a minimum of operations!
// sq - , const struct square_info * sm = square_infos + sq; // , shift - uint32_t index = (all >> sm->shift) & 0x7F; // const struct mam_take_magic * mtm = mam_take_magic[sq] + index; // mtm , , , For diagonals that are parallel to a large one, getting answers to these questions is somewhat more difficult. One of the ways is to support two numbers at the same time, one of which would be more convenient for checking the captures on the diagonals parallel to the big one, and the other on the diagonals parallel to the twin. This numbering looks like it is rotated at a 90Âş angle. Hence the name - rotated bitboards. When I once implemented a generator of moves in chess based on this idea, every time I read bitboards in hexadecimal form, rotated 90Âş degrees, involuntarily turned my head myself. Here is a possible numbering for rotated beatwords:
+ - + - + - + - + - + - + - + - + | | 25 | | 19 | | 13 | | | 7 | eight + - + - + - + - + - + - + - + - + | 24 | | 18 | | 12 | | 6 | | 7 + - + - + - + - + - + - + - + - + | | 17 | | 11 | | 5 | | 31 | 6 + - + - + - + - + - + - + - + - + | 16 | | 10 | | 4 | | 30 | | five + - + - + - + - + - + - + - + - + | | 9 | | 3 | | 29 | | 23 | four + - + - + - + - + - + - + - + - + | 8 | | 2 | | 28 | | 22 | | 3 + - + - + - + - + - + - + - + - + | | 1 | | 27 | | 21 | | 15 | 2 + - + - + - + - + - + - + - + - + | 0 | | 26 | | 20 | | 14 | | one + - + - + - + - + - + - + - + - + abcdefgh
But there is also a more beautiful idea! So, consider the big. In our bitboard, these are bits 0, 7, 14, 21, 28, 3, 10, 17. We need to come up with a function that would move these bits to places from zero to seventh, in any order. Then we could use the table prepared in advance.
As for me, such an operation would be very useful in the instruction set of the processor, especially which is designed to implement logic in different games. The instruction itself could have the form SUBBITS a, v , where a is a certain number, v is a bitmask, which indicates which bits should be left and moved to the lower digits. For example, SUBBITS 0xFF00FF, 0x111111 should output 110011 2 at the output: leave bits with numbers 0, 4, 8, 12, 16, 20 and transfer the zero bit to the zero position, the fourth - to the first, eighth - to the second, ...
Well, this is a lyrical digression. In most cases, such an operation is easy to implement efficiently with existing commands. Moving the bits to the right is a division. In practice, it turned out that it is easier to move all the bits to the leftmost positions (multiplication), and then make a big shift to the right. How?
Consider one bit. Suppose we have the number x, and we want the 10th bit of this number to the 31st position, which is uninteresting to the rest of the bits. This is a rather simple task, since 31 - 10 = 21, we get x << 21. Suppose that we have not only the 10th bit, but also the 20th bit, which we would like to move to the 30th position. This is not difficult to do:
bit10 = 1 << 10; bit20 = 1 << 20; mask10 = x & bit10; mask20 = x & bit20; result = (mask10 << 21) | (mask20 << 10); And now let's try to look at this sequence in a different way. First of all, we can replace the OR operation in the last line with the addition by the addition: no overflow will spoil our life. Secondly, after replacing the OR sign with a plus sign, the expression in the last line suspiciously resembles multiplication. Really,
(x << 21) + (x << 10) == x * 0x00100400 mask10 and mask20 are obtained from the same x, so we can bring our example to the form:
bit10 = 1 << 10; bit20 = 1 << 20; mask = x & (bit10 | bit20); result = mask * 0x00100400; If you don’t pay attention that there may be garbage left in other bits, this will work.
Let's sum up. If the stars in the sky are successful, then you can move the specified bits to higher positions by the AND operation and multiplication. Or maybe not. In our case, bits 10 and 20 are located far from each other, and the result of addition can in no way affect the 31st and 30th bits of the result.
When will our method fail? Suppose we want to move the 4th bit to the 7th place, the 2nd bit to the 6th, and the 0th to the 5th. In this case, our magic constant will look like 0x38, it has three bits set: the fifth (shift by five), the fifth and the third. But the problem is that when we try to implement our multiplication, the bits will overlap one another:
* 10101
111,000
--------
10,101,000
10,1010000
1010100000
-----------
???
How to get around this trouble? The way out is that we can try another bit permutation. For example, 4 → 6, 2 → 7, 0 → 5. In this case, our magic constant will look like 0x24, only two bits are set in it, because the second and zero bits must move to the same value.
* 10101
100,100
--------
10,10100
1010100000
----------
..111 .....
What does this mean in relation to bitboards in checkers? We have seven diagonals, and if we are lucky, but we can find such a permutation of bits that multiplying by a magic constant takes every bit to the right place and doesn’t spoil anything. But for this we will need to write a separate search program that would not only find such constants, form magical arrays storing answers to the questions whether it is possible to take a take, which checker is being killed, what fields a woman can go after taking (or continue the fight ).
Conclusion
Of course, there may still be technical difficulties in generating a list of moves. For example, we must not forget about the Turkish strike , when the dead drafts are removed from the board only after the completion of the strike. But they are all technical. For this article, I implemented a small learning example that presents the implementation of a move generator using magic bit masks. It can be said on the link checkers-0.1.tar.bz2 .
Source: https://habr.com/ru/post/272815/
All Articles