Rustで将棋合法手生成、速度改善

memo.sugyan.com

の続き。

前記事時点でだいたい合法手の生成が出来ていたが、速度面でやや問題があった。 perft の計測してみるとRust版Aperyと比較して2倍程度遅い。 だいたい同じ手順になるよう実装しているはずなんだけど どうしてそんなに差がついているのかなぁと気になって、調べながら色々修正し、ようやく遜色ないくらいの速度まで改善できたのでメモ。

改善PR: Improve performance by sugyan · Pull Request #5 · sugyan/yasai · GitHub

build options

まず大事なのが、 PEXT が有効に使えていなかったこと。 前記事で書いた通り bitintr crate を使って簡単に記述できるようにしていたが、これは内部で target_feature attribute で分岐されていて、 bmi2 が有効になっていないと拡張命令が使われず普通のbit演算で逐一処理するようにフォールバックされるようだった。よく分かっていなかった…。

RUSTFLAGS='-C target-feature=+bmi2' といった rustc に渡すコンパイラオプションを指定してやることで PEXT 拡張命令が使われるようになり、手元の環境ではこれだけで数段速くなった。 実際にはCPUによって結果は異なることになると思われ、例えば PEXT 命令が異常に遅い環境の場合はかえってこれを有効にしない方が速い、ということもあるのかもしれない。

あとは Aperyの Cargo.tomllto の設定が書いてあったのに気付いて、真似して使うようにした。

[profile.release]
lto = true

https://doc.rust-lang.org/cargo/reference/profiles.html#lto

具体的にどういうところによく効いてくるのかちょっと理解できていないけど、これもつけるかつけないかで速度に結構差がでることが分かった。

無理に共通化しない

合法手生成の際、自陣の各駒種について移動可能範囲を列挙していくことになるが、当初は記述コード量が少なくなるように 利きテーブルからの表引きも共通インタフェースを用意してすべて共通の処理で行うようにしていた。

    fn generate_all(&mut self, pos: &Position) {
        let target = !pos.pieces_c(pos.side_to_move());
        for &pt in PieceType::ALL.iter().skip(1) {
            self.generate_for_piece(pt, pos, &target);
        }
        ...
    }

    fn generate_for_piece(&mut self, pt: PieceType, pos: &Position, target: &Bitboard) {
        let c = pos.side_to_move();
        let occ = pos.occupied();
        for from in pos.pieces_cp(c, pt) {
            let p_from = pos.piece_on(from);
            let from_is_opponent_field = from.rank().is_opponent_field(c);
            for to in ATTACK_TABLE.attack(pt, from, c, &occ) & *target {
                if to.rank().is_valid_for_piece(c, pt) {
                    self.push(Move::new_normal(from, to, false, p_from, pos.piece_on(to)));
                }
                if pt.is_promotable() && (from_is_opponent_field || to.rank().is_opponent_field(c))
                {
                    self.push(Move::new_normal(from, to, true, p_from.promoted(), pos.piece_on(to)));
                }
            }
        }
    }

これは確かにコードとしては簡潔で済んでいたが、やはり無駄な分岐や判定が含まれることになっていた。

  • 歩兵・香車・桂馬 のみに必要な「行きどころのない段への不成移動」判定
  • 金将玉将・成駒 には不要な「成りの可否」判定
  • 香車・角行・飛車 にのみ必要な occupied bb の使用
  • 玉将・飛車・角行 などどちらの手番でも同じ動きをする駒での手番情報
  • 金将・成駒 どれも同じ動きをするのでまとめて処理できる

どれも一つ一つは数ステップの処理でたいして時間もかからないが、何千万・何億と膨大な局面を探索する際にはこういった差異も馬鹿にできない。 結局はそれぞれの駒種のための「似ているけど、それぞれちょっと違う」関数を用意してそれぞれ無駄のない最小の処理で生成するようにしてあげた方が良いようだ。

また、特に駒数の多い歩兵についてはさらに特殊で、他の駒と違って「前方に1つしか進めない」という特性から、移動先が一意に定まる。

他の駒の場合は「駒の居る位置を求め、それぞれを移動元としたときの移動先候補を列挙し、それらから自軍駒の位置を除外(既に自軍駒のある位置には移動できない)」となるが、歩兵の場合は「駒の居る位置のbbを1つだけシフトして、自軍駒の位置を除外」で一気に移動先候補が求まり、そこから逆算で移動元を求める方が効率が良い。 縦型Bitboardならではの方法で、64bit整数2つを繋げてshiftするのは面倒だが正しい盤面であればそもそも境界の場所には歩は居ないはずなのでそこは無視してそれぞれ独立してshiftしてしまえば良い。 手番によって方向が変わるので分岐は必要になるが、いちいち移動元と移動先の2重ループを回す必要がなくなり簡潔になる。なるほど〜。

