巷に出ているビットボードでオセロの実装をするソースコードがマジで理解できず大変な思いをしているので、自分の理解のために図解してみます。今回は特に合法手の検出を解説します。
計算はこちらの記事のソースコードに準拠しています。
また、ボードとビットの対応については以下の画像を参照してください。
この配置にすることで、シフトの方向が直感的になります。
合法手の計算
以下のような盤面を考えます。
ここでの手番は黒なので、この盤面から黒が置ける場所を探していきます。
番兵を用意する
ここでは、石の右側を見ていくことにします。右側なので、元記事での「左右端の番兵」にあたる値を用います。
相手のボードと0x7e7e7e7e7e7e7e7eをAND演算した値を用いるのですが、この0x7e7e7e7e7e7e7e7eはボード上で見ると、以下のように左右端を除いた全てのマスにビットが立っています。
相手のボード(ここでは白)とAND演算をすると、以下のようになります。
基本的に、AND演算をして残った部分を足すという操作の繰り返しになります。
そのままではシフトしていくと反対側の左右から出てきてしまうことになりますが、左右の端が0であるこのボードを用意することで、端にたどり着いた値は必ず0とAND演算されて消滅することになり、結果としてループすることを防いでいます。
ここでは簡単のため『番兵ボード』と呼ぶことにします。
自分のボードをシフトする
冒頭で述べたボードのレイアウトの通りであれば、石の右側を探す場合には右シフトしていきます。
以下の画像では1ビット右にシフトしています。
先程用意した番兵ボードと重ねるとこのようになります。
AND演算を行ったあとのボードを一時変数に入れておきます。
以上の工程を、この1行で行っています。
tmp = 番兵ボード & (自分のボード >> 1)
同様の操作を5回繰り返し、一時変数にOR演算で加えていきます。
今回の盤面では、3回で一時変数の値が変化しなくなりました。
tmp |= 番兵ボード & (tmp >> 1)
空ボードと重ね合わせる
駒を置いていない部分のビットが立っている空ボードを用意します(実際のコードではシフト操作を行う前に用意します)。白と黒のボードをOR演算し、それを反転させることで作ることができます。
空ボード = ~(自分のボード | 相手のボード)
もう一回一時変数を右シフトして、空ボードとのAND演算を行い、合法手ボード変数に代入します。
画像右のように、現在の盤面と重ねて見ると、右側の合法手が全て現れていることがわかります。
合法手ボード = 空ボード & (tmp >> 1)
※既に他の方向を調べ、合法手ボードに何か値が入っている場合は、|=演算子でOR演算をしつつ代入します。
全ての方向に対して同じことを行う
当然合法手はすべての方向に現れる可能性があるので、あとの7方向に対しても同じようにシフトによる合法手検出を行います。各方向には当然別の番人がいます。
各方向においては、以下のようにシフトします。
- 左: 左に1ビット
- 右: 右に1ビット
- 上: 左に8ビット
- 下: 右に8ビット
- 右上: 左に7ビット
- 左上: 左に9ビット
- 右下: 右に9ビット
- 左下: 右に7ビット
まとめ
きちんと調べるまではイメージが湧かなかったのですが、実際に画像化することでどのような動作を行っているのかがなんとなくわかるようになりました。難しいからこそ、ただコピペせず何をやっているのかをきちんと理解した上で実装したいと思います。