二人零和有限確定完全情報ゲーム
二人零和有限確定完全情報ゲームはゲーム理論で扱われるゲームの分類のひとつである。将棋・囲碁・オセロ・石取りゲーム・連珠・五目並べ・三目並べ(○×ゲーム)などがこれに分類される。
これらの特徴は理論上は完全な先読みが可能であり双方のプレーヤーが最善手を打てば、必ず先手必勝か後手必勝か引き分けかが決まるという点である。無論、実際には完全な先読みは人間には不可能なためゲームとして成立するが、五目並べは先手必勝、三目並べは引き分けになることがすでに知られている。
「二人零和有限確定完全情報ゲーム」という言葉は以下のように分解できる
- 二人 3人以上のプレーヤーの対戦では、誰にとって不利な行動を自分にとって最も有利な行動とするか確定できない。すなわち、完全な先読みができない。
- 零和 二人の得点の合計が0になる、つまり相手にとっての手損がそのまま自分にとっての手得になる。非ゼロ和ゲームの代表例として囚人のジレンマがあり、これは最適行動が確定できない。
- 有限 いつかは終わるゲームであること。将棋も、千日手を禁止しているため有限ゲームとなる。
- 確定 偶然の要素が入り込まないこと。
- 完全情報 相手に自分の手を隠さないこと。
二人零和有限確定完全情報ゲームの先読みは人工知能の分野で早くから研究されてきた。ミニマックス法を改良したα-β法を基本とするアルゴリズムが主流。