ゲームの規則

ゲームの規則を完全に定める。

先手後手とバスの回数制限

ここまでの例では，どちらが先に攻撃をする権利を持つかは，重要ではなく，同じ最終状態に行き着く。しかし，一般には，先手か後手かで最終状態が異なる場合もあるので，プレーヤー $A$,$B$ のいずれかが先手で，交互に行動を選択するという規則を追加しよう。プレーヤーの可能な行動は，パスか攻撃であり，攻撃を選んだ場合には，相手の都市の個数（価値が零になっていない都市の個数）は，減少する。したがって，攻撃の回数は有限回に限られる（両者の都市の数の合計を越えることはない）。

しかし，パスは状態を変ないので，パスの回数に制限を設けないと，最終状態の定義が困難になる。そこで，ゲームの規則として，$2$ 以上の整数値 $p$ を設定して，パスが $p$ 回連続した場合には，ゲームは終了するということにする。

状態の推移

ゲームが進行している途中の時点での状態を定義する：

手番は $A$ なのか $B$ なのか：これを $C$ で表す。したがって， $C$ の値は $A$ もしくは $B$.
直前に連続しているパスの回数：これを $j$ で表す。初期状態（ゲーム開始時点）では $j=0$ であり，ゲーム終了時点では，ゲームの規則により $j = p$.　ゲームが終了していないならば， $j \leq p-1$ であり，どちらかが攻撃を選択すると， $j$ の値は $0$ にリセットされる。
その時点での，$A$ の都市の価値 $\vec{a} = (a_1,\ldots,a_m)$ と $B$ の都市の価値 $\vec{b}=(b_1,\ldots,b_n)$.

Remark. ここまで，両者の都市の個数は $m,n$ としてきたのだが，どちらかの都市の個数が少ないならば，初期状態において価値が零の都市を付け足して，$m=n$ としてしまうことができる。例えば， $$ m=2,\,n=3,\quad a_1 = 8,\,a_2 = 5,\,\,b_1 = 4,\,b_2 = 2,\,b_3 = 1$$ ならば，$m=3$ に変えた上で$a_3=0$ を付け加え， $$ \begin{pmatrix} \vec{a}\\ \vec{b} \end{pmatrix} = \begin{pmatrix} 8 & 5 & 0\\ 4 & 2 & 1 \end{pmatrix} $$ とすれば良い。

それぞれの時点で，

$\vec{a}$ を $A$ の配列， $\vec{b}$ を $B$ の配列
$S = \dbinom{\vec{a}}{\vec{b}} = {}^t(\vec{a},\vec{b}) $ を配列

と言うことにする。

手番 $C$, パスの回数 $j$, 及び配列 $S$ で決まる状態を，記号 $$ {}^{C}_{j}{S} $$ で表す。

状態は，その時点で $C$ が行動（攻撃，もしくは，パス）を選択したことにより，以下のように変化する：

