ゲーム木
ゲーム木（ゲームき、英: game tree）は、組合せゲーム理論において、ゲームの盤面を有向グラフのノードで、手をエッジで表したものである。完全ゲーム木とは、ゲームの最初から指せる全ての手を含んだゲーム木である。なお、組合せゲーム理論ではない通常のゲーム理論の「ゲームの木」については展開型ゲームを参照。
右図は、三目並べのゲーム木の最初の2レベル（あるいは2手）までを示したものである。ここでは、盤面を回転させたり反転させて同じになるものは等価としているため、最初の1手は3種類（中心、角、角と角の間）しかない。2手目は、1手目が中心の場合は2種類、そうでない場合は5種類ある。
完全ゲーム木の葉ノードの数をゲーム木複雑性(game-tree complexity)と呼び、そのゲームが最終的にどれだけの異なる盤面で終わるかを示している。三目並べのゲーム木複雑性は 26,830 である。
ゲーム木は人工知能で重要であり、最良の手はゲーム木を探索することで得られ、ミニマックス法などのアルゴリズムを使用する。三目並べのゲーム木は小さいので探索も容易だが、チェスなどの完全ゲーム木は大きすぎて全体を探索することができない。その場合は代わりに部分ゲーム木を使う。部分ゲーム木は、一般に現在の盤面から指せる手を時間内に探索できるぶんだけ含んだものである。
2人で対戦するゲームはAND/OR木で表現することもできる。先手が勝つには、後手がどういう手を指しても先手が勝つ手が存在しなければならない。これをAND/OR木では、先手の指せる手を論理和で表し、後手のさせる手を論理積で表す。
ゲーム木の解法
[編集]
完全ゲーム木があれば、ゲームを解くことができる。つまり、その解に従って打っていけば、負けないことを保証できる。そのアルゴリズムは再帰的に以下のように説明できる。
- 最終盤面でプレイヤー1が勝つ盤面とプレイヤー2が勝つ盤面を色分けし、引き分けになる盤面を第三の色にする。
- 1つ前の手（盤面）を見る。そのレベルの盤面になる手を自分の手とする。そのとき相手が勝つ盤面が子ノードとして1つでも存在する場合、このノードを相手の色に塗る。直下の子ノードの色が全て同じなら、このノードも同じ色に塗る。そうでない場合は引き分けの色に塗る。
- 以上を順次上に向かって繰り返し、全てのノードを色分けする。根ノードがどの色になるかで、このゲームの性質が決まる。
右図は、上記のアルゴリズムに従って色分けしたあるゲームのゲーム木を示したものである。
参考文献
[編集]- Hu, Te Chiang; Shing, Man-tak (2002年). Combinatorial Algorithms. Courier Dover Publications. ISBN 0486419622 2007年4月2日閲覧。
- Aske Plaat, Jonathan Schaeffer, Wim Pijls, and Arie de Bruin. Exploiting Graph Properties of Game Trees