指し手オーダリングのための高速ソート手法の提案(下書き)


めちゃんこすんごいろんぶんのしたがき

著者 : LS3600 & ひよこ


■ 概要

指し手のオーダリングを行なうために、生成した指し手に対して何らかの手法で点数をつけて、その点数によってソートしなければならない。これをオーダリングと呼ぶ。

本提案は、このオーダリングのときのソートの高速化のための手法を提案するものである。


■ Bonanzaでのオーダリング

Bonanzaでは、gen_next_moveがco-routineになっていて、この関数で指し手を逐次生成するが、駒を捕獲する指し手のあとはhistoryの指し手を生成するフェーズとなっている。

historyとは、指し手の移動元、移動先、駒種、手番の情報を元にうんぬんかんぬん(中略)

Bonanzaではhistoryの指し手はスコアの上位2手しか生成せず、残りの指し手は何のオーダリングもされていない。これは、たいていのノードではhistory2までにbeta cutが生じるし、そこまでにbeta cutが生じなければall node(すべての指し手がalpha値を下回るノード)であることが多いので、オーダリングのためにソートするコストに見合わないとBonanzaの作者が判断したためだと思われる。

しかし著者らの実験によれば、ここでstd::sortをしても自己対戦での勝率はほぼ変わらない。すなわち、オーダリングのためのソートがもっと高速に出来るならば導入する価値はあると言える。

そして、ここで指し手が適切にオーダリングされているなら、それを利用した枝刈り(そのノードであとのほうの指し手ほどreductionの幅を大きくするなど)がしやすくなる。

つまり、ここでソートをなるべく追加コストの少ない形で実現できればうんぬんかんぬん(中略)

■ ソートの要件

ここでは完全にソートされている必要はないと言う点に着眼する。そもそもhistoryの値自体がそこまで信頼できる値ではないので、全体的にそこそこ妥当な並びになっていれば良く、厳密な大小関係を守らなくとも良い。[要検証データ]

ここでのスコアはBonanzaに倣い、その指し手の試行回数tried , その指し手がbestであった回数 good (もう少し詳しく書くべき)とを使って次のように決定する。

 score = (good + 1) / (tried + 2)

このscoreの順に指し手をソートしたい。

そこで、高速にソートする手法としてbin sortをすることを考える。

■ bin sortとは

bin sortとは(中略。ググレカス)

いまscoreを0〜65535の範囲にスケーリングするとして、bin sortを適用するには、このscoreからbinのindexへマップしなければならない。

これは、たとえば、次のようにして端数を切り捨ててしまう方法が考えられる。

index = score / 1024;

しかし、この方法だと、小さなスコアばかりのときに適切にオーダリングされない。
そこでscoreの対数をとる方法が考えられる。2を対数の底にするならば、これはbsr(BitScanReverse)が使える。bsrとは(中略。ググレカス)

index = bsr(score);

(中略)

■ 割り算をやめる

割り算は一般的にlatencyの大きな命令で、scoreの計算のときにこれを無くす方法を考える。

(中略)

ゆえに、
index = bsr(good + 1) - bsr( tried + 2 ) + 16;

のように引き算をすることにより、うんぬんかんぬん(中略)
この場合、good,triedが0〜65535の範囲であれば、indexのとりうる値の範囲は、うんぬんかんぬん(中略)


■ 具体的な効果

Bonanza 6をこのbin sortを用いてhistoryの指し手1,2以外もすべてソートするように変更し、また、そのノードで生成された指し手の順番(中略)reduction深さを(中略)したところ、自己対戦では勝率X割になった。これはレーティングで言えばXXXに相当する。

ここに比較のための資料etc(略)

■ 結論

指し手オーダリングのためにソートするコストが見合うかどうかというのは、コンピューター将棋の探索部において非常に大きな課題であり、ソートすることにより可能になる枝刈りもあるが、ソートのコストが見合わないために導入をためらっていた開発者も多い。

しかし、今回、ソートするコストを限りなく小さく抑える手法を開発できたことは著者らの喜びであり、なんやかや(略)

お前らどんどん使ってたもれ(あとで別の言葉で書き換える)