Nim¶

Nimは不偏ゲームと呼ばれるゲームの1つで、必勝法が存在する。

Nimの必勝法¶

初期状態における石の山それぞれについて、石の個数の排他的論理和をとる。
このとき、 \(\bigoplus_i^N a_i \neq 0\) ならば先攻に必勝法が、\(\bigoplus_i^N a_i = 0\) ならば後攻に必勝法が存在する。
特に、両者が常に最適な一手を選ぶならば、初期状態のみで勝敗が判定できる。

[1]:

from functools import reduce
from operator import xor


def solve_nim(X):
    return reduce(xor, X) != 0

上の関数は、先攻に必勝法が存在するならばTrueを、後攻に必勝法が存在するならばFalseを返す。

[2]:

X = [2, 3, 5, 7]
print("Win" if solve_nim(X) else "Lose")

Win

[3]:

X = [3, 6, 12, 9]
print("Win" if solve_nim(X) else "Lose")

Lose

不偏ゲームと状態遷移図¶

Nimでは両者が最適に動くとき、「勝ち状態」 \(\bigoplus_i^N a_i \neq 0\) と「負け状態」 \(\bigoplus_i^N a_i = 0\) が交互に繰り返される。

Nimを含む不偏ゲームでは、状態を上手く定義することにより、次のような状態遷移図を作ることができる。

勝ち状態からは、勝ち状態と負け状態のいずれにも移動できる。
一方、負け状態からは常に勝ち状態へしか移動できない。
負け状態は終端状態 (Nimの場合は石が全てなくなった状態) を含む。

先攻が勝つとき¶

先攻が勝つには、ゲームの初期状態が勝ち状態で、かつ先攻のプレイヤーが勝ち状態を維持するように手を選べばよい。

先攻が「勝ち状態から負け状態への移動」を選択するのが最適で、このとき後攻は常に負け状態で回ってくる。

後攻が勝つとき¶

後攻が勝つとき、初期状態は負け状態である。
先攻はどのような手を選んでも、「負け状態から勝ち状態への移動」となる。
後攻が「勝ち状態から負け状態への移動」を選択することにより、先攻は常に負け状態で回ってくる。