More than 3 years have passed since last update.

BitBoard を利用してリバーシの反転処理を実装する

Python

Last updated at 2020-08-15Posted at 2020-08-15

リバーシを BitBoard で実装します。今回は反転処理を実装します。
（簡単のために 4x4 の例で説明しますが、実装は 8x8 です。W: 白石、B: 黒石、x: 石がない、をそれぞれ表します。）

xxxx
xWBx
xBWx
xxxx

この盤面を BitBoard では黒石の配置

と白石の配置

の二つの bit列で表現します。

黒番の着手 move :

に対して、反転する石の配置 flipped :

を求めると、白番の反転処理は opponent_board ^= flipped つまり白石の配置は

0000   0000   0000
0100 ^ 0000 = 0100
0010   0010   0000
0000   0000   0000

また黒石の配置は self_board ^= flipped | move または self_board |= flippled | move から得られます。

0000   0000   0000
0010 ^ 0000 = 0010
0100   0011   0111
0000   0000   0000

ここからは反転する白石flipped を求めることに注力します。
反転する白石は必ず、着手move の上下左右斜め8方向のいずれかにあります。そのうち、まず左方向の探索から考えます。
左方向の反転は以下の二つのパターンのいずれかに該当します。

BWo
BWWo

（W: 白石、B: 黒石、o: 黒番の着手、をそれぞれ表します。）

着手move を左にシフトして、白番の配置と積をとります。結果をさらに左にシフトして、白番の配置と積をとることで flipped を得ます。（8x8 では合計6回シフトすると flipped を得ます。）ただし、演算の前に左方向に反転できる白石があることを確かめておく必要があります。これは合法手を見つける方法と同じです。

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

        # 左方向に反転できる白石があることを確かめる
        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 は move か 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

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up