ゲーム木（ゲームき、）は、組合せゲーム理論において、ゲームの盤面を有向グラフのノードで、手をエッジで表したものである。完全ゲーム木とは、ゲームの最初から指せる全ての手を含んだゲーム木である。なお、組合せゲーム理論ではない通常のゲーム理論の「ゲームの木」については展開型ゲームを参照。右図は、三目並べのゲーム木の最初の2レベル（あるいは2手）までを示したものである。ここでは、盤面を回転させたり反転させて同じになるものは等価としているため、最初の1手は3種類（中心、角、角と角の間）しかない。2手目は、1手目が中心の場合は2種類、そうでない場合は5種類ある。完全ゲーム木の葉ノードの数をゲーム木複雑性()と呼び、そのゲームが最終的にどれだけの異なる盤面で終わるかを示している。三目並べのゲーム木複雑性は 26,830 である。ゲーム木は人工知能で重要であり、最良の手はゲーム木を探索することで得られ、ミニマックス法などのアルゴリズムを使用する。三目並べのゲーム木は小さいので探索も容易だが、チェスなどの完全ゲーム木は大きすぎて全体を探索することができない。その場合は代わりに部分ゲーム木を使う。部分ゲーム木は、一般に現在の盤面から指せる手を時間内に探索できるぶんだけ含んだものである。2人で対戦するゲームはAND/OR木で表現することもできる。先手が勝つには、後手がどういう手を指しても先手が勝つ手が存在しなければならない。これをAND/OR木では、先手の指せる手を論理和で表し、後手のさせる手を論理積で表す。完全ゲーム木があれば、ゲームを解くことができる。つまり、その解に従って打っていけば、負けないことを保証できる。そのアルゴリズムは再帰的に以下のように説明できる。右図は、上記のアルゴリズムに従って色分けしたあるゲームのゲーム木を示したものである。

出典:wikipedia