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

出典: フリー百科事典『ウィキペディア(Wikipedia)』
ナビゲーションに移動 検索に移動

二人零和有限確定完全情報ゲーム(ふたり ぜろわ(れいわ) ゆうげん かくてい かんぜんじょうほう ゲーム)は、ゲーム理論によるゲームの分類のひとつで

  • 二人:プレイヤーの数が二人
  • 零和(「ゼロ和」と読むのが一般的だが「レイワ」とも読む)プレイヤー間の利害が完全に対立し、一方のプレイヤーが利得を得ると、それと同量の損害が他方のプレイヤーに降りかかる
  • 有限:ゲームが必ず有限の手番で終了する
  • 確定:サイコロのようなランダムな要素が存在しない
  • 完全情報:全ての情報が両方のプレイヤーに公開されている

という特徴を満たすゲームのことである[1]。伝統的なボードゲームの多くがこのカテゴリに属する(詳細は「#具体例」を参照)。


なお、

  • ゲーム理論でいうプレーヤーとはゲームを行う際にゲームの着手を決定する、意思決定する主体を指す。コンピュータであっても良く、また、最終的に意思決定が一つに定まるのであれば、二人以上のチームであっても良い。
  • 零和ゲームは上述のように一方のプレイヤーの利得と他方のプレイヤーの利得(=損害をマイナスしたもの)の合計が0である事が求められるが、合計が0でなくとも定数和であれば、零和ゲームに簡単に変換できる事が知られている。
  • 「確定」と「完全情報」の違いがわかりにくいので補足すると、すごろく(周り双六)やバックギャモンはサイコロを使うため確定ゲームではないが、サイコロの出た目を含めゲームの全ての情報は全プレイヤーに公開されているので完全情報ゲームである。一方じゃんけんはサイコロのような乱数を生成する道具を使わないので確定ゲームであるが、相手がどんな手(グー、チョキ、パー)を出すかという情報を知らない状態で自分の手を決めねばならないので完全情報ゲームではない。

具体例[編集]

チェス将棋チェッカーオセロ石取りゲームニム)・囲碁連珠五目並べ三目並べ(○×ゲーム)・マンカラツイクストなど、運に左右されないゲームが二人零和有限確定完全情報ゲームに相当する。

ただし

  • 囲碁では日本囲碁規約の規定上は三劫以上の多元劫、長生、循環劫などの状態になった場合、対局者が合意しないと勝負は無限に継続される[2]ため、厳密には有限ゲームではない。
  • 将棋も千日手に絡み、勝利とみなすか、引き分けとみなすか、敗北とみなすかが現行ルールで決まっていない局面が存在することが詰将棋の最後の審判 (詰将棋)によって示されている[3]
  • チェスでは千日手(スリーフォールド・レピティション)や戦力不足(双方駒が減りすぎて勝敗がつかない事)になっても、いずれかの対局者が申し立てをしない限りゲームは続くため、厳密には有限ゲームではない。

特徴[編集]

二人零和有限確定完全情報ゲームの特徴は、理論上は完全な先読みが可能であり、双方のプレーヤーが最善手を指せば、必ず先手必勝か後手必勝か引き分けかが決まるという点である。実際には選択肢が多くなると完全な先読みを人間が行う事は困難であるため、ゲームとして成立する。

双方のプレーヤーが最善手を打った場合の勝敗が判明しているゲームには以下のものがある。

先手必勝
初期ルールの五目並べ[4]
後手必勝
6×6のオセロ[5]どうぶつしょうぎ[6]
引き分け
三目並べ[7]チェッカー[8]

厳密な定義[編集]

二人零和有限確定完全情報ゲームは厳密には二人展開型ゲーム[9]として定義される。以下プレイヤーの名前をA、Bとすると、

  • 二人展開型ゲームが零和であるとはAの利得関数EAとBの利得関数EBがEA=-EBを満たす事を言う[9]
  • 二人展開型ゲームが有限であるとはゲーム木が有限グラフである事を言う
  • 二人展開型ゲームが確定であるとは偶然手番が存在しない事を言う
  • 二人展開型ゲームが完全情報であるとは全ての情報集合が唯一つの手番からなる事を言う[9]

二人零和有限確定完全情報ゲームの研究[編集]

ゲームの理論の中で二人零和有限確定完全情報ゲームは、最も単純なゲームといえ、ゲーム理論の研究の最初期から研究されてきた。現在では研究の中心はゲームの性質についての研究から、人工知能を用いた具体的なゲームにおける戦略の研究にその中心が移っている。二人零和有限確定完全情報ゲームの先読みは人工知能の分野で早くから研究されてきた。ミニマックス法を改良したα-β法を基本とするアルゴリズムが主流である。

参考文献[編集]

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

脚注[編集]

[ヘルプ]
  1. ^ 石水 p.1
  2. ^ 日本囲碁規約参照。第12条の「無勝負」において、両対局者の合意により無勝負となるとある。
  3. ^ 可能な手の組み合わせの総数が有限でない場合、単純に0の加算を続けるからといって合計を0と判断できない場合があるが、多くの場合は0であると考えてよい。
  4. ^ 1899年、黒岩涙香が「萬朝報」紙に必勝法を掲載した。連珠#歴史も参照。
  5. ^ 1994年、イギリスの研究者ファインシュタインが証明。参照:Perfect play in 6x6 Othello from two alternative starting positions”. 2009年11月1日時点のオリジナル[リンク切れ]よりアーカイブ。2008年6月1日閲覧。
  6. ^ 田中, 哲朗 (2009), “「どうぶつしょうぎ」の完全解析”, 情報処理学会研究報告. GI, [ゲーム情報学] 2009-GI-22 (3): 1-8, http://ci.nii.ac.jp/naid/110007993265 .
  7. ^ 三目並べ#戦法のコツ参照。
  8. ^ 2007年、アルバータ大学の研究チームによって発表された。参照:Project - Chinook - World Man-Machine Checkers Champion(同研究チームのサイト)およびCheckers Is Solved -- Schaeffer et al. 317 (5844): 1518 -- Scienceサイエンス誌)。
  9. ^ a b c 岡田(1996) pp.61-66, 78

関連項目[編集]