BonaPiece inverse hackという新しいアイデアを思いついたので簡単に書いておきます。

いまPはBonaPiece型、KはSquare型、BKは先手玉、WKは後手玉であるものとします。

KPPT型の評価関数の計算をするときにΣKPPとして、BKPPとWKPPとを別個に計算しています。テーブル自体は、先手から見たときのKPPテーブル(BKPP用)なので、WKPPを計算するときに、このKPPテーブルを用いるならば、WK,P,Pをinverseしてやる必要があります。

inverseというのは盤面を180度回転させたときの駒を求める関数だと思ってください。
WKは単に盤上の升なのでinverseは 80-sq などとやるだけで良いです。ところが、Pのinverseは簡単ではないので表引きしています。

実際にはΣWKPPの計算のときにこの表引きが発生すると嫌なのでPieceListというPのlistにfb(from black = 先手から見たP)とfw(from white = 後手から見たP。要するにfbをinverseしたもの)とを格納しています。

このfbとfwの両方を更新するコストが嫌だというのと、WKPPのときにfbとfwとそれぞれにアクセスしないといけないのが嫌だというわけです。

これというのも、Pのinverseに表引きが必要になるのが原因なわけで、これを簡単な演算で済ませるように出来ないか？というのが今日のお題です。

BonaPieceの定義を組み替えて(変更して)みます。

BonaPiece型の終端はfe_endです。この前半に先手の駒を集めて、後半には後手の駒を集めるとします。
先手の駒に対して、fe_end/2を足したときにinverseされたPになるように後半をうまく定義します。

そうすると、fwを持つ必要がなくなり、ΣWKPPの計算でfwを用いずともfbのほうにfe_end/2を加算するだけで済みます。この加算は、定数加算なので、x86/64ではmov命令のときに定数オフセットを指定するアドレッシングに変換されるので、ほぼノーコストで済みます。またAVX2化するときも、fwのほうの値を取って来なくて良いので、fbの値を詰め込んであるレジスタに事前に用意したfe_end/2が各packed dwordに詰まっているようなレジスタと加算するだけで済みます。

そんなわけで、このBonaPiece inverse hackを用いると数%の高速化が見込めるはず…なのですが、従来の評価関数ファイルと互換性がなくなるのでコンバーターを書いたりしないといけなくて、色々面倒なわりに数%しかnpsが上がらないので(レーティングで言うとR5ぐらい？)、よほどのことがない限り、SDT5が終わってからの実装しようと思っています。

ちなみに、このアイデアをたぬきさんに話したところ、たぬきさんは(うまくAVX2化できそうで)いたく感動された様子でした。

やっぱりやね師匠は天才だなぁ…。

— nodchip@tanuki- (@nodchip) October 12, 2017

パズルゲーム強い人の発想じゃて…… https://t.co/BOKbG2rvCL

— Qhapaq (@Qhapaq_49) October 13, 2017

追記 2017/10/14 15:00

間違ってました。fbの駒がP < fe_end/2を満たすとは限らないので、fe_end/2を加算するのは良くなかったです。inverseを2回適用したときに元の値にならない時点でおかしいと気づくべきでした。(inverse(inverse(p)) ≠ pになってしまっている。)

正しくは、fe_end/2を起点として対称にすべきで、つまり、inverse(p) { return (fe_end-1) – p; } こうですね。