やねうら王 classic v2.15のNEW_TTなしの不具合 [コンピュータ将棋]
Aperyでコンパイルでグローバル変数が0になる問題もC++14によるスマートな解決方法が見つかったのと、mingwがあまりに不安定なので、やねうら王の不具合解析なるものをやってみた。
誰かやねうら王miniのデバッグきぼんぬhttp://yaneuraou.yaneu.com/2016/03/01/%E8%AA%B0%E3%81%8B%E3%82%84%E3%81%AD%E3%81%86%E3%82%89%E7%8E%8Bmini%E3%81%AE%E3%83%87%E3%83%90%E3%83%83%E3%82%B0%E3%81%8D%E3%81%BC%E3%82%93%E3%81%AC/
■セットアップ
txtファイルとかが、ほんとうに親切
評価関数のバイナリはコンピュータ将棋選手権のページから落としてくる
■ビルド
VisualStudioでビルドするだけ
■設定
とりあえずいつも通り4コア。
デフォルトで置換表サイズが16MBになっているが、将棋所で1秒自己対戦させるとハッシュが溢れるので128MBぐらいにしておく。
■NEW_TTありなし
NEW_TTありが16bit Keyの最新Stockfishの置換表
NEW_TTなし(以下OLD_TT)は2013年頃までの古いスタイル+独自拡張
NPSは17万~23万ぐらい
全幅探索はNEW_TTが17~22ぐらい、OLD_TTが14~16ぐらい
■バグ
NEW_TT同士では更新履歴に書いてあるようなクラッシュする不具合は簡単に出なかった
次に、NEW_TTvsOLD_TT
NPSはほとんど同じだが、NEW_TTのほうがたまに謎の高速化で全幅探索で+5ぐらいいくときがあり、微妙な局面で5手も先に読むと中盤から引き離して圧勝。レーティングは200以上差があるように思われる。
OLD_TTは結構落ちやすいようで、1回目は37戦で発生したが、PDB保存してなかったので再度実行。2回目は一晩放置して66戦で発生した。
2回目のクラッシュをデバッガで確認したところ、更新履歴に書いてあるようにinsert_pv_in_ttのアサートに引っかかっていた。早い話PVが合法手ではなかったので引っかかっていたが、その内容が後手による8九歩打だった。
こういうのが出るときはpseudoLegalと相場が決まってるのでposition.cppを見てみたところ、8九に歩を打つかどうかのチェックが入っていなかった。ひとまず入れたところ、NEW_TTより遅いだけの安定したバージョンができたように見えた。
が、コメントを読んでいるうちに怪しい箇所を見つけた。
例えばPromotionの場合は
と書かれているが、駒打ちのほうだと
最初は合法手チェックが入ってないだけだと思っていたのだが、「bit 0」は置換表に入れるときに潰してる部分なので、コメントの想定通りになっていない。
bit 0を潰しているので後手が打った手を先手が取り違える可能性があり、△8九歩打の理由が説明できる。
ついでに、このような条件にどの程度ぶつかるか、benchコマンドで確認した。
自分のPCでは約585万回書き換えにくるが、その際にDropが違法手になるのは3回だった。
これをビット0を保存するようなハッシュキーにしたところ、発生回数が0回になったので、多分コメントに書いてあるような想定通りに動いていると思われる。(と思ったけど、下のようにサイズ変えるだけで出たり出なかったりするのでイマイチ自信がない)
NEW_TTのときになんでこうならなかったのかは、置換表のキーサイズが16ビットからだという奇妙な現象だった。OLD_TTでキーサイズを48bit => 32bit => 16bitと試してみたところ、ハッシュキーが衝突したうえでDropする3回の現象が、でる => でる => でない となった。すごい、意味がわからない。NEW_TTで現象が出ないのはたまたまなのか、何かしらの理由があるのかは今後の課題とする。(やらないパターン)
追記
一応一晩走らせてみたところ、NEW_TT 128-9-63 OLD_TT となったので、探索速度的なレーティング差とほぼ同じになったのででかい問題はないと思われる。
誰かやねうら王miniのデバッグきぼんぬhttp://yaneuraou.yaneu.com/2016/03/01/%E8%AA%B0%E3%81%8B%E3%82%84%E3%81%AD%E3%81%86%E3%82%89%E7%8E%8Bmini%E3%81%AE%E3%83%87%E3%83%90%E3%83%83%E3%82%B0%E3%81%8D%E3%81%BC%E3%82%93%E3%81%AC/
■セットアップ
txtファイルとかが、ほんとうに親切
評価関数のバイナリはコンピュータ将棋選手権のページから落としてくる
■ビルド
VisualStudioでビルドするだけ
■設定
とりあえずいつも通り4コア。
デフォルトで置換表サイズが16MBになっているが、将棋所で1秒自己対戦させるとハッシュが溢れるので128MBぐらいにしておく。
■NEW_TTありなし
NEW_TTありが16bit Keyの最新Stockfishの置換表
NEW_TTなし(以下OLD_TT)は2013年頃までの古いスタイル+独自拡張
NPSは17万~23万ぐらい
全幅探索はNEW_TTが17~22ぐらい、OLD_TTが14~16ぐらい
■バグ
NEW_TT同士では更新履歴に書いてあるようなクラッシュする不具合は簡単に出なかった
次に、NEW_TTvsOLD_TT
NPSはほとんど同じだが、NEW_TTのほうがたまに謎の高速化で全幅探索で+5ぐらいいくときがあり、微妙な局面で5手も先に読むと中盤から引き離して圧勝。レーティングは200以上差があるように思われる。
OLD_TTは結構落ちやすいようで、1回目は37戦で発生したが、PDB保存してなかったので再度実行。2回目は一晩放置して66戦で発生した。
2回目のクラッシュをデバッガで確認したところ、更新履歴に書いてあるようにinsert_pv_in_ttのアサートに引っかかっていた。早い話PVが合法手ではなかったので引っかかっていたが、その内容が後手による8九歩打だった。
こういうのが出るときはpseudoLegalと相場が決まってるのでposition.cppを見てみたところ、8九に歩を打つかどうかのチェックが入っていなかった。ひとまず入れたところ、NEW_TTより遅いだけの安定したバージョンができたように見えた。
が、コメントを読んでいるうちに怪しい箇所を見つけた。
例えばPromotionの場合は
// --- 成らない指し手 // 駒打ちのところに書いた理由により、不成で進めない升への指し手のチェックも不要。 // 間違い → 駒種をmoveに含めていないのでこのチェック必要だわ。
と書かれているが、駒打ちのほうだと
// --- 移動できない升への歩・香・桂打ちについて // 打てない段に打つ歩・香・桂の指し手はそもそも生成されていない。 // 置換表のhash衝突で、後手の指し手が先手の指し手にならないことは保証されている。 // (先手の手番の局面と後手の手番の局面とのhash keyはbit0で区別しているので) // ゆえに、ここではこれ以上のチェックは不要なのである。
最初は合法手チェックが入ってないだけだと思っていたのだが、「bit 0」は置換表に入れるときに潰してる部分なので、コメントの想定通りになっていない。
uint64_t key32 = key >> 16;
bit 0を潰しているので後手が打った手を先手が取り違える可能性があり、△8九歩打の理由が説明できる。
ついでに、このような条件にどの程度ぶつかるか、benchコマンドで確認した。
自分のPCでは約585万回書き換えにくるが、その際にDropが違法手になるのは3回だった。
これをビット0を保存するようなハッシュキーにしたところ、発生回数が0回になったので、多分コメントに書いてあるような想定通りに動いていると思われる。(と思ったけど、下のようにサイズ変えるだけで出たり出なかったりするのでイマイチ自信がない)
NEW_TTのときになんでこうならなかったのかは、置換表のキーサイズが16ビットからだという奇妙な現象だった。OLD_TTでキーサイズを48bit => 32bit => 16bitと試してみたところ、ハッシュキーが衝突したうえでDropする3回の現象が、でる => でる => でない となった。すごい、意味がわからない。NEW_TTで現象が出ないのはたまたまなのか、何かしらの理由があるのかは今後の課題とする。(やらないパターン)
追記
一応一晩走らせてみたところ、NEW_TT 128-9-63 OLD_TT となったので、探索速度的なレーティング差とほぼ同じになったのででかい問題はないと思われる。
mingw-w64 gcc 5.3.0でグローバル変数の配列が0初期化されてしまう問題 [コンピュータ将棋]
AperyにはBitBoard_tという64bit*2=128bit長のクラスがあり、グローバル変数としてconstの変数や配列が定義されている。このときにRankMask => InFrontMask の順番で初期化が行われなければならない。
まず、ここ2,3日、gcc 5.3.0-2 でRankMask/FileMaskが0になってしまっていた理由は、mingw-w64-crt-gitの修正ミスによるものだったらしい。crtパッケージはmain関数の前にグローバル変数を初期化するためのルーチン(CTOR)が入っているが、それの指定が間違っていて、グローバル変数の初期化が0初期化以外全く行われなかったっぽい。今日配信されたバージョンでは直っていた。
InFrontMaskが0になる問題は残っていたのだが、上記の問題と解決方法から初期化する優先度が想定と違うのではないかということを思い出したので、GCC拡張であるinit priority指定をやったところ、無事数値が入っているのが確認できた。
こんな感じ
https://github.com/woodyring/apery/commit/f4d335e06d17bc133599d4ec0b07b8bc261f26ee
前2つのコミットでヘッダにある定数は全部cppに移動してある。
C++の規格書だと3.6.2あたりの初期化について書かれている(と思う)
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3337.pdf
3.6.2 Initialization of non-local variables
グローバル変数への代入する順番はリテラル>ノンリテラルの順番で行われていて、BitBoard_tはノンリテラルなので、定数宣言>配列宣言 となって欲しいところが、そうならなかったのが原因・・・
と思ってたのだが、決まった順番で初期化されるようなことが書かれている。
Together, zero-initialization and constant initialization are called static initialization; all other initialization is dynamic initialization. Static initialization shall be performed before any dynamic initialization takes place. Dynamic initialization of a non-local variable with static storage duration is either ordered or unordered.
<中略:テンプレートについて>
Other non-local variables with static storage duration have ordered initialization.
Variables with ordered initialization defined within a single translation unit shall be initialized in the order
of their definitions in the translation unit
正直よくわからないので、もう少し調べてみる予定
こういう問題をスマートに解決してくれるのがC++14で入るconstexprの拡張らしい。
追記
すごい気になったので初期化シーケンスを調査したところ面白いことがわかった
呼び出しがあったかどうかはgdbで確認した。
・グローバル初期化シーケンス
mingwではmingw-w64-crt-git/crt/gccmain.cあたりの__do_ctor_initializeとかそのへん
ubuntuではlibcから長ったらしい関数名で呼び出されている
・Aperyのmasterではビットボードの初期化が8回ぐらい呼び出される
これは最初に書いたようにヘッダにコードと変数があるので複数回呼びだされてしまう
私がプッシュしたfix~ブランチのようにソースファイルに移動すると1回しか呼び出さないのを確認した
・mingwのgccではrankMask()を初期化時に呼び出さない
テンプレートの展開ができていないくせに呼び出さない
・mingwではInFrontMaskのallZeroBBであるBlack1とWhite9の初期化しか呼び出さない
どっちも0だからやらなくてもいいぐらいなのに・・・
・Ubuntuのgcc 5.2.0は、rankMask()を定数として処理する
-O0でも定数化してしまう。驚いた。
・mingwのgccでもC++14のconstexprコンストラクタを使うことでリテラル化できる。
せっかく新しいバージョンなのでMakefileのバージョンをC++14に指定して、constexprコンストラクタを使ったところ、rankMaskのテンプレート関数が呼び出されるのを確認した。
今のところ、mingwのgccは呼び出し順番が決定できない場合に何もしない挙動になってしまうように思える。
ちゃんとデバッガで原因を目視で確認できたのでスッキリした。
まず、ここ2,3日、gcc 5.3.0-2 でRankMask/FileMaskが0になってしまっていた理由は、mingw-w64-crt-gitの修正ミスによるものだったらしい。crtパッケージはmain関数の前にグローバル変数を初期化するためのルーチン(CTOR)が入っているが、それの指定が間違っていて、グローバル変数の初期化が0初期化以外全く行われなかったっぽい。今日配信されたバージョンでは直っていた。
InFrontMaskが0になる問題は残っていたのだが、上記の問題と解決方法から初期化する優先度が想定と違うのではないかということを思い出したので、GCC拡張であるinit priority指定をやったところ、無事数値が入っているのが確認できた。
こんな感じ
https://github.com/woodyring/apery/commit/f4d335e06d17bc133599d4ec0b07b8bc261f26ee
前2つのコミットでヘッダにある定数は全部cppに移動してある。
C++の規格書だと3.6.2あたりの初期化について書かれている(と思う)
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3337.pdf
3.6.2 Initialization of non-local variables
グローバル変数への代入する順番はリテラル>ノンリテラルの順番で行われていて、BitBoard_tはノンリテラルなので、定数宣言>配列宣言 となって欲しいところが、そうならなかったのが原因・・・
と思ってたのだが、決まった順番で初期化されるようなことが書かれている。
Together, zero-initialization and constant initialization are called static initialization; all other initialization is dynamic initialization. Static initialization shall be performed before any dynamic initialization takes place. Dynamic initialization of a non-local variable with static storage duration is either ordered or unordered.
<中略:テンプレートについて>
Other non-local variables with static storage duration have ordered initialization.
Variables with ordered initialization defined within a single translation unit shall be initialized in the order
of their definitions in the translation unit
正直よくわからないので、もう少し調べてみる予定
こういう問題をスマートに解決してくれるのがC++14で入るconstexprの拡張らしい。
追記
すごい気になったので初期化シーケンスを調査したところ面白いことがわかった
呼び出しがあったかどうかはgdbで確認した。
・グローバル初期化シーケンス
mingwではmingw-w64-crt-git/crt/gccmain.cあたりの__do_ctor_initializeとかそのへん
ubuntuではlibcから長ったらしい関数名で呼び出されている
・Aperyのmasterではビットボードの初期化が8回ぐらい呼び出される
これは最初に書いたようにヘッダにコードと変数があるので複数回呼びだされてしまう
私がプッシュしたfix~ブランチのようにソースファイルに移動すると1回しか呼び出さないのを確認した
・mingwのgccではrankMask
TDM-GCC MinGW Compiler [コンピュータ将棋]
msys2は常に最新版を特にデバッグもせずに突っ込むポリシーらしいので、アップデートも下手にやらないほうがよさそうなのだが、うかつにもアップデートかけたら、またしてもAperyの配列内のテンプレート定数が0になるようになってしまった。今回はソースに持ってくるという姑息な対策も通用しない。再インストールも入れた直後だとアップデートかけてくるので、古いバージョンに戻せないので、前の対策も全く役立たたずになってしまった。
多分5.3.0でテンプレートが要素になる配列が0になってしまうので、GCCのバージョンをもとに戻すべく別のパッケージを入れた。
http://tdm-gcc.tdragon.net/
https://sourceforge.net/projects/tdm-gcc/
ただ、これはバイナリ配布でLIBCとかは別途自分で用意しろスタイルなのでそのままだと使いにくい。msys2の他のパッケージ管理自体は便利なのでそれを流用しつつ、gccだけ変えるようにするため、export PATHを以下のようにする
バグが出るバージョン
対策
対策後
これでひとまず急場をしのいだ。static constなtemplate arrayの問題自体はこのバージョンでも直ってなかった。
Stockfishのビルドで使ってるらしいようなことを何処かで見たのだが、あまり定かではない。
そもそも5.xから出るようになったこの問題も、mingwだけの問題でUbuntuでは発生していなかった。Aperyはwindowsだとstaticオプションつけてるので、LTOとかも関係してるのかもしれない。
多分5.3.0でテンプレートが要素になる配列が0になってしまうので、GCCのバージョンをもとに戻すべく別のパッケージを入れた。
http://tdm-gcc.tdragon.net/
https://sourceforge.net/projects/tdm-gcc/
ただ、これはバイナリ配布でLIBCとかは別途自分で用意しろスタイルなのでそのままだと使いにくい。msys2の他のパッケージ管理自体は便利なのでそれを流用しつつ、gccだけ変えるようにするため、export PATHを以下のようにする
バグが出るバージョン
Using built-in specs. COLLECT_GCC=C:\msys64\mingw64\bin\gcc.exe COLLECT_LTO_WRAPPER=C:/msys64/mingw64/bin/../lib/gcc/x86_64-w64-mingw32/5.3.0/lto-wrapper.exe Target: x86_64-w64-mingw32 Configured with: ../gcc-5.3.0/configure --prefix=/mingw64 --with-local-prefix=/mingw64/local --build=x86_64-w64-mingw32 --host=x86_64-w64-mingw32 --target=x86_64-w64-mingw32 --with-native-system-header-dir=/mingw64/x86_64-w64-mingw32/include --libexecdir=/mingw64/lib --with-gxx-include-dir=/mingw64/include/c++/5.3.0 --enable-bootstrap --with-arch=x86-64 --with-tune=generic --enable-languages=c,lto,c++,objc,obj-c++,fortran,ada --enable-shared --enable-static --enable-libatomic --enable-threads=posix --enable-graphite --enable-fully-dynamic-string --enable-libstdcxx-time=yes --disable-libstdcxx-pch --disable-libstdcxx-debug --enable-version-specific-runtime-libs --disable-isl-version-check --enable-lto --enable-libgomp --disable-multilib --enable-checking=release --disable-rpath --disable-win32-registry --disable-nls --disable-werror --disable-symvers --with-libiconv --with-system-zlib --with-gmp=/mingw64 --with-mpfr=/mingw64 --with-mpc=/mingw64 --with-isl=/mingw64 --with-pkgversion='Rev2, Built by MSYS2 project' --with-bugurl=http://sourceforge.net/projects/msys2 --with-gnu-as --with-gnu-ld Thread model: posix gcc version 5.3.0 (Rev2, Built by MSYS2 project)
対策
export PATH=/c/TDM-GCC-64/bin/:${PATH}
対策後
Using built-in specs. COLLECT_GCC=C:\TDM-GCC-64\bin\gcc.exe COLLECT_LTO_WRAPPER=C:/TDM-GCC-64/bin/../libexec/gcc/x86_64-w64-mingw32/5.1.0/lto-wrapper.exe Target: x86_64-w64-mingw32 Configured with: ../../../src/gcc-5.1.0/configure --build=x86_64-w64-mingw32 --enable-targets=all --enable-languages=ada,c,c++,fortran,lto,objc,obj-c++ --enable-libgomp --enable-lto --enable-graphite --enable-cxx-flags=-DWINPTHREAD_STATIC --disable-build-with-cxx --disable-build-poststage1-with-cxx --enable-libstdcxx-debug --enable-threads=posix --enable-version-specific-runtime-libs --enable-fully-dynamic-string --enable-libstdcxx-threads --enable-libstdcxx-time --with-gnu-ld --disable-werror --disable-nls --disable-win32-registry --prefix=/mingw64tdm --with-local-prefix=/mingw64tdm --with-pkgversion=tdm64-1 --with-bugurl=http://tdm-gcc.tdragon.net/bugs Thread model: posix gcc version 5.1.0 (tdm64-1)
これでひとまず急場をしのいだ。static constなtemplate arrayの問題自体はこのバージョンでも直ってなかった。
Stockfishのビルドで使ってるらしいようなことを何処かで見たのだが、あまり定かではない。
そもそも5.xから出るようになったこの問題も、mingwだけの問題でUbuntuでは発生していなかった。Aperyはwindowsだとstaticオプションつけてるので、LTOとかも関係してるのかもしれない。
AperyのハッシュKeyのサイズを32bitから16bitにするとクラッシュする [コンピュータ将棋]
個人的に一段落したのでまとめ
・再現方法
masterの置換表のキーサイズを32bitから16bitにする(tt.hpp/tt.cpp)
使用メモリサイズを下限の256MBにして「大樹の枝」と一手3秒で対戦する
(一応バグってる場合に完全な自己対戦だとわかりにくいので)
これで、1,2局対局するだけでクラッシュする
この現象が出た当初、gdbでみるとPosition構造体の局面ビットマップや駒が入った配列に不正な値が入っていたので、ただのメモリ参照エラーだと思ってた。(Cluster配列の末尾処理ミスるとか)。
しかし、怪しいところ(自分が変更したところ)を何回見直しても原因がわからなかったので、要因を切り分けていったところ、上記の再現方法によってハッシュがぶつかった時の問題であろうとあたりがついたのは、ちょうど作者の平岡さんがツイートする2,3時間前だった。
ハッシュがぶつかった場合にTTEntryに入っている指し手は別の局面に対応する指し手なので、そのまま適用してしまうと局面がおかしくなる。
実際ハッシュキーがぶつかる場合を確認してみた。
以下は16bit化でハッシュがぶつかったときのPositionの中の配列を、GDB出力しただけなので左に90度回転している。
ここでtte->move()は1七のWBishopが、2七にいくという指し手になっていた。多分別局面では角の位置に別の駒がいたのだと思われる。
Aperyでは、こういう場合を想定してPosition::moveIsPseudoLegalという関数で確認することができる。指し手生成クラスのMovePickerにttMoveを渡しているは、仮にttMoveが変な手が入っていても、実際の指し手として反映させないようになっている。(上記の場合は実際には指し手としては使われない)
指し手がそこそこ正しい(psuedoLegal)かどうかを判断するようになっているが、Promotionが絡んだ時のときの条件が入っていなかったらしい。
実際、32bitハッシュキーの時では問題の局面(ハッシュがぶつかってさらに成る手で指し手が一致するような場合)はすぐには確認できなかった。32->16bit化でハッシュの衝突確率が高くなって顕在化したようだ。
対策としてPromotionのときに成れる駒かどうかと、成れる場所かどうかチェックするようにしてみた。移動できるかどうか確認する方法はすぐにはわからなかったので入れなかったが、それだけでクラッシュは無くなった。
元々16bit化したかったのは、Stockfish7の「Pack 3 TT entries in 32 bytes cluster」を取り込んで、32バイトに3個のエントリを入れるようにしてみたかっただけなので、随分遠回りした気もするがひとまず安定動作させることができたので満足した。
・再現方法
masterの置換表のキーサイズを32bitから16bitにする(tt.hpp/tt.cpp)
使用メモリサイズを下限の256MBにして「大樹の枝」と一手3秒で対戦する
(一応バグってる場合に完全な自己対戦だとわかりにくいので)
これで、1,2局対局するだけでクラッシュする
この現象が出た当初、gdbでみるとPosition構造体の局面ビットマップや駒が入った配列に不正な値が入っていたので、ただのメモリ参照エラーだと思ってた。(Cluster配列の末尾処理ミスるとか)。
しかし、怪しいところ(自分が変更したところ)を何回見直しても原因がわからなかったので、要因を切り分けていったところ、上記の再現方法によってハッシュがぶつかった時の問題であろうとあたりがついたのは、ちょうど作者の平岡さんがツイートする2,3時間前だった。
ttMoveが合法手かどうか判定するの、まともにその駒が移動元から移動先に利きが通ってて移動可能か調べんとアカンやん。
— 平岡 拓也 (@HiraokaTakuya) 2016, 2月 17
ハッシュがぶつかった場合にTTEntryに入っている指し手は別の局面に対応する指し手なので、そのまま適用してしまうと局面がおかしくなる。
実際ハッシュキーがぶつかる場合を確認してみた。
以下は16bit化でハッシュがぶつかったときのPositionの中の配列を、GDB出力しただけなので左に90度回転している。
1一 1九 WLance, Empty, Empty, WPawn, Empty, BPawn, WBishop, Empty, BLance, WKnight, Empty, WPawn, Empty, Empty, BRook, Empty, Empty, BKnight, WSilver, WGold, Empty, WPawn, Empty, Empty, BPawn, BSilver, Empty, Empty, Empty, WPawn, Empty, Empty, Empty, BPawn, BKing, BGold, WKing, Empty, WPawn, Empty, Empty, Empty, BPawn, Empty, Empty, WGold, WSilver, Empty,WPawn, Empty, Empty, BPawn, Empty, Empty, Empty, Empty, WPawn, Empty, BPawn, Empty, Empty, BGold, Empty, WKnight, WRook, Empty, Empty, Empty,Empty, BPawn, BSilver, BKnight, WLance, Empty, WPawn, Empty, Empty, Empty, BPawn, Empty, BLance 9一 9九
ここでtte->move()は1七のWBishopが、2七にいくという指し手になっていた。多分別局面では角の位置に別の駒がいたのだと思われる。
Aperyでは、こういう場合を想定してPosition::moveIsPseudoLegalという関数で確認することができる。指し手生成クラスのMovePickerにttMoveを渡しているは、仮にttMoveが変な手が入っていても、実際の指し手として反映させないようになっている。(上記の場合は実際には指し手としては使われない)
指し手がそこそこ正しい(psuedoLegal)かどうかを判断するようになっているが、Promotionが絡んだ時のときの条件が入っていなかったらしい。
@HiraokaTakuya transposition table から取得した move が合法手か判定するとき、成れない駒が移動元にいる時にpromotion flagが立っていても合法手と判定する。この手で駒を動かすとクラッシュすると思う。
— 平岡 拓也 (@HiraokaTakuya) 2016, 2月 17
実際、32bitハッシュキーの時では問題の局面(ハッシュがぶつかってさらに成る手で指し手が一致するような場合)はすぐには確認できなかった。32->16bit化でハッシュの衝突確率が高くなって顕在化したようだ。
対策としてPromotionのときに成れる駒かどうかと、成れる場所かどうかチェックするようにしてみた。移動できるかどうか確認する方法はすぐにはわからなかったので入れなかったが、それだけでクラッシュは無くなった。
元々16bit化したかったのは、Stockfish7の「Pack 3 TT entries in 32 bytes cluster」を取り込んで、32バイトに3個のエントリを入れるようにしてみたかっただけなので、随分遠回りした気もするがひとまず安定動作させることができたので満足した。
Aperyのdebug無しビルドでbenchが通らなかった問題の修正方法 [コンピュータ将棋]
もういいやと思ってたが、たまたま見たログ見てたらstatic変数の問題っぽいような挙動に見えたのでソースいじったら直った
static変数が定義されたヘッダファイルを複数のファイル(例えばa.cppとb.cpp)で参照されるヘッダファイルに入れた場合、a/bそれぞれにstatic変数がコンパイルされて、static変数が複数生成されるという現象がある。例えば1MBの配列になるstatic変数が定義されていると、a/bの中に1MBの配列が出来てイメージが2MBになる。
今回の大本はテンプレート定数を引数にした配列を先に宣言してあって、その後に定数を宣言しているのが(mingw-w64のg++には)問題っぽい
bitmap.hppの中では以下の様な定数が定義されている。
InFrontMaskにはbitboard.cppに本体がある
InFrontMaskの中身がいつ決定するか、何に決定されるかということだが、bitboard.cppだと確かにヘッダのコンパイルされた定数が入ることが期待できるのだが、他のcppファイルの場合、ヘッダに定義されているconstを使うと判断されてしまっているのではないかというのが予想。
なので、対策として、ヘッダで定義されているInFrontOfRank1Black などの実体をcppに移しただけで直った。
こんな感じ
https://github.com/woodyring/apery/commit/e70bfa30e96e4b640a718a466734ec9f04418a3a
VSのCLang 3.7やUbuntuのg++では問題なかったので、使ってるmingw-w64のg++の問題だと思う。mingw-w64のg++は5.2.0/5.3.0両方で発生。インストールしたのが年末で、update-coreすると5.3.0になってるが、どっちでも同じ現象だった。
ただ、最適化をしたときだけ出てくれると、この説も説得力があるのだが、-O0でも発生するのでいまいち腑に落ちない。
<追記>
https://msys2.github.io/
ここからx64版をダウンロード
http://repo.msys2.org/distrib/x86_64/msys2-x86_64-20150916.exe
update-core
pacman --needed -Sy bash pacman pacman-mirrors msys2-runtime
pacman -Su
pacman -S gcc make
で多分同様の現象がおきるはず
static変数が定義されたヘッダファイルを複数のファイル(例えばa.cppとb.cpp)で参照されるヘッダファイルに入れた場合、a/bそれぞれにstatic変数がコンパイルされて、static変数が複数生成されるという現象がある。例えば1MBの配列になるstatic変数が定義されていると、a/bの中に1MBの配列が出来てイメージが2MBになる。
今回の大本はテンプレート定数を引数にした配列を先に宣言してあって、その後に定数を宣言しているのが(mingw-w64のg++には)問題っぽい
bitmap.hppの中では以下の様な定数が定義されている。
const Bitboard InFrontOfRank1Black = allZeroBB(); const Bitboard InFrontOfRank2Black = rankMask(); const Bitboard InFrontOfRank3Black = InFrontOfRank2Black | rankMask (); extern const Bitboard InFrontMask[ColorNum][RankNum];
InFrontMaskにはbitboard.cppに本体がある
243 const Bitboard InFrontMask[ColorNum][RankNum] = {
244 >---{ InFrontOfRank1Black, InFrontOfRank2Black, InFrontOfRank3Black, InFrontOfRank4Black, InFrontOfRank5Black, InFrontOfRank6Black, InFrontOfRank7Black, InFrontOfRank8Black, InFrontOfRank9Black },
245 >---{ InFrontOfRank1White, InFrontOfRank2White, InFrontOfRank3White, InFrontOfRank4White, InFrontOfRank5White, InFrontOfRank6White, InFrontOfRank7White, InFrontOfRank8White, InFrontOfRank9White }
246 };
InFrontMaskの中身がいつ決定するか、何に決定されるかということだが、bitboard.cppだと確かにヘッダのコンパイルされた定数が入ることが期待できるのだが、他のcppファイルの場合、ヘッダに定義されているconstを使うと判断されてしまっているのではないかというのが予想。
なので、対策として、ヘッダで定義されているInFrontOfRank1Black などの実体をcppに移しただけで直った。
こんな感じ
https://github.com/woodyring/apery/commit/e70bfa30e96e4b640a718a466734ec9f04418a3a
VSのCLang 3.7やUbuntuのg++では問題なかったので、使ってるmingw-w64のg++の問題だと思う。mingw-w64のg++は5.2.0/5.3.0両方で発生。インストールしたのが年末で、update-coreすると5.3.0になってるが、どっちでも同じ現象だった。
ただ、最適化をしたときだけ出てくれると、この説も説得力があるのだが、-O0でも発生するのでいまいち腑に落ちない。
<追記>
https://msys2.github.io/
ここからx64版をダウンロード
http://repo.msys2.org/distrib/x86_64/msys2-x86_64-20150916.exe
update-core
pacman --needed -Sy bash pacman pacman-mirrors msys2-runtime
pacman -Su
pacman -S gcc make
で多分同様の現象がおきるはず
Aperyのdebug無しビルドでbenchが通らない その2 [コンピュータ将棋]
前のエントリの続き
・Position::isOKで文句が出るのはKingが消える
というところからたどっていったところ以下のようになった
・そもそもKingが取られていた
前のやつにログを追記しておいたが、片方のKingが消えているのがisOKで問題有りとされる理由だった
そしてKingが消えたのは相手の効きのある場所に突っ込んでいっていた
・なぜ突っ込んでいくか
benchコマンドではスレッド数1なのでSplitなど並列関係の不具合ではない
最適化オプションを全部はずしたので最適化も関係ない
>問題のある手を無効化できていないはず
・inCheck
探索の中で王手がかかっている場合はinCheck状態になっている
そこから移動するときはEvasionの指し手生成が行われる
指し手生成では非合法手も生成されているので、その手がちゃんとした手かチェックしてダメな場合はその手は破棄する
ここで、問題の手が破棄されていなかったのを発見した
・合法手の判定
Kingのときだけ特殊処理が入っていて、相手の駒の効きが働いていないときだけ移動できる
(Kingではない場合は、一応捨てる手もありうるので合法手)
このときに効きがあるかどうかをビットボードで判定している
・問題点
ビットボードの中身を確認すると、本来立っていないといけないはずのビットが立っていなかった
・ビットを立てるタイミング
幾つかのテーブルはコンパイル時に決定されているはずだが、その値が0であることがわかった。
このため、銀、歩などの正面の効きが無くなっていた。
念のためUbuntuとかVisutal Studioのclangでも確認してみたが、ちゃんと値が入っていたので、mingwコンパイラのバグの可能性が高い。
テンプレートで定数を作る時の何かが起きてると思うのだが、テストコード書いてみたけど特に問題ないようでさっぱりわからなかった。
というわけでどうにもならなさそうなのでAperyいじりはしばらくお休み。
・Position::isOKで文句が出るのはKingが消える
というところからたどっていったところ以下のようになった
・そもそもKingが取られていた
前のやつにログを追記しておいたが、片方のKingが消えているのがisOKで問題有りとされる理由だった
そしてKingが消えたのは相手の効きのある場所に突っ込んでいっていた
・なぜ突っ込んでいくか
benchコマンドではスレッド数1なのでSplitなど並列関係の不具合ではない
最適化オプションを全部はずしたので最適化も関係ない
>問題のある手を無効化できていないはず
・inCheck
探索の中で王手がかかっている場合はinCheck状態になっている
そこから移動するときはEvasionの指し手生成が行われる
指し手生成では非合法手も生成されているので、その手がちゃんとした手かチェックしてダメな場合はその手は破棄する
ここで、問題の手が破棄されていなかったのを発見した
・合法手の判定
Kingのときだけ特殊処理が入っていて、相手の駒の効きが働いていないときだけ移動できる
(Kingではない場合は、一応捨てる手もありうるので合法手)
このときに効きがあるかどうかをビットボードで判定している
・問題点
ビットボードの中身を確認すると、本来立っていないといけないはずのビットが立っていなかった
・ビットを立てるタイミング
幾つかのテーブルはコンパイル時に決定されているはずだが、その値が0であることがわかった。
(gdb) p PawnAttack $3 = {{{p_ = {0, 0}}}, {{p_ = {0, 0}} }} (gdb) p InFrontMask $4 = {{{p_ = {0, 0}}, {p_ = {0, 0}}, {p_ = {0, 0}}, {p_ = {0, 0}}, {p_ = {0, 0}}, {p_ = {0, 0}}, {p_ = {0, 0}}, {p_ = {0, 0}}, {p_ = {0, 0}}}, {{ p_ = {0, 0}}, {p_ = {0, 0}}, {p_ = {0, 0}}, {p_ = {0, 0}}, {p_ = {0, 0}}, {p_ = {0, 0}}, {p_ = {0, 0}}, {p_ = {0, 0}}, {p_ = {0, 0}}}}
このため、銀、歩などの正面の効きが無くなっていた。
念のためUbuntuとかVisutal Studioのclangでも確認してみたが、ちゃんと値が入っていたので、mingwコンパイラのバグの可能性が高い。
テンプレートで定数を作る時の何かが起きてると思うのだが、テストコード書いてみたけど特に問題ないようでさっぱりわからなかった。
というわけでどうにもならなさそうなのでAperyいじりはしばらくお休み。
Aperyのdebug無しビルドでbenchが通らない [コンピュータ将棋]
置換表いじってたら、そもそもpullしたやつで以下の様な現象が出てしまったので、問題が分かる人は是非教えて下さい。
■環境
Windows 8.1 64bit
$ g++ --version
g++.exe (Rev4, Built by MSYS2 project) 5.2.0
Ubuntu ではg++ 5.2.1で問題なし
■コミット
■ビルドオプションの変更
■ビルド
make clean && make -j4
■方法
benchコマンドを実行する
後手の王が消えてるっぽい
■環境
Windows 8.1 64bit
$ g++ --version
g++.exe (Rev4, Built by MSYS2 project) 5.2.0
Ubuntu ではg++ 5.2.1で問題なし
■コミット
commit e923d2764e54795bab465ee7ce87b0de2529acf1 Author: HiraokaTakuyaDate: Tue Jan 12 23:14:54 2016 +0900 key取得コマンド追加
■ビルドオプションの変更
-DNDEBUG => なし -Ofast => -O0 -g
■ビルド
make clean && make -j4
■方法
benchコマンドを実行する
bench sfen l6nl/5+P1gk/2np1S3/p1p4Pp/3P2Sp1/1PPb2P1P/P5GS1/R8/LN4bKL w GR5pnsg 1 info string optimum_search_time = 9500 info string maximum_search_time = 9500 info string book_ply 32767 info depth 1 seldepth 1 score cp -648 nodes 211 nps 14066 time 15 multipv 1 pv G*1g info depth 2 seldepth 2 score cp -367 nodes 613 nps 9887 time 62 multipv 1 pv G*1g R*3a info depth 3 seldepth 3 score cp -526 nodes 1646 nps 8108 time 203 multipv 1 pv G*1g 4c3d N*4e info depth 4 seldepth 6 score cp -463 nodes 7985 nps 7670 time 1041 multipv 1 pv 3i5g+ G*3h G*1g 2i2h info depth 5 seldepth 6 score cp 1121 nodes 11396 nps 8234 time 1384 multipv 1 pv 3i1g+ G*1c 1b1c R*3c 6f3c info depth 6 seldepth 7 score cp 1673 nodes 13909 nps 8847 time 1572 multipv 1 pv 3i1g+ G*1c 1b1c R*3c 6f3c 9h3h info depth 7 seldepth 8 score cp 2612 nodes 17241 nps 9304 time 1853 multipv 1 pv 3i1g+ G*1c 1b1c R*3c 6f3c 2i3h R*2h 3h4g 2h9h+ info depth 8 seldepth 9 score cp 2612 nodes 18498 nps 9207 time 2009 multipv 1 pv 3i1g+ G*1c 1b1c R*3c 6f3c 2i3h R*2h 3h4g 2h9h+ Error! failedStep = 1 prevKey = 2204564077694724662 currKey = 9196037520415893749 ' 9 8 7 6 5 4 3 2 1 P1-KY * * * * * * -KE-KY P2 * * * * * +TO * -KI * P3 * * -KE-FU * +GI * +FU * P4-FU * -FU * * * * * -FU P5 * * * +FU * * +GI-FU * P6 * +FU+FU-KA * * +FU * +FU P7+FU * * * * * +KI+GI-UM P8+HI * * * * * * * * P9+KY+KE * * * * * +OU+KY P-00FU00FU00FU00FU00FU P-00KE P-00GI P-00KI00KI P-00HI - key = 9196037520415893749 This application has requested the Runtime to terminate it in an unusual way. Please contact the application's support team for more information. Assertion failed! Program: apery.exe File: position.cpp, Line 383 Expression: isOK()
後手の王が消えてるっぽい
やねうら王mini(Stockfish)とAperyの置換表の違い [コンピュータ将棋]
やねうら王miniが公開された。Stockfishベースのところが日本語のコメントで親切に書かれているので大変わかり易い。
で、置換表の話。
やねうら王では以下のようにコメントが書かれている。
これはStockfishと同一だが、Stockfishでは最初からそうだったわけではなく、あるときに32バイトに収まるように変更が入った。
https://github.com/official-stockfish/Stockfish/pull/3
https://github.com/official-stockfish/Stockfish/pull/10
このコミットで、
・確認用のハッシュキーを32ビットから16ビットにして2バイト減らす
・キャッシュの世代管理をする変数generationと探索の確かさであるFail-High/Fail-Lowを保存するboundをまとめてgenBound8にして1バイト減らす
・Depthを16ビットから8ビットにして1バイト減らす。
ということをやって10バイトにした。
この変更は2014年のものだが、Aperyではこの変更が取り込まれていないので試してみたが、これをいれると3秒対戦中にかなりの確率でせぐるようになってしまった。(1秒だとなかなかセグらない)
デバッグ版や1秒対戦だとなかなかでないのだが、-g付きpgoビルドをして、gdbでアタッチできるのがわかったのでセグったところをうまく捕捉できたのだが、要因がさっぱりわからない。
要点は一番上のthisのポインタが0x48という明らかにInvalid Pointerで、それの出処は、moveStackList=moveStackList@entry=0x3ee17958 あたりなのだが、途中でヌルが入る理由がさっぱりわからない。
うまく行けばメモリ効率がかなり良くなるのでPCのメモリがあまり多くない人にも恩恵があるのではないかと思うのだが・・・
<追記>
かなり再現性があって
・ポインタが(たぶん)NULLになるのが要因
・大元のMovePickerの配列legalMove_の要素数を倍にしても関係ない
・search/qsearch中のMovePickerのnextMoveなどでEvasionの手を生成する時に発生する
・発生場所は王手回避のときのみ
Evasionの桂馬、銀、角のどれかで発生する
配列数は600弱もあり、回避するだけの候補手がそんなにでかくなるとも思えないのだが・・・
ここまではわかったが、そもそも置換表のコード入れたらバグったので、置換表のバグでメモリぶっ壊してるのではという気がしないでもない。
<追記>
元々のコードと同等だけどコードが変わるようなのを書いてみたところ、再現率が変わって発生場所も変わったので、やっぱりどっかでメモリを書き潰している可能性が高まった。バックトレースが途中で死亡したのでスタックがぶっ壊れていたりとか、あるので置換表のコードを見直すことにする・・・
で、置換表の話。
やねうら王では以下のようにコメントが書かれている。
// 置換表エントリー
// 本エントリーは10bytesに収まるようになっている。3つのエントリーを並べたときに32bytesに収まるので
// CPUのcache lineに一発で載るというミラクル。
これはStockfishと同一だが、Stockfishでは最初からそうだったわけではなく、あるときに32バイトに収まるように変更が入った。
commit ccd823a4ffd2ed3e60cb03ab49a841742bae1994 Author: Ron BritvichDate: Sat Jun 28 14:05:58 2014 -0400 Pack 3 TT entries in 32 bytes cluster Idea from Ron Britvich Code reworked by Marco Costalba and Joona Kiiski Bench: 8095369 Resolves #3 Resolves #10
https://github.com/official-stockfish/Stockfish/pull/3
https://github.com/official-stockfish/Stockfish/pull/10
このコミットで、
・確認用のハッシュキーを32ビットから16ビットにして2バイト減らす
・キャッシュの世代管理をする変数generationと探索の確かさであるFail-High/Fail-Lowを保存するboundをまとめてgenBound8にして1バイト減らす
・Depthを16ビットから8ビットにして1バイト減らす。
ということをやって10バイトにした。
この変更は2014年のものだが、Aperyではこの変更が取り込まれていないので試してみたが、これをいれると3秒対戦中にかなりの確率でせぐるようになってしまった。(1秒だとなかなかセグらない)
デバッグ版や1秒対戦だとなかなかでないのだが、-g付きpgoビルドをして、gdbでアタッチできるのがわかったのでセグったところをうまく捕捉できたのだが、要因がさっぱりわからない。
0x00000000004337b1 in Move::operator|= (rhs=..., this=0x48) at move.hpp:72 72 this->value_ |= rhs.value(); (gdb) bt #0 0x00000000004337b1 in Move::operator|= (rhs=..., this=0x48) at move.hpp:72 #1 selectedMakeMove<(MoveType)7, (PromoteMode)0> (pos=..., to=SQ11, from=, pt= ) at generateMoves.hpp:66 #2 makePromoteMove<(MoveType)7> (pt= , from= , to=SQ11, pos=...) at generateMoves.hpp:72 #3 0x00000000004fbadd in (anonymous namespace)::GeneratePieceMoves<(MoveType)6, (PieceType)3, (Color)1, false>::operator() (target= , pos=..., moveStackList=0x0, this= ) at generateMoves.cpp:239 #4 (anonymous namespace)::GenerateMoves<(MoveType)6, (Color)1, false>::operator()(MoveStack*, Position const&) [clone .isra.26] () at generateMoves.cpp:468 #5 0x0000000000433555 in generateMoves<(MoveType)6> ( moveStackList=moveStackList@entry=0x3ee17958, pos=...) at generateMoves.cpp:556 #6 0x00000000004f3b5b in MovePicker::goNextPhase() () at movePicker.cpp:239 #7 0x00000000004f34a8 in Move MovePicker::nextMove () () at movePicker.cpp:80
要点は一番上のthisのポインタが0x48という明らかにInvalid Pointerで、それの出処は、moveStackList=moveStackList@entry=0x3ee17958 あたりなのだが、途中でヌルが入る理由がさっぱりわからない。
うまく行けばメモリ効率がかなり良くなるのでPCのメモリがあまり多くない人にも恩恵があるのではないかと思うのだが・・・
<追記>
かなり再現性があって
・ポインタが(たぶん)NULLになるのが要因
・大元のMovePickerの配列legalMove_の要素数を倍にしても関係ない
・search/qsearch中のMovePickerのnextMoveなどでEvasionの手を生成する時に発生する
・発生場所は王手回避のときのみ
Evasionの桂馬、銀、角のどれかで発生する
配列数は600弱もあり、回避するだけの候補手がそんなにでかくなるとも思えないのだが・・・
ここまではわかったが、そもそも置換表のコード入れたらバグったので、置換表のバグでメモリぶっ壊してるのではという気がしないでもない。
<追記>
元々のコードと同等だけどコードが変わるようなのを書いてみたところ、再現率が変わって発生場所も変わったので、やっぱりどっかでメモリを書き潰している可能性が高まった。バックトレースが途中で死亡したのでスタックがぶっ壊れていたりとか、あるので置換表のコードを見直すことにする・・・
Aperyの置換表をStockfish7風にする [コンピュータ将棋]
<追記>一番重要なコミットを書き忘れていた上に、そのコミットで勝率が変わるかもしれないというひどさなので前に見たことがある人は一番下を見てください
LazySMPは(バグのせいかもしれないが)探索深さが浅いせいで単純比較だとR200ぐらい落ちたので、やる気もなくなったのだが、移植している時に気がついたのが置換表の仕様変更。
Lazy SMP移植してみたときは置換表については特に手を入れなかったので、改めてStockfishのソースコードを見て差異があるところを移植してみた。
やねうら王Blogでも解説されているように、ハッシュ1エントリをまとめてクラスタとして管理してL1キャッシュが効果的に動くようにしているという基本思想そのものは変わっていない。
以下、Aperyとの差異があると思われるコミット
・エントリに含まれているリハッシュ処理のタイミングがstore時じゃなくてprobe時にやるようにしている
probe時に格納先のアドレスを覚えておいて、store時はそのアドレスに書くだけになっている
これによって、似たようなクラスター探索ループ処理を2回動かさなくても良いようになった。
・Stockfish独自のパック処理
Stockfish7ではBoundとGenerationをまとめて1バイトにすることによって格納数を増やした。
Aperyの場合はエントリサイズが大きくしてあるので格納数は変わらないので手を付けなかった。
・置換表使用率の表示
(参考)連載やねうら王miniを強くしよう!7日目 | やねうら王 公式サイト http://ow.ly/WRdJd
やねうら王Blogに実装するべきと書かれていたが、Stockfishでもパフォーマンスの観点で一時的に消されていたらしいが復帰していた模様。
以前スローダウンすると間違った判断をされていたが、今どきのPCだと2ms程度なので気にするほどではないとのこと。
またやねうら王Blogにかかれているように、ハッシュ全体を検査したり、カウンタをつけるのではなく、頭の1000個のクラスタの中身を見て該当するかどうか調べているので、ハッシュサイズが大きくなったら問題が起きるとか、コア間の強豪が起きるとかもあまりないと思われる。
実際採用してみたが、いつもの4コア、2GB、3秒で2%ぐらい使うのがわかった。
数分放置してみたところキャッシュが98%で頭打ちになっていた。
32GB積んでいる8コアの第2回電脳戦モデルの場合、キャッシュに使えるサイズの最大値は16GBで、PCのコア数が倍なので、20分程度も長考すれば溢れることになる。
タイムマネージャーあたりの最適化の指針にはなるかもしれない
多分ほんのちょっとだけ速くなって、ほんのちょっとだけ遅くなったので、強さは変わってないと思う。
<追記>強くなっている可能性があるので下記参照
(一手1秒では50勝45敗5分、一手3秒では50勝41敗5分だった)
ちなみに、途中で取り込みミスがあったときは、R200ぐらい落ちたのだが、ミスの発生頻度を計算したところ、3局に1回おかしくなりそうだったので、まあ妥当なレーティングかなと思った。
LazySMPは(バグのせいかもしれないが)探索深さが浅いせいで単純比較だとR200ぐらい落ちたので、やる気もなくなったのだが、移植している時に気がついたのが置換表の仕様変更。
Lazy SMP移植してみたときは置換表については特に手を入れなかったので、改めてStockfishのソースコードを見て差異があるところを移植してみた。
やねうら王Blogでも解説されているように、ハッシュ1エントリをまとめてクラスタとして管理してL1キャッシュが効果的に動くようにしているという基本思想そのものは変わっていない。
以下、Aperyとの差異があると思われるコミット
・エントリに含まれているリハッシュ処理のタイミングがstore時じゃなくてprobe時にやるようにしている
probe時に格納先のアドレスを覚えておいて、store時はそのアドレスに書くだけになっている
これによって、似たようなクラスター探索ループ処理を2回動かさなくても良いようになった。
commit 14cf27e6f65787a1f9c8e4759ae0fcc218f37d2d Author: mstemberaDate: Sat Dec 13 07:16:35 2014 +0000 Avoid searching TT twice for the same key/position during probe() and store(). Just keep the pointer and remove code from tt.cpp
・Stockfish独自のパック処理
Stockfish7ではBoundとGenerationをまとめて1バイトにすることによって格納数を増やした。
Aperyの場合はエントリサイズが大きくしてあるので格納数は変わらないので手を付けなかった。
commit ccd823a4ffd2ed3e60cb03ab49a841742bae1994 Author: Ron BritvichDate: Sat Jun 28 14:05:58 2014 -0400 Pack 3 TT entries in 32 bytes cluster Idea from Ron Britvich Code reworked by Marco Costalba and Joona Kiiski
・置換表使用率の表示
(参考)連載やねうら王miniを強くしよう!7日目 | やねうら王 公式サイト http://ow.ly/WRdJd
やねうら王Blogに実装するべきと書かれていたが、Stockfishでもパフォーマンスの観点で一時的に消されていたらしいが復帰していた模様。
commit a3b4e9e23ca7f8949336014468b872e57da85762 Author: Jean-Francois RomangDate: Sun Jan 25 08:57:51 2015 +0100 Ressurrect hashfull patch This is an old patch from Jean-Francois Romang to send UCI hashfull info to the GUI: https://github.com/mcostalba/Stockfish/pull/60/files It was wrongly judged as a slowdown, but it takes much less than 1 ms to run, indeed on my core i5 2.6Ghz it takes about 2 microsecs to run!
以前スローダウンすると間違った判断をされていたが、今どきのPCだと2ms程度なので気にするほどではないとのこと。
またやねうら王Blogにかかれているように、ハッシュ全体を検査したり、カウンタをつけるのではなく、頭の1000個のクラスタの中身を見て該当するかどうか調べているので、ハッシュサイズが大きくなったら問題が起きるとか、コア間の強豪が起きるとかもあまりないと思われる。
実際採用してみたが、いつもの4コア、2GB、3秒で2%ぐらい使うのがわかった。
数分放置してみたところキャッシュが98%で頭打ちになっていた。
32GB積んでいる8コアの第2回電脳戦モデルの場合、キャッシュに使えるサイズの最大値は16GBで、PCのコア数が倍なので、20分程度も長考すれば溢れることになる。
タイムマネージャーあたりの最適化の指針にはなるかもしれない
<追記>強くなっている可能性があるので下記参照
(一手1秒では50勝45敗5分、一手3秒では50勝41敗5分だった)
ちなみに、途中で取り込みミスがあったときは、R200ぐらい落ちたのだが、ミスの発生頻度を計算したところ、3局に1回おかしくなりそうだったので、まあ妥当なレーティングかなと思った。
AperyのLazy SMP化するとどうなるか [コンピュータ将棋]
GithubのLazy SMPコミット見てたら、自分でも出来そうな気がしたので改造してみた。
大まかな実装自体はすぐ終わったが、(主にくだらないことで)ハマり、デバッグに一週間かかった。
以下ハマったポイント
・スレッドの管理の問題
YBWCでは、「親スレッドが動いた後、Depth5ぐらいになってSplitされた子スレッドが動く」という動きになっているので親=>子の順番で動くことが担保されていて適当なタイミングでスレッドをおこしても不具合が起きなかった。
Lazy SMPでは子スレッドのほうが親スレッドよりも先に反復深化が動く可能性があり、しかもの初期コミットではDepth0でサーチしてたりした。やねうら王Blogでも、メインスレッドの出力が1番目に来ていない場合がある。これがLazy SMPの特徴なので、これが正しい動作であるという前提で切り分けしないといけないのだが、別の問題とのコンボで割とはまった。
・BMI2ビルドが動かない環境なのにBMI2ビルドをしていて、Segmentation Faultを起こしていた
Evaluateの変数の代入でセグっていたので、自分のコードが間違っていると思いこみ、変数周りを見なおしていたが、Instructionのほうが問題だったというオチ(3日かかった(笑))
・ビルドしたファイルをsrc=>binにコピーしていなかった
デバッグはbinフォルダでやっていたのだが、当然、修正が反映されていない状況でデバッグをしていた。
いくらソースコードを見ても間違ってるように思えなかったので、寝起きにすっきりした頭で、クリーンビルドして実行したらすんなり動いた。
これで1日ぐらい潰したような。
日をまたぐと忘れるので公式アナウンス推奨のシンボリックリンク作成して試すようにした
・gdbが使いにくい
mingwのgdbだとエラーで止まってくれない
gdbでリダイレクトをするとエラーで止まってくれない
gdb上でリダイレクトありでgoコマンドを実行すると空白をひたすら送り続けるらしく、持ち時間0、秒読み0で探索が動いてしまう
これも1,2日ぐらい無駄にした気がする。とくに最後のやつがひどい。
・最適化ビルド
PGOやるにはsrcの下にシンボリックリンクを作るのが公式見解だった
詳しくは前のエントリ参照
・大樹の枝(配布版)との比較
設定
4コア、3秒(実質2.5秒)、ハッシュ2GB、先読み無し
NPS,5%~10%増し
探索深さ、0~-2(中盤妙にパフォーマンスが悪くなる場合がある)
というよくわからない状況になった。
ハッシュがヒットしているとカウントしないはずなのだが、探索深さが浅いのに数が多いというよくわからない状況になっている。
探索深さが2手浅いのが結構致命的で勝率は壊滅的だった。(ちょっと試した感じだとR200ぐらい落ちた)
本来なら8コアで伸びがあることを証明したいところだが、4コアのマシンしか持っていないので試せていない。
その後、あんまりひどいので探索周りを少しいじってたら、4コアでなんとなく互角っぽいLazy SMPバージョンが出来た(かもしれない)。探索深さ自体は変わっていないので、勝率は悪いはずだが、本家に存在する「4コア3秒のときに10局に1回ぐらい発生する中終盤で変な指し手を指すバグっぽい挙動(後述)」が改善された気がする(あくまでも「気がする」だけでちゃんと検証したわけではない)
・「4コア3秒のときに10局に1回ぐらい発生する中終盤で変な指し手を指すバグっぽい挙動」
割りとそれなりの頻度で、敗着っぽいのをいきなり指してしまう現象。
4コア3秒で指し手の候補が3つぐらい出てくるとき(Fail-Low連発してるとき?)に
0~2秒:3つぐらいの手で迷う
2~3秒:よりにもよって悪そうな手(無理攻め?)でロックされる
というのが、それなりの頻度である気がする。
電王トーナメントとかだと持ち時間制度なので、FailLowが発生したら持ち時間が伸びて解消されてると思うのだが、4コア1手3秒固定でやってると10局に1回ぐらいの頻度で発生しているように思う。(要出典)
・結論
すでにYBWCを実装している人は、電王トーナメントのような4コア前提ならやる意味は無い。
しかしマルチスレッド化をこれから実装する人はまずはLazySMPで実装してしまうのは良い方法だと思う。
大まかな実装自体はすぐ終わったが、(主にくだらないことで)ハマり、デバッグに一週間かかった。
以下ハマったポイント
・スレッドの管理の問題
YBWCでは、「親スレッドが動いた後、Depth5ぐらいになってSplitされた子スレッドが動く」という動きになっているので親=>子の順番で動くことが担保されていて適当なタイミングでスレッドをおこしても不具合が起きなかった。
Lazy SMPでは子スレッドのほうが親スレッドよりも先に反復深化が動く可能性があり、しかもの初期コミットではDepth0でサーチしてたりした。やねうら王Blogでも、メインスレッドの出力が1番目に来ていない場合がある。これがLazy SMPの特徴なので、これが正しい動作であるという前提で切り分けしないといけないのだが、別の問題とのコンボで割とはまった。
・BMI2ビルドが動かない環境なのにBMI2ビルドをしていて、Segmentation Faultを起こしていた
Evaluateの変数の代入でセグっていたので、自分のコードが間違っていると思いこみ、変数周りを見なおしていたが、Instructionのほうが問題だったというオチ(3日かかった(笑))
・ビルドしたファイルをsrc=>binにコピーしていなかった
デバッグはbinフォルダでやっていたのだが、当然、修正が反映されていない状況でデバッグをしていた。
いくらソースコードを見ても間違ってるように思えなかったので、寝起きにすっきりした頭で、クリーンビルドして実行したらすんなり動いた。
これで1日ぐらい潰したような。
日をまたぐと忘れるので公式アナウンス推奨のシンボリックリンク作成して試すようにした
・gdbが使いにくい
mingwのgdbだとエラーで止まってくれない
gdbでリダイレクトをするとエラーで止まってくれない
gdb上でリダイレクトありでgoコマンドを実行すると空白をひたすら送り続けるらしく、持ち時間0、秒読み0で探索が動いてしまう
これも1,2日ぐらい無駄にした気がする。とくに最後のやつがひどい。
・最適化ビルド
PGOやるにはsrcの下にシンボリックリンクを作るのが公式見解だった
詳しくは前のエントリ参照
・大樹の枝(配布版)との比較
設定
4コア、3秒(実質2.5秒)、ハッシュ2GB、先読み無し
NPS,5%~10%増し
探索深さ、0~-2(中盤妙にパフォーマンスが悪くなる場合がある)
というよくわからない状況になった。
ハッシュがヒットしているとカウントしないはずなのだが、探索深さが浅いのに数が多いというよくわからない状況になっている。
探索深さが2手浅いのが結構致命的で勝率は壊滅的だった。(ちょっと試した感じだとR200ぐらい落ちた)
本来なら8コアで伸びがあることを証明したいところだが、4コアのマシンしか持っていないので試せていない。
その後、あんまりひどいので探索周りを少しいじってたら、4コアでなんとなく互角っぽいLazy SMPバージョンが出来た(かもしれない)。探索深さ自体は変わっていないので、勝率は悪いはずだが、本家に存在する「4コア3秒のときに10局に1回ぐらい発生する中終盤で変な指し手を指すバグっぽい挙動(後述)」が改善された気がする(あくまでも「気がする」だけでちゃんと検証したわけではない)
・「4コア3秒のときに10局に1回ぐらい発生する中終盤で変な指し手を指すバグっぽい挙動」
割りとそれなりの頻度で、敗着っぽいのをいきなり指してしまう現象。
4コア3秒で指し手の候補が3つぐらい出てくるとき(Fail-Low連発してるとき?)に
0~2秒:3つぐらいの手で迷う
2~3秒:よりにもよって悪そうな手(無理攻め?)でロックされる
というのが、それなりの頻度である気がする。
電王トーナメントとかだと持ち時間制度なので、FailLowが発生したら持ち時間が伸びて解消されてると思うのだが、4コア1手3秒固定でやってると10局に1回ぐらいの頻度で発生しているように思う。(要出典)
・結論
すでにYBWCを実装している人は、電王トーナメントのような4コア前提ならやる意味は無い。
しかしマルチスレッド化をこれから実装する人はまずはLazySMPで実装してしまうのは良い方法だと思う。