2010年の世界コンピュータ将棋選手権の件

■ 2010年の世界コンピュータ将棋選手権の件


まだ予定だけで本当のところどうするかはわかりませんが、私はたぶん2010年の世界コンピュータ将棋選手権に出場すると思います。


何か某掲示板のほうでは私のことがいろいろ書かれているようですが、余計な勘ぐりをされたくないので聞かれそうなことを以下に Q & A形式でまとめておきます。


Q) Bonanzaはどの程度高速化しましたか?
A) 現時点では全体的には30%程度の高速化(1/0.7 ≒ 本家の1.43倍)をしています。


Q) Bonanzaは最終的にはどの程度速くなるとお考えですか?
A) このあと差分指し手生成、差分局面評価、利きのデータ構造の追加して、細かいところをいろいろチューンすれば本家の3〜4倍ぐらいの速度になると見込んでいます。「すべてがうまくいけば」の話で、2倍速までは確実に行けると考えていますが、4倍速まで行くかどうかは現時点では私にはわかりません。


Q) Bonanzaはここからどの程度強くなるとお考えですか?
A)
・差分指し手生成、差分局面評価と細かいチューンにより3〜4倍に高速化(+R200〜R300)。
・利きのデータ構造の追加して利きを利用した評価関数に変更(+R50程度)
・df-pnによる詰め将棋ルーチン(+R30程度)
・持ち時間制御を改良(+R50程度)
・指し手生成をもう少し細かくグループ分けしてオーダリングを改良(+R50程度)
すべてがうまくいけば、+R400前後の伸びしろがあると考えています。ただし、これらすべてがうまくいくかどうかは私には現時点ではわかりません。また、すべてを私一人でやるのは荷が重いです。


Q) あなたは大会には高速化したBonanzaで出場するのですか?
A) 私は改造Bonanzaでは出ません。BonanzaC++で書き直したのは、自分なりに書き直してどの程度速くなるのかを確認しておきたかったからです。


Q) gennocapだけ高速化しても仕方ないのでは?
A) gennocapだけ高速化するつもりは全くありません。プロファイラで見てボトルネックになっている部分を高速化すべきと言う人がいますが、私はプロファイラでは見ていますが、ボトルネックになっている部分のみの高速化で良いとは考えていません。ソースのうち探索速度に絡む部分すべてに対して最善を尽くすべきです。


Bonanzaの探索部なんてものはソース量で言うと400KB程度しかなく、くまなくソースを凝視して、すべての箇所に対してベストを尽くすことが十分できる量です。それゆえ私は探索速度に絡む部分に関しては1行たりとして妥協をしません。またデータ構造に対しても同様です。全体を見渡して、全体的なパフォーマンスに悪い影響を与えるデータ構造を改善していくような地道な作業が必要です。こういうことをするためにはプロファイラでボトルネックになっている部分を改善していくという考え方とは相容れないものがあります。


また、私は、C++のソースがアセンブラで何命令程度に変換されて、それぞれの命令のレイテンシがどれくらいで、そこを実行するのに何ns程度必要かというのはある程度感覚的にわかります。それゆえ、プロファイラに頼らなくとも自分でソースをC++で書き直す過程でボトルネックの分析は完了しています。


Q) bitboardはbitboardを使わない手法に比べて高速だと言えますか?
A) 保木さんは、「bitboardを用いているのは、コーディングを容易にするためで、高速化のためではない」ということをおっしゃっています。そういう考え方をしているコンピュータ将棋関係者は多いのが事実です。私も長らくそれを信じていました。


しかし、保木さんのコードを見る限り、bitboard部分に関して最適化の余地はかなりありました。例えば、Bonanzaのgendrop.c(駒を打つ指し手の生成ルーチン)は、私は本家の3倍程度に高速化できました。それゆえ、その発言をされたころに、保木さんがbitboardに関して正当な評価を下せる状態にあったとは私には思えません。やはり、両者のコード(bitboardを使うコード、使わないコード)を極限まで高速化してみて、それでどちらが速いのかというのを計測しないとfairであるとは言えないからです。


私は公平に見て、総合的には現代のx64(EM64)アーキテクチャではbitboardのほうが速いと考えています。しかし利き関係の処理に関して本当にbitboardのほうが速いのかどうかは現時点では私にはわかりません。この部分は、正直、自信がないです。いくつかの魔法のような技法が発見できれば、bitboardのほうが利き関係の処理も速い可能性もありますが、これに関しては私の当面の研究課題です。今後は「GPS将棋をbitboardで書き直すと速くなるのか」などを研究していきたいと思っています。


