4×4 オセロ完全解析【第1回】 | TECH PROjin

本稿では、データ構造にビットボードを用い、4×4サイズのオセロ[*1]の完全解析を行うためのアルゴリズムについて前中後編に分けて解説する。 *1 「オセロ」「Othello」は株式会社メガハウスの登録商標 「完全解析」とは、初期局面からゲームルールに従って到達可能な全局面を調査し、双方が常に最善手を打つと仮定して、それら全ての勝ち負けを決定することである。要するに、ゲームのすべてを調査しつくすということだ。 最初にビットボードというデータ構造について説明し、ついで、完全解析を行うためのアルゴリズムについて解説する。 なお、完全解析を行うプロジェクトは github（https://github.com/vivisuke/Othello4x4） で公開しているので、コード全体を読みたい・実際に実行して試してみたい人は参照されたい。 ビットボード 「ビットボード」とは、盤面の白石・黒石の状態を