プログラミング講座(38) ミニマックス法

ゲーム木の探索の結果、図34のように最終局面まで検索した結果、×が勝った場合を+1点、○が勝った場合を-1点、引き分けの場合を0点とした場合、×の手をマックスレベル、○の手をミニマムレベルと呼び、マックスレベルの場合はその次のミニマムレベルの手の中で一番大きい点数の手を、ミニマムレベルの場合はその下のマックスレベルの手の中で一番小さい点数の手を選ぶようにします。プログラムでは×をコンピュータ、○を人間としているが、×はもちろん、○も最善手を打つと仮定すると上記のようなアルゴリズムになります。

【図34 ミニマックス法】
このアルゴリズムはミニマックス法と呼ばれ、「情報理論」で知られるシャノンが1950年にチェスマシンに関する論文の中で発表しています。
このアルゴリズムにしたがって、作ったプログラムを LBW762-3 として「発行」しました。ミニマックス法で5レベル（5手先）まで探索しても実用的な時間で終わります。5手先まで読んでも結果が分からない場合は0点としました。参考書とした『思考ゲームプログラミング』では、min_level() と max_level() の2つのサブルーチンがお互いを再帰的に呼ぶようになっていましたが、発行したSmall Basicのプログラムでは、Player_MiniMax() というサブルーチンが×と○の両方の手番を実行できるようにしてあります。

【図35 MINIMAX vs HUMAN】
×○ゲームは最善を尽くせば引き分けになります。今回のプログラムは少なくとも引き分けに持ち込めるので最善の手が打てるようになっています。『思考ゲームプログラミング』にはオセロを強くするためのアルゴリズムが他にも紹介されていますが、×○ゲームならミニマックス法だけで十分のようです。
×○ゲームの作成はこれまでとし、次回からはまた別のプログラムにチャレンジしたいと思います。
（つづく）