競技プログラミングにおけるゲーム問題まとめ [Nim,Grundy数,後退解析,ミニマックス法]

ゲーム問題を解決する手段

Nim
- 「N個の石山があり、交互に山から石を任意個取っていく。先に取れなくなったほうが負け。」
- 各石山の個数をx[i]個とすると、勝敗は各山の個数を全てxorした値を見れば分かる。全てxorして=0なら先手は負け、!=0なら勝ち
- Nimの派生
  - 二次元nim 資料1 資料2 問題問題
Grundy数
- 2人でやるようなゲームではGrundy数に帰着させることでNimの原理で解ける場合がある
- Grundy数を以下のように定める
  - 負け状態のGrundy数は0
  - ある状態のGrundy数はそこから遷移可能な状態のGrundy数の中で最小の非負整数
- grundy数とNimにおける石の数は同じ意味
- 高さLの完全二分木のgrundy数はL&-L
- 規則性
  - ある周期になっている
後退解析、バックトラック参考
- 状態の遷移先に負け状態が1つでもあれば、相手を負けにできるので勝ち状態
- 逆に遷移先が全て勝ち状態ならば、自分は負けるしか無い
特殊な勝ち負け
- 偶奇を使う
- 相手の行動を真似ると負けない
  - 例えば、点対称に同様に置いていくと必ず置けるから、先手が置けるなら後手が必ず置けるので、後手必勝
ミニマックス法
- 自分は利得を最大化し、相手は利得を最小化する

問題

Nim
Grundy数
後退解析、バックトラック
偶奇を用いた勝ち負け
相手の真似をする必勝法
- HUPC2019 Day2 C 串刺し (Skewering) 解説
- WUPC2020 K Rectangle Game 解説
ミニマックス法

【発展的話題】Misere Nim

最後に石を取ると負けとしたNimのこと。よく分かる解説。
http://sigma425.hatenablog.com/entry/2014/12/07/132702
http://winjii.hatenablog.com/entry/2016/05/29/143653
簡単には、

積まれている石の数が2以上のものがあれば普通のNim
全部1の場合は山の偶奇によって勝敗が分かる

実装

int N; cin >> N;
int g = 0, ma = 0;
rep(j, 0, N) {
	int s; cin >> s;
	g ^= s;
	ma = max(ma, s);
}

if (ma == 1) {
	if (N % 2) printf("Second\n");
	else printf("First\n");
} else {
	if (g != 0) printf("First\n");
	else printf("Second\n");
}

はまやんはまやんはまやん

hamayanhamayan's blog

競技プログラミングにおけるゲーム問題まとめ [Nim,Grundy数,後退解析,ミニマックス法]

ゲーム問題を解決する手段

問題

【発展的話題】Misere Nim

Misera Nim問題