不偏ゲーム:Grundy 数および Nim

今回は競技プログラミングの記事です。たびたび AtCoder のコンテストで見かけることのある Grundy 数と、それを使った不偏ゲームの必勝法の有無の判定についてです。

概念の説明が主な記事なので、説明文が多めです。スクリプトとしては、記事の真ん中のあたりに、mex の計算スクリプトがあるので、よければ持ってっちゃってください。

突然ですが、30 ゲームと呼ばれるゲームはご存じでしょうか? バリエーションはいくつかありますが、以下のようなゲームです。

2人のプレイヤーが交互に数字を数え上げていく。
一回の手番で数え上げられる数は、1個から3個まで。例えば、相手が最後に「4」といった場合は、自分は「5」、「5、6」、「5、6、7」のいずれかを言うことができる。

最初は1からスタート。30 を言ってしまった人が負け。

このゲームは先手必勝で、先手が最初に「1」で自分の手番を終了することで、先手が必ず勝つことができます。

カニズムとしては、先手は最初に「1」で自分の手番を終了して相手に手番を渡すと、相手がどのような数え方をしても、 4 m + 1 m自然数)の数字で自分の手番を終えることができます。

すると、先手は「29」で手番を終えることができるので、相手が「30」を言わざるを得なくなり相手の負けになります。

AtCoder のコンテストでは、似たようなシチュエーションで高橋くんと青木くんが(30 ゲームよりは、何倍も複雑な)ゲームをプレイするような問題が出ます。両者が最適なプレイをした場合、どちらが勝者となるかを問われる問題です。

このゲームが不偏ゲームと呼ばれるゲームであるとき、最初の 30 ゲームのように、必勝法が存在することが知られています。

不偏ゲームの定義は以下の通りです。

  • プレイヤーが2人である
  • 交互に手番を交代してプレイする
  • 有限回の手番で、ゲームが終了する(ゲームの終了盤面が存在する)
  • ゲーム終了時に勝者となるプレイヤーが確定する
  • ある盤面に対し、手番でできる操作はプレイヤーによらない

不偏ゲームの必勝法を考える準備として、各盤面に対してある非負整数を割り当てます。結論から言いますと、この割り当てられる値が Grundy 数です。

割り当て方としては

  • 盤面が終了盤面の場合
    • 終了盤面で手番を迎えたプレイヤーが勝ちというルールの場合、1 を割り当てます。
    • 終了盤面で手番を迎えたプレイヤーが負けというルールの場合、0 を割り当てます。
  • 盤面が終了盤面以外の場合
    • その場面から遷移できる盤面の Grundy以外の 非負整数のうち、最小の整数を割り当てます。このような、与えられた非負整数以外の非負整数のうちの最小のものを、mex と呼んだりします。

こうして、各盤面に Grundy 数を割り当てていき、初期状態の盤面に割り当てられた値が 0 の場合後手必勝、0 以外の場合先手必勝となります。

冒頭の 30 ゲームで実験してみましょう。

def mex(sorted_list):
    i, v = next(
        filter(lambda x: x[0] != x[1], enumerate(sorted_list)),
        (len(sorted_list), None)
    )
    return i

# i まで数え上げられて手番が回ってきた盤面の Grudy 数が grundies[i] となるようにリストを用意します。
# 便宜上、初期盤面は「0 まで数え上げられて手番が回ってきた盤面」とします。
grundies = [-1] * 30

# for ループで用意するのが面倒だったので、ここは手打ち。
grundies[29] = 0
grundies[28] = 1
grundies[27] = 2

# 遷移可能な i+1 ~ i+3 の盤面の Grundy 数から、i の盤面の Grundy 数を大きい方から埋めていきます。
for i in range(26, -1, -1):
    next_grundies = [
        grundies[i + 1], 
        grundies[i + 2], 
        grundies[i + 3]
    ]
    next_grundies.sort()
    grundies[i] = mex(next_grundies)

# 初期盤面の Grundy 数が 0 でないので、先手必勝です。
print(grundies[0])
# => 1

