Grundy数を操ってゲームの必勝法を導け！

これは、FORCIA Advent Calendar 2021の5日目の記事です。

こんにちは。プロダクト部　技術研究所の大沢です。

私が大学生のころ、Nintendo DSのアソビ大全というゲームソフトに定番ゲームの1つとして収録されていた「ラストワン」というゲームがあり、必勝法がないものか、あるとしたらどうにか導けないか？と気になっていた時期がありました。何週間か考えていましたが、当時はプログラミングも学びたてで、結局必勝法を編み出すことはできませんでした。
つい最近になってそんなゲームがあったことを思い出し、ふと考え直してみたところ、なんと必勝法を編み出すことができました！
その解法には、私がここ数年腕を磨いている、競技プログラミングで得た知識が生きていると感じました。
10数年の時を超えてゲームを攻略した喜びを共有したく、この記事を書くことにしました。

ラストワンというゲームについて

ルールは単純です。もしかしたら皆さんも紙や黒板で遊んだことがあるかもしれません。
まず、初期状態として縦棒を並べて書きます。

ピラミッド型じゃなくても良いですが、とにかく横に何個か縦棒を並べたものを何行か書きます。
次に、じゃんけんか何かで、先攻か後攻かを決めます。
ゲームは先攻と後攻で順番を交代しながら進みます。
自分の番の人は、まだ消されていない縦棒を選び、横線で消します。

このとき、まだ消されていない縦棒が横に連続していれば、複数まとめて消すこともできます。

すでに消された縦棒をまたいで消したり、違う行の縦棒をまとめて消すことはできません。

このように順番に縦棒を消していき、最後に残った1本を消した人の負け です。

なお、Android端末では こちら より実際に遊ぶことができます！(筆者作のアプリです)

必勝法とは？

実はこのゲームはすべての局面が「勝ち」か「負け」かが決まっています。

負けの局面について

例えばこの状態で手番が回ってくると、負け確定もしくは、相手が間違えない限り負けてしまいます。

勝ちの局面について

例えばこの状態で手番が回ってくると、勝ち確定もしくは、自分が間違えない限り勝つことができます。

突き詰めると、初期状態で先攻か後攻かを適切に選ぶゲームになります。
つまり必勝法を知っている人にとっては、初期状態が勝ちの局面であれば先攻を選び、負けの局面であれば後攻を選ぶことができれば必勝となります。

後退解析による解法

実は特殊な知識がなくても、プログラミングが得意な方であれば、すべての局面を勝ちと負けに分類できます。
後退解析という手法を使います (動的計画法の一種)

ある局面Aからどれか1つでも負け局面に遷移できればAは勝ち局面といえます。
反対に、勝ち局面にしか遷移できなければAは負け局面といえます。
ゲームの終了状態での勝ち負けは決まっているので、ゲームの終了状態から遡っていくことで勝敗が分かります。
これをシミュレートするのが後退解析です。

局面を圧縮する

一般的に動的計画法で問題を解く際、無数に状態が存在するのを共通の特徴で同一視して、状態を減らすことを考えます。
このゲームでは、たとえば

この2つの局面は同じとみなすことができます。どちらも、
(3,2,1,1)
という数列で表現できます。
これは、1本の孤立した縦棒が3個、2本並んだ縦棒が2個、3本並んだ縦棒が1個、4本並んだ縦棒が1個
残っているという意味です。

メモ化再帰

この問題は再帰関数で実装するのが都合がよさそうです。
特に、再帰関数を実装する際、同じ状態の判定を2度行わないように結果をメモしておく手法をメモ化再帰と呼びます。
実装上は、状態を表す数列をキーにしてメモしたいので、hash化して使います。
Pythonなら、tuple型であれば勝手にhashを計算してくれますし、自前のhash関数を作っても構いません。

以下にPythonの実装例を記します。

memo = {} #判定結果をメモするdictionary
def is_win_state(state):
    if state == (0,0,0,0,0,0): return True #最後の1本を消したら負け ⇒ すべて消された状態で回ってきたら勝ち
    if state in memo: return memo[state] #判定済みなのでメモの内容を返す
    result = False
    #get_next_states()は state から遷移可能なすべての状態たちを配列で返すメソッド(実装略)
    for next_state in get_next_states(state): 
        if not is_win_state(next_state): #遷移先に負け局面が1つでもあれば、勝ちと判定する
            result = True
            break
    memo[state] = result #判定結果をメモする
    return result

result = is_win_state((1,1,1,1,1,1)) #6段ピラミッド型の初期状態が勝ち状態であるか負け状態であるかわかる
print(result) # True ちなみに先攻は勝ちのようです

後退解析を使うことで、あっさりとすべての局面が勝ちか負けかが求まってしまいました。
プログラミングで求めることはできましたが、残念ながらこのプログラムを頭の中で動かすことのできる人はそう居ないと思います。
(いくつかの局面の勝ち負けを暗記すればそれなりに強いですが...)

どんな局面に対しても「計算」で、それも暗算可能な範囲で、求めることができたら、嬉しいと思いませんか？
それが、次に紹介するGrundy数の方法です。

Grundy数を使った解法

ラストワンは不偏ゲームというジャンルに属するゲームです。
正確には、終了状態(terminal position)にした人が勝ちではなく負けになるので、「逆形の」不偏ゲームという分類になります。
不偏ゲームにはGrundy数の性質を使った必勝法があります。

Nimの例 (正規系不偏ゲーム)

Nimという有名な不偏ゲームがあります。
初期状態で、石がいくつかの山になっています。
プレイヤーは自分の番の時にどれか1つの山から、1個以上好きなだけ取り除きます。

これを交互に行い、操作ができなくなった人の負け、つまり最後の1つを取った人の勝ちです。

ある局面のGrundy数を、「その局面から1手で遷移可能な局面のGrundy数のmex」で定めます。
ここで、mexとは、
非負整数の集合に対して、その集合に含まれない最小の非負整数と定義されます。
例)

{0,1,2,3} のmex は 4
{0,1,3,4} のmex は 2
{1,2,3} のmex は 0
{} の mex は 0
特に、遷移不可能な局面 (terminal position) のGrundy数は、0です。

山ごとにGrundy数を考えます。次のように求まります。
まず、石が0個の状態は、遷移可能な局面がありませんので、Grundy数は0となります。
次に、石が1個の状態は、石が0個の状態にのみ遷移可能です。遷移可能なGrundy数の集合は{0}なので、これのmex、つまりGrundy数は1です。
次に、石が2個の状態は、石が0個の状態と石が1個の状態に遷移可能です。遷移可能なGrundy数の集合は{0,1}なので、これのmex、Grundy数は2です。
同様に、石が3個の状態は、遷移可能なGrundy数の集合は{0,1,2}なので、これのmex、Grundy数は3です。
...
すると、お気づきかと思いますが、結局NimにおけるGrundy数は、石の数に一致します。

Grundy数を求めると何が嬉しいかというと、
その局面の勝敗がわかります。0の局面は負け、0以外の局面は勝ちです。
このようにGrundy数を定めると、必ず0の局面(負け)から 0の局面(負け)に遷移させることは不可能であり、また必ず非0の局面(勝ち)からは0の局面(負け)に遷移させることが可能という性質を持ちます。

Grundy数にはもう1つ、嬉しい性質があります。
Grundy数同士は (bitwise) xor演算を使って合成できるのです。
本記事では(bitwise) xorの演算子として ⊕ を使います

(bitwise) xorとは、ビットごとの排他的論理和です。
排他的論理和はビット演算の1つで、2つのビットのどちらか一方のみが1のときに限り、1となる演算です。
ビットごとの計算なので、2進数になおして、それぞれの位について計算します。
簡単にいえば、「繰り上がりのない足し算」です。

このxorの性質でGrundy数を合成していくことによって、複数ある山をあたかも1つの山とみなして局面を考えられるのがGrundy数の嬉しいところです。

Nimのセオリーをまとめると

