リバーシ(オセロと呼んではいけない時代は終わったのでしたでしょうか…。)を BitBoard で実装します。アイデア自体については、オセロをビットボードで実装する などの記事を参考にしてください。
xxxx
xWBx
xBWx
xxxx
(簡単のために 4x4 の例で説明しますが、実装は 8x8 です。W: 白石、B: 黒石、x: 石がない、をそれぞれ表します。)
この盤面を BitBoard では黒石の配置
0000
0010
0100
0000
と白石の配置
0000
0100
0010
0000
の二つの bit列で表現します。
今回は、合法手をすべて求める方法を考えます。
黒番の合法手は必ず、盤面のある黒石の上下左右斜め8方向のいずれかにあります。そのうち、まず左方向(つまり、盤面の黒石の左方向から白石を挟める手)の探索から考えます。
左方向の探索では、この盤面における黒番の合法手のひとつ
0000
1000
0000
0000
が求められるはずです。
まず、盤面の黒石の左隣に隣接する白石を求めます。これは、黒石の配置を 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 で実装したものが以下です。
```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
```