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