NimK (index-K Nim) の必勝判定・必勝側の具体的な手の選択
- NimKの必勝判定
- 必勝側の具体的な手の選択
について書きます。
後者は前者の証明に出てくるのですが念のために?指す手を求めるプログラムを書きました。
必勝判定
NimK または index-K Nim とは通常の $N$ 山 Nim の変形で、各手番では山を $K$ 個まで選択して石をとることができるゲームです。それぞれの山に積まれている石の個数を $A_1, A_2, \dots, A_N$ 個とします。このゲームでは $A_i$ を $2$ 進表示したとき桁ごとにとった和について
- 和が $K+1$ の倍数でない桁があれば先手必勝
- すべて $K+1$ の倍数ならば後手必勝
が成り立ちます。
たとえば $N = 5, K = 3$ で石の個数が $(22, 11, 42, 23, 19)$ の局面を考えます。$2$ 進表示して各桁の和を $\mathrm{mod}\ K+1$ で求めると次のようになるためこの局面は先手必勝です。
010110 001011 101010 010111 010011 ------ 132113
証明: 次を示せばいいです。
先手必勝 → 後手必勝の手が存在する
後手必勝 → 後手必勝の手が存在しない (先手必勝に移る手しかない)
【$\exists$ 先手必勝→後手必勝】
$(A_1, \dots, A_N)$ が先手必勝だとします。また $S_i\ (i = 0, 1, \dots)$ を次のようにおきます。
- $A_1, \dots, A_N$ を $2$ 進表示して $2^i$ の桁について $\mathrm{mod}\ K+1$ で和をとった結果*1
示すべきことは $\forall i = 0, 1, \dots$ に対し $S'_i = 0$ となる $(A_1', \dots, A_N')$ が存在することです。ただし
- $A_j' \le A_j$
- $A_j' < A_j$ となる $j$ は最大でも $K$ 個
でないといけません。
$S_i$ が $0$ でない最大の $i$ を $t$ とします*2。$A_1, \dots, A_N$ のうちで $2^t$ の桁が $1$ になっているものが少なくとも $S_t$ 個あるので、それらを操作対象の山として選択します。選んだ山から石を $2^t$ 個ずつとると $S_t' = 0$ になります。そして、それぞれの石の個数について $2^{t-1}, \dots, 2^0$ の桁を $1$ にします*3。
次に $S_{t-1}'$ を見ます。$S_{t-1}' = 0$ ならば文句なしですが、そうでない場合でも $S_{t-1}' \le $ さっき選んだ山の個数 であれば問題ありません。実際、選んだ山に残っている石の個数について $2^{t-1}$ の桁を $1 \to 0$ にすることを $S_{t-1}'$ 回行えば $S_{t - 1}' = 0$ とできます。
$S_{t-1}' > $ さっき選んだ山の個数 であればしかたがないので必要な分だけ操作対象の山を増やすほかありません*4。さっき選んだ山といま選んだ山について、石の個数を以前のステップと同じように変化させます。つまり $2^{t-1}$ の桁を $1 \to 0$ にしてそれより下位の桁をすべて $1$ にします。
$S_{t - 1}' = 0$ にできたので、次は $S_{t - 2}'$ を見て...を $S_0'$ まで繰り返せばすべての $S_i'$ を $0$ にできるため、後手必勝の局面に移れることになります。
【$\not\exists$ 後手必勝→先手必勝】
$(A_1, \dots, A_N)$ が後手必勝だとします。簡単のため先頭から $k$ 個の山 $1, \dots, k$ を選んだとして、それぞれの山から $1$ つ以上石をとり $(A_1', \dots, A_k', A_{k+1}, \dots, A_N)$ になったとします。ただし $k \le K$ です。
各 $A_i'$ には $A_i' < A_i$ より $A_i$ では $1$ だった桁が $0$ になった箇所があります。$2^{r_i}$ に対応する桁がそのような桁のうちで最上位だとします。
$2^r := \max_{i}(2^{r_i})$ とおくと $2^r$ に対応する桁が $1 \to 0$ となった $A_i$ の個数は $1$ 以上 $k$ 以下です。一方 $0 \to 1$ となった $A_i$ は存在しないことが分かります。
$(A_1, \dots, A_N)$ に対し $2^r$ の桁について $\mathrm{mod}\ K + 1$ で和をとった値を $S_r$ として、$(A_1', \dots, A_k', A_{k+1}, \dots, A_N)$ に対するそれを $S_r'$ とします。$(A_1, \dots, A_N)$ は後手必勝だったので $S_r = 0$ であり、$S_r - k \le S_r' \le S_r - 1$ より $S_r'$ は $K+1$ で割り切れません。
したがって後手必勝の局面に移れません。
手の選択
先手必勝局面が与えられたとき、そこから移れる後手必勝局面を上の証明で出てきた手続きによって求めるプログラムです。計算量は $O(N(\mathrm{log}_2(\mathrm{max}A_i))^2)$ です。
#include <algorithm> #include <bitset> #include <cassert> #include <iomanip> #include <iostream> #include <vector> #define rep(i, n) for (int i = 0; i < (int)(n); i++) using namespace std; void print_vector(vector<int> &a) { for (auto e : a) { cout << setw(2) << e << " " << bitset<8>(e) << endl; } } int main() { int n = 5, k = 3; vector<int> a = {22, 11, 42, 23, 19}; puts("before:"); print_vector(a); vector<int> x; rep(i, 31) { int s = 0; for (auto e : a) { s += e >> i & 1; } x.push_back(s % (k + 1)); } assert(any_of(x.begin(), x.end(), [](const auto &e) { return e > 0; })); vector<int> chosen; for (int p = 30; p >= 0; p--) { for (auto j : chosen) { if (x[p] > 0) { a[j] ^= 1 << p; x[p]--; } } for (int j = 0; j < n and x[p] > 0; j++) { if (a[j] >> p & 1) { chosen.push_back(j); a[j] ^= 1 << p; x[p]--; for (int q = p - 1; q >= 0; q--) { if (!(a[j] >> q & 1)) { a[j] ^= 1 << q; x[q] = (x[q] + 1) % (k + 1); } } } } } puts("after:"); print_vector(a); assert(chosen.size() <= k); rep(i, 31) { int s = 0; for (auto e : a) { s += e >> i & 1; } assert(s % (k + 1) == 0); } return 0; }
実行すると次のような出力が得られます。
山 $2$ から石を $4$ 個とって山 $3$ から石を $21$ 個とったことが分かります。
before: 22 00010110 11 00001011 42 00101010 23 00010111 19 00010011 after: 22 00010110 7 00000111 21 00010101 23 00010111 19 00010011
まとめ
NimK では $N$ 個の山に積まれている石の個数を $2$ 進表示して各桁ごとに $\pmod{K + 1}$ で和をとった数を $X$ とすると
- $X$ (の $2$ 進表示) に $0$ でない桁があれば先手必勝
- すべての桁が $0$ ならば後手必勝
となります。必勝側のプレイヤーは $X$ の上位桁から見ていき各桁が $0 \pmod{K + 1}$ になるように各山の石を減らしていけばいいです。このとき、すべての桁を $0$ にするために触る山は最大でも $K$ 個で済みます。
