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

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

気づいてなかったです、というか「Kが動くのは頻度としては小さいだろう」と思って深く考えずに再計算で満足してた、かな。動かない方のKは、差分というか、動いたKが駒取らない限り全く変わらない？ http://t.co/VLUj1RETcN KPP差分計算の高速化(bonasseの功罪

— Eikyu Ito (@aq3948) September 25, 2015