大量に生成するデータはシンプルに

駒移動で相手の駒を取る指し手の場合、それを局面に適用する (do_move) のときには必要ないが 直前の状態に戻す (undo_move) ときには「何の駒を取っていたか」の情報が必要なのでどこかに記録しておく必要がある。

最初、どうせ undo_move のときにしか使わない情報で そのときにはどの指し手を戻すのか指定するわけだから指し手内に取得駒情報を入れておけば良いよね、と思ってそうしていた。

// ........ ........ ........ .####### : to
// ........ ........ ........ #....... : promotion flag
// ........ ........ .####### ........ : from (0 if drop move)
// ........ ........ #....... ........ : drop flag
// ........ ...##### ........ ........ : moved piece or dropped piece type
// ...##### ........ ........ ........ : captured piece (if moved)
pub struct Move(u32);

しかしそうすると、合法手候補の生成のたびに移動先の駒の情報を取得して 24bit shift して格納することになり、これも一つ一つは軽いものの 積み重なると重いものになっていた。

結局ここはAperyの実装に倣って、局面の履歴である states フィールドに持たせるようにして 指し手を適用したときにだけ取得して格納する方式に。指し手 Move の上位8bitは使わない実装になった。

あとで一気にまとめて処理する

合法手のリストは Vec に格納すると たとえ with_capacity() で最大サイズを指定していても遅く、 arrayvec crate を使うことで改善することは確認していた。

それはそれで良かったが、非合法手を除外する処理でまたパフォーマンスが違ってきていた。

まず合法手生成は基本的に「動かせる駒を可能な範囲に動かす手を列挙」するが、その中には非合法な手になってしまう場合がある。

  • 玉将がみずから相手の駒の利きの範囲に動いてしまう
  • 飛び駒から玉を守っている駒がそこから外れてしまう

これらは王手放置の一種となる反則なので除外する必要がある。

www.shogi.or.jp

なので、極力余計な容量を使わないように、と考えて最初は arrayvec への push の前に判定するようにしていた。

use arrayvec::ArrayVec;

pub struct MoveList(ArrayVec<Move, { MoveList::MAX_LEGAL_MOVES }>);

impl MoveList {
    const MAX_LEGAL_MOVES: usize = 593;

...

    fn push(&mut self, m: Move, pos: &Position) {
        if pos.is_legal_move(m) {
            self.0.push(m);
        }
    }
}

しかし、実際にはApery(や、他のエンジンでも同様にやっている?)のように「一旦候補手は全部突っ込んでおいて、最後に一気になめて詰め直す」という方式にした方が速かった。

    pub fn generate_legals(&mut self, pos: &Position) {
        ...

        let (mut i, mut size) = (0, self.0.len());
        while i != size {
            if pos.is_legal_move(self.0[i]) {
                i += 1;
            } else {
                size -= 1;
                self.0.swap(i, size);
            }
        }
        self.0.truncate(size);
    }

    fn push(&mut self, m: Move) {
        self.0.push(m);
    }

やっていることとしては最後にループ回して順番に判定し、非合法手だった場合は末尾と交換して size を縮小していって、最後に合法判定された sizetruncate() する、というもの。

判定回数自体は変わらなくて理論上の効率は一緒なのだけど、多少ではあるが速度に違いが出た。

やねうら王のやねうらおさんによると「単純な処理に分割してループ回したほうが、レジスタ効率良くなって速くなる」とのこと…

もしかすると push に渡す引数が増えることによるオーバーヘッドなどもある…?

最適化によってどのように処理されるようになるのか、レジスタが実際どのように使用されて計算されるのか、など コードだけでは見えない部分まで考える必要があり非常に難しい……。

現状

上述のような幾つかの改善を重ねた結果、以前よりは格段に速くなり、手元のMacbookで試した限りでは Aperyと比較しても数%遅いかな?くらいで 2倍もの差がつくようなことは無くなったように思える。

むしろ nightlyで portable_simd を使うようにしたら さらに速くなって追い越すかもしれない。

まだ細かいチューニングはできるかもしれないし Zobrist hash など未実装の機能を追加することでまた遅くなったりもするかもしれない。 飛び利きの計算を別の実装に変えることでさらに改善もされるかもしれない。ようやくスタートラインに並べたので、そろそろ試してみたいところ。

とりあえずは当初の方針であった 「unsafeunwrap を極力つかわないRustらしい書き方」だけでこれくらいまで出来たことは嬉しい成果だ。