ゲーム木

ゲーム木：ゲーム攻略の道標

組合せゲーム理論において、ゲームの進展を視覚的に捉える強力なツールとしてゲーム木があります。ゲーム木は、ゲームの各局面をノード（節点）、局面間の遷移（手）をエッジ（辺）で表した有向グラフです。全ての可能な手が含まれるゲーム木を完全ゲーム木と呼びます。

例えば、三目並べを考えましょう。ゲーム開始から考えうる全ての手と、それによって生じる全ての局面をノードとエッジで表現すると、複雑なゲーム木が構築できます。ただし、回転や反転で同じになる局面は同一視することで、ゲーム木のサイズを削減できます。

完全ゲーム木の葉ノードの数、すなわちゲームが最終的に到達しうる異なる局面の総数はゲーム木複雑性と呼ばれます。三目並べのゲーム木複雑性は26,830と比較的少ないですが、チェスなどでは途方もない数になります。

人工知能とゲーム木

ゲーム木は人工知能の分野で重要な役割を果たします。ゲームAIは、ゲーム木を探索することで最適な手を決定します。ミニマックス法などのアルゴリズムを用いて、将来の局面を予測し、自分の勝利確率を最大化する手を選択します。

三目並べ程度の規模であれば、完全ゲーム木を探索することで最適解を求めることができますが、チェスのような複雑なゲームでは完全ゲーム木の大きさは膨大で、現実的な時間内に探索することは不可能です。そのため、部分ゲーム木と呼ばれる、現在の局面から一定深さまで探索したゲーム木を用いるのが一般的です。部分ゲーム木は探索の深さや、探索アルゴリズムの効率化によって、現実的な計算時間で探索可能なサイズに調整されます。

AND/OR木と2人対戦ゲーム

2人対戦ゲームは、AND/OR木という特殊なゲーム木で表現することもできます。AND/OR木では、先手の選択肢を論理和（OR）、後手の選択肢を論理積（AND）で表現します。先手が勝利するには、後手がどのような手を選択しても、先手が勝利できる手が存在する必要があります。この条件をAND/OR木で表現することで、ゲームの勝敗を分析できます。

ゲーム木の解法

完全ゲーム木が得られれば、ゲームの最適解を得ることが可能です。これは、再帰的なアルゴリズムで実現できます。

1. まず、ゲームの最終局面を評価し、プレイヤー1の勝利、プレイヤー2の勝利、引き分けの3種類に分類します。
2. そこから遡って、一つ前の局面を評価します。自分の手番の局面では、もし相手が勝利する局面が一つでもあれば、その局面も相手の勝利に分類します。もし全ての子ノードが同じ結果であれば、その局面も同様の結果に分類し、そうでなければ引き分けに分類します。
3. この処理を根ノードまで繰り返し適用することで、ゲーム全体の勝敗を決定できます。根ノードの結果が、ゲーム全体の勝敗を示します。

この手法を用いることで、完全ゲーム木があれば、ゲームの性質（先手必勝、後手必勝、引き分け）を決定的に判定できます。ただし、現実的には完全ゲーム木を構築できるゲームは限定的です。

参考文献

Hu, Te Chiang; Shing, Man-tak (2002). Combinatorial Algorithms. Courier Dover Publications. ISBN 0486419622.
Aske Plaat, Jonathan Schaeffer, Wim Pijls, and Arie de Bruin. Exploiting Graph Properties of Game Trees

関連事項

展開型ゲーム
ミニマックス法
アルファ・ベータ法
木構造 (データ構造)

もう一度検索