We all know there are six bitwise operators in Python, and most of the other programming languages:
- Bitwise AND – &
- Bitwise OR – |
- Bitwise XOR – ^
- Bitwise Left Shift – <<
- Bitwise Right Shift – >>
- Bitwise NOT – ~
By using bitwise OR and AND, we can combine multiple (as many as 64) TRUE/FALSE or 1/0 values into one single integer. In this way we don’t need to declare lots of variables to hold boolean values. We could adopt this approach in Gobang game or Chess game to create a bitboard to speed up the AI search for the best move.
For example, by using bitboard we can find out in a 8×8 area whether there is 3/4/5 pieces in a row for any directions, namely, horizontal, vertical, forward and backward diagonal.
To do that, first we need to create a bitboard number from a 2D matrix.
Given the above matrix, the following code generates a bitboard value:
The bitboard value in both decimal and binary format are as follows for the above forward diagonal 5-piece-in-a-row.
As we can see, there are eight 0-bits between any two adjacent 1-bits. So the distance between a pair is 9 bits. To check whether there is a forward diagonal 5-pieces-in-a-row, all we need to do is to left shift 9 bits two times and apply bitwise AND operator after each shift. Then left shift 18 bits and apply bitwise AND operator one more time. If the final result is not zero, then we find one.
Similarly we could do 7-bits/8-bits/1-bit left shift for the other three directions, to find out whether there is any 3/4/5 pieces in a row. To simplfy out code, we can define a SHIFT_INFO for all four diections, then just loop through them one by one.
Following code showcase the search process:
As gobang board is 15×15 and a bitboard can only cover area of 8×8, a workaround is to use multiple bitboards for gobang. For example, following image shows that we need maximum 9 bitboards to cover any possible 5-in-a-row for 15×15 board.
Further analysis shows that we only need 4 bitboards during the game as we can use the lastest move as the center point to create the 4 necessary bitboards.