$C$ の値が $A$ ならば $B$ に， $B$ ならば $A$ に変わる。
$C$ がパスを選んだ場合には， $j$ は $j+1$ に変わる： $$ {}^{A}_{j}{S} \stackrel{P}{\longrightarrow} {}^{B}_{j+1}{S},\quad {}^{B}_{j}{S} \stackrel{P}{\longrightarrow} {}^{A}_{j+1}{S}. $$
$C$ が攻撃を選んだ場合には， $j$ の値は $j=0$ にリセットされ，相手の配列が攻撃に従って変化する： $$ {}^{A}_{j}{S} \stackrel{A}{\longrightarrow} {}^{B}_{0}{S'},\quad {}^{B}_{j}{S} \stackrel{B}{\longrightarrow} {}^{A}_{0}{S''} $$

$j=p-1$ の状態で $C$ がパスを選んだ場合には，$j=p$ となりゲームは終了する。

帰結と最終的価値関数

状態 ${}^{C}_{j}{S}$ に対して，その状態からの帰結と，その状態の最終的価値関数の値を再帰的に定義する。 $A$, $B$ の最終的価値関数を，それぞれ，$\varphi^{fl}_A,\, \varphi^{fl}_B$ で表すことにする。

$j=p$ のときはゲームが終了しているので，
- その状態の帰結は，その時点での配列 $S$
- その状態での $A$, $B$ の最終的価値関数 $\varphi^{fl}_A, \varphi^{fl}_B$ の値は，配列 $S$ に対しての， $A$, $B$ の価値関数 $\varphi_A, \varphi_B$ の値
と定める。
その状態において， $C$ の選択しうる（パスも含めての）行動すべてに対して，その結果に対しての帰結と最終的価値関数が既に定まっているならば， $C$ は， $C$ の最終的価値関数の値が最大になる結果を選択する。このように $C$ が選択した結果の帰結と最終的価値関数 $\varphi^{fl}_A, \varphi^{fl}_B$ の値を，その状態からの帰結と $A,B$ それぞれの最終的価値関数として定める。

パスの連続回数に制限を与えているので，ゲームは必ず，有限回の行動（選択）で終了する。したがって，以上で，それぞれの（初期状態も含めての）状態からの帰結と $\varphi^{fl}_A, \varphi^{fl}_B$ の値が，再帰的評価により決定されることになる。

最大値の選択

以上の規則のみで，再帰的な記述が可能な言語を用いれば，$p$ の値，初期配列としての $S$, 及び先手後手としての $C$ の値を入力として，帰結と最終的価値関数を出力するプログラムを書くことができる。しかし，厳密には，規則が不足している。

例で説明するならば簡単なことで，初期状態における都市の個数が $m=n=4$ で， $A$ の配列が$$ (a_1,a_2,a_3,a_4) = (2,3,5,6) $$ の場合，プレーヤー $B$ が $a_1=2$ と $a_4=6$ を攻撃した場合の配列 $(0,3,5,0)$ と，$a_2=3$ と $a_3=5$ を攻撃した場合の配列 $(2,0,0,6)$ では，価値関数の値が等しくなってしまい，「どちらを選んでも同じ」ということになってしまう。これでは，再帰的手続きにおける「最終的価値関数の値が最大になるような結果を選択する」という定義がうまく機能せず，同じ値の場合の選択について，恣意的な選択をしなければならないはめになる。プログラムを書けば，意識的に，もしくは不注意で，複数の最大値からひとつを選び出す仕掛けを滑り込ませるだけのことであり，気にする必要はないのかも知れない。しかし，不十分な規則は，美観を損なう。

このような面倒な事態を避けるのは簡単なことで，都市の価値を表す数値として，ここまでの例のような整数値を指定することは避け，それなりの大きさの有効桁をもつ実数値を選んだおけば，都合の悪い一致が生じることは，まず無い。

しかし，「まず無い」で終わらせる訳にもいかないので，正式な追加の条件を述べておこう。この条件により，初期条件として許される配列を制限してしまう。

一意性条件： $\vec{a'},\, \vec{a''}$ は，それぞれ初期状態における $A$ の配列のいくつかの成分を $0$ に変えた配列であり，同様に，$\vec{b'},\, \vec{b''}$ は，$B$ の配列のいくつかの成分を $0$ に変えた配列であるとする。このとき，以下が成り立つ：

$$ \begin{gather} \sum \vec{a'} - k \sum \vec{b'} = \sum \vec{a''} - k \sum \vec{b''} &\mathrm{ ならば　 } \vec{a'} = \vec{a''},\, \vec{b'} = \vec{b''}.\\ \sum \vec{b'} - \ell \sum \vec{a'} = \sum \vec{b''} - \ell \sum \vec{a''} &\mathrm{ ならば　} \vec{a'} = \vec{a''},\, \vec{b'} = \vec{b''}. \end{gather} $$

配列の成分は有理数から選び，$k,\ell$ は無理数を選んでおけば，$\vec{b'} = \vec{b''} = \vec{0}$ の場合の条件： $$ \sum \vec{a'} = \sum \vec{a''} \mathrm{　ならば　} \vec{a'} = \vec{a''} $$ 及び， $\vec{a'} = \vec{a''} = \vec{0}$ の場合の条件を満たすだけで，一意性条件が満たされることが保証される。

実際には，$k,\ell$ は $0.2,0.3,0.8$ といった簡単な数値を選ぶことになる。建前としては，これらの数値に，$\sqrt{2} \times 10^{-50} $ が加えられている，とでも解釈しておけば良い。要するに，これからの「紙の上での解析」で，不等号のはずが等号になってしまうような失敗が生じなければ済むことであり，あまり気にする必要はない。