石取りゲームの必勝法その1

石取りゲームの必勝法

石取りゲームとは、2人のプレイヤーがいくつかの山から石を交互に取っていき、最後に石を取った者が勝ちである（これを正規形のゲームとよぶ）というゲームである。別名二ム（Nim）ともよばれる。ちゃんとルールを書くと、

• 石の山をいくつか用意する．
• 許される指し手は，山を一つ選び、その山から好きなだけ（ただし1個以上）石を取り除くことである．
• 終了局面（ゲームが終了した局面）は，石が無くなった状態である．

である。

このゲームの必勝法を探っていこう。

簡単な場合から考えよう

一山の場合

一山くずしの必勝法・・・一山にある石を全て取る

これは明らかすぎる。

二山の場合

二山くずしの必勝法・・・2つの山の石の数が常に同じになるように取る
何故か少し考えてみてほしい。終了局面から考えてみよう。
2つの山の石の数を$(m,n)$と表すことにすると、

• 終了局面$(0,0)$は相手は石を取れないので後手が必勝戦略を持つ.
• $(1,0),(0,1)$の局面では石1個を取って先手が必勝戦略を持つ.
• $(1,1)$の局面では、片方の石しか取れず上のどちらかの局面になるので後手が必勝戦略を持つ.
  このように終了局面から順に考えていくと,$(m,n)$の局面で,$m=n$となる局面が後手が必勝戦略を持つ局面であることがわかる。

二山くずしの必勝判定

二山くずしの必勝判定・・・

• $m=n$のとき,後手が必勝戦略を持つ
• $m\ne n$のとき,先手が必勝戦略を持つ

三山の場合

ここから数学的に面白くなってくる。

To be continued

参考文献

1. 石取りゲームの数学 (佐藤 文広 著) 数学書房
2. 組合せゲーム理論入門-勝利の方程式- (川辺 治之 訳) 共立出版