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個のエントリを入れるようにしてみたかっただけなので、随分遠回りした気もするがひとまず安定動作させることができたので満足した。
コメント 0