3年以上誰も発見できなかった探索部のbugがRustによって見つかったという話

だいたいにおいて、やねうら王ほどメジャーな将棋ソフトの探索部に大きなバグを埋め込むことは常識的に考えると不可能である。多くの人が改良に参加している&参考にしているので、誰かの目に止まるはずではある。ところが、公開後、数年も誰も気づかなかったbugがつい先日見つかった。Aperyの平岡さんが、AperyをRustで書き直している時にRustのコンパイラが警告を出したので気づいたと言うのだ。(WCSC29の会場で平岡さんから直接教えてもらった。)

bugの詳しい内容

ここから少し専門的な話が出てくる。プログラマでない人は次の見出しまで読み飛ばすこと推奨。

– Position::move16_to_move()のbug fix。thx.平岡さん
https://github.com/yaneurao/YaneuraOu/commit/9e6ba09029839838e10cd928456935111adeb971

内容的には、やねうら王では置換表に指し手を16-bitで格納している。(移動元 7bit、移動先 7bit、成りフラグ1bit/打ちフラグ1bit) これを取り出してきて使うのだが、指し手(Move)を表現するデータ自体は32-bitで、この指し手によって移動先の升に来る駒(例:先手の指し手で、歩を成る指し手であるなら、先手の「と」)を上位bitに格納している。そこで、置換表から取り出してきた直後に現在の盤面(Position)を見ながらその駒をMoveの上位bitに格納しなければならない。

このときに、成りフラグが立っているなら、移動元の駒を成駒化しなければならないし、打ちフラグが立っているなら駒打ち化しなければならない。

やねうら王のデータ構造では、駒(PIECE)は、+PROMOTE(+8)すると成り駒になる。SILVER(銀)に+8するとPRO_SILVER(成銀)になるという具合である。そこで、成りフラグが立っているなら+8するコードが書いてあった。

ところがこれが間違っていたのだ。

置換表へのアクセスに用いているhash keyがhash衝突を起こすとprobe(置換表のEntryを調べること)の時に異なる局面に関する情報を拾ってきてしまう。このとき、異なる局面の指し手であるから、指し手の移動元には現在の局面では偶然に後手の玉のような成れない駒が配置されていて、しかも置換表から取り出した指し手に成りフラグが立っているかも知れない。後手の玉 + 8は何の駒だろう?後手の玉は定数で24となっている。+8すると32となる。これはどの駒も表現しない。駒は31までしか使わないからである。配列も32までしか確保していない。これではアクセス違反になる。

とは言え、MovePicker(指し手オーダリング器)から指し手を取り出すときに置換表の指し手に関しては疑似合法手(pseudo-legal)であるかをテストするコードが入っている。つまり、MovePickerから取得する場合は、このチェックに引っかかるからアクセス違反にはならない。これが私の考えであった。

ところが、Stockfishのコードは、置換表にヒットしたときに、置換表の指し手の評価値で枝刈りを行うコードが書いてあって、この枝刈りを行なう時にこの指し手がpseudo-legalか判定していない。まあ、判定していなくとも、hash keyの衝突は極めてレアであるから、ここで間違った枝刈りをしたところで棋力にはほとんど影響がない。(間違った枝刈りをしてしまう損失より、pseudo-legalかをチェックするコードを入れて探索速度が遅くなる損失のほうがはるかに大きい) やねうら王やAperyもこの考えに倣っている。

しかし、この置換表の値で枝刈りをしたときにupdate_statsと言って統計情報を更新するのだ。このときに駒番号が32になっているため、下手するとアクセス違反になる。実際は、置換表の衝突が起きるのが極めてレアで、アクセス違反になるケースも統計情報を格納している大きな多次元配列の末尾付近のエントリーにアクセスしようとした時に限るので、これが実際に発生するのは天文学的な確率の低さだとは思う。

なんにせよ、正しいコードは、” + PROMOTE” ではなく、” | PROMOTE” と書くことだ。(“|”はbitwise OR) これなら成り駒は成り駒にしかならず、範囲外の駒番号になることはないからである。

何故このbugが見つかったのか?

WCSC29に出場したAperyはRustで全面的に書き直されているらしい。

Rustで書いて、C++の時(のApery)と同じぐらいかやや遅いぐらいの速度なのだそうだ。

平岡さん曰く「やや遅いのは自分の書き方が悪いのかRust自体が悪いのかが現時点ではわからない」とのこと。

Rustは本記事のbugについてコンパイル時に警告(エラー?)を出してきたのだそうだ。

その話を聞いて、私はRustの凄さにつくづく感心をした。

C++で書かれたソフトを多大な労力を払ってRustで書き直して、しかも速度がC++より劣る、Stockfish(C++で書かれている)にキャッチアップしにくくなる、第三者に使ってもらいにくくなるなどとなるとマイナス面ばかりが目立つが、このように別の言語で実装しなおしているときに新たな発見をすることも多々あるし、ソフトウェア業界において車輪の再発明は自分の理解のためには必要不可欠なのではないかと思う。

追記 2019/05/23 21:20

3年以上誰も発見できなかった探索部のbugがRustによって見つかったという話」への8件のフィードバック

  1. あれだw
    Linux方面由来のコードに対してClang+LLVMを使うと、クソ大量にバグに直結しているようなレベルの警告が出るようなのとよく似てるw

      • より良いものが出て主流が変わったときに、細かい違いを調べつつ車輪の再発明移植をまたやるのは面倒だから、移植はRustでラストにしたいですよねw

          • Rustがラストと読めるだろうということで、そういう駄洒落が出来そうというのはこの記事を読んだ時点で頭の中に生成されたけど、それを埋め込む文章の元になる良いシーンの情報の記憶とつながったのが今日の朝で、完成した勢いで書き込んだという感じですかねぇw

  2. 少なくとも同一バージョンのやねうら王であれば、同じ局面では同じhash衝突が起こりうる?
    再現性のあるhash衝突のせいで、たまたまその先の有力な手順を枝刈りしてしまう不幸な局面も存在しうる?
    「やねうら王はごくまれにポカをする」ことを前提とした事前研究が成立しうる?

    でもhash衝突する可能性は100億局に1局出現するかどうか、みたいなオーダーなのかな?
    あ、そもそもhash用saltが起動ごとに変わるなら事前研究はできないか。

    (とんちんかんなコメントであるおそれもある)

    • > 同じ局面では同じhash衝突が起こりうる?

      その局面の探索過程において、hash衝突が起きる2つの局面が必ず置換表に書き込まれなければならないという条件を満たす必要がありますけども。

      > たまたまその先の有力な手順を枝刈りしてしまう不幸な局面も存在しうる?

      今回のはnonPVでの枝刈りなので、PVの指し手には影響しないですね。「2番目の候補手をよく読めば1番目の候補手より良い指し手であるのだが、それを見落としてしまう」ということです。なので、ポカというほどでもなくて…。

      > でもhash衝突する可能性は100億局に1局出現するかどうか

      32bit + αで判定してるので、現実的にはそのくらいですね。

      > あ、そもそもhash用saltが起動ごとに変わるなら事前研究はできないか。

      Zobrist Hashでsalt固定です。なのでシングルスレッドでの探索で探索depth固定で置換表サイズ固定で同じ探索部を用いるならば再現性はあります。

コメントを残す

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