公平ゲームと P・N 位置

有限の公平ゲームとは、有限の有向非巡回グラフ $(V,\to)$（頂点を局面、$u\to v$ を $u$ から $v$ への手という）で、手番のプレイヤーは現在の局面 $u$ から手 $u\to v$ を 1 つ選んで局面を $v$ に動かし、手がないときは負けとするものをいう。局面 $u$ から出発する最長の道の長さ（辺の数）を $h(u)$ と書く（非巡回で有限なので有限）。$h$ についての再帰で、局面を次のように P 位置と N 位置に分ける：手がない局面と、すべての手が N 位置に向かう局面は P 位置、ある手が P 位置に向かう局面は N 位置。