ビルゲイツの面接試験 - じゃんけん編

Life is beautifulのhttp://satoshi.blogs.com/life/2007/03/post_16.htmlより。おもしろそうなので回答してみる。みなさんも是非。

あなた（＝Aさん）とBさんにジャンケンを連続で１０００回してもらいます。あなたもBさんも、パーで勝つたびに５００円、チョキで勝つたびに２００円の賞金を主催者からもらえます。グーで勝ったり、アイコになった場合には一円ももらえません。この条件で、あなたの賞金を最大化するために、どんな戦略を採りますか？ただし、Bさんと前もって相談することはできないし、試合中はしゃべったり身振りで合図を送ってはいけません。表情も見えないように、ミラーガラスのヘルメットを被ってもらいます。試合中に見えるのは相手が何を出したかだけです。

回答。
相手の出した手を記録しておく。まず初めの1回はランダムで33%ずつグー，チョキ，パーを出す。その後の999回は相手はいままでと同じ確率でそれぞれの手を出すと仮定し，そのそれぞれの手に勝つ手を同じ確率で出す。
たとえば200回目終了時点で相手が100回グー，66回チョキ，33回パーを出してきていたとしたら，201回目の自分の手は50%の確率でパー，33%の確率でグー，17%の確率でチョキを出す。

これが一番だと直感的には感じたわけだが，初期のランダムで出す回数(上の回答では1回)やその間の各手の確率の値(上の回答ではどの手もそれぞれ33%)によってまだましになるかもしれない。
改良していくと，1回ずつの相手の手の確率だけでなく連続する2手，3手の統計的確率から自分の出すべき手がわかりそうだが，1000回という制限つきなのであまり効果はあがらなさそうだ。

追記 考察

一日中頭の片隅で考えていたのだけれど、この問題の悩みどころは勝ち手は自分では決められないことに尽きる。勝ち手によって報酬の差はあるものの、

1. 1. 勝てば報酬はあるが、罰はない
   2. 事前に勝ち手を決めることはできない

の二条件があるかぎり勝ち手による報酬が500円と200円と0円どころか100億円と10円と0円でも、逆に100円と100円と100円でも結局のところ同じであり、普通のじゃんけん必勝法を考えることになってしまうようだ。

google:じゃんけん 必勝法

考え直し

前言撤回。0円の手で勝っても仕方がないから、基本は上と同様で、

相手の出した手を記録しておく。まず初めの1回は71%の確率でパー、29%の確率でチョキを出す。その後の999回は相手はいままでと同じ確率でそれぞれの手を出すと仮定し，その手に勝つ手をグー、チョキ、パーに5:0:2の重みをつけた確率で出す。
たとえば200回目終了時点で相手が100回グー，66回チョキ，33回パーを出してきていたとしたら，201回目の自分の手は89%*1の確率でパー，0%の確率でグー，11%の確率でチョキを出す。

こちらの方がよいような気がしてきた。重みづけは報酬に応じて。

それにしてもこの問題、考えれば考えるほどわからなくなってくる…。いい問題だ。

*1: