有限局面DAGのminimax
必ず終了するゲームの局面DAGで、終端利得と各手番の最大化・最小化から局面値を求める。
この典型を扱う単元: minimax・得点差・局面値を評価するゲームDP
検索別名: minimax、ミニマックス、得点差ゲームDP
未知問からこの典型を見つける手掛かり
- 扱う対象
- ゲーム
- 先手
- 局面
- 後手
- 得点
- 手番
- 使う手掛かり
- 互いに最適
- 最善手
- 最大化
- 最小化
- 保つ不変量
- 局面値
- 得点差
- 手番ごとの目的
- 求めるもの
- ゲームの値
- 勝敗
- 最終得点
- 最適手数
- 適用しない条件
- 個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果
分類と直接の前提
概念上の親: DP状態と遷移
関連する典型
- game状態・Grundy DP: impartial gameのGrundy数と、双方の目的が異なる局面のminimax値を同じゲームDPへ混同しない。
学習成果と学習単位
有限DAGの局面で手番ごとの最大化・最小化と終端値を定義し、得点差や利得を後続状態から評価できる。循環時の無限継続と独立な数ゲームの加算は別の技能として扱う。
minimax・得点差・局面値を評価するゲームDPで学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
関連問題
この典型が主タグまたは補助タグとして付いている問題です。