二人零和有限確定完全情報ゲーム
二人零和有限確定完全情報ゲーム（ふたりれいわゆうげんかくていかんぜんじょうほうゲーム）は、ゲーム理論で扱われるゲームの分類のひとつである。 将棋・囲碁・オセロ・石取りゲーム（ニム）・連珠・五目並べ・三目並べ（○×ゲーム）などが該当し、偶然に左右されない読みの深さを競う。これに分類されるゲームの特徴は、理論上は完全な先読みが可能であり、双方のプレーヤーが最善手を打てば、必ず先手必勝か後手必勝か引き分けかが決まるという点である。無論、実際には完全な先読みを人間が行う事は困難であるため、ゲームとして成立するが、五目並べは先手必勝、三目並べは引き分けになることがすでに知られている。
「二人零和有限確定完全情報ゲーム」という言葉は以下のように分解できる。
• 二人: 3 人以上のプレーヤーの対戦では、誰にとって不利な行動をとれば、それが自分にとって最も有利な行動となるのか確定できない。すなわち、完全な先読みができない。 • 零和: 二人の得点の合計が0になる、つまり相手にとっての損がそのまま自分にとっての得になるという特徴。 • 非零和ゲームの代表例として囚人のジレンマがあり、これは最適行動が確定できない。 • 有限: いつかは終わるゲームであること。将棋も千日手を禁止しているため有限のゲームとなる。 • 無限であればゲームツリーを書ききれず、完全な先読みができない。理論上無限のゲームに、トランプのページワンなどがある。 • 確定: 偶然の要素が入り込まないこと。 • バックギャモンなどの双六系のゲームでは、サイコロでランダムにコマを進めるため、不確定ゲームに分類される。 • 完全情報: 相手に自分の手を隠さないこと。 • 不完全情報ゲームである戦艦ゲーム、軍人将棋などは偶然の要素こそないものの、相手の手は不完全にしか把握できないため完全な先読みができない。
二人零和有限確定完全情報ゲームの先読みは人工知能の分野で早くから研究されてきた。ミニマックス法を改良したα-β法を基本とするアルゴリズムが主流。
