第19回世界コンピュータ将棋選手権
第19回世界コンピュータ将棋選手権が5月3日〜5月5日の日程で開催されている。
第19回世界コンピュータ将棋選手権
http://www.computer-shogi.org/wcsc19/
中継ページ
http://homepage.mac.com/junichi_takada/wcsc19/
■ 漫遇将棋
長年にわたる人工知能研究の成果を生かし、従来型のソフトより人の脳の働きに近いのが特徴。
状況判断力が高く奇策にも強いといい、稲垣准教授は「将来の目標は打倒・羽生善治４冠。
改良を加え、ハブキラーの『将棋マングース』として、いつか勝利を収めたい」と意欲を燃やしている。
プロに勝てる？ 京都大準教授が新型将棋ソフト
http://sankei.jp.msn.com/life/trend/090409/trd0904091318003-n1.htm
どんなソフトかなと思っていたら、初手78銀。そのあとの漫遇将棋の指し手だけ書くと、26歩、58玉、68金、27飛。弱い。弱すぎる。おそらく20級程度。
しかも3回戦では、持ってもいない角を打っての反則負け。「角を角し持っていたとは」「漫遇、強くなる前にイカサマを覚えたのか」などと2chでは盛り上がっている模様。漫遇将棋の人気ぶりに嫉妬
しかし、よくこんなので大会に出ようという気になったなぁ。それ以前に、よくあれだけのプレスリリースを出したなぁ…。この開発者、将棋のルール本当に知ってんの？というレベル。まあ、今後に期待というところかな。
続報によりますと、
昨日今日と他の開発者の方に直接会って話が出来たんで、その辺のことをチラッと書いときます。
漫遇将棋は事前予想とは違い結果が振るわなかったのですが、どうも例の記事は記者の人が誇張してと言うか煽ってと言うか、そういう感じで書いた結果だそうです。学習に関しては色々思う所がある様で、「学習ではなく進化を実現したい」という風な事をおっしゃっていました。
一次予選終了(GA将!!! 作ってます)
http://d.hatena.ne.jp/streakeagle/20090503
だそうです。
■ Bonanza 4.1.1
BonanzaのCSAライブラリ版(大会で使って良いライブラリ)が、4.0.3から4.1.1にバージョンアップした。評価関数で利用しているテーブルの値に変更があったようなのだが、レーティングで100点ぐらい向上しているらしい。
Bonanza 4.1.1 は評価関数だけでレーティングが100点向上？
大会直前ですが、BonanzaのCSAライブラリ版が4.0.3から4.1.1に変わっています。
http://www.computer-shogi.org/library/保木さんによると、4.1.1に含まれるバイナリ fv.bin はより深い最善応手手順を
求めて作った評価関数とのことで、YSSwithBonaでも実験してみました。
コンピュータ将棋や囲碁の掲示板(YSSと彩のページ)
http://524.teacup.com/yss/bbs
このBonanza 4.1.1は、Bonanzaメソッドでの学習のときの「1手＋静止探索」を「2手＋静止探索」に変更したものらしい。
この「N手＋静止探索」のNを増やしていけば学習に時間はかかるようになるがまだ伸びしろはあるということなのだろう。
どこでサチる*1のかは興味深いが、Nを増やすに従って指数関数的に学習に時間がかかるようになるので、いまのところN=3か4ぐらいまでが限界なのかな。
これこそ、スパコンを使うか、grid computingなんかで学習させて欲しい気もするけど。まあ、N→∞でも、いまよりR200〜300ぐらい伸びればいいほうのだろうから、そんなに力を入れてやることでもないのかも知れないが。
あと、「探索速度 YSS 約350000局面/秒 YSSwithBona 100000局面/秒」で、Bonanza 4.1.1の評価関数は重く、YSSの1/4ぐらいの局面しか探索出来ていないらしいのだけど、それで互角以上というのも興味深い。
■ A級リーグ指し手1号
FPGAを用いて、桁違いの探索速度を実現しているのは、A級リーグ指し手1号。
学習はソフトのモデル（「Cモデル」…C++だけど）を使ってやってまして、
ここではパラメタはすべてfloatにしてます。微分を計算しやすいので。が、
ハードではfloatなんてないので値を「量子化」しなくてはなりません。
9.67とかいう値になってても、シフトで1/2/4/8/...倍しかできないから8に
しようとか、3bitに収めたいから7にしようとか普通にやってます。何やっ
てるのかわからん気もしますが、でもしょーがないしねぇ。この量子化の
作業は各パラメタによって微妙に事情が変わるので、いちいち手作業でや
ってます。ソフトの方はおそらく半自動でできてるのでしょうが、ハード
では苦労するとこの一つです。
Ａ級リーグ指し手１号
http://aleag.cocolog-nifty.com/blog/2009/02/post-8d63.html
FPGAでは巨大なメモリは使えない。例えば、A級リーグさんが今回使用しているAltera DE3*2では、外部メモリとしてDDR2 SO-DIMMは使えるが、このメモリへのアクセスは非常に遅く、普通のPCでのメモリよりさらに遅いのでFPGAの利点が生きなくなってしまう。
結局、大きなテーブルは使えず、なるべくシンプルな評価関数にするしかない。9.67という値をシフトで済むように8にしているなどというエピソードは仰天ものだが、こんないい加減な数値精度でも探索速度が桁違いであれば、それなりの強さになるのが将棋というゲームの面白いところだと思う。
■ 特徴因子を増やすということ
初代Bonanzaから、4.1.1に至るまでに特徴因子は少しずつ増えてきた。特徴因子を増やすと評価に時間がかかるようになり、大雑把に言えば、探索できるノード数は特徴因子の数に反比例するような形で減る。
現状のBonanzaを見る限り、探索ノード数が減ったとしても特徴因子を増やして行ったほうが強くなるようだし、まだサチっていない。
ところが、テーブルが大きくなると頻繁にアクセスする必要のあるデータがL2 cacheに載らなくなる。L2 cacheに載らなくなると急激に探索できるノード数が低下して弱くなる。昔のノートパソコンで走らせた場合、最新版のBonanzaより初代Bonanzaのほうが強いことがあるのはこのためである。
結局、特徴因子はもっと増やしたほうが強くなるが、テーブルサイズは頻繁にアクセスするデータがL2 cacheに収まるサイズにしなければならないという制約がある。
だから、今後、プロセッサが進化してL2 cacheが増えるごとに特徴因子を増やすというチューンをしていくことになる。
たぶん、(このL2 cacheの進化に合わせてテーブルサイズを拡大するというのは)Bonanzaメソッドで自動学習しているソフトにとっての定石となるだろう。
■ 文殊
合議制を採用しているらしい文殊。
文殊の中の人と話したら ６個のBona.4.1.1のfv.binに適当に乱数を与えて それぞれの探索結果を合議しているらしく 「保木さんいわく、共謀数探索に近いことになっているのでは？」 とのことらしい
文殊の話(毎日がEveryDay！)
http://d.hatena.ne.jp/issei_y/20090502/1241264336
これでもとのBonanzaより強くなっていれば素晴らしい成果と言えると思うが、弱くなっていたら何をしてるかわからない。
それから台風の目、文殊。4コア×2プロセッサのマシンを3台使い、4コアずつ使う探索ルーチンが6つでの合議制だそうです。今の方式もまだ実験中で、色々とやり方は検討されているみたいでした。
一次予選終了(GA将!!! 作ってます)
http://d.hatena.ne.jp/streakeagle/20090503
合議制で、それぞれのマシンが異なる結果を出した場合などは、読みが安定していないので、もう少し時間を費やして深く読んだほうが良いだとか、持ち時間の調整には使えるのかな？
YSSの山下さんが、激指、Bonanza、AI将棋、新東大将棋の合議将棋で
合議は単独よりもやや強い（勝率0.54程度、レーティングで40点？）とのことで
個人的には序盤の悪手が減っているような印象でした。
と言っていたので、うまくすれば、それなりに意味はあるのかも。
【5月4日追記】
文殊の開発を行なっている電気通信大学、情報工学科伊藤研究室でアルゴリズムの解説記事が公開された。
合議アルゴリズムと文殊のページ
http://homepage1.nifty.com/ta_ito/ito-lab/gougi/gougi.html
■ 並列化効率は√Nよりいいのでは？
Nコアでの並列探索のときの効率は、おおよそ√N台分ぐらいの向上になると言われているが、実際は、これより少しいいんじゃないかという話がある。
よく、１スレッドでの nps が T で、並列化で n スレッドになると、実効 nps は (√n) * T 相当になると言われていますね（全てのスレッドが T nps で動く場合ですけど）。その計算だと、８スレッドでも４スレッドでもほぼ同じ強さということになりますか。意外に好成績。
ただし、実効 nps はもう少し高いという説もあります。第15回選手権に山下さんが YSS を４スレッドにされて、１スレッドの 2.2 倍相当の棋力になったと言われていましたし、昨年のＧＰＷのときだったか、大槻さんも (√n) よりも大きいと思うと言われていましたし、私自身も (√n) よりも大きいと感じています。
Core i7 マシンで(マイムーブ)
http://chocobo.yasuda-u.ac.jp/~nisimura/mymove/index.cgi?no=1715
本当のところ、よくわからないが、これがもし本当だとすると「マルチコア化が進んで32コアぐらいになってもコンピュータ将棋の強さには影響しない」説は覆ることになる。
また、32コアぐらいになるとさきほど書いたBonanzaメソッドの「N手＋静止探索」での学習がしやすくなる。(学習は並列化できるから) そして、そのころにはL2 cacheのサイズも桁違いに大きくなっているだろうから、評価関数で使うテーブルサイズ自体も大きく出来そう。
そう考えると、プロセッサのクロック数がほとんど伸びずともそういった面でのコンピュータ将棋の棋力向上が考えられる。プロセッサのクロック数以外の伸びしろが結構あるんだなぁと。
楽観的に見れば、コンピュータ将棋がトッププロの棋力に到達するのは、あと、3,4年ではないかと思う。
■ GPUを使ったコンピュータ将棋の可能性
これは、長くなるので、また機を改めて書く。
■ GPS将棋が優勝
GPS将棋の優勝に決まりました。Bonanzaも激指もYSSも来年の決勝のシード権を失うという意外な展開に。
それでも、GPS将棋は、もともと実力があったのに、いままで結果が出せていなかったのが不思議なくらいなので、私としてはこの優勝は順当だと思います。(そういや、私はGPS将棋のソースコードは結構読みました。GPS将棋ソースコードひとり勉強会 → http://shogi.yaneu.com/index.php?GPS%BE%AD%B4%FD%A5%BD%A1%BC%A5%B9%A5%B3%A1%BC%A5%C9%A4%D2%A4%C8%A4%EA%CA%D9%B6%AF%B2%F1 )
