だいたいにおいて、やねうら王ほどメジャーな将棋ソフトの探索部に大きなバグを埋め込むことは常識的に考えると不可能である。多くの人が改良に参加している＆参考にしているので、誰かの目に止まるはずではある。ところが、公開後、数年も誰も気づかなかった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

コンパイル時ではなく、実行時のチェックで見つかりました。C++でもサニタイザ使えばおそらく見つかると思います(´･_･`)

— 平岡 拓也☀‹‹(´･_･` )/›› (@HiraokaTakuya) May 23, 2019