プログラミングコンテストチャレンジブック 4-2 その2

4-2 の続きからです。

  • Georgia And Bob - 一列のマスに並んだ駒を一方向に詰めるように動かしていって動かせなくなったほうが負け
    • 駒を2つずつペア(山に相当)にして Nim と同じゲームに帰着できる
  • コインのゲーム2 - コインの山から交互に取っていって最後に取ったら勝ち。ただし一度に取れるコインの個数は決まった数のいずれかでないといけない
    • Grundy 数というのを導入すると Nim に帰着できる
    • Grundy 数 = 今の状態から1手で行ける状態の Grundy 数に含まれない最小の非負整数
    • Grundy 数 が Nim の1つの山のコイン数と対応するので、全 Grundy 数の XOR で勝ち負けが判定できる

「多くのゲームは Grundy 数を求めることができます」とあるけれど、Grundy 数が適用できるかどうかの判断方法が書かれていないような。

  • Cutting Game - 格子に区切られた長方形の紙を交互に切っていって最初に1x1の格子を切り出したほうが勝ち
    • これも Grundy 数を求めることができる。紙を切って2つに分かれた時に g1 XOR g2 でまとめて表現できる