偶奇不変量からゲームの勝敗を決める
概要
偶奇不変量によるゲーム戦略
後続局面をDPで列挙せず、合法手の独立な消費や終端状態の偶奇不変量を証明して、先手・後手の勝敗を決める。
考え方
一手ごとに偶奇がどう変わるかを式にし、終局条件と結び付ける。操作回数の偶奇や保存される剰余が分かると、巨大な局面探索を数個の分類へ縮められる。
合法手が固定されたM候補から未使用一個を選んで消すだけで、他候補の合法性を変えないなら、終局までの手数は必ずM。手を出せない側が負けるnormal playではMが奇数なら先手、偶数なら後手が勝つ。途中の選択に依存しないことが、残手数の偶奇だけで判定できる根拠である。
応答戦略では、候補に自分以外の相手を割り当てる対合を作り、「使われていない候補は常に対で残る」を保つ。相手が片方を使ったらその相方を使う。この応答が常に合法で、対の消費が他の対を壊さないなら、偶数候補で後手が最後まで応答できる。固定点が一個ある奇数候補なら先手が最初にそれを使い、残りで同じ戦略を取れる。graphや盤面の対称性だけでは合法応答を保証しないため、相方が既使用・隣接禁止にならない条件まで示す。
成立条件と計算量
不変量は合法手の存在まで自動的には保証しない。必勝戦略には相手の各応答後にも戦略を続けられる根拠が必要。局面の走査O(N)など、初期不変量を求める費用と手の構築費用を分ける。
問題一覧
- ABC398 E「Tree Game」 公式問題
技能・出典
主題: 偶奇不変量からゲームの勝敗を決める(合法手が独立な固定候補の消費に限られる場合や、成分分類から残手数の偶奇を求められる場合に、勝敗を決める偶奇量と応答戦略を証明し、局面ごとのDPなしで勝者を判定できる。)。追加で学ぶ技能: 二部彩色と成分構造を扱う(各連結成分を二色に塗って矛盾を検出し、二つの部の大きさと色反転の自由度を成分ごとに集約できる。)。既習技能: 対話protocolを守って情報を取得する(judgeとの問い合わせ応答または交互手番のprotocolを守り、許された形式で応答依存の探索・合法手の提示・終了処理を実行できる。query上限がある場合はその回数も満たす。)。主タグ: 二部グラフの彩色と成分構造、偶奇不変量によるゲーム戦略 / 補助タグ: 対話protocolとquery設計
- ABC398 G「Not Only Tree Game」 公式問題組合せ: 二部彩色と成分構造を扱う
技能・出典
主題: 偶奇不変量からゲームの勝敗を決める(合法手が独立な固定候補の消費に限られる場合や、成分分類から残手数の偶奇を求められる場合に、勝敗を決める偶奇量と応答戦略を証明し、局面ごとのDPなしで勝者を判定できる。)。追加で学ぶ技能: 二部彩色と成分構造を扱う(各連結成分を二色に塗って矛盾を検出し、二つの部の大きさと色反転の自由度を成分ごとに集約できる。)。
各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。
前提・学習成果・出典
習得対象の目安: 青色(1600–1999)。局面ごとの勝敗再帰が不要な条件を見つけ、手数・終端量の偶奇から成立する戦略を証明する。
対象色の読み方は本書の読み方を参照してください。
概念上の親: モデル変換とアルゴリズム設計。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。
Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-game-parity-invariant
習得する技能
- 合法手が独立な固定候補の消費に限られる場合や、成分分類から残手数の偶奇を求められる場合に、勝敗を決める偶奇量と応答戦略を証明し、局面ごとのDPなしで勝者を判定できる。
前提と範囲
共通前提: prereq-abc-advanced-v1 (1.0.0)。
直接の前提単元: なし。
このUnitを直接前提とする単元: なし。
局面ごとの再帰計算が必要かを先に問い、各手が固定候補を一つ消費する場合や終端量の偶奇が不変量で決まる場合に、全局面を追わない勝敗戦略を証明する。
このUnitでは扱わないもの
- 後続状態の勝敗を再帰計算するGrundy DP、局面値を評価するminimax、およびグラフの二部彩色そのもの。