不変ゲームの定義

二人零和有限確定完全情報ゲームで、どの盤面であっても、プレイヤーによって取りうる操作の選択肢は変わらないゲーム。

(チェスは白番・黒番で取りうる操作が変わるので不変ゲームではない)

N局面・P局面

N局面・P局面の定義

N局面・P局面の特徴づけ

着手できない(終了局面)場合に負けの場合、終了局面はP局面である。

P局面は、どのような手をとってもP局面にいけない局面

N局面は、ある手を取ればP局面にいける局面

(気持ち: 相手にP局面を押し付けたい)

山の数が2の場合の Nim における N局面・P局面

image.png

(左上が終了局面)

Nim

Nim