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

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

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

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

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

なお、

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

具体例[編集]

例を挙げると、チェス将棋チェッカーオセロ石取りゲームニム)・囲碁連珠五目並べ三目並べ(○×ゲーム)・マンカラツイクストなどが二人零和有限確定完全情報ゲームである。

ただし(以下、囲碁と将棋は日本でのルールとする)、

  • 囲碁では、日本囲碁規約の規定上は三劫以上の多元劫、長生、循環劫などの状態になった場合、対局者が合意しないと勝負は無限に継続される[2]ため、厳密には有限ゲームではない。
  • 将棋では、「連続王手による千日手」と打ち歩詰めの両方が絡むと、現行ルールではどう扱われるか決まっていないため、勝敗を確定できない場合があるかもしれない。2018年現在、公式戦などの記録としてはこれによる困った事態の発生は記録されていないが、そのような局面の具体的な存在は、詰将棋作品「最後の審判」によって示されている。
  • チェスでは千日手(スリーフォールド・レピティション)や戦力不足(双方駒が減りすぎて勝敗がつかない事)になっても、いずれかの対局者が申し立てをしない限りゲームは続くため、厳密には有限ゲームではない。

といったように、ルールの複雑なコーナーケースによって厳密には要件を満たさないようなものも、通常はこれに含めて扱われることが多い。

特徴[編集]

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

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

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

厳密な定義[編集]

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

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

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

理論的な扱いが最も単純なゲームともいえ(ゲームとして単純だ、とはいっていない)、ゲーム理論の研究というよりは、ゲーム研究の一分野と言える「ゲーム情報学」の対象として古くから今もたゆまざる研究が進んでいる。チェスや将棋(コンピュータ将棋)についてのそれが一般的にはおそらく最も知られているが、いわゆる「人工知能」の研究と共に進んできたような部分もあれば、そうでない部分もある。ともあれ2010年代には、将棋でもプロリーグの上位棋士に対抗できるほどに強くなった。

二人零和有限確定完全情報ゲームは「AND-OR木」により、そのゲームの「ゲームの木」が、先手必勝か後手必勝かを確定できる、という特性がある。これの勝ち負けを盤面の評価値に拡張するとミニマックス法となる。ミニマックス法を効率的に実行する枝刈り手法の最も基本的な考えかたがα-β法である。コンピュータ将棋など実際のプログラムでは、以上のようなオーソドックスな手法を基本としたものとは全く異なる、より強くなるための手法を多数使うのが主流である。

脚注[編集]

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

参考文献[編集]

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

関連項目[編集]