オセロプログラムのアルゴリズム
オセロプログラムで最も重要な点は、やはり石を置いて相手の石をひっくり返す部分です。この解説ページでは、石が置けるかどうかの判定処理と、相手の石をひっくり返す処理に重点を置いて解説します。
なお、これはあくまで自作プログラムの解説です。自作プログラム以外のオセロが、以下の解説通りに実装されているとは限りませんので、ご注意ください。
１．石が置けるか判定する
石が置けるマスというのは、自分の石を置いた時に、相手の石を1つでもひっくり返せるマスのことを指します。
※当然、石がまだ置かれていないことも条件です。
Excelファイルでは、「judgeStone」プロシージャでこの判断をしています。
判定の大まかなアルゴリズムは以下の通り。
- 盤面内の各マスにおいて、とりあえず全て石が置けないものと考える。
- 該当マスに石が既に置かれていないか確認する。置かれていた場合はここで終了（石が置けない）。
- 該当マスから上下左右斜めの8方向を調べ、相手の石が並んでいる数をカウントする。
- 3の相手の石が並んでいる数が1以上 ＆ 並びの先に自分の石がある（＝相手の石が自分の石に挟まれている状況）、という方向が1つでもある場合、石が置けると判断する。それ以外は石が置けない。
- 判定結果を保管しておく（Excelファイルではセル[X4:AE11]。0 = 石が置けない、1 = 石が置ける）。
このアルゴリズムによって、石が置けるかの判定だけでなく、パスの判定もできます。
石が置けるマスが1つもない場合は、必然的にパスとなるためです。
２．相手の石をひっくり返す
相手の石をひっくり返す処理は、上記の石が置けるか判定する処理とほぼ同じです。
Excelファイルでは、「reverseStones」プロシージャでこの処理をしています。
石を置いたマスから上下左右斜めの8方向について、相手の石が並び、並びの先に自分の石があった場合に、並んでいる相手の石を自分の石に変えてしまえばよいです。
なお、ExcelファイルではVBAの都合により、相手の石が並んでいる数を調べてからその数の分だけ石を変えていますが、スタックやキューを利用した方がより効率的です。並んでいる相手の石の位置をスタック or キューに入れていき、並びの先に自分の石があった場合、スタック or キューから位置を取り出し、石を変えていけばOKです。
※スタック・キューについてはこちら。