KPP差分計算の高速化(bonasseの功罪について)

Bonanza型のKPPでの評価関数を採用しているコンピューター将棋開発者がほとんどかと思いますが、この差分計算についてはあまり正しく理解されていないので、ここに詳しく書いておきます。


まず、前提としてFV38は、やっているものとします。

Bonanzaのmake_listの38要素化
http://d.hatena.ne.jp/LS3600/20141024

去年の電王トーナメントではFV38をSeleneはやっていないと西海枝さんがおっしゃってましたが、そのせいでSeleneのnpsが上位ソフトのnpsより1,2割ぐらい低かったので、「是非やりましょう」と伝えておきました。(笑)

また、Bonanzaのmake_listを差分更新するには、Bonanzaの三角配列を正方配列に変換しておく必要があるので、それも当然やっているものとします。

さて、KPPにおいてPが移動したときは、差分計算できます。Pがxからyに変わったとしたら、
eval = 前回のeval – ΣKxP + ΣKyP
となります。簡単ですね。

世間ではKが移動したときは、差分計算出来ないように思われていますが(実際、Bonanza6のソースコードがそうなっていますが)、それ自体が誤りです。

どういうことかと言うと、KPPとは言っても、先手Kに対するKPPと後手Kに対するKPPとがあり、個別に集計しておけば、先手玉が移動したなら、後手Kに対するΣKPPは前回の値で済むわけです。(玉の移動による駒の捕獲がある場合は、もう片側のΣKPPを差分計算する必要がある)

よって、Kの移動に関しても、差分計算をすることにより、おおよそ半分の計算コストで済むようになります。

しかしBonanza6のソースコードはそうなっていません。Aperyのソースコードもそうなっていません。

Aperyの平岡さんに昨日、尋ねたところ、「前回の電王トーナメントのときにそれに気づいて(知って?)、今回の出場までには修正する」とのことでした。

保木さんには、私はBonanza4のときに評価関数が差分計算できること自体はメールでお伝えしたのですが、具体的なソースコードの形で示したのはbonasseです。

bonasseは、ボンクラーズの伊藤さんによるBonanzaの高速化であり、評価関数の差分計算やSSEを用いた高速化など様々なテクニックを広く知らしめた意味で、非常に意義深いものです。

bonasseからソースコードを取り込む形でBonanza6が誕生したので、この部分が漏れたのです。要するに伊藤さんが気付かなかった(忘れていた?)のが原因ではないかと思います。

そのせいもあって、Bonanza6のソースコードを参考にしている、ほとんどの開発者はいまだKPPのKが移動したときの差分計算が出来ることを知らないのです。

念のため、保木さんに昨日メールでKPPのKが移動したとき、片側のKPPは差分計算が出来ることをお伝えしたところ、「全く気づきませんでした。私の知る限りでは、他にこのようなことをおっしゃっていた方はおりません。」とのことでした。要するに、多くの開発者の盲点となっていることは間違いないようです。

私も本件を記事にするのをすっかり忘れていたのですが、一昨日、Aperyのソースコードを眺めているときに思い出したので、こうしてまとめておくことにしました。他の開発者の皆様の参考になれば幸いです。

追記 2015/9/25 13:00

伊藤さんから言及がありました。

KPP差分計算の高速化(bonasseの功罪について)」への3件のフィードバック

  1. 久しぶりに本気のプログラマらしいやねさん発揮ですね。何事にも盲点というか、エアポケットのようなものってあるんだなぁとしみじみ。

    ところでブラうら王…………….

    ブラうら王

  2. これは、やねうら×伊藤御大のねっちょり中年コンビで叡王をボッコにする流れくるで

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です