二人零和有限確定完全情報ゲーム
出典: フリー百科事典『ウィキペディア（Wikipedia）』
二人零和有限確定完全情報ゲーム（ふたり れいわ ゆうげん かくてい かんぜんじょうほう ゲーム）は、ゲーム理論で扱われるゲームの分類のひとつである。チェス・将棋[1]・オセロ・石取りゲーム（ニム）・囲連星・連珠・五目並べ・三目並べ（○×ゲーム）などが該当し、偶然に左右されない読みの深さを競う。
目次 |
[編集] 概要
これに分類されるゲームの特徴は、理論上は完全な先読みが可能であり、双方のプレーヤーが最善手を打てば、必ず先手必勝か後手必勝か引き分けかが決まるという点である。無論、実際には完全な先読みを人間が行う事は困難であるため、ゲームとして成立するが、初期ルールの五目並べは先手必勝[2]、三目並べ[3]とチェッカー[4]は引き分けになることがすでに知られている。
「二人零和有限確定完全情報ゲーム」という言葉は以下のように分解できる。
[編集] 二人
ゲームを行うプレーヤーが二人のゲーム。
ゲーム理論でいうプレーヤーとはゲームを行う際にゲームの着手を決定する、意思決定する主体を指す。コンピュータであっても良く、また、最終的に意思決定が一つに定まるのであれば、二人以上のチームであっても良い。
ダイヤモンドゲーム、麻雀など、三人以上のプレーヤーが対戦するゲームは含まれない。また、ポーカー等の各種カードゲームの多くや、モノポリーや人生ゲームなど一部のボードゲームのように、プレーヤーの数が可変で2人の場合もあり得るゲームについても含めないのが一般的である。
3人以上のプレーヤーの対戦では、例えばプレーヤーをPa、Pb、Pc、とした時、Paの手がPaにとって有利な手だとしても、別のプレーヤーPbには助けとなり、Pcには損害となることがありえるが、このとき、状況としてPbがPaにとって最大の敵で、Pcはむしろ潜在的な同盟者というようなことも可能性としてはあり得るため、単純にPaの手がPaにとって有利な手だから良いとはいえない。つまり、誰にとって不利な行動をとる事が、自分にとって最も有利な行動となるのかという、自分の直接の利害以外の要素を考える必要があるため、簡単に自分の打つ手を確定することができず、コンピューターなどで完全な先読みを行うことは難しい。
[編集] 零和
ゲーム上、プレーしている全プレーヤーの利得の合計が常にゼロ、または個々のプレーヤーの差す手の組合せに対する利得の合計が全て一定の定まった数値（零和）となるゲーム。利得とはプレーヤーがゲーム終了時（あるいはターンの終了時）に獲得する状況に対する評価である。
全てのプレーヤーがゲーム中に差しうる手の組み合わせを全て考えることができるとき、全ての手の組み合わせに対して各プレーヤーがそれぞれの状況に対して評価値を定めることにより利得表を作ることができる。例えば、ルーレットのようなカジノで行うゲームでは獲得金額を利得として考えることができ、将棋やチェスなどのゲームでは勝利を1、引き分けを0、敗北を-1のように状態に数字をつけて考えることができる。利得表の合計が常にゼロのゲームでは、相手にとっての損がそのまま自分にとっての得になる。また、各状況に対する各プレーヤーの利得の合計が常に一定の定まった数値となるゲームでは、合計を0とする利得表に変換することができるので零和ゲームとして考えることができる。
ルーレットのようなカジノで行うゲームでは、各プレーヤーの利得の合計は必ずしも0あるいは一定の数値になるとは言えないため、零和のゲームとは言えない。[5]
将棋やチェスのような二人ゲームで、終了時の状態が、あるプレーヤーからみた場合、勝利、引き分け、敗北となるゲームについては、可能なすべての打ち手の組み合わせに対して、各プレーヤー毎に勝利を1、引き分けを0、敗北を-1と点を付けることができる場合、各手の組み合わせについて考えると、一方のプレーヤーの勝利の場合、そのプレーヤーの利得が1で相手の利得は-1となるため、その手の組み合わせの利得の合計は0となり、引き分けとなる手の組み合わせの場合は両方のプレーヤーの利得が0となるため、やはりその組み合わせの利得も合計は0となるため、結果として、ゲームの利得表の合計は常に0となることが知られている。[6]
零和でないゲームは、囚人のジレンマのように均衡点が最適点でなかったり、チキンゲームのように最適点が相手の行動に依存するゲームがあったりと、零和のゲームに比べて一般に複雑であり、コンピューターなどで先読みを行うことは難しいことが多い。
[編集] 有限
そのゲームにおける各プレーヤーの可能な手の組み合わせの総数が有限であるゲーム。一般に各種ボードゲームや、カードゲームはゲームの途中の状態が理論上有限であるため、ある状態から別の状態に変わり、そこからまた元の状態に戻るといった反復が無限に繰り返されない限り有限のゲームとなる。
囲碁では日本囲碁規約の規定上は三劫以上の多元劫、長生、循環劫等の状態になった場合、対局者が合意しないと勝負は無限に継続される[7]ため、厳密に言えば有限なゲームではない。ただし、中国やヨーロッパ等の囲碁においてはスーパーコウルールといわれる反復の禁止ルールがあるため勝負はいつかは終わる。この場合でも、無勝負(引き分け)の場合再戦が行わることがあり、再戦でも無勝負となることがありうるため、どちらかのプレーヤーが必ず勝たなければならない試合においては無限の繰り返しとなる可能性があるが、1つ1つの試合(ゲーム)を考えた場合、スーパーコウルールのある囲碁は有限であるといえる。
将棋やチェス等の将棋系のボードゲームにおいては、同一の状態がルール上の規定数反復されると千日手（チェスではパペチュアル）となり、引き分けとなって終了するか、あるいは一方が手を変えなければならなくなる（変えない場合負けとなる）。このため指し直し（再戦）を考慮しなければ、有限のゲームといえる。
有限でないゲームは1つ1つの手の組み合わせ（戦略という）を書ききれず、完全な先読みができない。
[編集] 確定
プレーヤーの着手以外にゲームに影響を与える偶然の要素が入り込まないゲーム。
ポーカー等のカードゲームの一部や麻雀のように、ランダムに積み上げられた山から何かを引くようなゲーム、あるいはバックギャモンなどのサイコロでランダムにコマを進める双六系のゲームは、不確定ゲームに分類される。
囲碁や将棋については、それぞれニギリ、振り駒という独特の方法で先手後手を決めるときがあり、これらを含めた場合不確定ゲームと言えるが、通常はこうしたことが終わってからゲームが始まると考えられるため、囲碁、将棋は確定ゲームに分類される。
[編集] 完全情報
各プレイヤーが自分の手番において、これまでの各プレイヤーの行った選択（あるいは意思決定）について知ることができる（完全情報）ゲーム。
将棋や囲碁、囲連星、チェス等のボードゲームの多くでは、各プレーヤーが他のプレーヤーの状況を常に把握でき、また、どのような手を差したのかも明確にわかるため完全情報ゲームといえる。
麻雀やポーカー等のカードゲームの多くでは、各プレーヤーの手牌や手札を他のプレーヤーが見ることができず、他のプレーヤーがどのような状況でその牌やカードを切ったのかを知ることができないため不完全情報ゲームとなる。 じゃんけんのように各プレーヤーの手が同時に指されるゲームについては、自分の手を決定する際に、相手の手を見てから選択できず、海戦ゲーム、軍人将棋などは偶然の要素こそないものの、相手の手は不完全にしか把握できないため完全な先読みができないため、不完全情報ゲームに分類する。
完全情報ゲームでは、ゲーム終了時の状況から、その状態となる、ひとつ前の手をさせる状態を考えることができ、、そこからさらに1つ前の状態を、さらに1つ前の状況をと考えることにより、ゲーム上有利な状況を探り、あるい不利な状態を避けることができるが、不完全情報ゲームではその状態の1つ前の他のプレーヤーの状態がわからないためこのような推論を行うことができない。
[編集] 二人零和有限確定完全情報ゲームの研究
ゲームの理論の中で二人零和有限確定完全情報ゲームは、最も単純なゲームといえ、ゲーム理論の研究の最初期から研究されてきた。現在では研究の中心はゲームの性質についての研究から、人工知能を用いた具体的なゲームにおける戦略の研究にその中心が移っている。二人零和有限確定完全情報ゲームの先読みは人工知能の分野で早くから研究されてきた。ミニマックス法を改良したα-β法を基本とするアルゴリズムが主流である。
[編集] 脚注
- ^ 将棋のルールは現在の日本将棋連盟の対局規定に基づく。以下、将棋においてはこれに基づいたものについて述べるものとする。
- ^ 1899年、黒岩涙香が「萬朝報」紙に必勝法を掲載した。連珠#歴史も参照。
- ^ 三目並べ#戦法のコツ参照。
- ^ 2007年、アルバータ大学の研究チームによって発表された。参照：Project - Chinook - World Man-Machine Checkers Champion（同研究チームのサイト）およびCheckers Is Solved -- Schaeffer et al. 317 (5844): 1518 -- Science（サイエンス誌）。
- ^ プレーヤーとして胴元も含めるとこれらのゲームでも零和となるものが多い。ただし、カリビアンスタッドポーカーのようなジャックポットのあるゲーム等では非零和となるものがある。
- ^ 可能な手の組み合わせの総数が有限でない場合、単純に0の加算を続けるからといって合計を0と判断できない場合があるが、多くの場合は0であると考えてよい、。
- ^ 日本囲碁規約参照。第12条の「無勝負」において、両対局者の合意により無勝負となるとある。
[編集] 関連項目
| ゲーム理論のトピックス | |
| 定義 | 協力ゲーム - 非協力ゲーム |
| 均衡 | ナッシュ均衡 - 部分ゲーム完全均衡 - ベイジアン・ナッシュ均衡 - 逐次均衡 - 完全均衡 - 合理化可能性 - 進化的に安定な戦略 - パレート効率性- 戦略的補完性 |
| ゲームのクラス | 標準型ゲーム - 展開型ゲーム - 特性関数型ゲーム - 完全情報ゲーム - 不完全情報 - 繰り返しゲーム - ゼロ和 - 非ゼロ和 - 二人零和有限確定完全情報ゲーム |
| ゲーム | 囚人のジレンマ - チキンゲーム - スタグハントゲーム |
| 理論 | ミニマックス法 - フォーク定理 - コアの極限定理 |
| 関連項目 | 数学 - 経済学 - 進化論 - 集団遺伝学 - オペレーションズリサーチ - 社会生物学- 環境社会学 |
