酔っ払いのチョコレートゲーム（Chomp）

計算機科学の研究者と飲みに行ったら、「こういう口伝で伝わるゲームがあるんだけど、先手必勝と後手必勝のどっちかわかる？」と言われた。 問題を口伝で伝えるなんて、２１世紀の研究者とは思えないので、何か文献に載っていないのか聞いたが、知らないという。 一緒に飲みに行っていた人が見つけてくれた。Chompというらしい。

ここに記録として残しておくので、何か関連する文献を知っている方がいれば教えていただけるとありがたい。 せっかく書いたので、投稿して供養します。

ゲームの定義

彼は特に名前に言及していなかったので、酔っ払いのチョコレートゲームと呼ぶことにする。ルールは以下の通りである。

縦方向に $n$ 分割、横方向に $m$ 分割された格子になるように、割れ目が入れられたチョコレートがある。2人のプレイヤーは次の操作を交互に行う。

• 好きなマスを選んで、それより右下（自身を含む）の長方形の領域を全て取り去る。

最終的に、左上のマスを選んでしまったプレイヤーが負けである。

記法

$n \times m$ のチョコレートに対して行う酔っ払いのチョコレートゲームを、 $\mathrm{DCG}(n, m)$ で表す。

$(i, j)$ で、上から $i$ 番目、左から $j$ 番目のマスを表す。すなわち、ゲーム開始時点で最も右下にあるマスは $(n, m)$ であり、$(1, 1)$ を選んでしまったプレイヤーが負けである。

考察

自分で考えたい人のために、自分が行った考察を順に紹介する。結果と証明だけを見たい人は次の節まで進んでほしい。

$n \leq m$ を仮定する。 $n > m$ の時は、適切にチョコレートをひっくり返せば良い。

$1 \times 1$ のとき

ゲーム開始時点で、先手は $(1, 1)$ を選ぶ以外に選択肢がない。したがって、先手が必ず負ける。

$1 \times 2$ のとき、 $1 \times m \, (m > 2)$ のとき

$1 \times 2$ のとき、先手が $(1, 2)$ を選べば、後手は $(1, 1)$ を選ぶしかなくなる。よって、先手必勝である。

この手法は $1 \times m\,(m > 2)$ のときにも使える。先手が $(1, 2)$ を選べば、後手に残される選択肢は $(1, 1)$　しかなくなる。よって、$1 \times m \, (m > 2)$ のとき、先手必勝である。

$2 \times 2$ のとき

今までの議論から、先手が最善を尽くすならば、$(2, 2)$ を選ぶしかない。なぜならば、$(1,1)$ を選べばすぐに負けるし、$1 \times 2$ の領域が残るように選ぶと、後手から $\mathrm{DCG}(1, 2)$ が始まることになるので、負けてしまう。

先手が $(2, 2)$ を選んだ場合、後手は $(1, 2)$ と $(2, 1)$　のどちらかを選ぶしかない。どちらの場合も、先手から始まる $\mathrm{DCG(1, 2)}$ に帰着する。よって、先手必勝である。

$2 \times 3$ のとき

$2 \times 3$ より小さい長方形にすると負けるということがわかっているので、先手は $(2, 2)$ か $(2, 3)$ を選ぶしかない。$(2, 2)$ を選ぶと、後手が $(1, 3)$ を選べば、前節で見た状態に持っていかれるので負けである。$(2, 3)$ を選ぶと、後手はどのマスを選んでも、すでに見たことがある先手が勝てる状態になってしまう。よって先手必勝である。

ここで重要なのは、先手が $(2, 2)$ を選んだ場合と、先手が $(2, 3)$ を選んでから後手が $(2, 2)$ を選んだ場合で、チョコレートの状態が同じになることである。操作の性質から、2段の階段をひっくり返した形をした状態は、１手で作ることができる。（ちなみに、自分はゲーム木をそれなりに省略していたので、この事実に気がついたのは $\mathrm{DCG}(2, 4)$ を考えていたときである。）

2手以上かからないと作れないのはどういう状態だろうか？これは３段以上の階段をひっくり返した形をしたものである。なぜなら、１回操作を行うたびに、段は高々１つしか増えないからだ。（ちなみに、自分がこれに気がついたのは $\mathrm{DCG(3,4)}$ を考えているときだった。）

方針

ここまで考察してきた結果、 $\mathrm{DCG(1,1)}$ を除き、先手必勝になりそうである。これを証明したくなる。（なお、自分は事前に先手必勝であることを聞いていた）

後手必勝ではないことを証明するテクニックとして、後手必勝を仮定し、先手が後手必勝法を使って勝つ方法を生み出し、矛盾を導くというものがある。（自分はこれをHEXというゲームが先手必勝であることの証明で見たことがある。）これを使って証明を試みよう。

証明

次の定理を証明する。

定理. $n > 1$ または $m > 1$ のとき、$\mathrm{DCG}(n, m)$ は先手必勝である。

一般性を失わず、$n \leq m$ を仮定する。 $n > m$ の時は、行と列を入れ替えればよい。

$n = 1$ のとき: 先手必勝である。（これは上の節で述べたので省略する）

$n > 1$ のとき: 後手必勝であると仮定する（背理法の仮定）。先手がまず $(n, m)$ をとり、その後、後手が先手必勝法にしたがって1回操作をした後のチョコレートの形で場合分けをする。

• $n \times k \,(1 \le k < m)$ の長方形になるとき: 先手は初手で $(1, k+1)$ を取れば、あとは後手必勝法を使って勝つことができる。
• $k \times m \,(1 \le k < n)$ の長方形になるとき: 前の場合と同様に、先手は初手で $(k+1, 1)$ を取れば、あとは後手必勝法を使って勝つことができる。
• ２段の階段状になるとき: 後手が選択するマスが　$(k,l) \, (1 < k \leq n, 1 < l \leq m)$ だとする。先手は初手で $(k, l)$ を選択すれば、あとは後手必勝法を使って勝つことができる。
• 3段の階段状になるとき:　これはありえない。先手が $(n, m)$ を選んだ場合、後手はどのマスを選んでも、先手が消した範囲（$(n,m)$ だけだが）を完全に消してしまい、３段の階段状にすることはできない。
  
• (本当はこれで全ての場合を取り尽くしたことを示さなければならない気がするが、飽きてきたので省略する）

よって、先手は後手必勝法を利用して勝つことができる。これは後手必勝であることに矛盾する。後手必勝を仮定して矛盾が導かれたので、このゲームは後手必勝ではない。

このゲームに引き分けは存在しないため、先手必勝である。

反省

先手必勝を証明できた理由は何だったか

先手がうまく１手目を選べば、後手が実現できる状態を、先手が1手で実現できる範囲に制限できたことである。

うまくいかなかったところ

頭の中で可能性を事前に消していき、ゲーム木を描くのを一部省略していたので、$2 \times 4$ を考えるまで、重要なことに気が付かなかった。ちょっとだけ丁寧にゲーム木を描くのも大事だなと思った。

今後の課題（あまりやるつもりはないが）

• この証明では、具体的な必勝方法を構成できていない。必勝法を具体的に構成できるだろうか？今のところ見つかっていないようである。
  • 本文では触れていないが、$\mathrm{DCG}(n,n)$ に対する必勝法は簡単に構成できる。初手で$(2, 2)$ を選ぶと良い。
• 次元を増やした場合も、先手必勝だろうか？同様に証明できるだろうか？（普通にできそう。やってないけど）