W - Parity Game 解説
by
COOH2
このゲームでは石の個数が2個以上の未着手の山の数を2個から1個にした瞬間、そのプレイヤーが負けてしまいます。そのことに注意しながら考察すると、次の結果を得ます。
初期局面において石数が1個の山の総数を\(u\)とします。これらを除いた\(n-u\)山の状態についてまず考えます。
もし\(n-u = 0\)であれば石の個数が1個の山しかないため、互いにこれらの山から石を1個取りあって最終的に石がなくなります。したがって、Aliceの勝ちになります。
\(n-u = 1\)のときも、Aliceが最初に石が2個以上ある山から石をすべて取り去れば、\(n-u=0\)のときと同様の議論でAliceの勝ちになります。
\(n-u\ge 2\)の場合について考えてみましょう。このとき、石が2個以上ある山のうち、最小の2山を除いたすべての山の石の個数\(A_i\)に対して\(\left \lfloor \frac{A_i+1}{2} \right \rfloor\)の排他的論理和を取って、さらに\(u\)が奇数の場合はそれと1の排他的論理和を取ったものが、0であればBobに必勝戦略があり、0でなければAliceに必勝戦略があります。証明は次の通りです:
途中局面も含めた状態について考えます。
未着手かつ1個石のある山の数を2で割った余りを\(U\), 未着手かつ2個以上石のある各山の石の個数を\(A_1\le A_2 \le A_3 \le \cdots \le A_m\), 着手済みの山の石の個数を\(B_1, \ldots, B_k\)とします。ただし、\(m \ge 2\)とします。
石が0個の山に値0を、未着手で石が1個の山に値1を割り当て、未着手で石が2個以上のそれぞれの山について、値\(\left \lfloor \frac{A_i+1}{2} \right \rfloor\)を割り当て、着手済みのそれぞれの山について、値 \(\left \lfloor \frac{B_i}{2} \right \rfloor \)を割り当てると、各山から石を取る着手は、元の値から1以上値を下げることになり、かつ元の値より小さく0以上の任意の値について、その値を持つ山に変えることができるため、ニムと同様の性質がいくつか使えることに注意しておきます。また、未着手で石が1個の山すべてについて割り当てられた値の排他的論理和は、それが偶数なら0、奇数なら1なので、\(U\)に一致していることにも注意しておきます。
未着手かつ石の数が2個以上ある山が2個以上存在する任意の局面について、\(A_1\)と\(A_2\)を除いた\(\left \lfloor \frac{A_i+1}{2} \right \rfloor\)すべての排他的論理和、\(\left \lfloor \frac{B_i}{2} \right \rfloor \)すべての排他的論理和、および\(U\)を排他的論理和で足し合わせた結果、\(0\)になれば後手のプレイヤーに必勝戦略があり、そうでなければ先手に必勝戦略があることを石の総数に関する帰納法で示します。
帰納法の出発点として、未着手かつ石の数が2個以上ある山が1個しかない局面については、プレイヤーは直ちに、その山から石をすべてまたは1個残すように取ります。以降の手は石を偶数個取る手(もしくは石数1個の未着手の山から石を1個取る手)しかないので、終了局面の石数のパリティはこの時点で決定されますから、ここで適切に手を選べば必ず勝つことができます。
未着手かつ石の数が2個以上ある山が2個以上存在する任意の局面について考えます。まず、排他的論理和が0になっている局面からの着手について考察し、どう着手しても着手者の相手側に必勝戦略があることを確認します。
石数が1個の初期局面に着手すると、\(U\)のパリティが変化します。その結果として得られる局面は帰納法により着手者の相手側に必勝戦略があります。
既に着手済みの山に着手して値を減らした場合は、ニムと同様に、排他的論理和が0でなくなり、かつ未着手かつ石の数が2個以上ある山が2個以上残っているので、帰納法により着手者の相手側に必勝戦略があります。
石数が2個以上の未着手の山に着手した場合について考えます。もし、小さい方から数えて3番目以上の山に着手した場合は、ニムと同様に、排他的論理和が0でなくなり、かつ最小の2山の大きさは変わりませんので、未着手かつ石の数が2個以上ある山が2個以上残っています。よって帰納法により着手者の相手側に必勝戦略があります。
石数が2個以上の未着手の山のうち、1番目または2番目に小さい山から着手して石を\(b\)個にした場合が最も注意すべきですが、この場合についても、もともと3番目以上の山が存在した場合は、(着手の結果として3番目の山が小さい方から2番目の山になるので)3番目の山から石を取って\(b\)個にした場合と同様になり、やはり割り当てられた値の排他的論理和が0でなく、かつ未着手で石の数が2個以上ある山が2個以上残っていますので、帰納法により着手者の相手側に必勝戦略があります。3番目の山が存在しなかった場合は、着手の結果として石の数が2個以上の未着手の山の個数が1個になるため、帰納法の出発点より、着手者の相手側が勝てます。
一方、排他的論理和が0でないときは、いずれかの値を減らして排他的論理和を0にすることができます。着手の結果として、石の数が2個以上ある未着手の山の数が2個以上であるという状況が保たれますので、帰納法により、これで着手者が勝てます。
以上から、主張は示されました。
なお、不偏ゲームのように互いに同じ着手が可能であるものの、いずれのプレイヤーが最後の着手を行ったかではなく、このゲームのように終了局面の種類によって勝者を決めるゲームはEnding Partisanゲームと呼ばれ、数年前から日本で研究が行われだしています。
