この記事は、2019年に作成した記事を移設したものです。
こんばんは、Enjapmaです。この記事はISer Advent Calendar 2019の19日目の記事として書かれたものです。
昨日はliwiiさんの「今学期プリンストンで受けた授業の振り返り」でした。
はじめに
今回の記事では、「Nim」と呼ばれる二人用石取りゲームとその変種について深く掘り下げてみます。
題材自体は耳にしたこともある人も多いと思いますが、色々な変種ルールなどが考案されていて、それらに対する必勝法なども研究されています。
初めての方にも読めるような内容を心がけておりますので、簡単すぎると思ったら適宜飛ばして読んでください。
ゲームの必勝法とは
ゲーム
今回考える「ゲーム」とは、以下の定義を満たすものとします。
- プレイヤーの数が二人で、交互に手番を行う
- どちらかのプレイヤーが勝ち、他方は負ける
- ゲームが必ず有限の手番で終了する
- ランダムな要素が登場しない
- 全ての情報が両方のプレイヤーに公開されている
俗にいう「二人零和有限確定完全情報ゲーム」と言われるものです。
「勝ち状態」と「負け状態」
上で定義したゲームの局面には、「勝ち状態」と「負け状態」が存在します。
両者が最適にゲームをプレイすると仮定した場合、自分の手番の開始時に、ゲームの局面が「勝ち状態」であればそのゲームに勝利することができ、「負け状態」であれば勝利することができません。
これらは以下の条件を満たしている必要があります。
- 全ての局面がどちらかに属している
- 「負け状態」からは、どのような手を打っても「負け状態」へ遷移することはない
- 「勝ち状態」からは、ある手であって「負け状態」へ遷移することができる
気持ち的には、「負けが決まっている局面では勝敗をひっくり返すことができず」、「勝ちが決まっている局面では油断さえしなければ相手を負けにできる」といった感じだと思います。
色々なゲーム
ここからは、色々なゲームの必勝法を淡々と述べていきたいと思います。
必勝法を述べるといってもアルゴリズムを正確に述べるとかではなくて、「負け状態」が何であるかを述べることにします。
そうすることで、相手に「負け状態」を常に押し付けるような手が必勝法であるとわかるからです。
(なお、3-2、3-3、3-5では論文を参照した箇所がありますので注釈に引用元論文を載せておきます。)
1. 通常のNim
Nimとは、以下のようなゲームです。
- 何個か石の積まれた山がいくつかある
- 両者は自分の手番で、山を一つ選び、その山から何個か石をとる
- 最後の石を取った人が勝ち
このゲームの負け状態
「負け状態」=「全ての山について石の個数のXORをとると0」
証明は省きます。(「Nim」とかで調べればたくさん出てくると思うので)
2. Nimの変種 その1
ここからは、取れる山の種類に制限をかけてみましょう。
- 何個か石の積まれた山がいくつかある
- 両者は自分の手番で、石の個数がもっとも多い山から、何個か石をとる
- 最後の石を取った人が勝ち
このゲームの負け状態
「負け状態」=「石の個数がもっとも多い山の個数が偶数個」
(「石の個数がもっとも多い山にある石の個数が偶数個」ではないことに注意してください)
(証明)
1.「負け状態」からの遷移について
石を一つ以上取らなくてはならないことから、石がもっとも多い山の個数は必ず1減少し、奇数になります。
2.「勝ち状態」からの遷移について
石の数がもっとも多い山の個数が3個以上だった場合、ある山から石を1つだけ取れば良いです。
山の個数が1個だった場合、石の取り方を工夫することで、もっとも多い山の個数を必ず偶数にすることができます。
3. Nimの変種 その2
変種その1に少しルールを付け加えてみましょう。
- 何個か石の積まれた山がいくつかある。全ての山について石の個数は異なる。
- 両者は自分の手番で、石の個数がもっとも多い山から、何個か石をとる。ただし、手番後に、2つの山であって石の個数が同じであるようなものが存在してはいけない。
- 最後の石を取った人が勝ち
このゲームの負け状態
「負け状態」=「石の個数がもっとも多い山にある石の個数をnとしたとき、nが偶数で、かつ、n-1個の石があるような山も存在する」
(証明)
1.「負け状態」からの遷移について
石を2個以上取らなくてはならないことから、もっとも多い山にある石の個数はn-1となり、これは奇数であるため勝ち状態への遷移となります。
2.「勝ち状態」からの遷移について
n以外で最大のものが奇数であったなら、その値をkとして、n個の石の山から取ってk+1個にすれば良いです。
n以外で最大のものが偶数であったなら、その値をkとして、k-1個の石の山が存在するように石を取れば良いです。
4. Nimの変種 その3
次は、少し違った種類の制限をかけたルールを見てみましょう。(証明に誤りがあったのでルールを訂正しています 12/19 9:24追記)@yuui_nesyaさんが解を見つけてくれたので元の設定に戻しました。
- 何個か石の積まれた山がいくつかと、矢印がある。矢印は最初一つの山を指している。
- 両者は自分の手番で、矢印が指している山から、何個か石をとる。ただし、手番後に、好きな山を一つ選び、その山を矢印が指すように矢印を動かす。
- 最後の石を取った人が勝ち
このゲームの負け状態
「負け状態」=「石の数が1個ではない山が存在し、矢印が指している山にある石の個数が1個で、石が1個しかない山の個数が奇数個」もしくは「全ての山にある石の数が1個で、山の数が偶数個」
(証明)
1.「負け状態」からの遷移について
必ず1個しかない山の個数が1減少するので、石が1個しかない山の数の偶奇が反転します。
2.「勝ち状態」からの遷移について
全ての山にある石の個数が1個で、山の数が奇数個のとき、山の数が偶数個になります。
矢印が指している山にある石の個数が1個では無い場合、
1個の山が偶数個で、その山以外に1個ではない山が存在する場合、その山にある石が1個になるように石を取れば良いです。
1個の山が偶数個で、その山以外に1個ではない山が存在しない場合、石を全て取れば良いです。
1個の山が奇数個で、その山以外に1個ではない山が存在する場合、石を全て取り、1個の山を指すように矢印を移動させると良いです。
1個の山が奇数個で、その山以外に1個ではない山が存在しない場合、その山にある石が1個になるように石を取れば良いです。
矢印が指している山にある石の個数が1個の場合、
全てが1個の山で、山の数が奇数個の場合、山の数が偶数個になります。
1個ではない山があって、1個の山の数が偶数個の場合、1個の山の数が奇数個になります。
5. Nimの変種 その4
その3のルールをちょっとだけ変えます。
- 何個か石の積まれた山がいくつかと、矢印がある。矢印は最初一つの山を指している。
- 両者は自分の手番で、矢印が指している山から、何個か石をとる。ただし、手番後に、自分が石を取った山以外から好きな山を一つ選び、その山を矢印が指すように矢印を動かす。
- 最後の石を取った人が勝ち
このゲームの負け状態
「負け状態」=「山の個数が偶数個で、かつ、矢印の指している山にある石の個数が、全ての山の中で最も少ない」
(証明)
1.「負け状態」からの遷移について
石を残した場合、矢印の指す山は最小の山ではなくなります。
石を全て取る場合、山の個数が偶数個ではなくなります。
2.「勝ち状態」からの遷移について
山の個数が偶数個の場合、その山から石を1つ以上とって、最小の山に矢印を動かせば良いです。
山の個数が奇数個の場合、その山の石を全て取って、最小の山に矢印を動かせば良いです。
6. Nimの変種 その5
最後は少し難しめのルールです。
- 何個か石の積まれた山がいくつかと、コインがある。コインは、最初「表」を上にして置かれている。
- 両者は自分の手番で、山を一つ選び、何個か石をとる。ただし、コインが「表」を向いているなら取る石の個数は偶数個、「裏」を向いているなら取る石の個数は奇数個でなければならない。
- 石をとったあと、コインを裏返しても良い。
- 最後の石を取った人が勝ち
このゲームの負け状態
「負け状態」=「全ての山にある石の個数を2で割って切り捨てて、その上で3-1に帰着させた時の負け状態と同じ」
(証明)
まず、取るべき石の個数が偶数・奇数と入れ替えさせるコインの存在が厄介です。
そこで今回は、取るべき石の個数は「常に偶数である」としてしまいましょう。
そうすると、山の個数を2で割って切り捨てることで、通常のNimに帰着させることができます。
しかし、コインが裏を向いている時は、石を取る個数は奇数になってしまう事実は変わりません。どうすれば良いのでしょうか?
実は、コインの表裏が勝敗に関係しないことがわかります。
まず、コインがずっと表を向いていると仮定した場合には、勝敗を決めることができます。このときの仮定の下で勝利が約束された側を「勝者」、そうでない側を「敗者」と呼ぶことにしましょう。
このとき、勝者は当然ですがコインを表にした状態で敗者に渡すのが最適です。問題は、敗者がコインを裏にした状態で自分の手番に回してきた場合について考えます。
当初の予定(表で回ってくるとした仮定の下)で、「m個ある石の個数を2k、あるいは2k+1にしよう」と考えていたとします。2kにしようと思っていた場合、2k+1個にすることができます。2k+1にしようと思っていた場合、2kにすることができます。よって、勝者の立場は揺らがないことがわかります。
(よりformalに説明するには、grundy数という概念を導入するとわかりやすいです。コインが表から裏になることで、各山のgrundy数は増加こそすれ減少はしないということがわかります。)
まとめ
いかがだったでしょうか?ひたすらルールとその解を提示していくという流れになり、ちょっと単調な記事になってしまいましたが、それでもゲームの面白さが伝わってくれれば幸いです。今回の記事では石取りゲーム限定の紹介になってしまいましたが、世の中には様々なゲームが存在して、その負け状態が日々研究されています。興味を持ってくれた人は、そちらも見てみると良いかもしれません。
最後に、AtCoderで出題されている中でオススメのゲーム系の問題をいくつか置いておきます。
D – An Ordinary Game
D – Alice&Brown
D – Harlequin
E – Prefix-free Game
明日の記事はlmt-swallowさんです!どんな話をするのか、楽しみですね!それでは。
コメント