Developers Club geek daily blog

1 year, 6 months ago
This article — an illustration how bit tricks can be used not only in tasks on interviews, but also at a solution of real tasks. In article the description of one method of fast generation of the courses in the Russian checkers on the basis of magic bitbord (magic bitboard) is given. Bitborda — representation of a position in the form of several unsigned integers which each bit is responsible for a status of some game element, for example cages. Usually use of bitbord gives a prize on performance and on the amount of the used memory, but is connected with more sophisticated programming. At the same time often there is a problem of receipt of value of certain bits in a bitborda, for example, for the subsequent addressing the table. There are two basic approaches to a solution of this task. The first — use and support of excess representation in the form of additional bitbord with renumbering of bits. Such bitborda asto are called rotated. The second method — multiplication by a magic constant, shift and the addressing the table. About such magic bitborda the speech in this article will also go.

Representation of a position


Representation of a position in game — a responsible step which influences all the subsequent. When I was a student, without hesitation, selected the most arising array representation from 32 bytes, on one on each cage. It was an inefficient solution. And if it at the very least worked at checkers, then in case of chess results were deplorable.

Later I learned that one of the fastest algorithms of receipt of the list of all courses use bitborda. In case of chess this representation of a position in the form of 64-bit numbers where each bit is responsible for one cage of a board. In total several bitbord, one for storage of an arrangement of white pawns, another for storage of an arrangement of black horses etc. are used. For generation of all courses in chess two main methods are used: "the rotated bitbord" and "magic bitbord". Use of a method of "the rotated bitbord" is described in article "The rotated bitborda: new round of old idea". Use of a method of "magic bitbord" can be found in English on the website chessprogramming wiki. Whom implementation in a programming language C interests, I advise to watch a code of the chess Crafty engine which is available on the website craftychess.com. The author of the engine, professor Robert Hiatt (Robert Hyatt) paid to readability of a code much attention, many places are supplied with explanations. Also he is the author of several interesting articles on chess programming.

In case of chess use of bitbord looks natural. 64 cages — 64 bits. There is no question of numbering of bits. Let's say we go to generate all movements of white pawns on one field. For this purpose we should take a bit mask of all pawns, to shift on eight bits to the left (black pawns move respectively to the right), to make AND with bitbordy all free cages, and we instantly receive a bit mask of fields where I can move pawns. It was necessary only to create the list of the courses.

With the Russian checkers everything is a little more difficult. What has to be compliance between bits and fields of a board? To take one of options as much as possible from chess — to use representation of a board in the form of a 64-bit integral number where only 32 bits which are responsible for black fields would be used. Yes, the option, but oppresses me the fact that exactly a half of all bits will not be used. If for game only 32 black cages are used, then why not to use 32-bit numbers as bitbord?

So, the position in the Russian checkers is described by an integral number which will show queue of the course, and four 32-bit bitborda. And bits we will leave a question about compliance of fields so far for later. What four bitbord should be selected for representation of a board? I stopped on option when for each party two bitbord are used: all simple checkers, and all checkers both simple, and kings. In this case we can receive one operation all bitborda interesting us. 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];


Numbering of bits


Important issue is numbering of bits. It is the simplest to consider a problem of generation of the courses of simple checkers. For each method of numbering of bits we should find simple expression which would allow us to receive a bit mask of possible movements idle time. Let's begin, perhaps, with the most obvious option of numbering of bits:

+--+--+--+--+--+--+--+--+
|  |28|  |29|  |30|  |31| 8
+--+--+--+--+--+--+--+--+
|24|  |25|  |26|  |27|  | 7
+--+--+--+--+--+--+--+--+
|  |20|  |21|  |22|  |23| 6
+--+--+--+--+--+--+--+--+
|16|  |17|  |18|  |19|  | 5
+--+--+--+--+--+--+--+--+
|  |12|  |13|  |14|  |15| 4
+--+--+--+--+--+--+--+--+
| 8|  | 9|  |10|  |11|  | 3
+--+--+--+--+--+--+--+--+
|  | 4|  | 5|  | 6|  | 7| 2
+--+--+--+--+--+--+--+--+
| 0|  | 1|  | 2|  | 3|  | 1
+--+--+--+--+--+--+--+--+
  a  b  c  d  e  f  g  h


