拡張された数取りゲームの必勝法

Twitter で不偏ゲームに関するとある問題が流れてきました。

このゲームをさらに一般化した次のゲームを考えます。

このゲームの必勝法（および、先手必勝か後手必勝か）を述べます。

結論

$m = 1$ のとき、$n$ が奇数ならば先手必勝、$n$ が偶数ならば後手必勝
$m \geq 2$ のとき、先手必勝

となります。必勝法は後述します。

必勝判定の方法について

以下の記事では Grundy 数を既知のものとして扱います。（ただし、最後に提示する必勝法を理解する上では Grundy 数に関する知識は不要となります）

愚直な必勝判定法

このゲームに登場する盤面のパターンは $2^{n}$ 通り存在します。
また、ある盤面から遷移可能な盤面は、高々 $n \times m$ 種類以下となります。

以上より、ゲームに登場する盤面を頂点とし、ある盤面から盤面への遷移を辺で表現したグラフを考えることで、終了盤面から Grundy 数をトポロジカルソート順に頂点を辿ることで定めることができます。

トポロジカルソートおよび各盤面の Grundy 数を求める計算量は全体で $O(mn 2^{n})$ となります。

少し改善された必勝判定法

$n = n_{0}$ におけるゲーム開始直後の盤面の Grundy 数を $G(n_{0})$ と書くことにします。便宜的に $G(0) = 0$ とします。

このとき、Grundy 数の性質とゲームのルールより、以下が成り立ちます。

$$ G(n_{0}) = \underset{1 \leq x \leq m, 0 \leq y \leq n_{0} - x}{\operatorname{mex}} \lbrace G(y) \oplus G(n_{0} - x - y) \rbrace $$

ただし $\oplus$ は排他的論理和を指します。

これにより、$G(0), G(1), G(2), \dots$ と順番に計算することで、$G(n_{0})$ を求めることができます。

全体的な計算量は $O(mn^2)$ となります。

最も改善された必勝判定法

まず、$m=1$ の場合、$G(n_{0})$ は $n_{0}$ を $2$ で割った余りになります。（証明は割愛）

次に、 $m \geq 2$ ならば、任意の $n_{0} \gt 0$ に対し $y = n_{0} - x - y$ を満たすような整数 $x, y$ （ただし $1 \leq x \leq m, 0 \leq y \leq n_{0} - x$ ）が存在します。このことから、先ほどの $G(n_{0})$ に関する式より $G(n_{0}) \gt 0$ が成り立ちます。

このことから、

$m = 1$ のとき、$n$ が奇数ならば先手必勝、$n$ が偶数ならば後手必勝
$m \geq 2$ のとき、先手必勝

がわかります。計算量は $O(1)$ です。

必勝法について

$m = 1$ については、どの順番で数字を言ってもゲームの勝敗に影響を与えないので割愛します。

$m \geq 2$ の場合について、先手は以下のように数を言うことで先手必勝となります。

1. $k = \lfloor \frac{n}{2} \rfloor $ とします。 $n$ が偶数の場合は先手は初めに $k, k + 1$ を、$n$ が奇数の場合は $k$ を言う。
2. それ以降は、先手は $n+1$ から直前に相手が言った数字を引いたもの（複数あるなら複数個）を言う。

イメージしづらい場合は、実際に先手の動きを追ってみるとよいかもしれません。
元ネタの問題の $n=21, m=3$ のケースを考えてみます。

最後に先手が 13 を言ったことで、残っている数字がなくなったため、後手の負けとなりました。

各手番で、先手が数字を言った直後の盤面を見ると、左右対称になっていることがわかります。
また、先手が一番初めに真ん中の数字を言ってしまったため、後手は左右非対称な盤面しか返せなくなってしまっています。

記事中では１パターンのみ例を挙げていますが、後手がどのように数字を言っても、先手は適当な数字を言うことで左右対称な盤面を後手に回すことができます。（証明は割愛）

全ての数字が宣言済みの盤面は左右対称な盤面なので、常に左右対称な盤面を押し付けることができる先手の勝ちとなることがわかります。