Hatena::ブログ(Diary)

物理学と切手収集 Twitter

2017-05-15 elmoとPonanzaの力関係

ちょっと遅れましたが、アンケートをやってみて面白かったので少し解説してみます。


アンケートはこれです。



まず少し背景から。


5月3~5日に世界コンピュータ将棋選手権が川崎で開催されていました(第27回世界コンピュータ将棋選手権)。Ponanza*1は、3連覇を狙っていたプログラムで、大方の予想でも本命とされていました。一方elmoは新参加で、Ponanzaに二次予選でも決勝トーナメントでも勝ち、優勝したプログラムです。


「2局の結果から何が言えるか?」というのが質問で、結論から言うと多分25~50%が一番ありそうな所で、75%以上はあまりありそうにないという風に考えていますが、どういう風に考えてそうなるのか書いてみます。


この問題をどう考えるのかは、前提知識によって違ってくる、というのが重要なポイントになります。

予備知識がゼロの場合


まずコンピュータ将棋どころか、将棋についても予備知識が無く、どういう性質のゲームなのか分からない場合を考えてみます。


この場合、elmoとPonanzaが対局する前にはelmoが勝つ確率は全くの謎です。なので、0%から100%まで同じくらいありえそう、という前提から入ることにします。この時に考えられるelmoの勝率の分布(事前分布)はこう。


f:id:hundun2:20170514203424p:image:w360


elmoとPonanzaの対戦結果などの新情報が入るたびに、ベイズの定理に従ってこの分布を更新する、というのがベイズ統計の考え方。elmoがPonanzaに2勝した場合には、この分布にxの2乗を掛けて*2、分布の下の面積が1になるように正規化すると、事後分布の出来上がり。新情報を組み込んだ確率分布になります。


f:id:hundun2:20170514204214p:image:w360

(青は事前分布、赤が更新後の事後分布)


この場合の事後分布はシンプルで、3x2です。当然のように、elmoの勝率が高い確率が高くなります(この話はずっと「確率の確率」なのが少しややこしいですが避けようがなさそうです)。アンケートで出て来た区間ごとに分布の下の面積を計算すると、


区間確率
0~25%1.6%
25~50%10.9%
50~75%29.7%
75~100%57.8%

となって、実際の勝率が75~100%の区間にある確率が一番高くなります。

大差は付いていないと仮定した場合


「対戦情報以外に何も知らない」というのは、実際とかけ離れています。elmoとPonanzaという特定のプログラムについて何も知らなかったとしても、この2つのプログラムはどちらも選手権の決勝に出て来るレベルのものです。この場合には、「どっちが上かは分からないけれど、95%とか5%みたいな一方的な勝率はあまり無いだろう」、というのはリーズナブルな仮定です。そこで一例ですが、こういう事前分布から始めてみます。


f:id:hundun2:20170514204215p:image:w360


elmoの勝率が10%以下の確率も、90%以上の確率も約10%という仮定です。ここからさっきと同じように2勝0敗の対戦結果を組み込んで事後分布を計算するとこうなります。


f:id:hundun2:20170514204216p:image:w360


この場合には、elmoの勝率が50~75%の範囲に入る確率が50%くらいになっています。75~100%まで上がる確率は25%弱。つまり、「どちらが強いかは分からないけれど、どちらかが圧倒的に強い事はないだろう」という仮定から始めると、50~75%が恐らく妥当なアンケートの選択になります。

Ponanzaが有利だと考えていた場合


実際の状況をもっとよく知っていた場合を考えてみます。今回の大会のelmoとPonanzaの直接対決以外の情報で、勝率を推測するのに使えそうな情報はこの辺です*3


  • Ponanzaは2連覇中。今年のプログラムは去年のプログラムとの対戦では8割ほどの勝率
  • elmoは新参加。強豪プログラムのコードを利用して作られているとはいえ、この強豪プログラム自体はPonanzaほど強くはなかった。
  • 直接対決以外ではPonanzaは全勝。
  • elmoは2次予選で技巧に負けた以外は全勝。
  • PonanzaはGPUを大量に使うなど、マシンのスペックでelmoより上。
  • 人間の間の前評判では、Ponanzaが圧倒的有利という話だった。表彰式でのelmoの瀧澤さんと、Ponanzaの山本さんのやりとりが分かりやすい。


要するに、elmoの勝率の事前分布は、少ない方にピークがあるものだったはずなわけです。例えばこんな感じ*4


f:id:hundun2:20170514204217p:image:w360


elmoの勝率は2割くらいじゃないか、という前提です。山本さんの「10%も行かないんじゃないですか〜」は誇張が入っていたかもしれませんが、もう少し自信満々に、低い勝率に高いピークがある分布で考えてたんじゃないでしょうか。僕はそんな詳しくないのでこれくらいでやってみます。


f:id:hundun2:20170514204218p:image:w360


すると、25~50%の勝率になる確率が50%くらいになりました*5。まだPonanza有利ですが、elmoが勝ち越す可能性も結構ある、という結論になります。


もっと自信を持ってPonanza有利を予想していた人なら、elmoの勝率が50%を超えている可能性はあまり無さそう、と言っているでしょう。「まだ25%以下」と考えている人も結構いるのは、アンケート結果から分かります。

最後に


elmoが2勝した、という情報だけからだと、elmoの勝率は結構高いんじゃないか、と思わせるアンケートでしたが、他の情報を利用するとそうとも言えなくなってきます。持っている情報と、その情報をどういう風に評価するかによって事前分布は変わるもので、最終的に考えるelmoとPonanzaの力関係も変わってくる、というのをかなりアバウトにですが示せたかと思います。


あと、1回や2回の勝負では、多くの人間が思うほど極端に分布が変わるわけではない、というのも言えると思います。これは例えば、スポーツの1試合の結果で結論めいた話をするのは危険、みたいな応用も出来ますね。


追記


Ponanzaの山本さんが、(主に自分の研究・開発のためでしょうが)対戦させた結果をブログに書いてます。


電王戦2017最終局前夜 - 山本一成とPonanzaの大冒険


引用

「あとで検証したところ、Ponanza173勝 elomo89勝 4引分 勝率65.8%でした。(対局条件は10秒秒読み・Xeon24core ・定跡なし・クラスタなし・Deep Learning未使用)なかなか公平な対局条件をつけるのは難しいですが、まだなんとかPonanzaのが強そうと言えそうですね。」


大会と同じ条件ではないのでアンケートの答えが確定したかのような話にはなりませんが、大会と比較してどちらかが明らかに有利になる、という比較にも見えません*6。elmoの勝率が25~50%という可能性は高くなったと思います。

*1:今回の登録名はPonanza Chainer

*2:x2がこの観測結果に対応する尤度関数Wikipedia記事)。偶然にも、Wikipediaの「簡単な例」がピッタリ同じ話です。一般には、elmoとPonanzaの対戦成績がa勝b敗だった場合、尤度関数はxa (1-x)bになります。

*3:コンピュータ将棋関係者、特にelmoとPonanzaの開発者さん達はもっと色々挙げられるでしょうが、遠くから見てるような自分でも分かるような情報から考えます。

*4:これもただの一例です。

*5:ここでさらに言うと、対局内容(多分特に定跡の選択)から、詳しい人ならもう少し細かい更新ができるでしょう。

*6:この情報をどう料理するのかも人それぞれでしょうし、それはそれで問題無いわけです。