BitBoardを利用してリバーシの合法手を求める #Python

リバーシ（オセロと呼んではいけない時代は終わったのでしたでしょうか…。）を BitBoard で実装します。アイデア自体については、オセロをビットボードで実装するなどの記事を参考にしてください。

xxxx
xWBx
xBWx
xxxx

（簡単のために 4x4 の例で説明しますが、実装は 8x8 です。W: 白石、B: 黒石、x: 石がない、をそれぞれ表します。）
この盤面を BitBoard では黒石の配置

と白石の配置

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

今回は、合法手をすべて求める方法を考えます。
黒番の合法手は必ず、盤面のある黒石の上下左右斜め8方向のいずれかにあります。そのうち、まず左方向（つまり、盤面の黒石の左方向から白石を挟める手）の探索から考えます。

左方向の探索では、この盤面における黒番の合法手のひとつ

が求められるはずです。

まず、盤面の黒石の左隣に隣接する白石を求めます。これは、黒石の配置を 1 bit 左にシフトして、白石の配置との積を求めることと同じです。

0000   0000   0000
0100 & 0100 = 0100
1000   0010   0000
0000   0000   0000

さらに 1 bit 左にシフトすると、黒番の合法手を見つけることができますが、白石が連続する場合が考慮できていません。少し盤面を変えます。

xWWB
xWBB
xWBW
xBWB

まず、黒石の配置を 1 bit 左にシフトして、白石の配置との積をとります。ここまでは同じです。

0010   0110   0010
0110 & 0100 = 0100
0100   0101   0100
1010   0010   0010

黒石の左隣にある白石の、さらに左隣にある白石を求めます。つまり、これは、黒石の左隣にある白石の配置を 1 bit 左にシフトして、白石の配置との積を求めることと同じです。

0100   0110   0100
1000 & 0100 = 0000
1000   0101   0000
0100   0010   0000

結果として、黒石の左隣に連続している白石の配置

0010   0100   0110
0100 | 0000 = 0100
0100   0000   0100
0010   0000   0010

を求めることができます。4x4 では黒石の左隣に白石は二つしか隣接しないので、これ以上の演算は不要ですが、8x8 では計6回繰り返すことで、黒石の左隣に隣接する連続した白石をすべて求められます。

黒番の合法手はさらに 1 bit 左にシフトすることで見つけれます。ただし、その位置に石があり着手できない場合を取り除くため、石のない位置との積をとります。

1100   1000   1000
1000 & 1000 = 1000
1000   1000   1000
0100   1000   0000

黒番の合法手をすべて見つけることができました。

最後に、これまで無視していた左端の石の取り扱いを考えます。左端の石はひとつ上の段の右端の石と隣接していることになります。次の盤面を例に考えます。

WBxW
BWBx
WWBx
WBxx

左端の白石は左方向の探索ではひっくり返せない白石なので、あらかじめopponent_board から取り除きます。
また、左端の黒石が一つ上の段の右端の白石と隣接していると判定しないように、右端の白石もopponent_board から取り除きます。

1001   0110   0000
0100 & 0110 = 0100
1100   0110   0100
1000   0110   0000

上記を python で実装したものが以下です。

board.py

class Board:
    BLACK, WHITE = True, False

    def __init__(self, black=0x000010080000, white=0x000008100000):
        self.board = {Board.BLACK: black, Board.WHITE: white}

    def legal_moves(self, player):
        self_board = self.board[player]
        opponent_board = self.board[not player]
        blank_board = ~(self_board | opponent_board)
        opponent_board = opponent_board & 0x7e7e7e7e7e7e7e7e

        temp = self_board << 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

        temp = temp << 1 & blank_board

        return temp