二人零和有限確定完全情報ゲーム

二人零和有限確定完全情報ゲーム：その定義と具体例

ゲーム理論において、「二人零和有限確定完全情報ゲーム」は、重要な分類の一つです。このゲームは、以下の特徴を備えています。

二人: プレイヤーは二人です。
零和: 一方のプレイヤーの利得は、もう一方のプレイヤーの損失と完全に等しくなります。合計するとゼロになることから「零和」と呼ばれます。
有限: ゲームは、有限の手番で必ず終了します。無限に続くことはありません。
確定: サイコロなどのランダムな要素は存在しません。ゲームの結果は、プレイヤーの選択によってのみ決定されます。
完全情報: 全ての情報が、両方のプレイヤーに公開されています。隠された情報はありません。

これらの条件を満たすゲームは、伝統的なボードゲームに多く見られます。チェス、将棋、囲碁、オセロなどは、典型的な例です。これらのゲームでは、盤上の状況が全て公開され、プレイヤーは自身の戦略に基づいて行動します。

ゲーム理論におけるプレイヤーと零和ゲーム

ゲーム理論における「プレイヤー」は、ゲームの着手を決定する意思決定主体です。必ずしも人間である必要はなく、コンピュータや、意思決定を一つにまとめた複数の人間からなるチームもプレイヤーとなります。

零和ゲームでは、プレイヤー間の利得の合計が常にゼロになる必要があります。しかし、合計が定数であれば、簡単な変換によって零和ゲームとして扱うことができます。

「確定」と「完全情報」の補足

「確定」と「完全情報」の概念は、理解しにくい点があります。

確定ゲーム: サイコロやトランプなどのランダムな要素がないゲームです。じゃんけんは確定ゲームですが、後述するように完全情報ゲームではありません。
完全情報ゲーム: ゲームの全ての情報が、全てのプレイヤーに公開されているゲームです。すごろくは、サイコロの出目も公開されるため完全情報ゲームですが、確定ゲームではありません。

厳密な定義：二人展開型ゲーム

厳密には、二人零和有限確定完全情報ゲームは、「二人展開型ゲーム」として定義されます。プレイヤーをAとBとすると、以下の条件が満たされます。

零和: Aの利得関数EAとBの利得関数EBが、EA = -EBを満たします。
有限: ゲーム木が有限グラフです。ゲームの全ての可能な展開が有限個です。
確定: 偶然の手番（ランダムな要素）が存在しません。
完全情報: 全ての情報集合が、唯一つの手番からなります。つまり、プレイヤーは常に、ゲームの全ての履歴を知ることができます。

具体例と例外

多くのボードゲームが、二人零和有限確定完全情報ゲームに分類されます。しかし、ルールやその解釈によっては、厳密な定義を満たさない場合があります。

囲碁: 三劫止まりや長生などの特殊な状況では、ゲームが無限に続く可能性があり、厳密には有限ゲームではありません。また、引き分けや両者負けなども存在するため、完全に零和ゲームとは言えません。
将棋: 千日手や持将棋のルールが複雑で、勝敗判定が明確でない場合があります。
チェス: 千日手や引き分けの規定が、厳密な有限性や零和性を満たさない場合があります。

ツェルメロの定理とゲームの複雑性

二人零和有限確定完全情報ゲームでは、理論的には完全な先読みが可能であり、双方が最善手をプレイすれば、先手必勝、後手必勝、または引き分けが決定します（ツェルメロの定理）。

しかし、囲碁や将棋、チェスなど、選択肢が多すぎるため、人間が完全な先読みを行うのは不可能です。そのため、これらのゲームは、競技として成立しています。

研究の現状

二人零和有限確定完全情報ゲームは、ゲーム理論の初期から研究されてきました。近年は、ゲームの性質そのものの研究から、人工知能を用いた具体的なゲーム戦略の研究に移行しています。ミニマックス法やモンテカルロ法、ディープラーニングなどの技術が用いられ、人工知能は人間を凌駕するレベルに達しています。

参考文献

石水隆. “情報論理工学研究室 第4回：2人有限零和ゲーム” (pdf). 3年生卒研ゼミ用資料. 2019年1月3日閲覧。
岡田章 (1996/12/20). ゲーム理論. 有斐閣. ISBN 978-4641067943

もう一度検索