パズルの国のアリス

運試しのような神経衰弱(解答)

坂井 公(筑波大学)題字・イラスト:斉藤重之

解答例 カードが2n枚残っていて,そのうちk枚が既知だとする。既知のk枚の中にマッチするカードはない(あるならばその2枚を取ってから考えればいい)。当然,k≦nだ。

グリフォンが授けた秘策は「未知のカードをめくり,それが外れ(既知のカードとマッチしない)なら,n-kが奇数のときはもう1枚は既知カードを選び,偶数のときは2枚目として未知カードをめくる」というもの。

このやりかたは厳密には最善ではないが,驚くべきことに,ほとんどのケースで得点期待値が最も高くなる。以下に詳しく解説しよう。

一般に神経衰弱では,自分の手番で以下の3つの戦略を採れる。

戦略0 2枚とも既知のカードを選ぶ(パスと同じ)戦略1 未知のカードをめくり,それが外れならもう1枚は既知のカードを選ぶ(相手の得にさせないため)戦略2 未知のカードをめくり,それが外れでももう1枚を未知のカードから選ぶ

このほかに,最初に既知のカードを選び,もう1枚を未知のカードにするという方法もあるが,明らかに戦略1より劣るので考慮に値しない。

どうやら帽子屋はもっぱら戦略2をとっているようだが,まずどちらも最善を尽くした場合の戦略を検討しよう。そのときの手番のプレーヤーの得点期待値をf(n,k)とする。まず戦略0をとるかどうかが最初の戦略分岐点になる。これについて考察してみよう。

戦略1か2をとるとする。未知のカードをめくって,それが既知のカードのどれかとマッチする確率はk/(2n-k)だ。マッチした場合,得点を得て,以後の得点期待値はf(n-1,k-1)となる。一方,1枚目が既知カードとマッチしない確率は(2n-2k)/(2n-k)で,既知カードはk+1枚になり,2枚目も未知カードをめくるかどうか(戦略1か2か)の戦略分岐点になる。そこからの得点期待値をg(n,k+1)としておこう。以上より戦略0をとらなかった場合の得点期待値をf+ とすると,f+ は下の数式1の漸化式となる。

  

当たり前だが,k=n(ペアの一方がすべて既知)のときf+(n,k)=nとなる(残りのペアをすべて取れる)ことが数式1より得られる。k<nの場合はf+ の値を知るのにgの値が必要になる。戦略0はパスと同じで,手番を相手に渡すことになり,期待値は正負が逆転する。よって,f+>0 ならば戦略0は採用すべきでない。したがってfの値は,一般にはf+(n,k)=max(0,f+(n,k))となる(maxは大きい方の意味)。しかし,カードは最低2枚選ぶので,既知のカードが1枚や0枚の場合(k=0,1)の場合は戦略0は採れない。以上を整理すると,次のようになる。

f(n,0)= f+(n,0)f(n,1)= f+(n,1)f(n,k)= max(0,f+(n,k))(ただしk≧2)

次は手番での2枚目のカードのめくり方にかかわるg(n,k)を考えよう。

まず戦略2を採った場合,第2のカードが1枚目のカードにマッチする確率は1/(2n-k)で,得点1を獲得し,その後の期待値はf(n-1,k-1)。また,第2のカードが他の既知カードにマッチする確率は(k-1)/(2n-k)となる。この場合,自分はそのペアを取れないだけなく,次の手番で相手が取ることになるので,得点は-1で,その後の期待値は-f(n-1,k-1)となる。さらに第2のカードが,既知のどのカードにもマッチしない確率は(2n-2k)/(2n-k)で,その場合も,手番は相手に移るのでその後の期待値は-f(n,k+1)となる。以上より戦略2をとった場合の期待値g+ は下の数式2のようになる。

  

一方,戦略1を採れば,単に手番が相手に移るので,その場合の期待値は-f(n,k)となる。普通はこのうち有利な方を採用するが,既知のカードが1枚だけの時は戦略1は採れないので,一般にはgは次のようになる。

g(n,1)= g(n,1)

g(n,k)= max(g(n,k),-f(n,k))(ただしk≧2)

この漸化式の計算にはエクセルなどの表計算ソフトが便利だ。実際にf,f+,g,g+を計算すると下の表のようになる。赤い数字は負の値を示す。

 

最終的に戦略を決めるにはfとgの表だけを見ればいい。fの表の水色のマスは戦略0が有利になる状況を表し,gの表の緑のマスは1枚目が外れた場合に戦略1が戦略2よりいい状況をあらわす。最善の手を打つにはこの表に従う必要があるが,ヤマネがそれを覚えられるはずもない。おそらくグリフォンからの忠告は,gの表に基づいたもので,「未知カードを開いてみてそれが外れだったなら,n-kが奇数のときは戦略1,偶数のときは戦略2」という程度のものだったろう。戦略0が有利な状況はまれだし,戦略1と戦略2の選択に関しては,ほとんどすべての場合がこれでカバーされる。

 

戦略0を禁じ手にすると

戦略0があると,双方にとってそれが最善の場合には,ゲームが進まなくなってしまうし,そもそも不自然な手だ。戦略0を禁止するとどうなるだろう。この場合,常にf =fとなるので,計算しなおすと上の表のようになる。重要なのはgの表で,緑マスが戦略1を採るべき状況を表す。戦略0があるときと同様,n-kが奇数の場合に戦略1を採ることにしておいても,あまり悪い結果にはならないだろうが,(n,k)=(7,2),(8,3)の周辺では戦略が逆転することを覚えておくと,より有利にゲームを進めることができる。

帽子屋が戦略2しか採らないなら,ヤマネにはもっと有利な戦略があるが,複雑になるので省略する。興味のある読者は挑戦してみられたい。

実はこのゲームは日経サイエンス1991年12月号の「数学レクリエーション」でスチュアート(Ian Stewart)が書いたことがある。覚えのある読者もいるかもしれないが,同じ問題をあえて取り上げたのは,奈良女子大学の篠田正人(しのだ・まさと) 准教授による最近の研究に触れたかったからだ。

篠田氏の研究は,残りペア数nと既知枚数k以外に,それまでに獲得した得点差sを加味した戦略だ。この場合,最終的な得点差は意味がなく,相手より多く得点すれば勝ちで,同得点ならば引き分けになる。よって,戦略0をそのときに負けている側が採用することはないので,互いが戦略0を繰り返すことによる手詰まりがめったに生じない。一方,その時点で勝っている側が戦略0を採ることはあり得る。戦略全体はかなり複雑になるので,詳細は下記を参照されたい。

 

 

参考にした本:「神経衰弱の確率」篠田正人,大学への数学2008年7月号Winning Strategy of the Memory Game,篠田正人,第13回ゲーム・プログラミングワークショップ2008

 

 

 

 

 

問題はこちらです