指し手生成祭り開催 - Bonanzaソース完全解析ブログ

■　指し手生成祭り開催

指し手生成の早さ競争
http://d.hatena.ne.jp/mkomiya/20091107/1257596065

小宮さん、mclh46さん、aki.さんのところで盛り上がっているようなので私も大人げなく私の将棋ライブラリで参加してみました。

Bonanza改造ソースを「私の将棋ライブラリなどと呼ぶな！」とお叱りを受けそうですが、指し手生成に関しては、高速化のためにソースをいじくり倒したためBonanzaのソースの痕跡すら残っていません。

そこでこれ以降何の恥じらいもなく「私の将棋ライブラリ」と呼ばせていただきます。皆様、あらかじめご了承ください。

まず、問題の局面での指し手生成は、

つんデレ（？）は86,058回/sec
Blunderが152,788回/sec
misakiはだいたい311,000回/secぐらい

らしいです。

この局面を素のBonanzaで計測してみましたが、私の普段使っているマシン(Core2Duo2.8GHz)で、1.1M/secぐらいでした。素のBonanzaからは多少改造してあるソースで測定したので参考スコアということでお願いします。

私の将棋ライブラリのほうもやってみました。私の将棋ライブラリは駒を打つ部分のコードは、アルゴリズム的な改良に加えて、持ち駒の歩の有無×香の有無×桂の有無×銀金飛角の種類の数(0〜4種) = 2×2×2×5通り = 40通りでunrollしてあります。

このコードは駒が多ければ多いほど威力を発揮します。本家Bonanza比で(持ち駒が7種類ある局面ならば)4倍以上の高速化を達成しています。まあ平均的には2,3倍ってところなのですが。

それで5M回ループを回してみました。盤面表示は、id:issei_yさんの外字登録をするというアイデアを拝借しています。issei_yさんには、この場をお借りして御礼申し上げます。

結果、シングルスレッドで2325[ms]でした。つまり、2.15M/secですね。VC++でPGOなし×32bit環境用でbuildしてあるので、ICCでbuild + PGO有り ×64bit環境用ならこれより25%程度速いと思います。また、まだコード的には工夫の余地があるので、あと15%ぐらいなら速くなるかも知れません。要するにシングルスレッドで2.15×1.25×1.15 = 3.09M/sぐらいの性能が出ると思います。あと、大会参加用のマシンならば、さらに2割増しぐらいだと思います。

まあ、bitboard本来の性能を引き出せば、ここまでの速度が出るんだよと知ってもらえれば幸いです。

あと後手23玉という先手の利きに移動する自爆手(非合法手)を生成しています。そのためmisakiの指し手生成結果より1つだけ手が多いです。これは、Bonanzaの名残です。Bonanzaでは非合法手も生成します。どうせ、gencapで生成した手でたいていは枝刈りされますし、局面を進めたり戻したりするのは利きの情報の更新がないのでmove/unmoveはたいした計算量でもないので、どんどん手を生成したほうが速いからです。

■　追記(2009/11/10)

上で私の指し手生成ルーチンが、5M回で2325[ms]と書きましたが、打ち歩詰め判定をループ外に移動させると2235[ms]になりました。そのあと、コンパイルオプションをいじったりレジスタ割り付けしやすいようにコードを移動させたりなんやかやで2082[ms]になりました。ということで、2.40M/secで記録更新です。まだコードの改良により10%程度は伸びそうですが、この先は茨の道なので、いまは歩かないことにしておきます。

■　追記(2009/11/18)

http://d.hatena.ne.jp/LS3600/20091117にある、BitScanForwardを使うように変更したところ5%ほど高速化しました。あと、細かいところ少しいじって3%ほど高速化しました。5M回1937[ms]で2.58M/secで記録更新しました。