【Pythonで動くコード付き】ビットボードでオセロを作ってみた．
はじめに
最近NovocStudioというwebサービスでオセロAIを開発してみました。そのサービスでは「AI vs AI」しかできなかったので、ローカル上でオセロを作成し、AI対戦できるようにしてみました。ビットボードで作成するほうが高速化できるということだったので、PythonでPygameというライブラリを使用してそれらを実装しました。
ビットボードとは？
ビットボードは、ボードゲームの状態をビット列（0と1の並び）で表現する手法です。オセロのような2次元のボードゲームにおいて、各マスの状態を1ビットで表現することで、非常に効率的にゲームの状態を管理できます。
ビットボードのメリットは以下の通りです。
- メモリ効率: 通常の2次元配列よりも少ないメモリでボードの状態を保持できます。
- 計算速度: ビット演算（シフトやAND、ORなど）は高速で、ゲームの状態変更や合法手の探索などの処理を迅速に行えます。
通常のボードの表現
まず、オセロの通常のボード表現について説明します。一般的なオセロのボードは8×8の64マスで構成され、それぞれのマスには「黒」「白」「空白」のいずれかの状態が入ります。この状態を数値で表すと次のようになります。
- 黒の石:
1 - 白の石:
-1 - 空白:
0
この表現方法では、以下のような2次元配列でオセロの盤面を管理します。
disc = [
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, -1, 1, 0, 0, 0],
[0, 0, 0, 1, -1, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0]
]
この形式は直感的で扱いやすいですが、全ての操作において多くのループ処理が必要になるため、大規模な探索やシミュレーションを行う際には非効率です。
ビットボードでの表現
ビットボードでは、黒と白の状態をそれぞれ独立したビット列として管理します。オセロボードの各マスは、黒、白、または空白のいずれかですので、これをビットボードで表現する場合、黒と白を分けて管理する必要があります。
具体的には、以下のように「黒の石があるかどうか」を示すビットボードと、「白の石があるかどうか」を示すビットボードを用意します。たとえば、次のようなビット列で表現します。
-
black_disc_bit: 黒の石がある位置を1にするビットボード -
white_disc_bit: 白の石がある位置を1にするビットボード
黒と白の石の配置がビットボードとしてどのように表現されるかを示します。
# 盤面（ビットボード）の初期化
black_disc_bit: 0000000000000000000000000001001000100000000000000000000000000000
white_disc_bit: 0000000000000000000000000010010000100000000000000000000000000000
black_disc_bit = 0x0000000810000000 # 黒石(16進数で)
white_disc_bit = 0x0000001008000000 # 白石(16進数で)
合法手を探す
オセロのプレイ中、次に石を置ける場所（合法手）を探す処理はゲームの進行において非常に重要です。ビットボードを使うことで、この処理を効率的に実装できます。
ビットボードではビットシフトとマスク操作を組み合わせて、合法手を探します。
合法手とは？
まず合法手の考え方について具体的に説明します。
たとえば、自分が黒石で、以下のような盤面であったとします。
- - -
- - -
- 白 黒
この場合、黒石の２つ左に合法手がありますね。
これは、黒石の左側が白石で かつ その左側が空白だから合法手というわけです。
これをすべての盤面にある黒石で「左上、上、右上、左、右、左下、下、左下」それぞれの方向で確認していくと合法手が分かるわけです。
つまり、これをまとめると、以下のようなステップで合法手を獲得したことが分かります。各方向についても同様であるので、黒石の左側における場所があるかを確認する方法に絞って説明しています。
- 黒石の左側が白石かどうかを調べる
- 白石ではなくなった箇所から1つ左が空白かを調べる
ビットボードで合法手を表現（説明）
では、これをビットボードであらわすとどうなるでしょうか？
ここでも自分が黒石で、左側における場所があるかで説明していきます。
左側における場所があるかどうかは以下の手順で調べることができましたね。
- 黒石の左側が白石かどうかを調べる
- 白石ではなくなった箇所から1つ左が空白かを調べる
ではまず、1についてはどうすればよいのかということですが、分けて考えてみましょう。
- 黒石の左側 = 1ビット左にシフト
-
白石かどうか = 黒石の左側 & 白石のビットボード
で求まるというわけです。
2については簡単で、空白かどうかというのは以下のように表されますね。（~はnotという意味）
空白 = ~(黒石 または 白石)
これらを組み合わせればほとんど完成しそうなのですが、まだ1つ問題があります。
それは黒石が一番左端に存在するときです。例えば以下のような場合です。
- - 白
黒 - -
- - -
この場合、黒は置くことができませんが、黒を1ビット左にずらす = 現在白石が置かれているところとなってしまいます。
これではオセロが成り立ちませんのでビットマスクしてやるわけです。具体的には白石の右端にある石はすべて0にしてしまおうというわけです。つまり以下のような手順を踏むということです。
0 0 1 1 1 0 0 0 0
0 0 0 & 1 1 0 = 0 0 0
0 0 0 1 1 0 0 0 0
これらを全方向で行えば問題ないというわけですね。ビットマスクはどの方向に進むかによって変わってしまうので考えてみてください。具体的なコードは以下の通りです。
ビットボードで合法手を表現（コード）
def legal_bit(self, color):
"""石を置ける場所の取得(bit)"""
blank_bit, player_bit, opponent_bit = self.get_bit(color)
op_h_masked, op_v_masked, op_all_masked = self.get_op_masked_bit(opponent_bit)
# 各方向に対して合法手を探索
legal_bit = self.legal_l(player_bit, op_all_masked, blank_bit, 9) # 左上
legal_bit |= self.legal_l(player_bit, op_v_masked, blank_bit, 8) # 上
legal_bit |= self.legal_l(player_bit, op_all_masked, blank_bit, 7) # 右上
legal_bit |= self.legal_l(player_bit, op_h_masked, blank_bit, 1) # 左
legal_bit |= self.legal_r(player_bit, op_h_masked, blank_bit, 1) # 右
legal_bit |= self.legal_r(player_bit, op_all_masked, blank_bit, 7) # 左下
legal_bit |= self.legal_r(player_bit, op_v_masked, blank_bit, 8) # 下
legal_bit |= self.legal_r(player_bit, op_all_masked, blank_bit, 9) # 右下
return legal_bit
def legal_l(self, player_bit, op_masked_bit, blank_bit, shift):
"""左方向にシフトして合法手を探索"""
tmp = (player_bit << shift) & op_masked_bit
for _ in range(self.size - 3):
tmp |= (tmp << shift) & op_masked_bit
legal_bit = (tmp << shift) & blank_bit
return legal_bit
def legal_r(self, player_bit, op_masked_bit, blank_bit, shift):
"""右方向にシフトして合法手を探索"""
tmp = (player_bit >> shift) & op_masked_bit
for _ in range(self.size - 3):
tmp |= (tmp >> shift) & op_masked_bit
legal_bit = (tmp >> shift) & blank_bit
return legal_bit
def get_bit(self, color):
"""指定された色に応じてビットボードをセット"""
blank_bit = ~(self.black_disc_bit | self.white_disc_bit) # 空きマスのビットボード
if color == "black":
player_bit = self.black_disc_bit
opponent_bit = self.white_disc_bit
else:
player_bit = self.white_disc_bit
opponent_bit = self.black_disc_bit
return blank_bit, player_bit, opponent_bit
def get_op_masked_bit(self, opponent_bit):
"""端と端がプログラム上つながるので、maskを設定"""
horizontal_mask = 0x7e7e7e7e7e7e7e7e
vertical_mask = 0x00ffffffffffff00
allside_mask = 0x007e7e7e7e7e7e00
op_horizontal_masked = opponent_bit & horizontal_mask # 左右のマスク後
op_vertical_masked = opponent_bit & vertical_mask # 上下のマスク後
op_allside_masked = opponent_bit & allside_mask # 斜めのマスク後
return op_horizontal_masked, op_vertical_masked, op_allside_masked
ひっくり返せる石を探す
オセロでは、合法手を置くと、その手によって挟まれた相手の石がひっくり返ります。ビットボードを使ってひっくり返せる石の場所を探すことも効率的に行えます。
ひっくり返せる石とは？
ひっくり返せる石を探す方法も合法手を探す方法とほとんど同じです。
この操作は、以下の手順で実現できます。
- ビットシフトで移動: 置く石から特定方向にシフトさせて相手の石を確認します。
- 連続する相手の石を探す: そのシフトされた場所に相手の石が連続する限り、再度シフトを続けます。
- 自分の石に到達したら終了: 自分の石が連続する範囲を確認して、ひっくり返す石の位置を特定します。
具体的なコードは以下の通りです。
ひっくり返せる石を探す（コード）
def flippable_disc_bit(self, color, put_bit):
"""ひっくり返せる石を取得"""
_, player_bit, opponent_bit = self.get_bit(color)
op_h_masked, op_v_masked, op_all_masked = self.get_op_masked_bit(opponent_bit)
# 各方向に対してひっくり返る石を探索
flip_bit = self.flip_l(player_bit, op_all_masked, put_bit, 9) # 左上
flip_bit |= self.flip_l(player_bit, op_v_masked, put_bit, 8) # 上
flip_bit |= self.flip_l(player_bit, op_all_masked, put_bit, 7) # 右上
flip_bit |= self.flip_l(player_bit, op_h_masked, put_bit, 1) # 左
flip_bit |= self.flip_r(player_bit, op_h_masked, put_bit, 1) # 右
flip_bit |= self.flip_r(player_bit, op_all_masked, put_bit, 7) # 左下
flip_bit |= self.flip_r(player_bit, op_v_masked, put_bit, 8) # 下
flip_bit |= self.flip_r(player_bit, op_all_masked, put_bit, 9) # 右下
return flip_bit
def flip_l(self, player_bit, op_masked_bit, put_bit, shift):
"""左方向にシフトしてひっくり返せる石を探索"""
tmp = (put_bit << shift) & op_masked_bit
flip_bit = tmp
if flip_bit == 0:
return 0
for _ in range(self.size - 2):
tmp = tmp << shift
if tmp & op_masked_bit == 0: # 連続している相手の石はなくなった
break
else:
flip_bit |= tmp
if player_bit & tmp == 0: # 自分の石がないならば挟めていない
return 0
else:
return flip_bit
def flip_r(self, player_bit, op_masked_bit, put_bit, shift):
"""右方向にシフトしてひっくり返せる石を探索"""
tmp = (put_bit >> shift) & op_masked_bit
flip_bit = tmp
if flip_bit == 0:
return 0
for _ in range(self.size - 2):
tmp = tmp >> shift
if tmp & op_masked_bit == 0: # 連続している相手の石はなくなった
break
else:
flip_bit |= tmp
if player_bit & tmp == 0: # 自分の石がないならば挟めていない
return 0
else:
return flip_bit
def get_bit(self, color):
"""指定された色に応じてビットボードをセット"""
blank_bit = ~(self.black_disc_bit | self.white_disc_bit) # 空きマスのビットボード
if color == "black":
player_bit = self.black_disc_bit
opponent_bit = self.white_disc_bit
else:
player_bit = self.white_disc_bit
opponent_bit = self.black_disc_bit
return blank_bit, player_bit, opponent_bit
def get_op_masked_bit(self, opponent_bit):
"""端と端がプログラム上つながるので、maskを設定"""
horizontal_mask = 0x7e7e7e7e7e7e7e7e
vertical_mask = 0x00ffffffffffff00
allside_mask = 0x007e7e7e7e7e7e00
op_horizontal_masked = opponent_bit & horizontal_mask # 左右のマスク後
op_vertical_masked = opponent_bit & vertical_mask # 上下のマスク後
op_allside_masked = opponent_bit & allside_mask # 斜めのマスク後
return op_horizontal_masked, op_vertical_masked, op_allside_masked
石の数を求める
ゲーム終了時や戦略を評価する際には、ボード上の石の数を数える必要があります。ビットボードを用いた方法では、ビット列の1の数をカウントすることで効率的に石の数を求められます。これは分割統治法に基づいて行いました。
コードは以下の通りです。
以下の数を求める（コード）
def count_score(self, disc_bit):
"""石の数を数える"""
disc_bit = disc_bit - ((disc_bit >> 1) & 0x5555555555555555)
disc_bit = (disc_bit & 0x3333333333333333) + ((disc_bit >> 2) & 0x3333333333333333)
disc_bit = (disc_bit + (disc_bit >> 4)) & 0x0f0f0f0f0f0f0f0f
disc_bit = disc_bit + (disc_bit >> 8)
disc_bit = disc_bit + (disc_bit >> 16)
disc_bit = disc_bit + (disc_bit >> 32)
return disc_bit & 0x7f
この方法を用いることで、黒と白の石の数を迅速に取得し、ゲームの評価や次の一手の計算に役立てることができます。
以上が「Pythonで作るオセロビットボード」の概要です。ビットボードを利用することで、オセロのゲームAIの効率を大幅に向上させることができます。ビット操作は直感的ではないかもしれませんが、理解すると強力なツールとなるとわかりました。
UIを加えてGitHubに公開
これにプラスでUIを実施してGitHubに挙げているのでここに載せておきます。
参考になった資料
Discussion