Q) 小宮さんいわく、「保木さんすら気づかない効率化を見出すなんてこのブログ主は只者じゃないですね(^^; 」(→ http://d.hatena.ne.jp/mkomiya/20091108/1257607505 )とありますが、これについてはどう思いますか?


A) 保木さんが気づいていなかったわけではないと思います。保木さんは泥臭い最適化を嫌うのだと考えています。保木さんの最近の講演「将棋プログラムBonanza:完全公開!強い将棋プログラムの作り方」で、『皆さまには、「将棋は意外と簡単に作れそうだ」という感触を得て頂けると幸いです。』とおっしゃられているように、保木さんはシンプルで、かつ、教育的で、それでいてある程度の強さを持った将棋プログラムを書くことを理想とされているように思います。


特にBonanza4での評価関数には手番の評価もなければ、進行度というパラメータすらありません。Bonanzaには詰め将棋ルーチンすらなく、利きすら持っていません。トップクラスの将棋ソフトとしては異例中の異例ですが、そこに保木さんの哲学のようなものを感じます。


保木さんはBonanzaのソースを汚す(可読性や保守性を落とす)ようなチューンはしないのではないかと思います。仮に私の改造Bonanzaのソースが「本家の3倍に速くなった」と言ってそれを保木さんに手渡しても、保木さんは本家のコードに取り入れるようなことはされないのではないかと思います。


Q) あなたがBonanzaの改良をしようと思ったのは、来年の大会で優勝できれば、プロ棋士と対局できるという情報を知ったからですか?
A) いいえ、違います。私は昨年GPS将棋のソースについて熟読しました。またそれを元に将棋プログラムをある程度作っていました。私はGPS将棋の開発チーム以外でGPS将棋のソースを詳細まで理解している世界で唯一の存在かも知れません。


しかしGPS将棋のソースは改造するにはとても扱い辛く、VC++コンパイルを通すのもひと苦労で、局面のデータ構造や指し手生成など、ある程度の部分までは私なりに書き直してVC++コンパイルが通ってはいたのですが、その後の作業は作業量の観点からGPSの移植は中断していました。GPS開発チームから「いずれはVC++コンパイルを通るようにしたい」というアナウンスがあったため、私がいろいろソースをいじくりまわしてもそれはまるっきり無駄になると思ったからというのもあります。


またGPS将棋はその開発チームによって、もうすでにかなり念入りに最適化されているので、私が改造しても伸びしろが小さいように思いました。私が改良して伸びたとしてもR100いけばいいほうでしょう。


GPS将棋はbitboardを使わない将棋ソフトのコードとしてはかなり究極に近い位置にあると思います。それに対して、Bonanzaはbitboardを使う将棋ソフトとしてはまだ最適化の余地を多く残しており、すなわち、bitboardに対する正当な評価を受けられていないと感じたため、しばらくBonanzaのチューンに取り組んでいました。


それは、Bonanzaのそれぞれの関数の実行速度の詳細を知りたかったからというのもありますし、どの程度それぞれの関数が高速化できるのか自分の目で確かめてみたかったからというのもあります。


Q) FPGAを使った将棋には関心はないのですか?
A) 正直に言うとFPGA用の将棋プログラムをしばらく開発していましたし、いまも興味は持ってはいます。


しかし、大きな評価関数テーブルは既存のFPGAには到底収まらず、かつ、置換表もFPGA内のメモリには収まりません。評価関数テーブル自体は妥協して小さなものにするとしても、置換表として外部メモリを使わないといけないのは致命的で、外部メモリを使うとそれほど探索速度が出せません。


A級リーグさんのように置換表自体を持たないか、FPGA本体内のわずかばかりのメモリを使うしかないのですが、置換表が300KB程度のときにどの程度探索効率が低下するのかを測定したところ、探索深さが12〜13手を超えたあたりから絶望的に悪くなったので、これは実用に耐えないと判断しました。FPGAの内蔵メモリが今後増えてくれば状況は変わってくると思うので、今後も継続的に調査していこうと思っています。


