木を用いた記述

経路の一意性

与えられた初期状態から帰結を一意に決めるための規則は，以上で十分である。しかし，帰結は配列として定めているのであり，また，状態に対しての帰結を定めているだけなので，帰結までの過程については何も言っていない。例えば，\(B\) の都市が一つも残っておらず \(A\) には二つの都市が残っている状態からは， \(B\) の攻撃により \(A\) の都市すべてが消去されるという帰結が確定している。しかし，\(B\) は一度に二つの都市を消去するだけでなく，\(A\) のパスを間に挟んで，１つずつ消去することもできる。重要なのは帰結でそこへの経路ではないのだが，このような一意性の欠如は，最大値選択の一意性の欠如を引き起こす。

一意性条件を課さない場合の最大値選択の問題は，帰結が異なるという「不都合な事実」を引き起こしたのだが，この場合の最大値選択は，帰結までの道のりに影響するだけなので，「任意の最大値を選ぶ」で片付けてしまうこともできる。しかし，解としてなにを求めているのか，という観点を明確にするために，このゲームに対しての木を定義して，その枝を刈り込んでいくという形の言い換えをしておく。

ゲームの木の定義

初期状態を根(root)とする木(tree) を定める：初期状態において選択し得る（パスも含めての）すべての行動のそれぞれを，根から伸びる枝(edge) として（根を始点とする枝として），その行動の結果の状態を新たな節点(vertex, node)として書き加え，つまり，枝と，枝の伸びる先の点（枝の終点）を節点として書き加え，さらに，その節点から新たな枝と節点を追加していく，という操作を繰り返し，初期状態から選択しうるすべての可能な状況を網羅した木（tree）を作ることができる。正確には，木の節点は単なる点であり，枝は点と点を結ぶ矢印であり，節点には状態がラベルとして付随し，また，枝には攻撃やパスを表すラベルが付随していると考える。異なる節点に同じ状態が付随している可能性もある。節点の状態（節点に付随した状態）が終了条件を満たしているならば，そこから伸びる枝はなく，その節点は木の葉(leaf) となる。パスの回数が \(p\) に制限されているので，こうして定められる木は，\(j=p\) の状態を葉とする有限木である。正確には，\(j=p\) である状態が付随した節点を葉とする有限木，と言うべきだが，以下，意味が通じそうな場合は簡単な言い方で済ます。

根以外の節点 \(v\) に対して，節点 \(v\) を終点とする枝が１つだけ存在する。この枝の始点を，\(v\) の直前の節点と言うことにする。任意の節点から，直前の節点を辿りながら遡ることにより，根からその節点までの経路が一意に定まる。ひとつの節点に対して，その節点を始点とする枝が存在するならば，その枝の終点を直後の節点と言うことにする。

木の任意の節点 \(v\) から始めて，それを始点とする枝と終点を付け加える操作を繰り返すことにより，\(v\) を根とする部分木を考えることができる。ただし，部分木の根は， \(j=0\) の状態に限定されないことに注意。

ゲームを木として記述しても，状態の変化として記述しても，実質的には変わりはない。ただし，根から始めて［初期状態から始めて］節を作っていくときに［それが変化した状態を作っていくときに］，同じ状態が付随する節が現れても，それらを「合流」して一つの節点にすることはしない。この「合流させない」ということにより，節から節への経路は（それが存在する場合には）一意に決まる，という利点を利用できることになる。

再帰的定義

節点に対しての帰結を再帰的に定義することになるのだが，最大値をとる枝を選ぶのではなく，それ以外の枝を刈り込んでしまうという方針をとる：

葉に対しては，帰結はそれ自身で，最終的価値関数はその葉の配列の価値関数として定める
ある節点 \(v\) の直後の節点すべてに対して帰結と最終的価値関数が定められているならば，\(v\) での状態における手番のプレーヤー \(C\) から見て，最終的価値関数が最大とならない直後の節点 \(v'\) については，\(v'\) を根とする部分木と \(v\) から \(v'\) への枝を刈り取ってしまう。
この刈り取りを行った結果として得られる \(v\) を根とする部分木の葉には，一意性条件により，すべて同じ配列が付随していることが保証されるので，この部分木を，\(v\) の帰結として定める。\(v\) での最終的価値関数は，この配列の価値関数として定める。
以上の再帰的手続きを根まで続けることにより得られる「刈り込みの修了した木」を，このゲームの解と言うことにする。

ゲームの解（である木）の葉を，帰結と呼ぶことにする。帰結（である節）に付随する配列は，いずれも，最初に定義した帰結（配列として定義された帰結）に等しい。根から葉までの経路を，合理的経路，もしくは，ゲームの合理的展開，と呼ぶことにする。

以上，ゲームの解析の目的は，

（配列としての）帰結，最終的価値関数，及び，すべての（葉としての）帰結までの合理的経路を求めること

とする。

多くの場合，複数の合理的経路があったとしても，それらは「廻り道」によるものに過ぎないので，例えば最短の経路であることを要求するなどにより，合理的経路を一つだけ求めるのみで解析を終わっても良いことにする。