# 自分が、1、5、9、... で言い終えて相手に手番を渡せば、相手が負けることがわかります。
print(grundies)
# => [1, 0, 3, 2, 1, 0, 3, 2, 1, 0, 3, 2, 1, 0, 3, 2, 1, 0, 3, 2, 1, 0, 3, 2, 1, 0, 3, 2, 1, 0]

確かに、30 ゲームは先手必勝となることがわかりました。

さて、なぜ初期盤面が 0 がそれ以外かで先手後手必勝が判定できるのかといいますと、Grundy 数の定義より

  • Grundy 数が 0 の盤面からは、Grundy 数が正の盤面にしか遷移できない。
  • Grundy 数が 正の盤面からは、必ず Grundy 数が 0 の盤面に遷移できる。

が成り立ちます。

このことから、一度相手プレイヤーに Grundy 数が 0 の盤面を押し付けることができれば、以降ずっと相手には Grundy 数が 0 の盤面を、自分には Grundy 数が 0 以外の盤面が来るようにすることができます。

プレイし続けるうちに、いつかはゲームが終了盤面となりますので、

  • 最終的に自分が Grundy 数 0 以外の盤面でゲーム終了する(= 自分が勝利する)
  • もしくは相手が Grundy 数 0 の盤面でゲームが終了する(= 相手が敗北する)

ことができます。

これが不偏ゲームの必勝法です。

コンテストでは、いくつかの不偏ゲームを複数個同時並列でプレイするような問題がでる場合もあります。不偏ゲームを複数個同時並列でプレイするようなゲームも、定義上は不偏ゲームであるのですが、盤面の遷移のパターンが複雑になり、処理時間に間に合わない可能性があります。

同時並列でプレイしているすべての不偏ゲームが終了盤面に到達し、自分の手番で操作ができなくなったプレイヤーが負けというルールの場合に限り、「各ゲームの初期盤面の Grundy 数の xor をとったもの」を考えると必勝法を考えることができます。

各ゲームの初期盤面の Grundy 数の xor をとったものが

  • 0 の場合、後手必勝
  • 0 以外の場合、先手必勝

となります。不思議ですね。

これを説明するには、Nim と呼ばれるゲームの知識があるとよいです。

ニム - Wikipedia
ニム和 - Wikipedia

Nim は、Nim 和(= 各山の初期の石の数の xor をとったもの)が

  • 0 の場合、後手必勝
  • 0 以外の場合、先手必勝

となります。なんだかさっきの Grundy 数の xor に似ていますね。

Nim の負け盤面における Nim 和は 0 です(すべての山の石が 0 なので)。
また、 Nim 和が 0 の盤面からは Nim 和が 0 以外の盤面にしか遷移できず、逆に Nim 和が 0 以外の盤面からは必ず Nim 和が 0 の盤面に遷移できます。

この性質から、一度相手に Nim 和が 0 の盤面を押し付ければ、以降ずっと相手に Nim 和 が 0 の盤面を押し付け続けることができます。(そしてそのうち終了局面となり、相手の負け=自分の勝ち、となります)

Grundy 数も、Grundy 数の定義より、今の Grundy 数より小さい Grundy 数の盤面すべてに自由に遷移することができます。

そうすると、一度 Grundy 数の xor が 0 の盤面を相手に押し付けると、以降ずっと相手に Grundy 数の xor が 0 の盤面を押し付け続けることができます。

Nim の石の数と違い、Grundy 数は 0 から 0 以外への遷移もありますが、定義より 0 以外から 0 への遷移が保証されているため、上のような性質が成り立つことが証明できます。

以上、Grundy 数を使った不偏ゲームの必勝法でした。

ちなみに、いくつかの不偏ゲームを複数個同時並列でプレイするような問題で、終了盤面を迎えたプレイヤーが勝ちというルールの場合 は、xor を取って先手必勝後手必勝を逆にすれば OK... というわけではない のにご注意ください。そちらに関してはまた後日。

(追記)

katoufujibanana.hatenadiary.jp

記事ができました。