グランディ数

Competitive Programming Advent Calendar 2016 - Adventarの12日の記事になります。

この記事では、競技プログラミングの問題にたまに出てくる、グランディ数についての解説記事です。解説と言いつつ、ひたすら自己流の証明を書きなぐった記事みたいになってしまったので、読みづらいかもしれません・・・。内容としてはグランディ数の基礎的な部分しか扱っていないので、知っている人は読む必要がないかもしれません。

グランディ数を知ると何ができる？

競技プログラミングでたまに見かける、2人で交互に行う系のゲームの勝敗判定を行う問題の解法によくグランディ数が使われます。実装自体はとても簡単なので、知らないと全くわからないが、知っていると超簡単になる傾向があります。なので知っていて損ではないと思います。グランディ数自体はとても面白いので、少し興味があれば知っておくといいと思います。

Nimゲームの必勝法

グランディ数の考え方の大元には、Nimゲームの必勝法が使われます。まずはじめにNimゲームの必勝法について見ていきましょう。Nimゲームとは、以下のようなゲームです（Wikipediaから引用）。

2人のプレイヤーがいくつかのコインの山からコインを取り合う。ゲームの目的は、最後のコインを取ることである。（コインの代わりに石や豆を使ってもよい）。

  • まず、コインの山を複数準備する。山の数や各山のコインの枚数は（プレイヤー同士で合意すれば）自由に決めてよい。
  • 2人のプレイヤーの順番は交互である。じゃんけん等で先手を決める。
  • 各々のプレイヤーは自分の順番のとき、コインの山を1つ選んでその山から1枚以上のコインを取り去る。（複数の山からコインを取ったり、コインを一枚も取らなかったりするのは反則である）。これが終わったら次のプレイヤーの手番になる。
  • すべての山のコインがなくなったとき、ゲームは終わりである。そして、最後のコイン（複数のときもある）を取ったときのプレイヤーが勝者である。
https://ja.wikipedia.org/wiki/%E3%83%8B%E3%83%A0

ここで、山の数をnとし、i番目の山のコインの枚数をs_iとします。このゲームの勝敗判定は、各山のコインの枚数の排他的論理和（XOR）で判定できます。

\displaystyle G(s) = s_1 \oplus \cdots \oplus s_n

G(s)の値から、この山の状態sからコインを取ろうとしているプレイヤーの勝敗がわかります。G(s) = 0のときは負け、それ以外のときは勝ちとなります。

ここまでは誰でもできます。人によっては常識レベルかもしれません。しかし、そもそもなぜこれで勝敗判定ができるのでしょうか？また、勝ちと判定された場合、プレイヤーはどのようにコインを取れば良いのでしょうか？

必勝法を考える

まず、シンプルなn = 2（山が2つ）の場合を考えましょう。1番目の山のコインの枚数がx、2番目の山のコインの枚数がy枚という状態を{x, y}と書くことにします。先程の勝敗判定の式から、{7, 8}は勝ち、{8, 8}は負けとなります。この場合には有名な必勝法があります。それは、2つの山のコインの枚数が同じになるようにコインを取るというものです。{7, 8}の場合で試すと、

{7, 8} -> {7, 7} -> {3, 7} -> {3, 3} -> {3, 0} -> {0, 0}

のように、絶対に先手が勝つことができます。この遷移の各状態に、先程の勝敗判定の式を適用してG(s)の値を計算してみましょう。

15 -> 0 -> 4 -> 0 -> 3 -> 0
(7 \oplus 8 = 15, \space 7 \oplus 7 = 0, \space 3 \oplus 7 = 4, \space 3 \oplus 3 = 0, \space 3 \oplus 0 = 3, \space 0 \oplus 0 = 0)

このように、0とそうでない数字が交互に並んでいます。つまり、必勝法というのは、相手にG(s) = 0の状態を与える手を選択し続けることなのです。G(s) = 0の状態からどのようにコインを取っても、必ず次の状態 s'は G(s') \ne 0となるので、負けの人は為す術がありません。

山が2つの時の必勝法がわかりましたが、実はこの必勝法は山の数がいくつでも成り立ちます。山が沢山ある場合でも、勝ちの人は常に相手の手番のG(s)の値が0となるようにコインを取ればよいのです。

必勝法が成り立つための2つの条件

