プログラミング講座(36) ゲームの木

今回はゲームの木についてプログラミングしてみようと思います。参考資料は『思考ゲームプログラミング―オセロゲームのアルゴリズムと作成法 (アスキーブックス)』です。この本はオセロゲームのプログラミングについて書かれた本で、プログラミング言語にはC言語を使用しています。IBMのDeep Blueがチェスのチャンピオンを破った1997年より11年も前の1986年に発行された本です。

【図31 思考ゲームプログラミング】
ゲームの木とはゲーム開始の局面からすべての局面に通ずる手をグラフ化したものです。初手はA1からC3まで9局面あり、それぞれがルートノードからの1段目のノードになります。2手目が初手A1に対してB2からC3までの8局面あり、初手B1に対しても8局面というように、2段目のノードは計72局面になります。このように終局までをすべてつないでいきます。

【図32 ゲームの木】
ゲームにおいて次の手を考えるということは、ある局面（ノード）から分岐する次の局面（ノード）のどれを選ぶのが一番得かを考えることになります。これをゲーム木の探索と呼んでいます。
このような先読みのプログラムに取りかかる予行演習として、すべての局面を次々と表示するプログラムを作ってみましょう。疑似コードは次のようになります。
【リスト11 すべての局面を表示するプログラムの疑似コード】
Sub SearchNextCross ‘ 次の×
　For iY = 1 To 3
　　For iX = 1 To 3
　　　盤[iX][iY]が空なら
　　　　そこに×を打つ
　　　　終局でなければ
　　　　　SearchNextNought() ‘ 次の○
　　　　打った手を元に戻す
　　EndFor
　EndFor
lExitCross:
EndSub
この疑似コードは先手×の手を打つサブルーチンですが、後手○のサブルーチンも同様の形になります。お互いがお互いを再帰的に呼び出します。
（つづく）