|
|
| 1行目: |
1行目: |
| − | '''二人零和有限確定完全情報ゲーム'''（ににん ぜろわ ゆうげん かくてい かんぜんじょうほう ゲーム）は、[[ゲーム理論]]による[[ゲーム]]の分類のひとつである。[[チェス]]・[[将棋]]<ref>将棋のルールは現在の[[日本将棋連盟]]の[http://www.shogi.or.jp/osirase/qa/taikyoku-kitei.html 対局規定]に基づく。以下、将棋においてはこれに基づいたものについて述べるものとする。</ref>・[[チェッカー]]・[[オセロ (遊戯)|オセロ]]・[[石取りゲーム]]（[[ニム]]）・[[囲碁]]・[[連珠]]・[[五目並べ]]・[[三目並べ]]（○×ゲーム）・[[マンカラ]]・[[ツイクスト]]など、偶然（運）に左右されないゲームが相当する。
| + | {{テンプレート:20180815sk}} __NOINDEX__ |
| − | | |
| − | == 概要 ==
| |
| − | これに分類されるゲームの特徴は、理論上は完全な先読みが可能であり、双方のプレーヤーが最善手を打てば、必ず先手必勝か後手必勝か引き分けかが決まるという点である。実際には選択肢が多くなると完全な先読みを人間が行う事は困難であるため、ゲームとして成立する。
| |
| − | | |
| − | 双方のプレーヤーが最善手を打った場合の勝敗が判明しているゲームには以下のものがある。
| |
| − | ;先手必勝
| |
| − | :初期ルールの[[五目並べ]]<ref>1899年、[[黒岩涙香]]が「[[萬朝報]]」紙に必勝法を掲載した。[[連珠#歴史]]も参照。</ref>
| |
| − | ;後手必勝
| |
| − | :6×6の[[オセロ (遊戯)|オセロ]]<ref>1994年、イギリスの研究者ファインシュタインが証明。参照：{{cite web|url=http://www.feinst.demon.co.uk/Othello/6x6sol.html|title=Perfect play in 6x6 Othello from two alternative starting positions|accessdate=2008-06-01|archiveurl=https://web.archive.org/web/20091101013931/http://www.feinst.demon.co.uk/Othello/6x6sol.html|archivedate=2009年11月1日|deadlinkdate=2017年9月}}</ref>、[[どうぶつしょうぎ]]<ref>{{Citation|last=田中|first=哲朗|year=2009|title=「どうぶつしょうぎ」の完全解析|journal=情報処理学会研究報告. GI, [ゲーム情報学]|volume=2009-GI-22|issue=3|pages=1-8|url=http://ci.nii.ac.jp/naid/110007993265}}.</ref>
| |
| − | ;引き分け
| |
| − | :[[三目並べ]]<ref>[[三目並べ#戦法のコツ]]参照。</ref>、[[チェッカー]]<ref>2007年、[[アルバータ大学]]の研究チームによって発表された。参照：[http://www.cs.ualberta.ca/~chinook/project/ Project - Chinook - World Man-Machine Checkers Champion]（同研究チームのサイト）および[http://www.sciencemag.org/cgi/content/abstract/1144079 Checkers Is Solved -- Schaeffer et al. 317 (5844): 1518 -- Science]（[[サイエンス]]誌）。</ref>
| |
| − | | |
| − | == 解説 ==
| |
| − | 「二人零和有限確定完全情報ゲーム」という言葉は以下のように分解できる。
| |
| − | | |
| − | === 二人 ===
| |
| − | ゲームを行うプレーヤーが二人のゲーム。
| |
| − | | |
| − | ゲーム理論でいうプレーヤーとはゲームを行う際にゲームの着手を決定する、[[意思決定]]する主体を指す。コンピュータであっても良く、また、最終的に意思決定が一つに定まるのであれば、二人以上のチームであっても良い。
| |
| − | | |
| − | [[ダイヤモンドゲーム]]、[[麻雀]]など、三人以上のプレーヤーが対戦するゲームは含まれない。また、[[ポーカー]]等の各種[[カードゲーム]]の多くや、[[モノポリー]]や[[人生ゲーム]]など一部の[[ボードゲーム]]のように、プレーヤーの数が可変で二人の場合もあり得るゲームについても含めないのが一般的である。
| |
| − | | |
| − | 三人以上のプレーヤーの対戦では、例えばプレーヤーを[[アリスとボブ|アリス]]、ボブ、キャロル、とした時、アリスの手がアリスにとって有利な手だとしても、ボブには助けとなり、キャロルには損害となることがありえるが、このとき、状況としてボブがアリスにとって最大の敵で、キャロルはむしろ潜在的な同盟者というようなことも可能性としてはあり得るため、単純にアリスの手がアリスにとって有利な手だから良いとはいえない。つまり、誰にとって不利な行動をとる事が、自分にとって最も有利な行動となるのかという、自分の直接の利害以外の要素を考える必要があるため、簡単に自分の打つ手を確定することができず、コンピューターなどで完全な先読みを行うことは難しい。
| |
| − | | |
| − | === 零和 ===
| |
| − | ゲーム上、プレーしている全プレーヤーの利得の合計が常にゼロ、または個々のプレーヤーの指す手の組み合わせに対する利得の合計が全て一定の数値（[[零和]]）となるゲーム。利得とはプレーヤーがゲーム終了時（あるいはターンの終了時）に獲得する状況に対する評価である。
| |
| − | | |
| − | 全てのプレーヤーがゲーム中に指しうる手の組み合わせを全て考えることができるとき、全ての手の組み合わせに対して各プレーヤーがそれぞれの状況に対して評価値を定めることにより利得表を作ることができる。例えば、[[ルーレット]]のような[[カジノゲーム|カジノで行うゲーム]]では獲得金額を利得として考えることができ、将棋やチェスなどのゲームでは勝利を1、引き分けを0、敗北を-1のように状態に数字をつけて考えることができる。利得表の合計が常にゼロのゲームでは、相手にとっての損がそのまま自分にとっての得になる。また、各状況に対する各プレーヤーの利得の合計が常に一定の数値となるゲームでは、合計を0とする利得表に変換することができるので[[零和]]ゲームとして考えることができる。
| |
| − | | |
| − | [[ルーレット]]のような[[カジノゲーム|カジノで行うゲーム]]では、各プレーヤーの利得の合計は必ずしも0あるいは一定の数値になるとは言えないため、零和のゲームとは言えない<ref>プレーヤーとして胴元も含めるとこれらのゲームでも[[零和]]となるものが多い。ただし、[[カリビアンスタッド|カリビアンスタッドポーカー]]のような[[プログレッシブジャックポット|ジャックポット]]のあるゲーム等では非零和となるものがある。</ref>。
| |
| − | | |
| − | [[将棋]]や[[チェス]]のような二人ゲームで、終了時の状態が、あるプレーヤーからみた場合、勝利、引き分け、敗北となるゲームについては、可能なすべての指し手の組み合わせに対して、プレーヤー毎に勝利を1、引き分けを0、敗北を-1と点を付けることができる場合、各手の組み合わせについて考えると、一方のプレーヤーの勝利の場合、そのプレーヤーの利得が1で相手の利得は-1となるため、その手の組み合わせの利得の合計は0となる。引き分けとなる手の組み合わせの場合は両方のプレーヤーの利得が0となるため、やはりその組み合わせの利得も合計は0となる。結果として、ゲームの利得表の合計は常に0となることが知られている。ただし実戦上ではまず現れることのない極めて稀なケースではあるが、将棋には現行ルール上に不備があり、勝利、引き分け、敗北のいずれとも決定できない合法的な局面が存在することが詰将棋の[[最後の審判 (詰将棋)]]によって示されている<ref>可能な手の組み合わせの総数が有限でない場合、単純に0の加算を続けるからといって合計を0と判断できない場合があるが、多くの場合は0であると考えてよい。</ref>。
| |
| − | | |
| − | [[非ゼロ和|零和でないゲーム]]は、[[囚人のジレンマ]]のように[[ナッシュ均衡|均衡点]]が[[パレート効率性|最適点]]でなかったり、[[チキンゲーム]]のように[[パレート効率性|最適点]]が相手の行動に依存するゲームがあったりと、[[零和]]のゲームに比べて一般に複雑であり、コンピューターなどで先読みを行うことは難しいことが多い。
| |
| − | | |
| − | === 有限===
| |
| − | そのゲームにおける各プレーヤーの可能な手の組み合わせの総数が[[標準型ゲーム#定義|有限]]であるゲーム。一般に各種ボードゲームやカードゲームはゲームの途中の状態が理論上有限であるため、ある状態から別の状態に変わり、そこからまた元の状態に戻るといった反復が無限に繰り返されない限り有限のゲームとなる。
| |
| − | | |
| − | [[オセロ (遊戯)|オセロ]]では、ゲームの特性上 8 × 8 − 4（初期配置）の60手しかなく、ゲーム研究上有限である。ただし組み合わせ総数は、膨大であり現時点ではコンピュータで全ては解析されていない。
| |
| − | | |
| − | [[囲碁]]では日本囲碁規約の規定上は三劫以上の多元劫、[[長生]]、循環劫などの状態になった場合、対局者が合意しないと勝負は無限に継続される<ref>[http://park6.wakwak.com/~igo/igorule/jp_rule.html 日本囲碁規約]参照。第12条の「無勝負」において、両対局者の合意により無勝負となるとある。</ref>ため、厳密に言えば有限なゲームではないが、実際にはほぼ有り得ないことであり、ゲーム研究では有限として研究されている。
| |
| − | | |
| − | 将棋やチェスに関しては、同一の状態が反復される[[千日手]]（チェスでは「[[千日手#チェスにおける千日手|スリーフォールド・レピティション]]」）があり、将棋でもチェスでも反復回数がルール上の規定数に達すると引き分けとなって終了するか、あるいは一方が手を変えなければならない規定があるため有限性は保たれる<ref>実はチェスでは千日手になっても、いずれかの対局者が申し立てをしない限りゲームは続くため、厳密には有限ではない。ただし現実には手を変えると不利になる方が申し立てをして引き分けにするので、実質的には有限と見てよい。</ref>。[[将棋]]の[[持将棋]]でも両対局者の確認と承諾を必要としているため合意が形成されない場合、対局が非現実的な長さに継続することもありうるが理論上は有限性が保証されている。また前述の[[最後の審判 (詰将棋)]]は千日手の規定の不備をついた形になっている。
| |
| − | | |
| − | この節における以上の議論は「[[アナログ]]と[[デジタル|ディジタル]]」の語義通りの意味でのディジタルなゲームについてのものである。（近年良く言われる「[[アナログゲーム]]」ではなく）語義通りの意味でアナログであるゲーム（たとえばボードゲームの「ハープーン」は、図上に円を描いて判定するなど、ディジタルではない）は有限ではない。コンピュータゲームで[[浮動小数点数]]を使用しているといった場合は、浮動小数点数を真の[[実数]]とみなせば有限ではないが、多くのゲームで組合せ爆発による大きな空間であっても有限として扱っている以上、通常の浮動小数点数であれば有限となる。一方でディジタルであっても、大きさに制限の無い真の整数を扱っている場合は無限になり得る（なお、そのようなコンピュータゲームのプログラムは、理論上、メモリ不足による実行時エラーを起こす可能性が絶対に存在するものとなる）。
| |
| − | | |
| − | 有限でないゲームは1つ1つの手の組み合わせを探索しきれず、完全な先読みができない。
| |
| − | | |
| − | === 確定 ===
| |
| − | プレーヤーの着手以外にゲームに影響を与える[[偶然]]の要素が入り込まないという意味。[[軍人将棋]]、[[海戦ゲーム]]などは初期配置等を含めプレイヤーの意思以外の要素が働かないので確定ゲームである。
| |
| − | | |
| − | [[ポーカー]]などの[[カードゲーム]]の一部や[[麻雀]]のように、ランダムに積み上げられた山から何かを引くようなゲーム、あるいは[[バックギャモン]]などの[[サイコロ]]でランダムにコマを進める[[双六]]系のゲームは、不確定ゲームに分類される。[[人生ゲーム]]も[[ルーレット]]で確率要素が介在するので不確定ゲームである。
| |
| − | | |
| − | === 完全情報 ===
| |
| − | {{seealso|完全情報ゲーム}}
| |
| − | 各プレイヤーが自分の手番において、これまでの各プレイヤーの行った選択（あるいは意思決定）について全ての情報を知ることができるゲーム。
| |
| − | | |
| − | [[将棋]]や[[チェス]]、[[囲碁]]、[[オセロ (遊戯)|オセロ]]など多くの[[ボードゲーム]]では、各プレーヤーが他のプレーヤーの状況を常に把握でき、また、どのような手を指したのかも明確にわかるため完全情報ゲームといえる。普通の双六も偶然の要素は含むものの、完全情報ゲームである。
| |
| − | | |
| − | [[麻雀]]や[[ポーカー]]等の[[カードゲーム]]の多くでは、各プレーヤーの手牌や手札を他のプレーヤーが見ることができず、他のプレーヤーがどのような状況でその牌やカードを切ったのかを知ることができないため[[不完全情報]]ゲームとなる。
| |
| − | [[じゃんけん]]のように各プレーヤーの手が同時に指されるゲームでは、自分の手を決定する際に、相手の手を見てから選択することができない。また[[海戦ゲーム]]、[[軍人将棋]]などは偶然の要素こそないものの、相手の手を不完全にしか把握できず完全な先読みができないため、不完全情報ゲームに分類される。
| |
| − | | |
| − | 完全情報ゲームでは、ゲーム終了時の状況から、その状態となる一つ前の状態を考えることができ、そこからさらに1つ前の状態を、さらに1つ前と考えることにより、ゲーム上有利な状況を探り、あるいは不利な状態を避けることができるが、不完全情報ゲームではその状態の1つ前の他のプレーヤーの状態がわからないためこのような推論を行うことができない。
| |
| − | | |
| − | == 二人零和有限確定完全情報ゲームの研究 ==
| |
| − | ゲームの理論の中で二人零和有限確定完全情報ゲームは、最も単純なゲームといえ、ゲーム理論の研究の最初期から研究されてきた。現在では研究の中心はゲームの性質についての研究から、人工知能を用いた具体的なゲームにおける戦略の研究にその中心が移っている。二人零和有限確定完全情報ゲームの先読みは[[人工知能]]の分野で早くから研究されてきた。[[ミニマックス法]]を改良した[[アルファ・ベータ法|α-β法]]を基本とする[[アルゴリズム]]が主流である。
| |
| − | | |
| − | == 脚注 ==
| |
| − | {{脚注ヘルプ}}<div class="references-small"><references /></div>
| |
| − | | |
| − | == 関連項目 ==
| |
| − | * [[ゲーム理論]]
| |
| − | * [[ランチェスターの法則#第2法則]]
| |
| − | | |
| − | {{ゲーム理論}}
| |
| − | | |
| − | {{デフォルトソート:ふたりれいわゆうけんかくていかんせんしようほうけえむ}}
| |
| − | [[Category:ゲーム理論]]
| |
| − | [[Category:数学に関する記事]]
| |
| − | [[Category:抽象戦略ゲーム|*]]
| |