ゲーム木 - Wikipediaゲーム木（ゲームき、英: game tree）は、組合せゲーム理論において、ゲームの盤面を有向グラフのノードで、手をエッジで表したものである。完全ゲーム木とは、ゲームの最初から指せる全ての手を含んだゲーム木である。なお、組合せゲーム理論ではない通常のゲーム理論の「ゲームの木」については展開型ゲームを参照。 三目並べの最初の2手のゲーム木 右図は、三目並べのゲーム木の最初の2レベル（あるいは2手）までを示したものである。ここでは、盤面を回転させたり反転させて同じになるものは等価としているため、最初の1手は3種類（中心、角、角と角の間）しかない。2手目は、1手目が中心の場合は2種類、そうでない場合は5種類ある。 完全ゲーム木の葉ノードの数をゲーム木複雑性(game-tree complexity)と呼び、そのゲームが最終的にどれだけの異なる盤面で終わるかを示している。三目並べのゲーム木複雑性は
