ゲームの結論(1) 必勝法

ゲーム理論で有名な定理に以下のものがある。

二人・零和・有限・確定・完全情報ゲームには必勝法が存在する。

いろんなところで解説されていることだが、まずこの定理の内容についてまとめておく。

「二人・零和・有限・確定・完全情報ゲーム」とは、以下が全て成り立つゲームをいう。

  • 二人: 文字通り、二人で対戦するゲームであること。
  • 零和: ゲーム終了時にプレーヤーの得点の合計が必ず0になること。二人で勝敗を競うゲームであれば、勝ちを1、負けを-1、引き分けを0と見なせば、「どちらか一方が勝って他方が負けるか、引き分けになる」という条件に相当するので、たいてい成り立つ。囲碁やオセロのように終局時に地や石の数を数えるゲームでは、例えば「黒の5目半勝ち」のときの得点は黒5.5、白-5.5とすればよい。
  • 有限: 有限手数で必ずゲームが終了すること。
  • 確定: プレーヤーの意志と関係ない偶然の要素が入り込まないこと。例えば双六ではサイコロの目、人生ゲームではルーレットの目という偶然の要素が入るのでこの条件を満たさない。
  • 完全情報: ゲームを左右する全ての情報が全プレーヤーに開示されていること。例えば将棋なら盤上の駒の配置・持ち駒・手番といった情報はどちらのプレーヤーにも明らかになっている。対してババ抜きでは相手の持っている札がわからない(二人でやれば相手の札の集合はわかることになるが手の中の順番まではわからない)し、麻雀では他人の手牌や山の牌の内容がわからない。

これらの条件を全て満たすゲームには「必勝法が存在する」。これは、双方が最善を尽くすと「先手必勝」「後手必勝」「引き分け」のいずれになるのかの結論があらかじめ決まっているということを意味する。例えば囲碁や将棋は上記の条件を満たす(若干のルール修正が必要だが)。ただしこれらのゲームの結論は我々人間にはわかっていない。どんな複雑な手順も全て読みきれる「ゲームの神様」がいれば、理屈の上では初手から全てを読みきって結論を出してしまえるということである。

例えば子供のころにやった、図の「○×ゲーム」。縦横斜めのいずれかに3つ並べると勝ちというもの。全ての手をしらみつぶしに調べてもそんなに時間はかからない。先手が初手で真ん中に○を置いた場合、後手が2手目の×を辺に置いてしまうと、最善を尽くせば図のように先手の勝ちになる。しかし2手目を隅に置けば、以後先手がどのように置いても後手は最低限引き分けにはすることができる。初手が真ん中以外の場合も同様に、悪くても引き分けには持ち込める。先手の方も、ミスをしなければ少なくとも負けることはない。したがってこのゲームの結論は「引き分け」である。この程度の単純なゲームなら我々も「神様」になれる。

ところで、この定理の「必勝法が存在する」という言い方は誤解を招きやすいのではないかと思う。「必勝法」というと「先手必勝」「後手必勝」のどちらかであると解釈されかねないと思うのだが。実際には○×ゲームのように結論が引き分けという場合も含むのである。

有名なボードゲームについて、その結論にまつわる状況をおいおいまとめていくことにする。対象となるのはオセロ、五目ならべ/連珠、チェッカー、チェス、将棋、囲碁ぐらいか。それぞれについて、以下のようなことを少しずつ調べて書いてみたい。

  • 有限かどうか
    上で述べた条件のうち、成り立つかどうかが自明でないのは「有限」である。1億手かかっても1兆手かかってもいいから、とにかくいつかは終わるという保証がなければならないが、ルールの設定によってはいつまでも決着がつかずに指し続けることが可能なゲームもある。
  • 結論が出ているケース
    ゲームとして成立しているからには、「先手必勝」「後手必勝」「引き分け」のいずれであるかの結論はたいてい出ていないのだが、盤を少し狭くするとかルールを少し変更するとかした場合の結論がわかっているゲームもある。
  • 結論を推測する材料
    例えばトップレベルの人たち同士の対局での先手・後手の勝率。これで結論がわかるわけではないが、推測する材料にはなる。
  • 人間対コンピュータの状況
    結論が出るとしたらコンピュータを使った計算の結果としてだろう。そういう意味では、コンピュータソフトが現在人間に対してどの程度の実力かは、結論を出すためにどれくらいのところまできているかを知る材料にはなる。ゲームによってはすでに人間は全く歯が立たなくなっている。
[参考ページ]
二人零和有限確定完全情報ゲーム - Wikipedia

(つづく)