Codeへの愛とCuriosity

CodeIQ への出題・解説解題・その周辺について、思いつくままに。

CodeIQ に出した「JavaScriptじゃんけん大会!」の解説・解題

CodeIQ に「JavaScriptじゃんけん大会!」( https://codeiq.jp/ace/nabetani_takenori/q888 )という問題を出した。
挑戦の募集はすでに締めきっている。
というわけで、解説・解題。

で。
まずは問題

問題

■問題
JavaScript によるじゃんけん大会を行います。
じゃんけんプログラムを作成し、優勝を目指して下さい。

■ルールの詳細
・挑戦者全員で総当り戦を行います。
・各プレイヤーは、自分以外のすべてのプレイヤーと1回ずつ戦います。この戦いを「マッチ」と呼びます。
・1回の「マッチ」は、100回の「じゃんけん」によって構成されます。
 ※ あいこも1回のじゃんけんに数えます。
・じゃんけんの結果、グーで勝つと17点、グー以外で勝つと10点の得点が入ります。
・あいこと負けの場合は得点が入りません。
・100回じゃんけんを行い、得点の合計が多いほうが「マッチ」の勝者となります。
・「マッチ」に勝つと、30010点の勝ち点が入ります。
 引き分けは10001点、負けは0点です。
・勝ち点の合計を競います。勝ち点の合計が最も多いプレイヤーが優勝です。

■じゃんけんのインターフェース
WebWorker の仕組みから呼ばれます。
「マッチ」が始まると WebWorker が newされ、「マッチ」が終了すると terminate されます。
「じゃんけん」のたびに、postMessage されますので、addEventListener に登録した関数で受けて、postMessage で返して下さい。
渡ってくるデータは "GCPGCP,PPGGPP" のような文字列で、addEventListener に登録した関数 の引数の data プロパティに格納されています。
文字列の形式は
 あなたが今まで出した手 + ", " + 相手が今まで出した手
です。G がグー、Cがチョキ、Pがパー を示します。
あなたが出す手を決めたら self.postMessage( "G" ) のような形で通知し、即座に関数を抜けて下さい。

■実行方法とサンプルコード
jangkeng.zip をディレクトリ付きで展開し、Firefox 29 で jangken_runner.html を開くと、総当り戦が実行されます。
Your Code.js の中身を書き換えて勝てそうなプレイヤーを作って下さい。
Your Code.js 以外にもサンプルコードが入ってますので、それも参考にして下さい。

■詳細と注意事項
・複数回投稿した場合、最後のものが有効になります。
・締め切り前でも投稿内容を公開して構いません。
  ※もちろん、他のプレイヤーが対策可能になるので本番用とは別のものを公開することをお勧めします。
・実行は Firefox 29 で行います。
・何度実行しても同じ結果が出るようなプログラムを書いて下さい。日付(Date)や JavaScript に組み込まれた乱数(Math.random) 等を利用してはいけません。
・じゃんけんの勝敗の数や、得失点差は順位に影響を与えません。勝ち点のみで評価します。
・ネットワークへのアクセス、DOMへのアクセス、他のプレイヤーのソースコードや結果へのアクセス、ファイルシステムへのアクセスは禁止します。
 つまり、importScripts や XMLHttpRequest などは禁止です。
・あまりにも可読性が低い場合(難読化/minify されている場合など)は、失格とします。
・処理時間があまりにも長い場合は失格とするかもしれません。
・失格にならなかったコードは、コメントや挑戦者名とともに拙ブログ( http://nabetani.hatenablog.com ) や http://nabetani.sakura.ne.jp/codeiq/jsjangkeng/ で 全て公開されます。

■解答形式
あなたの書いた JavaScript のコードを下記フォームに入力し、送信して下さい。
jangkeng.zip に同梱されている「Your Code.js」の形式に従い、JavaScript のコメント内に以下の項目を書いて下さい。
・プレイヤー名
・感想など

こんな感じ。

この問題を出した時点では Firefox 29 だったんだけど、今は Firefox の最新版は 30。もちろんそれでも問題ない。

出題の背景と意図とか

挑戦者同士の総当り戦をやったら楽しいだろうと思い。
じゃあサンドボックスを用意して ruby で、と思ったんだけど、サンドボックスの準備が面倒そうだったので、ブラウザ上で WebWorker という選択をしてみた。

期間が3週間ぐらいしかないし、そんなにこのゲームに時間を割いてもらえるわけでもないと思い、極力簡単なものをということで、じゃんけんに。

グーで勝つと他より有利 というルールをいれて、対称性を崩して考えやすくしたつもり。

ゲームの理解

絶望からのスタート

真剣に取り組んだ方はお分かりと思うんだけど、突き詰めて考えると、どうしようもないということがわかる。
どんなプログラムでもそれに勝つプログラムが存在するので、必勝法がない。
何が優勝するのかは他のプレイヤーがどうなっているのかに依存する。
他のプレイヤーの戦略を知る方法がないので、勝つための道筋がない。

さらに。
サンプルの中に、Amazing Opossum というやつがいて、これが結構強い(強かったでしょ?)。
強いのはまあいいんだけど、Amazing Opossum のアプローチはこのゲームの正解じみた内容になっているのが厄介だと思う。
Amazing Opossum のことは参加者全員知っているので、これに勝てるのは当然というところからのスタートになる。
さてどうするか。

予測して勝つ

これはじゃんけんなので、相手の手がわかれば勝てる。
ということで、相手の手を予測したい。
Amazing Opossum のアプローチはひとつの正解だと思うが、まだまだやれることはある。
参加者は全員 Amazing Opossum を見てから来るので、 Amazing Opossum 自身や、それに類する戦略を予測する必要があるだろう。
どう予測するのかは非常に難しいし、正解のない部分だと思う。

予測されないようにする

予測されてしまうと負けるので、予測されない努力もするべきだろう。
特に前半は予測の材料がないのでランダムな手を出して様子をうかがうのがいいかもしれない。
もちろん、敵もそうしているかもしれない。
で。
ここで「ランダムな手」とはなんなのかが問題となる。

ランダムな手を出す

その意味で、G, C, P を同じ確率で出すという戦略は一見均等で中立的に見えるが、グーしか出さない人に負けてチョキしか出さない人に勝つので、このゲームの勝敗という観点からは中立的ではない。
中立的にするためには、G:C:P = 10:10:17 の割合で出せば良い。
この割合なら、相手が何を出しても期待値が0点になる。
たぶん、ゲーム理論用語の「ナッシュ均衡」なんだと思う。

確保できる勝ちを確保し、不用意に自ら負けを確定させない

99回までじゃんけんが済んでいて、得失点差 12点 で勝っている状況を考える。
この時にチョキを出すと、相手がグーを出した場合に負けてしまうが、チョキ以外を出せば勝ちが確定する。
逆に 12点差で負けている場合。
グー以外を出したら逆転の見込みがないので、相手の手によらず負けが確定してしまう。
というわけで、残りのじゃんけん数と得失点差に注意をはらうべきである。
確保できる勝ちはきっちり確保すべきだし、不用意に自ら負けを確定させるべきではない。
じゃんけんという曖昧でどうしようもないゲームではあるけれど、このフィーチャーだけは入れておいて損はない。

このフィーチャーが入っていることがすごくよく分かるのが以下の一戦 :
Mega Charizard X vs arthor
前半は Mega Charizard X さんが相手の手を的確に予測してチョキを出し続けている。
Mega Charizard X さん が勝ちを確信すると、あとは相手に勝つことではなく、得失点差 -17 を喰らわないことだけに注力するようになる。相手との差が縮まるが、計算の上でのことなのでぎりぎり勝つところで100回を終える。
見事。

結果

結果は http://nabetani.sakura.ne.jp/codeiq/jsjangkeng/ に上げてある。
優勝は R Fighter さんになった。おめでとうございます。
とはいえ。
他の参加者の人数比によっては優勝は carrotflakes さんになるわけで、本当に僅差だったと思う。

私と JavaScript と WebWorker と ブラウザ

JavaScript についての問題を出したんだけど、実は私は JavaScript のことをよく知らず、WebWorker に至っては生まれてはじめて書いた。
へーこういう仕組みなんだぁ、という気持ち。
私なりに誠実に書いたんだけど、手本とすべき内容になっているとは思わないので、素直にお手本にはしないでほしい。

それと。

競技場は、 HTML を開いた時点ですべての対戦についての WebWorker が走りだすという凶悪な仕様になっている。
現状 38人のプレイヤーがいるので、703組の試合が(論理的には)同時に走りだし、1400以上の WebWorker が同時に動く可能性がある。Firefox の場合はそれでもち最後まで計算が進むのだが、
SafariChrome は死んでしまう。( Opera は途中でやめるみたい。IE は未調査。 )
同時に走る WebWorker の数を制限するコードを入れればよかったのかもしれないけど、そのままにしてしまっている。

最後に

今月中に次の問題を出す予定(作成中)なのでよろしくお願い致します。

宣伝

第22回 オフラインリアルタイムどう書く( http://yhpg.doorkeeper.jp/events/12339 ) やります。7月5日(土) 横浜。
お暇とご興味のある方は是非。
ぬるいイベントなのでお気軽に。