二人零和有限確定完全情報ゲーム
概要
[編集]二人零和有限確定完全情報ゲームは、
- 二人：プレイヤーの数が二人[1]
- 零和：プレイヤー間の利害が対立し、一方が利得を得ると、他方に同量の損害が降りかかる
- 有限：ゲームが必ず有限の手番で終了する
- 確定：サイコロのようなランダムな要素が存在しない[1]
- 完全情報：全ての情報が両方のプレイヤーに公開されている[1]
伝統的なボードゲームの多くがこのカテゴリに属する（⇒ #具体例）。
なお、定数和ゲームは容易に零和ゲームへ変換でき、二人零和有限確定完全情報ゲームでの議論に持ち込みやすい。また「確定」と「完全情報」の意味合いがわかりにくいので補足すると、すごろく（周り双六）やバックギャモンはサイコロを使うため確定ゲームではないが、サイコロの出た目を含めゲームの全ての情報は全プレイヤーに公開されているので完全情報ゲームである。一方じゃんけんはサイコロのような乱数を生成する道具を使わないので確定ゲームであるが、相手がどんな手（グー、チョキ、パー）を出すかという情報を知らない状態で自分の手を決めねばならないので完全情報ゲームではない。
定義
[編集]具体例
[編集]二人零和有限確定完全情報ゲームの具体例には、チェス・将棋・チェッカー・リバーシ・石取りゲーム（ニム）・囲碁・連珠・五目並べ・三目並べ（○×ゲーム）・シャンチー・マンカラ・ツイクストが挙げられる。
このように、盤面にすべての要素や情報が表れており、勝敗が完全にプレイヤーの実力に依存し、サイコロや配牌といった「運」に左右されないボードゲームの多くが、二人零和有限確定完全情報ゲームに相当する。
ただし、ルールやその解釈により、厳密には二人零和有限確定完全情報ゲームとなっていないこともある[要出典]。
- 囲碁: 日本囲碁規約の規定上は三劫以上の多元劫、長生、循環劫などの状態になった場合、対局者が合意しないと勝負は無限に継続される[4]ため、厳密には有限ゲームではない。また対局結果は「片方の勝利」「引き分け（持碁）」「無勝負」の他に「両負け[5]」が規定されているため、厳密には零和ではない。
- 将棋: 千日手に絡み、勝利とみなすか、引き分けとみなすか、敗北とみなすかが現行ルールで定まっていない局面が存在することが、「最後の審判」と名付けられた詰将棋を例にして示されている[要出典]。また、持将棋でなおかつ、先手・後手の駒数が同一となる場合も、勝敗がつけられない。
- チェス: 千日手（スリーフォールド・レピティション）や戦力不足（双方駒が減りすぎて勝敗がつかないこと）になっても、いずれかの対局者が申し立てをしない限りゲームは続くため、厳密には有限ゲームではない。
特徴
[編集]二人零和有限確定完全情報ゲームの特徴は、理論上は完全な先読みが可能であり、双方のプレーヤーが最善手をプレイし続ければ、先手必勝、後手必勝、引き分けが決まることがエルンスト・ツェルメロによって証明されている[6]。
しかし選択肢が多く完全な先読みを人間が行うことが困難なゲーム（囲碁、将棋、チェスなど）は競技として成立している。
双方のプレーヤーが最善手をプレイし続けた場合の勝敗が判明しているゲームの例として、以下のものなどがある。
完全に解明されていないが、囲碁[16]、チェス（チェスの先手優位性）、将棋[17] は経験的に先手有利とされている。囲碁ではコミにより先手側にハンデを与えている[16]。チェスでは先後を入れ替えて複数回対局するマッチ（番勝負）で緩和している。連珠は五目並べの先手側にハンデを与えてゲームとして成立させている。
研究
[編集]ゲームの理論の中で二人零和有限確定完全情報ゲームは、最も[要出典]単純なゲームといえ、ゲーム理論の研究の最初期から研究されてきた。現在では研究の中心はゲームの性質についての研究から、人工知能を用いた具体的なゲームにおける戦略の研究にその中心が移っている[要出典]。二人零和有限確定完全情報ゲームの先読みは人工知能の分野で早くから[要出典]研究されてきた。ミニマックス法を改良したα-β法を基本とするアルゴリズム、モンテカルロ法によるプレイアウトなどが考案され、ディープラーニングにより人間を超える強さが実現した。
脚注
[編集]注釈
[編集]出典
[編集]- 1 2 3 4
二人零和有限確定完全情報ゲームでは、プレイヤー数が 2 名に限定され、かつランダム性が発生せず、すべての情報が両プレイヤーに公開されることが前提となる。
pp.37-38 より引用。中島, 千鶴 (2021). “障害非開示の発達障害者や発達障害の特性に似た傾向を持つ人に対応する周囲の人が専門家の関与なしに支援案を学ぶ手法の提案”. システムデザイン・マネジメント学 (481): 1–121. - 1 2 石水 p.1
- 1 2 3 岡田(1996) pp.61-66, 78
- ↑ 日本囲碁規約参照。第12条の「無勝負」において、両対局者の合意により無勝負となるとある。
- ↑ “Ⅱ日本囲碁規約（ルール）逐条解説 第十三条（両負け）”. 囲碁の日本棋院. 2023年12月11日閲覧。
- ↑ Davis, Morton.D 著、桐谷維、森克美 訳「第2章 完全情報・有限・2人・ゼロ和ゲーム」『ゲームの理論入門 チェスから核戦略まで』（第46刷）講談社〈ブルーバックス〉、1973年9月30日（原著1970年）、36-37頁。ISBN 4-06-117817-2。
- ↑ 1899年、黒岩涙香が「萬朝報」紙に必勝法を掲載した。連珠#歴史も参照。
- ↑ 1994年、イギリスの研究者ファインシュタインが証明。参照：“Perfect play in 6x6 Othello from two alternative starting positions”. 2009年11月1日時点のオリジナルよりアーカイブ。2008年6月1日閲覧。
- ↑ 田中, 哲朗 (2009), “「どうぶつしょうぎ」の完全解析”, 情報処理学会研究報告. GI, [ゲーム情報学] 2009-GI-22 (3): 1-8, NAID 110007993265.
- ↑ 田中哲朗「十六むさしの強解決」『ゲームプログラミングワークショップ2020論文集』第2020巻、2020年11月、194-201頁、CRID 1050855522099380608、NAID 170000184491。
- ↑ 山名, 琢翔、Yamana, Takuto「「オセロが解けた」を白黒ハッキリさせようじゃないか」『情報処理』第65巻第3号、2024年2月15日、134–136頁。
- ↑ Takizawa, Hiroki (2024-01-02), Othello is Solved, doi:10.48550/arXiv.2310.19387 2025年3月14日閲覧。
- ↑ “「双方にミスがなければオセロは“引き分け”になる」を証明した方法 オセロAI世界1位が解説”. ITmedia NEWS. 2025年3月14日閲覧。
- ↑ 三目並べ#戦法参照。
- ↑ 2007年、アルバータ大学の研究チームによって発表された。参照：Project - Chinook - World Man-Machine Checkers Champion（同研究チームのサイト）およびCheckers Is Solved -- Schaeffer et al. 317 (5844): 1518 -- Science（サイエンス誌）。
- 1 2 “コミ6目半の対局手番別勝率 ―平成19年集計―”. 日本棋院のアーカイブ (2008年1月5日). 2019年2月4日閲覧。
- ↑ “羽生善治九段「将棋AIは先手勝率7割」に仰天…最強ソフト開発者との対談で「“将棋の結論” を考え直します」”. smart-flash (2023年7月9日). 2023年12月10日閲覧。
参考文献
[編集]- 石水隆. “情報論理工学研究室 第4回：2人有限零和ゲーム” (pdf). 3年生卒研ゼミ用資料. 2019年1月3日閲覧。
- 岡田章 (1996/12/20). ゲーム理論. 有斐閣. ISBN 978-4641067943
