Implement reversi with BitBoard. This time we will implement the inversion process. (For the sake of simplicity, we will use a 4x4 example, but the implementation is 8x8. W: Shiraishi, B: Kuroishi, x: No stone.)
xxxx
xWBx
xBWx
xxxx
Kuroishi is placed on this board in BitBoard
0000
0010
0100
0000
And the arrangement of Shiroishi
0000
0100
0010
0000
It is represented by two bit strings of.
Black turn start move
:
0000
0000
0001
0000
In contrast to the flipped stone placement flipped
:
0000
0000
0010
0000
When you ask, the inversion process of the white number is ʻopponent_board ^ = flipped` In other words, the arrangement of Shiroishi is
0000 0000 0000
0100 ^ 0000 = 0100
0010 0010 0000
0000 0000 0000
Also, the arrangement of Kuroishiself_board ^= flipped | move
Orself_board |= flippled | move
Obtained from.
0000 0000 0000
0010 ^ 0000 = 0010
0100 0011 0111
0000 0000 0000
From now on, we will focus on finding the inverted Shiraishi flipped
.
The flipping Shiraishi is always in one of the eight directions diagonally up, down, left, and right of the start move
. First, let's start with a search to the left.
Inversion to the left corresponds to one of the following two patterns.
BWo
BWWo
(W: Shiraishi, B: Kuroishi, o: Kuroishi start, respectively.)
Shift the start move
to the left to get the white number placement and product. You get flipped
by shifting the result further to the left and taking the product with the white number placement. (In 8x8, a total of 6 shifts will give you flipped
.) However, you need to make sure that there is a white stone that can be flipped to the left before the operation. This is the same as How to find a legal hand.
class Board:
BLACK, WHITE = True, False
def __init__(self, black=0x000008100000, white=0x000010080000):
self.board = {Board.BLACK: black, Board.WHITE: white}
def flipped(self, player, move):
""" returns flipped stones """
flipped = 0b0
player_board = self.board[player]
opponent_board = self.board[not player]
blank_board = ~(player_board | opponent_board)
masked_opponent_board = opponent_board & 0x7e7e7e7e7e7e7e7e
#Make sure there is a white stone that can be flipped to the left
temp = player_board << 1 & masked_opponent_board
temp |= temp << 1 & masked_opponent_board
temp |= temp << 1 & masked_opponent_board
temp |= temp << 1 & masked_opponent_board
temp |= temp << 1 & masked_opponent_board
temp |= temp << 1 & masked_opponent_board
legal_moves = temp << 1 & blank_board
# move & legal_moves will be move or 0b0
temp = (move & legal_moves) >> 1 & opponent_board
temp |= temp >> 1 & opponent_board
temp |= temp >> 1 & opponent_board
temp |= temp >> 1 & opponent_board
temp |= temp >> 1 & opponent_board
temp |= temp >> 1 & opponent_board
flipped |= temp
return flipped
Recommended Posts