Loading article…
組み合わせゲーム理論の文脈において、ゲームツリーとは、完全情報を持つ逐次ゲームにおけるすべての可能なゲーム状態を表すグラフのことである。そのようなゲームには、チェス、チェッカー、囲碁、三目並べなどがある。
ゲームツリーは、ゲームの展開のあらゆる可能性を表すため、ゲームの複雑さを測る指標として利用できます。チェスのような複雑なゲームではゲームツリーが非常に大きくなるため、この種のゲームをプレイするために設計されたアルゴリズムでは部分的なゲームツリーを使用します。これにより、現代のコンピュータでの計算が可能になります。ゲームツリーを解くための方法は様々です。完全なゲームツリーを生成できる場合は、後方帰納法や逆行解析などの決定論的アルゴリズムを使用できます。完全なゲームツリーが生成できない場合は、ランダム化アルゴリズムやMCTSなどのミニマックスアルゴリズムを使用できます。
ゲームツリーをよりよく理解するために、ゲームツリーは、プレイヤーがゲームに勝つために取る行動を決定する、敵対的なゲームを分析する手法と考えることができます。ゲーム理論では、ゲームツリーは、ノードがゲーム内の位置（たとえば、ボードゲームの駒の配置）であり、エッジが動き（たとえば、ボード上の1つの位置から別の位置へ駒を移動すること）である有向グラフです。[ 1 ]
ゲームの完全なゲームツリーとは、初期位置から始まり、各位置から可能なすべての動きを含むゲームツリーのことです。完全なツリーは、展開形式のゲーム表現から得られるツリーと同じです。より具体的に言うと、完全なゲームはゲーム理論におけるゲームの規範です。これにより、多くの重要な側面を明確に表現できます。たとえば、利害関係者が取る可能性のある行動のシーケンス、各決定ポイントでの利害関係者の選択、各利害関係者が決定を下すときに他の利害関係者が取る行動に関する情報、およびすべての可能なゲーム結果の利益などです。[ 2 ]
完全なゲームツリーにおける葉ノードの数は、そのゲームをプレイできる可能性のある異なる方法の数を表します。例えば、三目並べのゲームツリーには255,168個の葉ノードがあります。
ゲームツリーは人工知能において重要です。なぜなら、ゲームで最善の手を選ぶ方法の1つは、多数のツリー探索アルゴリズムのいずれかを使用してゲームツリーを探索し、ミニマックスのようなルールを組み合わせてツリーを剪定することだからです。三目並べのゲームツリーは簡単に探索できますが、チェスのようなより大きなゲームの完全なゲームツリーは大きすぎて探索できません。代わりに、チェスをプレイするプログラムは部分的なゲームツリーを探索します。これは通常、利用可能な時間で探索できる現在の局面からできるだけ多くのプライを探索します。「病的な」ゲームツリー[ 3 ]（実際には非常にまれなようです）の場合を除いて、探索深度（つまり、探索するプライの数）を増やすと、一般的に最善の手を選ぶ可能性が高くなります。
2人対戦ゲームは、AND-ORツリーとして表現することもできます。最初のプレイヤーがゲームに勝つためには、2番目のプレイヤーのすべての手に対して、勝利となる手が存在しなければなりません。これは、AND-ORツリーにおいて、最初のプレイヤーの選択肢を論理和で表し、2番目のプレイヤーのすべての手を論理積で表すことで表現されます。
完全なゲームツリーがあれば、ゲームを「解決」することが可能です。つまり、先手または後手のどちらかが従うことができる一連の手を見つけることで、そのプレイヤーにとって最良の結果（通常は勝利または引き分け）が保証されます。決定論的アルゴリズム（一般に後方帰納法または逆行解析と呼ばれる）は、次のように再帰的に記述できます。
この図は、任意のゲームのゲームツリーを、上記のアルゴリズムを用いて色分けして示したものである。
通常、ゲームツリーのサブセットのみを使用してゲームを解くことが可能です（この技術的な意味での「解く」）。なぜなら、多くのゲームでは、同じプレイヤーにとってより良い別の手がある場合、その手を分析する必要がないからです（例えば、多くの決定論的ゲームではアルファベータ枝刈りを使用できます）。
ゲームを解くために使用できるサブツリーはすべて決定木として知られており、さまざまな形状の決定木のサイズはゲームの複雑さの尺度として使用されます。[ 4 ]
ランダム化アルゴリズムは、ゲームツリーの解決に利用できます。この実装方法には、速度と実用性という2つの大きな利点があります。決定論的なゲームツリー解決はO ( n )で実行できますが、ゲームツリーのすべてのノードの次数が2の場合、以下のランダム化アルゴリズムの期待実行時間はθ ( n 0.792 )となります。さらに、ランダム化アルゴリズムは「敵を出し抜く」ことができるため実用的です。つまり、解決順序がランダムであるため、対戦相手はゲームツリーの解決に使用されるアルゴリズムを知っていても、ゲームツリーのシステムに勝つことはできません。
以下はランダム化ゲームツリー解法アルゴリズムの実装例です。[ 5 ]
def gt_eval_rand ( u ) -> bool : """このノードが勝利と評価された場合は True を返し、そうでない場合は False を返します""" if u . leaf : return u . win else : random_children = ( gt_eval_rand ( child ) for child in random_order ( u . children )) if u . op == "OR" : return any ( random_children ) if u . op == "AND" : return all ( random_children )このアルゴリズムは「短絡」の考え方を利用しています。ルートノードが「OR」演算子とみなされる場合、1つのTrueが見つかると、ルートはTrueと分類されます。逆に、ルートノードが「 AND 」演算子とみなされる場合、1つのFalseが見つかると、ルートはFalseと分類されます。