さかなの思い

競技プログラミングの話が主になるかもしれません

変種石取りゲームの必勝法

f:id:Enjapma:20191211020448j:plain
1億円も夢じゃない
こんばんは、Enjapmaです。この記事はISer Advent Calendar 2019の19日目の記事として書かれたものです。
adventar.org
昨日はliwiiさんの「今学期プリンストンで受けた授業の振り返り」でした。

1 はじめに

今回の記事では、「Nim」と呼ばれる二人用石取りゲームとその変種について深く掘り下げてみます。
題材自体は耳にしたこともある人も多いと思いますが、色々な変種ルールなどが考案されていて、それらに対する必勝法なども研究されています。
初めての方にも読めるような内容を心がけておりますので、簡単すぎると思ったら適宜飛ばして読んでください。

2 ゲームの必勝法とは

2-1 ゲーム

今回考える「ゲーム」とは、以下の定義を満たすものとします。

  • プレイヤーの数が二人で、交互に手番を行う
  • どちらかのプレイヤーが勝ち、他方は負ける
  • ゲームが必ず有限の手番で終了する
  • ランダムな要素が登場しない
  • 全ての情報が両方のプレイヤーに公開されている

俗にいう「二人零和有限確定完全情報ゲーム」と言われるものです。

2-2 勝ち状態と負け状態

上で定義したゲームの局面には、「勝ち状態」と「負け状態」が存在します。
両者が最適にゲームをプレイすると仮定した場合、自分の手番の開始時に、ゲームの局面が「勝ち状態」であればそのゲームに勝利することができ、「負け状態」であれば勝利することができません。
これらは以下の条件を満たしている必要があります。

  • 全ての局面がどちらかに属している
  • 「負け状態」からは、どのような手を打っても「負け状態」へ遷移することはない
  • 「勝ち状態」からは、ある手であって「負け状態」へ遷移することができる

気持ち的には、「負けが決まっている局面では勝敗をひっくり返すことができず」、「勝ちが決まっている局面では油断さえしなければ相手を負けにできる」といった感じだと思います。

3 色々なゲーム

ここからは、色々なゲームの必勝法を淡々と述べていきたいと思います。
必勝法を述べるといってもアルゴリズムを正確に述べるとかではなくて、「負け状態」が何であるかを述べることにします。
そうすることで、相手に「負け状態」を常に押し付けるような手が必勝法であるとわかるからです。
(なお、3-2、3-3、3-5では論文を参照した箇所がありますので注釈に引用元論文を載せておきます。)*1

3-1 通常のNim

Nimとは、以下のようなゲームです。

  • 何個か石の積まれた山がいくつかある
  • 両者は自分の手番で、山を一つ選び、その山から何個か石をとる
  • 最後の石を取った人が勝ち

3-2 Nimの変種 その1

ここからは、取れる山の種類に制限をかけてみましょう。

  • 何個か石の積まれた山がいくつかある
  • 両者は自分の手番で、石の個数がもっとも多い山から、何個か石をとる
  • 最後の石を取った人が勝ち

3-3 Nimの変種 その2

変種その1に少しルールを付け加えてみましょう。

  • 何個か石の積まれた山がいくつかある。全ての山について石の個数は異なる。
  • 両者は自分の手番で、石の個数がもっとも多い山から、何個か石をとる。ただし、手番後に、2つの山であって石の個数が同じであるようなものが存在してはいけない。
  • 最後の石を取った人が勝ち

3-4 Nimの変種 その3

次は、少し違った種類の制限をかけたルールを見てみましょう。(証明に誤りがあったのでルールを訂正しています 12/19 9:24追記)@yuui_nesyaさんが解を見つけてくれたので元の設定に戻しました。

  • 何個か石の積まれた山がいくつかと、矢印がある。矢印は最初一つの山を指している。
  • 両者は自分の手番で、矢印が指している山から、何個か石をとる。ただし、手番後に、好きな山を一つ選び、その山を矢印が指すように矢印を動かす。
  • 最後の石を取った人が勝ち

3-5 Nimの変種 その4

その3のルールをちょっとだけ変えます。

  • 何個か石の積まれた山がいくつかと、矢印がある。矢印は最初一つの山を指している。
  • 両者は自分の手番で、矢印が指している山から、何個か石をとる。ただし、手番後に、自分が石を取った山以外から好きな山を一つ選び、その山を矢印が指すように矢印を動かす。
  • 最後の石を取った人が勝ち

3-6 Nimの変種 その5

最後は少し難しめのルールです。

  • 何個か石の積まれた山がいくつかと、コインがある。コインは、最初「表」を上にして置かれている。
  • 両者は自分の手番で、山を一つ選び、何個か石をとる。ただし、コインが「表」を向いているなら取る石の個数は偶数個、「裏」を向いているなら取る石の個数は奇数個でなければならない。
  • 石をとったあと、コインを裏返しても良い。
  • 最後の石を取った人が勝ち

4 まとめ

いかがだったでしょうか?ひたすらルールとその解を提示していくという流れになり、ちょっと単調な記事になってしまいましたが、それでもゲームの面白さが伝わってくれれば幸いです。今回の記事では石取りゲーム限定の紹介になってしまいましたが、世の中には様々なゲームが存在して、その負け状態が日々研究されています。興味を持ってくれた人は、そちらも見てみると良いかもしれません。

最後に、AtCoderで出題されている中でオススメのゲーム系の問題をいくつか置いておきます。

D - An Ordinary Game
D - Alice&Brown
D - Harlequin
E - Prefix-free Game

明日の記事はlmt-swallowさんです!どんな話をするのか、楽しみですね!それでは。

*1:M. H. Albert (2004) NIM RESTRICTIONS