ここまで当然のように書きましたが、2つの疑問が浮かび上がると思います。

  1. G(s) = 0である状態sの、任意の次の状態s'は必ずG(s') \ne 0となるのか？
  2. G(s) \ne 0である状態sからG(s') = 0である次の状態s'へ遷移できる手は必ず存在するのか？

1つ目は負けの人の手、2つ目は勝ちの人の手に関係します。そもそもこれが成り立たないと先程書いた必勝法は成り立ちません。それぞれ証明してみましょう。

G(s) = 0である状態sの、任意の次の状態s'は必ずG(s') \ne 0となるのことの証明

これは簡単です。1回の手では、s_1～s_nから1つを選んで、その値を1以上減らします。数字が変化している以上、1箇所以上のビットが変化しているはずです。ですので、G(s')の値は必ずG(s)の値と異なります。G(s) = 0ですので、G(s') \ne 0が成り立ちます。

G(s) \ne 0である状態sからG(s') = 0である次の状態s'へ遷移できる手は必ず存在することの証明

G(s)の値で1となっているビットのうち、最上位のものに着目します。これと同じ位置のビットが立っているs_iが存在するはずなので、そのうちの1つをs_kとします。この値を減らすことで、最上位のビットが1から0になり、かつそれ未満の位置に任意のビット列を含む数字に変化させことができます。このビット列を、G(s)の立っているビットを打ち消すように選択することにより、G(s') = 0とすることができます。

s = \{8, 6, 5\}の例を見てみましょう。わかりやすさのため、2進数表記で表します。

s_1 = 8_{(10)} = 1000_{(2)}
s_2 = 6_{(10)} = 0110_{(2)}
s_3 = 5_{(10)} = 0101_{(2)}
G(s) = 1011_{(2)}

G(s)の右から数えて4番目のビットが最上位の立っているビットです。それと同じ位置のビットが立っているのはs_1で、その値は8です。この数字を減らすことで、0000_{(2)}～0111_{(2)}の任意の数字を作り出す事ができます。G(s) = 1011_{(2)}の、011のビット列に合わせて、0011_{(2)}を作りましょう。この値は10進数では3なので、8から5を引けば作れます。その結果を見てみましょう。

s'_1 = 3_{(10)} = 0011_{(2)}
s'_2 = 6_{(10)} = 0110_{(2)}
s'_3 = 5_{(10)} = 0101_{(2)}
G(s') = 0000_{(2)}

めでたくG(s') = 0にすることができました。

Nimゲームの必勝法まとめ

Nimゲームの必勝法について見ていきました。山の数をnとし、i番目の山のコインの枚数をs_iとしたとき、次のことが言えることがわかりました。

  • 自分の手番の山の状態がsであるプレイヤーの勝敗は、sの排他的論理和(G(s) = s_1 \oplus \cdots \oplus s_n)で判定でき、この値が0の場合は負け、それ以外の場合は勝ちとなる。
  • 勝ちの人の必勝法は、相手の手番の状態s'がG(s') = 0となる手を選び続ければ良い。

次は、この知識を使ってグランディ数について見ていきましょう。

グランディ数が計算できればNimゲームの必勝法が適用できる

グランディ数はNimberとも呼ばれています。その名の通り、Nimゲームが関係します。次のゲームの必勝法を考えてみましょう。

板チョコがn枚あり、i番目の板チョコはh_i \times w_iピースで構成される。これらの板チョコを2人交互に食べていく。自分の手番の時、板チョコを1枚選び、それ1枚をすべて食べるか、縦か横の切れ目に沿って2枚に分割してどちらか片方を食べる。最後のチョコを食べた人が勝ちとなる。

Nimゲームの山がコインから板チョコに変化したゲームです。このゲームにも必勝法があります（必勝法があるかどうかの判断方法も書いたほうがよい？）。実は、各板チョコのグランディ数を求めることにより、Nimゲームと全く同じ必勝法を適用することができます。簡単に言うと、「グランディ数＝山のコインの枚数」とするNimゲームに帰着できるということです。

グランディ数の求め方

グランディ数は、ゲームの全体の状態（複数の板チョコ）ではなく、プレイヤーが自分の手番で変更を加えることができる単体の状態（1枚の板チョコ）に視点を当てて計算するのが基本です。

まず、負けの状態（その板チョコに対して操作が行えない）のグランディ数を0とします。ここでは、0 \times 0の板チョコのグランディ数を0とします。それ以外の状態sのグランディ数は、以下の方法で求めます。

  1. 状態sから1回で遷移できる任意の状態s'のグランディ数を求める。このグランディ数の集合をVとする。
  2. Vに含まれない最小の非負の整数を、状態sのグランディ数とする。

これは、グランディ数gの状態は、1回の操作でグランディ数g-1～0の状態に遷移できることを意味します。Nimゲームにおいて、x枚のコインの山は、1回の操作でx-1～0枚に変化させることができます。つまり、このようにグランディ数を定めることで、「グランディ数＝山のコインの枚数」とするNimゲームに帰着できるというわけです。

例として、3 \times 2の板チョコのグランディ数を求めてみましょう。板チョコの状態を(縦のサイズ, 横のサイズ)と表すことにします。まず、各状態が1回で遷移できる状態を列挙しましょう。例えば、(3, 2)は1回の操作で(3, 1), (2, 2), (1, 2), (0, 0)の4つの状態に遷移可能です。

(3, 2) -> (3, 1) or (2, 2) or (1, 2) or (0, 0)
(3, 1) -> (2, 1) or (1, 1) or (0, 0)
(2, 1) -> (1, 1) or (0, 0)
(1, 1) -> (0, 0)
(2, 2) -> (2, 1) or (1, 2) or (0, 0)
(1, 2) -> (1, 1) or (0, 0)

(0, 0)のグランディ数として0を当てはめ、順番にグランディ数を計算しましょう。ここで、g(h, w)は板チョコの状態(h, w)のグランディ数を表し、mex(S)は、集合Sに含まれない最小の非負の整数を表します。

g(0, 0) = 0
g(1, 1) = mex(\{g(0, 0)\}) = mex(\{0\}) = 1
g(1, 2) = mex(\{g(1, 1), g(0, 0)\}) = mex(\{1, 0\}) = 2
g(2, 1) = mex(\{g(1, 1), g(0, 0)\}) = mex(\{1, 0\}) = 2
g(2, 2) = mex(\{g(2, 1), g(1, 2), g(0, 0)\}) = mex(\{2, 2, 0\}) = 1
g(3, 1) = mex(\{g(2, 1), g(1, 1), g(0, 0)\}) = mex(\{2, 1, 0\}) = 3
g(3, 2) = mex(\{g(3, 1), g(2, 2), g(1, 2), g(0, 0)\}) = mex(\{3, 1, 2, 0\}) = 4

めだたくグランディ数を計算することができました。これであとはNimゲームと同じ必勝法を適用したいところですが、ちょっと待って下さい。g(2, 2)について見ると、

g(2, 2) = mex(\{g(2, 1), g(1, 2), g(0, 0)\}) = mex(\{2, 2, 0\}) = 1

グランディ数が1にもかかわらず、グランディ数が2の状態に遷移できています。これは、Nimゲームに置き換えると、コインが1枚から2枚に増える操作を許していることになります。これではNimゲームではないじゃないかと思うかもしれません。しかし、重要なのは、Nimゲームで使用した必勝法（相手の手番の状態s'がG(s') = 0となる手を選び続ける）が適用できるかどうかです。先程と同様に、必勝法が成り立つための2つの条件について考えてみましょう。

G(s) = 0である状態sの、任意の次の状態s'は必ずG(s') \ne 0となることの証明

グランディ数の定義から、ある状態のグランディ数と、そこから遷移した状態のグランディ数は必ず異なります。よって、Nimゲームの時と同様にこれは成り立ちます。

G(s) \ne 0である状態sからG(s') = 0である次の状態s'へ遷移できる手は必ず存在することの証明

Nimゲームの時と同じ方法をとれば、G(s') = 0へ遷移できます。

これで、今度こそ安心してNimゲームの必勝法を適用することができます。各板チョコのグランディ数を求め、排他的論理和をとることで、勝敗判定をすることができます。

以下は、1枚の板チョコの縦横のサイズを入力すると、その板チョコのグランディ数を求めてくれるプログラムです。グランディ数はメモ化再帰で求めることが多いです。

#include <iostream>
#include <cstring>
#include <set>
using namespace std;

const int MAX_H = 100;
const int MAX_W = 100;
int grundy[MAX_H][MAX_W];

int calcGrundy(int h, int w)
{
  int &g = grundy[h][w];
  if (g != -1) return g;
  if (h == 0 && w == 0) return g = 0;
  set<int> V;
  V.insert(calcGrundy(0, 0));
  for (int i = 1; i < h; ++i)
    V.insert(calcGrundy(i, w));
  for (int i = 1; i < w; ++i)
    V.insert(calcGrundy(h, i));
  g = 0;
  while (V.count(g)) ++g;
  return g;
}

int main()
{
  memset(grundy, -1, sizeof(grundy));
  int h, w;
  cin >> h >> w;
  cout << "Grundy number of (" << h << ", " << w << ") is "
       << calcGrundy(h, w) << endl;
  return 0;
}

分割が起こるゲームにおけるグランディ数

今度は次のゲームの必勝法を考えてみましょう。

板チョコがn枚あり、i番目の板チョコはh_i \times w_iピースで構成される。これらの板チョコを2人交互に分割していく。自分の手番の時、1 \times 1以外の板チョコを1枚選び、それ1枚を縦か横の切れ目に沿って2枚に分割する。分割できなくなった人の負けとなる。

先程のゲームと似ていますが、このゲームでは板チョコの「分割」が起こります。今まで登場したゲームでは、複数あるもののうちから1つを選び、その状態を変更するものでした。しかし、今回のゲームでは、複数あるもののうちから1つを選び、それを複数に分割します。このようなゲームでも、グランディ数を計算することができるのでしょうか？

実は、以下の定理を使うことで、この問題を解くことができます。

g(s, t) = g(s) \oplus g(t)

これは、2つの独立したゲームs, tを状態としてもつゲームのグランディ数はs, tそれぞれのグランディ数の排他的論理和に一致する、ということです（この定理の証明をすごく入れたかったのですが、思ってたより重いので省略しますすいません）。この定理を繰り返し適用することで、3つ以上の独立したゲームについても同様のことが成り立ちます。

この定理を使うことで、複数に分割された状態を1つのグランディ数で表現することができ、先ほどと同様の解法が適用できます。今回の板チョコの問題だと、1回の操作で2枚の板チョコs, tに分割された時、その状態のグランディ数はg(s) \oplus g(t)と表現することができます。

プログラムで書くと以下のようになります。遷移先の状態で排他的論理和をとるようになった以外は先ほどと同じです。

#include <iostream>
#include <cstring>
#include <set>
using namespace std;

const int MAX_H = 100;
const int MAX_W = 100;
int grundy[MAX_H][MAX_W];

int calcGrundy(int h, int w)
{
  int &g = grundy[h][w];
  if (g != -1) return g;
  if (h == 1 && w == 1) return g = 0;
  set<int> V;
  V.insert(calcGrundy(0, 0));
  for (int i = 1; i < h; ++i)
    V.insert(calcGrundy(i, w) ^ calcGrundy(h - i, w));
  for (int i = 1; i < w; ++i)
    V.insert(calcGrundy(h, i) ^ calcGrundy(h, w - i));
  g = 0;
  while (V.count(g)) ++g;
  return g;
}

int main()
{
  memset(grundy, -1, sizeof(grundy));
  int h, w;
  cin >> h >> w;
  cout << "Grundy number of (" << h << ", " << w << ") is "
       << calcGrundy(h, w) << endl;
  return 0;
}

今回は2つに分割される場合でしたが、3つに分割される場合、nつに分割される場合でも同様に排他的論理和をとることで1つのグランディ数で表現することができます。この定理から、Nimゲームの時に出てきたG(s)は、ゲーム全体の状態を表すグランディ数と捉えることもできます。

グランディ数まとめ

ここまで、グランディ数について見てきました。しかし、実際にコンテストでグランディ数を扱う場合、証明などの難しいことは一切考える必要がありません。グランディ数自体が何なのかわからなくても、以下のグランディ数の求め方さえ理解していれば、問題を解くことができます。

  • 負けの状態のグランディ数を0とし、それ以外の状態sのグランディ数は、以下の方法で求める。
    1. 状態sから1回で遷移できる任意の状態s'のグランディ数を求める。このグランディ数の集合をVとする。
    2. Vに含まれない最小の非負の整数を、状態sのグランディ数とする。
  • 1回の遷移で分割が起こる場合、分割された各状態のグランディ数の排他的論理和をとれば良い。

この記事は以上になります。ありがとうございました。