【解決】gensfenで教師局面生成時に遅くなる問題

やっと解決した(気がする)
開発者向けに原因を手短に書いておく。しかし、これがめっちゃ長い。

1.
まずSSE4.2向けだと途中で停止するという話があった。

この原因は、AVX2用だとBonaPiece型が32bitであるのに対してSSE4.2以前だと16bit型にしてあったからだ。そして16bit型だと、BonaPiece::fe_endとかが16bitなので、オーバーフローしていた。

2.
教師局面生成中に遅くなっていく現象も、1.と関連しているのかと思って、SSE4.2関係のコードをずっと調べていたのだが、そうじゃなかった。AVX2でもこの現象は起きていた。また、gcc/clangだけではなく、VC++でコンパイルした場合もこの現象が起きるという報告があった。

3.
そして再現条件をelmoの瀧澤さんが突き止めた。

bookfile no_book
gensfen eval_limit 1000

これで確かに遅くなっていく。

4.
調べていくと私が一つ勘違いしていたことがわかった。

置換表が小さいとhash衝突する。hash衝突すると異なる局面の評価値を取ってきてしまうことになる。普通はPV nodeではそうなってもTTEntryの値(value)は信用しないようになっているので、問題ないと思っていた。ところが、現在の探索部はそうはなっていなかった。動作は複雑であるが、要するに、この置換表の値がそのままsearch()の返し値として返ってくることがある。

5.
通常のsearch()では、反復深化をしていくのでこうなったところで次の反復で上書きされるから問題ないのであるが、今回の場合、depth固定で探索しているので反復動作がなく、hash衝突してしまった場合、いつまでも誤った値がsearch()から返ってくる。

6.
とは言え、本来なら一過性の問題なのであるが、教師局面生成のときには繰り返し開始局面からまた1局の将棋を開始するので、例えば、開始局面でhash衝突して変な値が書き込まれてしまうとどうなるかという問題があった。

7.
私はeval_limitを大きくしていたので、そうなっても停止することなくプレイアウトまで対局が進み、教師局面が書き出されていたのだが、eval_limitを3000とか、1000とか低めに設定している場合、この変な評価値が返された時点で対局を終了する動作となる。それゆえ教師局面がいつまでも書き出されないことになる。

8.
原因はわかったが解決するのは簡単ではない。
まずスレッドごとに置換表を分割する機能がある。
GlobalOptions.use_per_thread_tt = true;
とすると、この機能が有効になる。

gensfenコマンドを実行するときには、こうしてある。
ところが、これだけではhash衝突は回避できない。

9.
そこで教師局面生成時の探索ごとにTT.new_search()を呼び出してTTのgeneration(世代カウンター)を進めることにした。実は、そうしていたつもりであったが、そのコードを書き忘れていた。

10.
これだけでは実はまだこの現象は解決しない。

なぜなら、現状、StockfishのTT.probe()の実装はTTのgenerationとTTEntryのgenerationが異なる場合でも置換表にhitしてしまう。この動作は通常の探索時の動作としてはわからなくはないが、今回の目的ではhitされるとそのhash衝突したときに書き込まれたvalueかも知れないので困るのである。

そこで、この世代カウンターがぴったり一致しない場合は、置換表にhitしてもそのTTEntryはVALUE_NONEを返すための機能を提供することにした。

GlobalOptions.use_strict_generational_tt = true;
とするとそういう動作になる。

gensfenで教師局面を生成するときはそうすることにした。

11.
実に長い長い道のりであったが、これでようやく解決した気がする。
私の勘違い等もあって、非常に時間がかかった。
バグ報告をいただいた方々に感謝の意を表したい。


【解決】gensfenで教師局面生成時に遅くなる問題” への7件のコメント

  1. 根本的な解決策ではありませんが、私の環境でv4.72sse4.2ではeval_limitを短く設定したい場合、
    eval_limitを広く設定し、ResignValueで終わらせたい評価値を設定すると10%程度生成速度が上がりました。

    • この問題って、本日の修正で完全に直ってませんか?
      「eval_limitを広く」というのはどういうことでしょう?大きな値にするということでしょうか…。

      • elmoの瀧澤さんがeval_limit 1000と設定したい場合ならこんな感じです。

        YaneuraOuV471learn.exe threads 24 , ResignValue 1000 , bookfile no_book , gensfen random_move_maxply 0 random_move_count 0 depth 6 eval_limit 32000 loop 100000000

    • 2手前で探索したときに置換表に書き出された循環局面絡みの値が信用できないので、PV nodeでは置換表の値を信用せずに(指し手は信用して)探索しなおすのが普通ではあります。PV nodeは全体の1%に満たないので、そこで再探索になってもオーバーヘッドは小さいですし。

      • 回答、どうもありがとうございます。
        なるほど、そういうことだったんですね。

        ちょっと他の箇所で分からなかったのですが、

        struct TTEntry {
        // hash keyの上位16bit。下位48bitはこのエントリー(のアドレス)に一致しているということは
        // そこそこ合致しているという前提のコード
        uint16_t key16;

        TTEntry* TranspositionTable::probe(const Key key, bool& found
        if (tte[i].key16 == key16)

        ここって16bitなんてケチらずに、湯水のようにメモリ使ってハッシュ256bitくらい記録して、256bitで比較とかすると、やっぱり駄目なんでしょうか?

        • > 256bitで比較とかすると、やっぱり駄目なんでしょうか?

          256bitどころか、そこを仮にそこ32bitにでもするとTTEntry 3つでもTTClusterが32bytes超え、cache line(32bytes)をまたぐので、すこぶる遅くなりますね。

コメントを残す

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