また、静止探索だけFPGAボードで行なわせて、通常探索はPC側で行なうというハイブリッドな手法は有力だとは思いますが、1) FPGA←→PC間の通信のlatencyの問題 2) 大きな評価関数をFPGA側に実装できないという問題 の2つの問題があって、その両方を克服しないとトップレベルのソフトには太刀打ちできません。


また、Bonanza型の評価関数は実は差分計算が容易なので、FPGA←→PCの通信latencyより短い時間で局面の評価をすることが出来ます。結局、そうなってくると、FPGA自体の優位性が薄らいでくるので、いまのところ私はFPGAではトップレベルのソフトには迫れないと私は考えています。


FPGAの将棋ソフトがPCソフトを超えることがあるとするなら、FPGAが、10MB程度の内蔵メモリを搭載して、置換表だけ外部のSRAM/DDRメモリに置いてFPGAだけで探索を完結させられるようになったときだと思います。まだ、3,4年は厳しいような…


Q) あなたなら、評価関数にいくつか特徴を追加して、その改造Bonanzaとやらで出場すれば十分優勝候補ではないですか?
A) Bonanzaの評価関数の再学習(Bonanzaのfv.binと同質のパラメータを生成する)というのは、保木さん以外にいまだに成功した人はひとりもいません。詳しい話は割愛します。それゆえ、仮に特徴を1つや2つ追加してBonanzaに再学習させるだけでもとても難しいということだけ書いておきます。


実際のところBonanzaの評価関数の再学習でfv.binと同じぐらいの精度のパラメータを作れるのかというといまの私には自信がありません。


Q) あなたが大会で使うコンピュータ将棋ソフトでは、ボナメソは使わない、すなわち、Bonanzaの評価関数を変更せず、Bonanzaの評価関数をそのまま使うということですか?
A) 機械学習はとても奥深く、大会までにそこまで出来る自信は私にはありません。たぶん、ボナンザメソッドによるパラメータの自動学習は使わないと思います。しかし、Bonanzaの評価関数そのままということはしないと思います。ボナンザメソッドを使わずに評価関数をチューンすることを考えているからです。


これについては成果が出るかどうかわかりませんし、研究中の課題なのでここでは多くは書きません。


Q) 結局、大会には出るのですか?
A) いまのところわかりません。出ないかも知れません。自分で納得のいく成果が出るかどうかが現時点ではわからないからです。また、3倍速くなっただけのシャア専用Bonanzaで出場するということだけはあり得ないと言っておきます。


まあ、本当に3倍速くなれば、同じスペックのマシンでの自己対戦(同ソフトの対戦)なら勝率9割近くにはなるはずで、大会では3位ぐらいには入れると思いますが、そんなソフトで出場するのは私の美学が許さないので、それは100%無いです。


Q) 小手先のテクニックで高速化しても強くならなければそれまででは?
A) 某掲示板では「高速化」を「小手先の技」だと勘違いしている人が結構いますが、それは大きな間違いです。


この手のソフトウェアを大きく高速化するためには、アルゴリズム的な変更やデータ構造の変更が必須で、ソース全体を俯瞰して改善していく能力が必要です。局所的に、何か作業でもこなすかのように文字を置き換えたりして速度が2倍や3倍に向上するという類のものでは決してないです。


Q) あなたは、あなたの将棋ソフトにアセンブラを使いますか?
A) 開発効率上、オールアセンブラとかは全く考えてはいません。インラインアセンブラを使っている箇所もごくわずかで、PopucountはSSE4.2の命令なら速くなるかなという程度です。


あとは、SEE(SSEと紛らわしいですが、こちらはstatic exchange evaluationの略です)とオーダリングまわりはSSEの命令で書けば速くなるかな?という部分はあるのですが、これも研究中なのでまだ何とも。ともかくソースの99%はC++で書いています。残り1%ぐらいだけSSEの命令を使いところがあるかな、という程度です。


■ 追加(2009/12/17)


Q) 完成したらバイナリを公開する気はありますか?
A) x64に大きく依拠する書き方になっていたり、評価関数のために20GB程度の巨大テーブルが必要になったりしているので、現時点では大多数のマシンでは動作すらしないでしょう。ですので、バイナリは公開してもあまり意味がないとは思います。ただ、公開する気はあります。


Q) 完成したらソースを公開する気はありますか?
A) しかるべき時期が来たら何らかの形で公開しようとは考えています。