Looks beautifully, but it is a little inconvenient. Business is in that, the number of bits on which we should shift a bit mask of simple depends on parity of a row. What forces to write us more difficult expression.

  // Ход белых вверх вправо, чётные горизонтали надо сдвигать на пять, нечётные — на четыре:
  uint32_t up_right_bb = 0
    | ((bb &RANK_1357) >> 4
    | ((bb &RANK_2468) >> 5
  ;


Let's hold meanwhile such option as a reserve parachute, and we will try to find such numbering at which numbers of bits on one diagonal formed an arithmetic progression. Having a little played, there is such option of numbering:

+--+--+--+--+--+--+--+--+
|  |31|  | 5|  |11|  |17| 8
+--+--+--+--+--+--+--+--+
|24|  |30|  | 4|  |10|  | 7
+--+--+--+--+--+--+--+--+
|  |23|  |29|  | 3|  | 9| 6
+--+--+--+--+--+--+--+--+
|16|  |22|  |28|  | 2|  | 5
+--+--+--+--+--+--+--+--+
|  |15|  |21|  |27|  | 1| 4
+--+--+--+--+--+--+--+--+
| 8|  |14|  |20|  |26|  | 3
+--+--+--+--+--+--+--+--+
|  | 7|  |13|  |19|  |25| 2
+--+--+--+--+--+--+--+--+
| 0|  | 6|  |12|  |18|  | 1
+--+--+--+--+--+--+--+--+
  a  b  c  d  e  f  g  h


If to take the diagonals going up-to the left then everything is remarkable for generation of the courses simple it is possible to use the simple left shift [to the right] for white [black]. If to take the diagonals going parallel to the diagonal of a1-h8 (bolshaka) then we have an arithmetic progression where addition on the module 32 is used that corresponds to operation of cycle shift. This operation has to be rather effective as contains in a set of instructions of some processors, in particular x86 families. On it we will also stop.

Not all simple can go to realities forward-to the left. Therefore in the real program it is necessary to execute before shift still the operation AND, having left only those checkers which have the present possibility. If to exclude technical difficulty that it is possible to take several checkers of the opponent for one course, then takings of simple are considered similarly, only we should execute two successive shifts, on first of which to do AND with bitbordy the opponent's checkers, and on the second with bitbordy free fields. Below the example for a taking check case is given up-to the left:

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 received rather effective solution, but it works only for a board 8x8. In case of the international checkers (a board 10x10) on a board of 50 black cages. Using similar type of numbering we step on a rake that it is necessary to execute cycle shift for 50 bits. There is no such one instruction so it is necessary to execute receipts of a bit mask for three operations: left shift, right shift and OR. In case of Sparintseti's checkers which differ in nothing from the Russian checkers except that the board 8x10 is used, it is difficult to think up even analog of similar numbering so most likely it is necessary to use representation of a board in the form of a subset 10x10.

Magic


Now we will consider questions which concern taking by kings. Whether the king can perform taking what checker will be killed where there can be a king after taking? It seems that for the answer to these questions not to do without tiresome cycle. But if to look narrowly attentively, then for the answer to these questions only bits of one diagonal are used. Diagonals which are parallel to the double (diagonals of g1-a7 and h2-b8) have sequential numbering of bits. What leads us to quite simple idea: bitbord all checkers it is necessary to shift to the right so that all bits of diagonal took the youngest positions. And then it is simple to address some in advance made table. And it 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 which are parallel to a bolshak to receive answers to these questions slightly more difficult. One of methods, it to support at the same time two numberings, one of which would be more convenient for check of the takings on diagonals, parallel to a bolshak, and another — after the diagonals parallel to the double. Such numbering looks as if turned on a corner 90º. From here and the name — the rotated bitborda. When I implemented the generator of the courses in chess on the basis of this idea in due time, reading every time in a hexadecimal type of a bitborda, turned on 90º degrees, involuntarily and itself turned the head. Here possible numbering for the rotated bitvord:

+--+--+--+--+--+--+--+--+
|  |25|  |19|  |13|  | 7| 8
+--+--+--+--+--+--+--+--+
|24|  |18|  |12|  | 6|  | 7
+--+--+--+--+--+--+--+--+
|  |17|  |11|  | 5|  |31| 6
+--+--+--+--+--+--+--+--+
|16|  |10|  | 4|  |30|  | 5
+--+--+--+--+--+--+--+--+
|  | 9|  | 3|  |29|  |23| 4
+--+--+--+--+--+--+--+--+
| 8|  | 2|  |28|  |22|  | 3
+--+--+--+--+--+--+--+--+
|  | 1|  |27|  |21|  |15| 2
+--+--+--+--+--+--+--+--+
| 0|  |26|  |20|  |14|  | 1
+--+--+--+--+--+--+--+--+
  a  b  c  d  e  f  g  h


But there is also more beautiful idea! So, we will consider bolshak. In our bitbord it is bits 0, 7, 14, 21, 28, 3, 10, 17. We should think up such function which would rearrange these bits on places with zero on the seventh, in any order. Then we could use in advance prepared table.

As on me, such operation would be very useful in a set of instructions of the processor, especially which is intended for implementation of logic in different games. The instruction could have a type of SUBBITS a, v where a — some number, v — a bit mask which indicates what bits should be left and transferred to low orders. For example, SUBBITS 0xFF00FF, 0x111111 has to give on an output 1100112: we leave bits with numbers 0, 4, 8, 12, 16, 20 and we transfer zero bit in zero positions, the fourth — to the first, eighth — in the second, …

Well this lyrical digression. In the majority a case simply effectively to implement such operation also the available commands. Transfer of bits is a division to the right. In practice it turned out that it is simpler to transfer all bits to the most left positions (multiplication), and then to make the big right shift. How?

Let's consider one bits. Let's allow we have a number x, and we want the 10th bit of this number in the 31st position that with other bits to us it will be become uninteresting. It is rather simple task as 31 — 10 = 21, we receive x << 21. Предположим, что у нас есть не только 10-й бит, но еще и 20-й, который бы мы хотели перенести в 30-ю позицию. Сделать это не сложно:

bit10 = 1 << 10;
bit20 = 1 << 20;
mask10 = x &bit10;
mask20 = x &bit20;
result = (mask10 << 21) | (mask20 << 10);


And now we will try to look at this sequence in a different way. First, we can replace the operation OR the last line with addition without serious consequences: any overflow to us life will not be spoiled. Secondly, after replacement of the sign OR by plus, expression the last line suspiciously reminds multiplication. Really,

(x << 21) + (x << 10) == x * 0x00100400


mask10 and mask20 turn out from one x therefore we can give our example to a type:

bit10 = 1 << 10;
bit20 = 1 << 20;
mask = x &(bit10 | bit20);
result = mask * 0x00100400;


If not to pay attention that in other bits there can be a garbage, it will work.

Let's sum up the results. If stars stand on the sky successfully, then can transfer the set bits to the senior positions it will turn out the operation AND and multiplication. And it can not turn out. In our case bits with numbers 10 and 20 are located far apart, and the result of addition cannot mention the 31st and 30th bit of result in any way.

When - our method glitches? Let us want to move the 4th bit to the 7th place, the 2nd bit on the 6th, and 0 on the 5th. In this case our magic constant will take a form 0x38, in it three bits are set: the fifth (shift on five), the fifth and third. But the problem is that when we try to perform our multiplication, bits will be imposed one on another:

 *    10101
     111000 
   --------
   10101000
  101010000
 1010100000
-----------
   ???


How to bypass such trouble? The output consists that we can try other shift of bits. For example, 4→6, 2→7, 0→5. In this case our magic constant will take a form 0x24, in it only two bits because the second and zero bit have to move on the same value are set.

 *    10101
     100100 
   --------
    1010100
 1010100000
 ----------
 ..111.....


What does it designate in relation to bitborda in checkers? We have seven diagonals and if to us carries, but we will be able to find such shift of bits that multiplication by a magic constant will transfer each bit to the right place, and will spoil nothing. But for this purpose we will need to write the separate program of search which not only found such constants, would create the magic arrays storing answers to questions whether it is possible to perform taking what checker is killed to what fields the king can pass after taking (or to continue fight).

Conclusion


Of course, at generation of the list of the courses still there can be technical difficulties. For example, it is necessary not to forget about the Turkish blow when the killed checkers are removed from a board only after completion of blow. But all of them have technical character. For this article I implemented a small educational example in which implementation of the generator of the courses about use of magic bit masks is provided. It can be told according to the link checkers-0.1.tar.bz2.

This article is a translation of the original post at habrahabr.ru/post/272815/
If you have any questions regarding the material covered in the article above, please, contact the original author of the post.
If you have any complaints about this article or you want this article to be deleted, please, drop an email here: sysmagazine.com@gmail.com.

We believe that the knowledge, which is available at the most popular Russian IT blog habrahabr.ru, should be accessed by everyone, even though it is poorly translated.
Shared knowledge makes the world better.
Best wishes.

comments powered by Disqus