○×ゲームの神の一手を導いてみた

小さい頃にノートの隅や地面で良く遊んだ○×ゲームを計算機で解いてみた。

○×ゲーム程度であれば、スクリプト言語を用いて、かつ枝刈りとかせずに終端までミニマックス法で全探索しても十分に解ける。ミニマックス法というのは、要するに負けない手を打てば勝てるという戦法で、○×ゲームのようなゲームではミニマックス法ですべての局面を調べることができれば、最善の一手が得られることが知られている。

○×ゲームは両者が最適な手を打てば引き分けとなる。先手に関しては一手目をどこに置いても、引き分けに持ち込むことができる。二手目以降からは、正しく受けないと負けてしまう。したがって、二手目を正しく受けれない可能性があるので、微妙に後手が不利かもしれない。

一手目が中の場合は、後手は隅で受ける必要がある。

初手が隅の場合は、中で受ける。

初手が、辺の場合は、隣の隅か中か対辺に打てばよい。

以下のPythonスクリプトを実行すると、先手後手双方が最善の一手を打ち合う

fjk@x240:~/works/ox-game$ ./oxgame.py 

   +---+---+---+
   |   |   |   | 
   +---+---+---+
   |   |   |   | 
   +---+---+---+
   |   |   |   | 
   +---+---+---+


   +---+---+---+
   |   |   |   | 
   +---+---+---+
   |   |   |   | 
   +---+---+---+
   |   | O |   | 
   +---+---+---+


   +---+---+---+
   |   |   |   | 
   +---+---+---+
   |   | X |   | 
   +---+---+---+
   |   | O |   | 
   +---+---+---+


   +---+---+---+
   | O |   |   | 
   +---+---+---+
   |   | X |   | 
   +---+---+---+
   |   | O |   | 
   +---+---+---+


   +---+---+---+
   | O |   |   | 
   +---+---+---+
   |   | X |   | 
   +---+---+---+
   | X | O |   | 
   +---+---+---+


   +---+---+---+
   | O |   | O | 
   +---+---+---+
   |   | X |   | 
   +---+---+---+
   | X | O |   | 
   +---+---+---+


   +---+---+---+
   | O | X | O | 
   +---+---+---+
   |   | X |   | 
   +---+---+---+
   | X | O |   | 
   +---+---+---+


   +---+---+---+
   | O | X | O | 
   +---+---+---+
   |   | X |   | 
   +---+---+---+
   | X | O | O | 
   +---+---+---+


   +---+---+---+
   | O | X | O | 
   +---+---+---+
   |   | X | X | 
   +---+---+---+
   | X | O | O | 
   +---+---+---+


   +---+---+---+
   | O | X | O | 
   +---+---+---+
   | O | X | X | 
   +---+---+---+
   | X | O | O | 
   +---+---+---+

特に結論とかはない。

---

ソースコード：