• 山ごとにGrundy数を求めます (Nimでは山の石の個数と一致)
• それらGrundy数すべてをxor演算で合成した値を求めます
• 結果が0であれば負け局面、それ以外であれば勝ち局面です
• 合成したGrundy数が非0であれば、相手にGrundy数0の局面を押し付けられるので、自分の番で非0をキープでき、勝てます(下図参照

• 上図で(A)が成り立つ理由
  • Grundy数0の局面とは、各山の石の個数のxor結果が0ということ
  • どこかの山から石を取り除くということは、どこかの山のどこかの位が最低1つは書き変わるということ
  • するとxor結果が0から書き変わり、必ず0以外になる
• 上図で(B)が成り立つ理由
  • Grundy数が非0の局面とは、各山の石の個数のxor結果が0以外ということ (この値をxとする)
  • xの最上位bit (2進数で最も上の位の1) に注目する
  • xの最上位bitと同じ位が1である山が必ず1つは存在する (この山の石の個数をyとする)
    • そうでなければ、xの最上位bitが1にはならず、矛盾する
  • yの山を選んで、yをy⊕x個にできれば、xor結果を0にできる
    • これは可能か？結論は可能
      • xの最上位bitが、yも1であるため、y⊕xにおける当該bitは0となり、y > y⊕xが成り立つ
      • よって、yからy⊕xに「減らす」ことが可能

ラストワンに適用する

逆形不偏ゲーム (Misère Game) ですので、少し注意しなければなりませんが、Grundy数を適用できます。
Grundy数を適用する前に、自明なケース(下記の(1)(2)) から考えます。

(1) まず、1本の孤立した縦棒しか残っていないとき、勝敗は本数の偶奇で決まります

残り本数が奇数ならば負け、偶数ならば勝ちです。

(2) 次に、2本以上並んだ縦棒のかたまりが丁度1つあり、残りが全部1本で孤立しているケースは、勝ちの局面です

なぜなら、1本の孤立した縦棒が奇数本ならば並んだ縦棒を全部消せば良く、偶数本ならば並んだ縦棒から1本残して消せば、残りが奇数本の①の局面を相手に渡せるからです。

(3) それ以外のケースをGrundy数を使って考えます

Nimと同様に、かたまり毎にGrundy数を定義します。
便宜上、これ以上消せない状態(0本の状態)があるとして、このGrundy数を0とします。
これではNimと同じだから、「逆形」不偏ゲームのラストワンと勝敗が逆になってしまうのでは？と心配になるかと思いますが、大丈夫です。(理由はのちほど)
では肝心のGrundy数の求め方なのですが、結論はNimと同じく、かたまりの本数に一致します。
確かに、
1本の状態からは0本にしか遷移できない (Grundy数：1)
2本の状態からは0本と1本に遷移できる (Grundy数：2)
3本の状態からは0本と1本と2本に遷移できる (Grundy数：3)
ので、Nimと同じように考えることができそうです。
ですが勘の良い方は、ちょっと待った、と思うでしょう。
ラストワンでは、Nimとは異なる考慮も必要で、それは何かというと、かたまり(Nimでいう山)が増える遷移もあるということです。
3本のかたまりで真ん中の1本を消すと、左右に1本ずつの縦棒が残ります。この遷移は大丈夫なのでしょうか？結論は大丈夫です。
Grundy数の求め方は、「その局面から1手で遷移可能な局面のGrundy数のmex」でした。
さらに、Grundy数同士はxor演算で合成できます。
3本のかたまりで真ん中の1本を消し、1本の縦棒が2つ残った状態は1⊕1で、Grundy数は0です。
これを踏まえて、3本の状態をより正しく解釈するとこうなります。

3本の状態からは0本と1本と2本と「1本が2つ」に遷移できるが、「1本が2つ」のGrundy数は0なので、{0,1,2,0}のmexを求めることになり、Grundy数は3になります。
同じように、4本の状態からは0本と1本と2本と3本と「1本が2つ」と「1本と2本」に遷移できるが、「1本が2つ」のGrundy数は0、「1本と2本」のGrundy数は 1⊕2 で3なので、{0,1,2,3,0,3} の mexを求めることになり、Grundy数は4になります。
このように、ラストワンにおいても、n本のかたまりのGrundy数はnに一致することが示せます。(証明は省略します)

ラストワンと勝敗が逆になってしまうのではないか？それが大丈夫な理由

この理由は、ラストワンでは③の状態からゲームが進むにつれて、必ず(2)の状態を経由して、次に(1)の状態を経由するからです。
特に(2)の状態のGrundy数は必ず非0となります。非0はNimでは勝ち局面でしたので、ラストワンの勝敗と一致します。
(2)の状態からはGrundy数を使わずに勝つことができますが、(2)から遷移すべき状態は(1)かつ残り奇数本の状態で、この状態のGrundy数は1です。
Nimでは非0の局面を相手に渡すと負けてしまいますが、ラストワンはこのケースならば勝ちです。
ここで勝敗がNimとは反対になるので、辻褄が合います。

ラストワンのセオリーをまとめると

• まず、(1)(2)(3)のどの状態であるか見極めます
  • (1)ならば勝敗は決しています
  • (2)ならば奇数本残るように①の状態にすると、勝ちます
  • (3)ならば、Grundy数を使います
    • Grundy数が非0ならば、相手にGrundy数0の局面を押し付けられるので、いずれ(2)の必勝局面が回ってきます。
    • Grundy数が0ならば、相手が間違えるのを待つしかありません。
• 初期状態が(3)のとき、先攻後攻を選べる状況ならば、Grundy数が非0ならば先攻、0ならば後攻を選ぶと良いです。
  
  

(おまけ) xorを暗算するときのコツ

先ほど暗算できると嬉しい... と書きましたが、実際xorの暗算は慣れていないと難しいです (笑)
2進数への変換は覚えるしかないのですが、少しだけコツを書き記します。
x⊕x = 0という大事な性質があり、同じ数のかたまりが2個あれば相殺されて0になります。

さらに加えて、
1⊕2⊕3 = 0
1⊕4⊕5 = 0
2⊕4⊕6 = 0
あたりを覚えておくとさらに計算を減らせることが出来て良い感じです。