主張

※「正規」や「ショート」などの用語解説は改めて別の記事で解説する予定ですので，お待ちください。

正規ショートゲームの例として「二ム」，「ドミニアリング(domineering)」，「ハッケンブッシュ(hackenbush)」などが考えられます。

中でも「二ム」は石取りをするゲームで，おそらくルールを見ればなんとなく知っているという方が多いと思います。

※「三山くずし」という呼び方の方がなじみ深い方が多いかもしれません(私はそうではないですが)。

「二ム」については代数と関係があり，かなり面白いので別の記事で改めて取り上げたいと思います。

「ドミニアリング」・「ハッケンブッシュ」は要望が多ければ解説しようと思います(もしくは参考図書\([1]\)を参照)。

これらのゲームではどちらか片方のみが必勝戦略を持つというのが，組み合わせゲームの基本定理です。

ただしあくまで必勝戦略の存在が判明しているだけなので，その戦略を見つけ出すのはゲームが複雑になるほど大変です。

そのため実際のゲームでは人間の能力に限界上，必勝戦略が存在すると分かっていても敗北することはもちろんあります。

証明

基本定理はかなり強力なことを述べていますが，証明はかなりスッキリしています。

以下「先手・後手」という言葉を使いますが，

「先手」は与えられた局面において次に手番を打つ人

「後手」は与えられた局面の前に手番を打った人

という意味で用いています。

この定義では一手打つごとに先手・後手が入れ替わっていくことに注意してください。

一手打つごとに，それまでの手を忘れて先攻・後攻を振りなおすというイメージです。

それでは証明です。

調べるゲームはショートである(特に有限性)ことから，そのゲームの局面の後続局面は有限個となります。

そこで局面\(\,G\,\)の後続局面数\(\,n\,\)に関する帰納法によって基本定理を証明していきます。

\([1]\,n=1\,\)のとき，定義より\(\,G\,\)自身も\(\,G\,\)の後続局面であるので，\(\,G\,\)の後続局面は\(\,G\,\)のみとなります。

正規性より，これは\(\,G\,\)が後手必勝であることを意味するので，\(\,n=1\,\)のときに基本定理が成り立つことが分かります。

\([2]\,n\leq k\in \mathbb{N}\,\)のとき成り立つと仮定して，\(\,n=k+1\,\)のときについて考えましょう。

このとき\(\,G\,\)から一手だけ進めた局面\(\,G^{N}\,\)の後続局面数は\(\,k+1\,\)未満になることをまずは示しましょう。

なぜなら\(\,G^{N}\,\)の後続局面は\(\,G\,\)の後続局面でもあるので，
まず\(\,G^{N}\,\)の後続局面数は\(\,k+1\,\)以下であることが分かります。

しかし\(\,G\,\)自身は\(\,G\,\)の後続局面ですが，\(\,G^{N}\,\)の後続局面ではありません。

なぜならもし\(\,G\to G^{N}\to \cdots\to G\,\)のように\(\,G^{N}\,\)の後続局面になったとすると，
これを繰り返すことで\(\,G\to G^{N}\to \cdots\to G\to\cdots\,\)のように無限に続くゲーム進行が得られます。

これはショートである(特にループフリー性)に矛盾します。

つまり\(\,G^{N}\,\)の後続局面数は\(\,G\,\)の後続局面数から少なくとも\(\,G\,\)の分の\(\,1\,\)だけは減少するので，
\(\,G^{N}\,\)の後続局面数は\(\,k+1\,\)未満になることが分かりました。

そこで帰納法の仮定を用いることで，
局面\(\,G^{N}\,\)では先手必勝か後手必勝のどちらかになっていることが分かります。

仮にどの局面\(\,G^{N}\,\)においても先手必勝だったとすると，これは局面\(\,G\,\)の時点でもともと後手必勝であることを意味します。

逆にある局面\(\,G^{N}\,\)において先手必勝でない，つまり後手必勝であったとすると，

局面\(\,G\,\)の時点の先手がその必勝局面\(\,G^{N}\,\)に移るように着手することで，その先手は勝つことができるので，これは局面\(\,G\,\)では先手必勝であることを意味します。

よって\(\,n=k+1\,\)のときも基本定理が成り立つことが分かりました。

したがって\(\,[1],[2]\,\)より，題意は示されました\(\quad\square\)

※証明を見れば分かるように，ゲームが正規である条件は\(\,n=1\,\)のときのみしか使っていませんね。

そのため正規の条件に代わる条件があれば，基本定理と同様のことが成り立つことが分かります。

例えばHexというボードゲームは正規ではありませんが，「引き分けは起こらない」という性質のために，基本定理と同様のことが成り立ちます。

興味のある方はHexの記事で解説しているので，読んでいただけると嬉しいです。

今回の記事では組み合わせゲーム理論の基本定理(fundamental theorem of combinatorial theory)を解説いたしました。

個人的には簡素ながら，かなり面白い定理だと思います。

もし「説明がわかりにくい」などご要望・ご感想がありましたら，
X（旧:Twitter）で#トイカラでつぶやいたり，
きる限り対応します。

ここまで読んでいただき，ありがとうございました。

• \([1]\) Aaron N. Siegel.”Combinatorial Game Theory”.American Mathematical Society.Volume: 146.p.9-10

※この記事の用語の定義はこの本\([1]\)に従っています。

• \([2]\) 安福智明, 坂井公, 末續鴻輝 著.”組み合わせゲーム理論の世界　～数学で解き明かす必勝法～”.初版.共立出版.2024出版.p.1-6.