ゲームの結論(2) オセロ(その1)

1. ルール

オセロは図のような8×8の盤と、白と黒が裏表に塗られた石を使う。図の状態から黒から始めて交互に打つ。相手の石を縦横斜めのいずれかの方向にはさめるところに石を置き、はさんだ石は裏返して自分の色にする。はさめるところにしか石を置くことができず、ない場合はパスする。逆にはさめるところがある場合はパスできない。全てのマスが埋まるか双方パス(一方が全滅した場合を含む)で終局し、石の多い方が勝ちである。

長谷川五郎が考案した日本生まれのゲームで、私が小学生の時に大ブームになり、友達とよく遊んだものだった。といっても元々リバーシというゲーム(19世紀のイギリスが発祥らしい)があって、オセロはその盤の形やサイズ(および盤と石の色)に制限を加えたものである。

2. 有限かどうか

置いた石は途中で取り除かれることはないので、交互に打っていけば、空きマスが全て埋まるか双方パスするかで必ず終局する。したがって有限なゲームである。

初形の空きマスは60個あるが、これらが全て埋まるまでに何回かパスが入ることがある。その最大回数は何回か? という問題を思いついたのだが、これは解かれているのだろうか。あるいはほとんど同じ問題で、パスも1手と数えるときの終局までの最大手数は? 調べた限りではわからなかった。なんとなく検証が大変そうなので、解かれていない(あるいは誰も興味を持たない)のかもしれない。

3. 結論の出ているケース

オセロは「二人・零和・有限・確定・完全情報」という条件を問題なく満たしているから、双方が最善を尽くせば「先手必勝」「後手必勝」「引き分け」のいずれかであるかはあらかじめ決まっているはずである。しかし変化の数が多すぎて、コンピュータを使っても全ての変化を調べ尽くすことはできず、結論はまだわかっていない。

盤をひとまわり小さくした6×6のオセロでは結論がわかっていて、双方最善を尽くすと図のような手順で白の4石勝ち(黒16 vs.白20)になる。

つまり6×6オセロは後手必勝で、図が双方の最強手順である。黒がこれ以外の手順できても、白はうまく打てば必ず4石以上勝つことができる。これを発見したJoel Feinstein氏のレポート(1993年)が以下にある。

• Perfect play in 6x6 Othello from two alternative starting positions (Othello Pages)

ここでは400億個の局面を2週間かかって探索したとある。そのあと、速いコンピュータを使えば一晩で計算できる、とあるのを別のところで読んだのがもう何年も前のことなので、今ならちょっと速めのPCで効率のよいプログラムを走らせれば数時間で結論を出せるのではないだろうか。

上記ページには、6×6オセロの初形として黒白たすき掛けではなく「二」の字に黒白どちらも横に並んだ形から始めた場合(こちらの方が局面の数がずっと多く、1000億個を5週間かけて探索したとのこと)の結論も書かれていて、黒17 vs.白19でやはり白の勝ちである。

4. 結論を推測する材料

6×6オセロの結論が「後手勝ち」であるのはある意味妥当だそうである。というのは、オセロは本質的に「マイナスの手」(ここでは「パスした方がましな手」という意味)が多いゲームだからである。

例えばセオリーとして「隅を取った方が有利」ぐらいを知っているだけの初心者だと、序中盤からなるべく相手の石をたくさん取ろうとしてしまう。そうしているとだんだん自分の石がダンゴになり、終盤になるに従って石を置けるところが少なくなって悪手しか打てなくなる。我々ヘボのレベルでも何度かやってみると実感できる。終盤に悪手しかない手詰まりの状態になるというのは、将棋などではおよそ起こり得ないことである。

オセロには「一石返し」という手筋があって、中盤までは相手の石を1個だけはさむようにするのがよい(少なくとも大悪手にはならない)ことが多いらしい。ガマンしてなるべく1個だけはさむようにしていると(石橋流)、中盤までは自分の石の方が少なくなるが、終盤に相手が手詰まりに陥って大逆転(局面の評価としての逆転ではなく、数の上で逆転したという意味だが)という気持ちのよい展開になることがある。上記Joel Feinstein氏も"Too many pieces can be bad for you!"というページで、中盤までで相手の石を多く取ろうとすることを戒めている。

ちなみに、上の「6×6オセロ最強手順」で相手の石を返す数を見てみると、序盤・中盤ともに1石返しよりも2石返す手の方が多い。「石橋流」を貫けばいいというものでもないらしい(当たり前か)。

私のレベルではこれくらいしか解説できないが、オセロというのは相手に悪手を打たせるゲームで、「ここで自分だけ1回パスできれば勝てるのに、パスできないために負け」という局面がよく出現するはずなのである。そして6×6オセロでは初形がまさにそういう局面だということになる。初形は黒白対称なので、初手だけ黒がパスすることができれば白が先手になったのと同じことになる。そのあと最善を尽くせば黒が4石以上勝てるわけで、黒の初手は「打ちたくないマイナス手」なのである。

とすると8×8オセロの結論もやはり白の勝ちなのだろうか。はっきりしたことは誰にも言えないにしても、強い人の実感はどうなのだろう。8×8オセロにおいてトップレベルの人間もしくはコンピュータの白と黒の勝率はどのくらいなのかをWebで調べてみたのだが、「オセロの黒と白は互角」とか書いてあるページばかりでわからなかった。誰かが統計をとっているはずだと思うのだが。

(つづく)

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

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

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

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

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

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

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

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

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

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

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

[参考ページ]

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

(つづく)