Introducing Bitboard-with a little Othello implementation-
Hello. This is Qiita's first post. Please feel free to take a look.
What is Bitboard
Have you ever heard of a data structure called Bitboard? I didn't know until I got involved with Procon (laughs) As many of you may have guessed from the name, Bitboard is a data structure that speeds up processing by expressing the board surface as Bit, that is, ** 0 and 1 binary numbers **. In the following, I will introduce it with concrete examples.
To express the board in binary
As mentioned in the title of this article, I will use Othello as an example throughout this article.
How do you usually express the board when writing an Othello program?
When I think of it at a glance, I think that there are many things that are expressed by substituting numbers etc. for the state that Kuroishi, Shiraishi, and not placed in the two-dimensional array of the size of the board like this.
In Bitboard, the place where the stone is placed is 1 and the place where the stone is not placed is 0, and it is expressed in binary. The size of the board is 8x8, that is, there are 64 squares, so you can see that it can be expressed in 64 bits. Also, since it is not possible to distinguish between Shiroishi and Kuroishi in binary numbers, ** the state of the board of Shiroishi and the state of the board of Kuroishi are retained **. It looks like this in the figure.
Speaking of simple, it is simple, but please be careful as it will be very difficult to understand if you drop it in the program.
About the operation of the board
Now let's actually operate the board.
In Bitboard, unlike arrays, the board is represented by binary numbers, so logical operations such as AND and OR and bit shifts that shift bits can be performed. Bitboard operates the board by making full use of this logical operation and bit shift.
Think of the board coordinates as ** 0 start **. From here, it's a little difficult to make a figure, so I will express the board with letters lol
Put a stone
The procedure for "putting a stone" is quite simple. Let's put it in the place of (5, 3). By the way, the expression is (x, y). First, prepare a variable in which the upper 1 bit is 1 and the remaining 63 bits are 0.
1000000000000000...0000000
Let's divide this into 8 bits and display it with a line break.
10000000
00000000
00000000
00000000
00000000
00000000
00000000
00000000
It looks like this. This is the board that was represented in the figure earlier.
Now, bit shift to the cell where you want to place it, and move 1.
The number to be shifted at this time can be calculated by y × 8 + x. In this example, the bit is shifted 3 × 8 + 5 = 29 times.
Then, it will be in the following state. You can see that the location has been moved correctly.
00000000
00000000
00000000
00000100
00000000
00000000
00000000
00000000
After that, you can add it by ORing the board surface of the color you want to place the board surface with the bit standing in this place you want to place.
00000000 00000000 00000000
00000000 00000000 00000000
00000000 00000000 00000000
00000100 OR 00010000 = 00010100
00000000 00001000 00001000
00000000 00000000 00000000
00000000 00000000 00000000
00000000 00000000 00000000
List the places where you can put it
This is an important process in Othello. The process is a little complicated. Let's take the process of enumerating the places where the initial state can be placed as an example.
Before explaining the specific processing, I would like to introduce a mask that shows the edge of the board.
horizontal mask vertical mask allside mask
01111110 00000000 00000000
01111110 11111111 01111110
01111110 11111111 01111110
01111110 11111111 01111110
01111110 11111111 01111110
01111110 11111111 01111110
01111110 11111111 01111110
01111110 00000000 00000000
Since the board is a binary number, the program does not know where the edge of the board is. ** (In this article, the binary number is broken by the size of the board to make it easier to understand) Therefore, the problem is solved by using the above mask that shows the edge of the board.
Now, let's get into the explanation of specific processing. In this example, I will list some places that can be placed in the initial state. First, prepare the board in the initial state.
player board enemy board
00000000 00000000
00000000 00000000
00000000 00000000
00010000 00001000
00001000 00010000
00000000 00000000
00000000 00000000
00000000 00000000
Next, AND the horizontal mask to the enemy board and apply the mask.
enemy board horizontal mask masked board
00000000 01111110 00000000
00000000 01111110 00000000
00000000 01111110 00000000
00001000 AND 01111110 = 00001000
00010000 01111110 00010000
00000000 01111110 00000000
00000000 01111110 00000000
00000000 01111110 00000000
Then bit shift the player board to the left and AND it with the masked board to see if there are any stones that can be turned over.
player board masked board tmp
00000000 00000000 00000000
00000000 00000000 00000000
00000000 00000000 00000000
00100000 AND 00001000 = 00000000
00010000 00010000 00010000
00000000 00000000 00000000
00000000 00000000 00000000
00000000 00000000 00000000
By performing this above processing, the bit will be set only at the location of the enemy stone adjacent to the player's stone. In other words, the bit stands only in the place of the stone that can be turned over.
From now on, tmp is bit-shifted and ANDed with masked board, and tmp before bit-shifting is ORed and updated.
Do this 6 times, which is the maximum number that can be flipped (maximum when placed on the edge).
tmp masked board tmp
00000000 00000000 00000000
00000000 00000000 00000000
00000000 00000000 00000000
00000000 AND 00001000 OR= 00000000
00100000 00010000 00010000
00000000 00000000 00000000
00000000 00000000 00000000
00000000 00000000 00000000
The final result is as follows. In this state, ** only the stones that can be flipped to the left of the player's stones are listed **.
tmp
00000000
00000000
00000000
00000000
00010000
00000000
00000000
00000000
I will keep the bit standing only in the place where it can be placed last.
First, OR the player board and enemy board to prepare the board on which both stones are placed.
player board enemy board current board
00000000 00000000 00000000
00000000 00000000 00000000
00000000 OR 00000000 = 00000000
00010000 00001000 00011000
00001000 00010000 00011000
00000000 00000000 00000000
00000000 00000000 00000000
00000000 00000000 00000000
Next, NOT current board to create a empty board in which bits are set only in places where no stones are placed on the current board.
current board empty board
00000000 11111111
00000000 11111111
00000000 NOT= 11111111
00011000 11100111
00011000 11100111
00000000 11111111
00000000 11111111
00000000 11111111
Bitshift tmp to the left and move it to the left of a stone that can be flipped over. This is the state where the bit stands only in the place where it can be pinched.
Then, by ANDing the empty board to the bit-shifted board surface, the state where the bit stands only in the place where the stone can be placed is completed.
tmp empty board legal board
00000000 11111111 00000000
00000000 11111111 00000000
00000000 11111111 00000000
00000000 AND 11100111 = 00000000
00100000 11100111 00100000
00000000 11111111 00000000
00000000 11111111 00000000
00000000 11111111 00000000
Doing this in all eight directions completes the enumeration.
Use horizontal mask for left and right, vertical mask for top and bottom, and allside mask for diagonal.
The process of turning over
Next is the process of turning over.
First, prepare a board with bits standing only where you want to place the stone. In the example, it is assumed to be placed at (5,3).
puted mask
00000000
00000000
00000000
00000100
00000000
00000000
00000000
00000000
Next, shift it 1 bit to the left and AND it with horizontal mask.
puted mask horizontal mask tmp
00000000 01111110 00000000
00000000 01111110 00000000
00000000 01111110 00000000
00001000 AND 01111110 = 00001000
00000000 01111110 00000000
00000000 01111110 00000000
00000000 01111110 00000000
00000000 01111110 00000000
AND the enemy board to tmp.
tmp empty board reverse tmp
00000000 00000000 00000000
00000000 00000000 00000000
00000000 00000000 00000000
00001000 AND 00001000 = 00001000
00000000 00010000 00000000
00000000 00000000 00000000
00000000 00000000 00000000
00000000 00000000 00000000
After that, tmp is further bit-shifted, ANDed with empty board, and the process of ORing the result to reverse tmp and updating is repeated until tmp AND empty board becomes 0. When tmp AND empty board becomes 0, it means that there are no more consecutive enemy stones.
AND player board and tmp at the timing when the iteration process is finally exited.
player board tmp reverse tmp
00000000 00000000 00000000
00000000 00000000 00000000
00000000 00000000 00000000
00010000 AND 00010000 = 00010000
00001000 00000000 00000000
00000000 00000000 00000000
00000000 00000000 00000000
00000000 00000000 00000000
If this result is other than 0, it means that the enemy stone is sandwiched between your own stones, so it is confirmed as the final upside-down stone. This time it is other than 0, so OR reverse to update and confirm. reverse is a variable whose bits are set only where it can be turned over.
reverse tmp reverse
00000000 00000000
00000000 00000000
00000000 00000000
00010000 OR= 00010000
00000000 00000000
00000000 00000000
00000000 00000000
00000000 00000000
When you finish in one direction, do it in the other direction.
Once this reverse part is created, it can be turned over with only the following logical operations. ^ means NOT and | means OR.
player board ^= puted mask | reverse
enemy board ^= reverse
That is all for the explanation. In addition to this, there are other things such as path processing and checking whether it can be placed, but it can be implemented by applying the processing introduced so far.
Practice
From here, I will introduce what I actually put into the program. The implementation itself is written in Swift, which I'm relatively familiar with, but if you want speed, I think it's best to write it in C ++, which can be accelerated by using AVX. When I actually tried to use it in a competition pro, I wrote it in C ++.
Put a stone
func put(x: String, y: String) {
guard let xInt = Int(x) else { return }
guard let yInt = Int(y) else { return }
var putedMask: UInt64 = 0x8000000000000000
putedMask = putedMask >> xInt
putedMask = putedMask >> (yInt * 8)
if isCanPut(putedMask: putedMask) {
doReverse(putedMask: putedMask)
nextTurn()
if shouldPass {
print("Passed because there is no space to put")
nextTurn()
}
} else {
print("(" + x + ", " + y + ")Cannot be placed in")
}
}
List the places where you can put it
//List and return the places that can be placed in 8 directions
func makeLegalBoard(playerBoard: UInt64, enemyBoard: UInt64) -> UInt64 {
var legalBoard = getCanPutPoint(mask: verticalMask, playerBoard: playerBoard, enemyBoard: enemyBoard, direction: .TOP)
legalBoard |= getCanPutPoint(mask: allSideMask, playerBoard: playerBoard, enemyBoard: enemyBoard, direction: .TOP_RIGHT)
legalBoard |= getCanPutPoint(mask: verticalMask, playerBoard: playerBoard, enemyBoard: enemyBoard, direction: .RIGHT)
legalBoard |= getCanPutPoint(mask: allSideMask, playerBoard: playerBoard, enemyBoard: enemyBoard, direction: .BOTTOM_RIGHT)
legalBoard |= getCanPutPoint(mask: verticalMask, playerBoard: playerBoard, enemyBoard: enemyBoard, direction: .BOTTOM)
legalBoard |= getCanPutPoint(mask: allSideMask, playerBoard: playerBoard, enemyBoard: enemyBoard, direction: .BOTTOM_LEFT)
legalBoard |= getCanPutPoint(mask: horizontalMask, playerBoard: playerBoard, enemyBoard: enemyBoard, direction: .LEFT)
legalBoard |= getCanPutPoint(mask: allSideMask, playerBoard: playerBoard, enemyBoard: enemyBoard, direction: .TOP_LEFT)
return legalBoard
}
//Return the board with the bit standing in the direction where it can be placed
func getCanPutPoint(mask: UInt64, playerBoard: UInt64, enemyBoard: UInt64, direction: DIRECTION) -> UInt64 {
let masked = mask & enemyBoard
var tmp: UInt64 = masked & getStridedBoard(target: playerBoard, direction: direction)
for _ in 0..<5 {
tmp |= masked & getStridedBoard(target: tmp, direction: direction)
}
return ~(playerBoard | enemyBoard) & getStridedBoard(target: tmp, direction: direction)
}
//Bit shift the target in the direction of direction
func getStridedBoard(target: UInt64, direction: DIRECTION) -> UInt64 {
return direction.stride.isNegativeNumber ? target << direction.stride.absValue : target >> direction.stride.absValue
}
The process of turning over
//The process of actually turning over
func doReverse(putedMask: UInt64) {
var reversed: UInt64 = 0
for i in 0..<8 {
var revTmp: UInt64 = 0
var tmp: UInt64 = moveTo(target: putedMask, direction: DIRECTION(rawValue: i)!)
while (tmp != 0) && ((tmp & enemyCell) != 0) {
revTmp |= tmp
tmp = moveTo(target: tmp, direction: DIRECTION(rawValue: i)!)
}
if (tmp & playerCell) != 0 {
reversed |= revTmp
}
}
playerCell ^= putedMask | reversed
enemyCell ^= reversed
}
//Move the target in the DIRECTION direction and then mask it
func moveTo(target: UInt64, direction: DIRECTION) -> UInt64 {
let stridedBoard = getStridedBoard(target: target, direction: direction)
return stridedBoard & direction.sideMask.rawValue
}
At the end
How was that? I did not compare the performance with the normal implementation this time, but I feel that it seems to be faster lol
I think the advantage of using Bit is that it can be obtained in parallel **. In Othello, the process of enumerating the places where you can put it can be obtained for all stones at the same time using Bitboard, but not so with arrays.
When I was actually writing the program in Procon, it was a camp game, but when I tried to express it in Bitboard, the processing speed became about 100 times faster lol (Processing after optimizing with AVX in C ++) Speed) I remember being a little impressed at that time.
This time I remembered that impression a little, so I wrote it. There is something called Magic Bitboard as an evolution of Bitboard. It may be interesting to look it up.
That is all. Thank you for browsing.