偶奇不変量によるゲーム戦略
後続局面をDPで列挙せず、合法手の独立な消費や終端状態の偶奇不変量を証明して、先手・後手の勝敗を決める。
この典型を扱う単元: 偶奇不変量からゲームの勝敗を決める
検索別名: parity invariant game、ゲームの偶奇戦略、手数parity
未知問からこの典型を見つける手掛かり
- 扱う対象
- 二人ゲーム
- 先手
- 合法手
- 後手
- 残り手数
- 使う手掛かり
- 一手ごとに候補を消費
- 不変量から勝敗
- 候補数の偶奇
- 終端量の偶奇
- 保つ不変量
- 合法手集合が変わらない
- 手数の偶奇
- 終端状態の偶奇
- 求めるもの
- 先手勝ち
- 勝敗
- 勝者
- 後手勝ち
- 適用しない条件
- 個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果
分類と直接の前提
概念上の親: モデル変換
関連する典型
- game状態・Grundy DP: 後続局面を再帰計算してmexや勝敗を求める方法と、合法手数・終端量の偶奇から局面探索なしに勝敗を決める方法を区別する。
学習成果と学習単位
合法手が独立な固定候補の消費に限られる場合や、成分分類から残手数の偶奇を求められる場合に、勝敗を決める偶奇量と応答戦略を証明し、局面ごとのDPなしで勝者を判定できる。
偶奇不変量からゲームの勝敗を決めるで学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
関連問題
この典型が主タグまたは補助タグとして付いている問題です。