競技プログラミングにおけるゲーム問題まとめ [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つでもあれば、相手を負けにできるので勝ち状態 逆