Rust+WASMでつくる、ブラウザ上で動く詰将棋Solver

成果物

局面を編集し指定し、その局面からの詰み手順を探索する。クエリパラメータにSFEN文字列を入れることで初期局面を指定することもできる。(例)

現時点での仕様は

  • 探索結果の指し手はCSAの文字列配列
  • 最短・最善の解を返すとは限らない
  • 探索しきれない場合は5秒で打ち切り

Repository: https://github.com/sugyan/tsumeshogi-solver-wasm

以下はこれが出来るまでの過程のメモ。

Rust製ソルバの改良

昨年末に、Rustでdf-pn探索を実装して詰将棋のソルバを作った。

memo.sugyan.com

ある程度動作していて そこそこの探索もできていたが、まだちょっと遅いので改善したい、という状態だった。

その後、今年に入ってから将棋AIを作成しようと挑戦を始め、その第一歩として合法手生成と局面探索を高速に実行するためのライブラリを自作することになった。

memo.sugyan.com

これは詰将棋ソルバのために作ったわけではなかったが、これを使うことでソルバの方も改善されそうだな、と思ったので組み込んでみることにした。

結果として、簡単なベンチマークで100倍ほど速くなるという予想以上の改善になった。

github.com

探索部の抽象化

以前は shogi crate を使って、shogi::Positionをwrapしたものから合法手の生成や局面ごとのハッシュ値を計算し、それを使って探索するよう実装していた。 当然のことながら shogi に依存した実装になっていたので、これを自作の yasai を使うように書き換える…ところから始めたが、実装を差し替えられるように trait を用意すれば良いことに気付いた。

pub trait Position {
    type M: Copy + PartialEq;

    fn hash_key(&self) -> u64;
    fn generate_legal_moves(&mut self, node: Node) -> Vec<(Self::M, u64)>;
    fn do_move(&mut self, m: Self::M);
    fn undo_move(&mut self, m: Self::M);
}

実際に探索中に必要なのは

  • 各局面に対するuniqueなハッシュ値が取得できる
  • 各局面からルールに則った指し手を列挙でき、各指し手について指し手を適用または戻すことができる

というだけのことだった。 これさえ満たしている型があれば、それを使って探索が実装できる。

shogi crate を使う場合は

use shogi::{Move, Position};

pub struct ShogiPosition(Position);

impl dfpn::Position for ShogiPosition {
    type M = Move;

    fn hash_key(&self) -> u64 {
        ... // 以前の実装のように自前で実装する
    }
    fn generate_legal_moves(&mut self, node: dfpn::Node) -> Vec<(Self::M, u64)> {
        ... // 以前の実装のようにひたすら候補を列挙し合法手チェックしてフィルタリング
    }
    fn do_move(&mut self, m: Self::M) {
        self.0.make_move(m).expect("failed to make move");
    }
    fn undo_move(&mut self, _m: Self::M) {
        self.0.unmake_move().expect("failed to unmake move");
    }
}

yasai を使う場合は合法手生成とZobrist Hashを求める機能がつけてあるので、

use yasai::{Move, Position};

pub struct YasaiPosition(Position);

impl dfpn::Position for YasaiPosition {
    type M = Move;

    fn hash_key(&self) -> u64 {
        self.0.key()
    }
    fn generate_legal_moves(&mut self, node: Node) -> Vec<(Self::M, u64)> {
        let mut moves = Vec::new();
        for m in self.0.legal_moves() {
            if node == Node::And || self.0.is_check_move(m) {
                self.0.do_move(m);
                moves.push((m, self.0.key()));
                self.0.undo_move(m);
            }
        }
        moves
    }
    fn do_move(&mut self, m: Self::M) {
        self.0.do_move(m);
    }
    fn undo_move(&mut self, m: Self::M) {
        self.0.undo_move(m);
    }
}

という感じで簡潔に記述できる。 両方の実装をbackendとして用意しておいて、あとはコマンド実行時にオプションで選択できるようにしておけばすぐに両方を切り替えて実行できる。

$ time ./tsumeshogi-solver --backend shogi '9/9/3pp4/+r2k1p3/2L1+p4/2+R6/B8/B8/9 b 4g4s4n3l14p 1'
9/9/3pp4/+r2k1p3/2L1+p4/2+R6/B8/B8/9 b 4g4s4n3l14p 1: Ok(["7e7b+", "P*8f", "7f7c"])
./tsumeshogi-solver --backend shogi   1.84s user 0.02s system 99% cpu 1.875 total
$ time ./tsumeshogi-solver --backend yasai '9/9/3pp4/+r2k1p3/2L1+p4/2+R6/B8/B8/9 b 4g4s4n3l14p 1'
9/9/3pp4/+r2k1p3/2L1+p4/2+R6/B8/B8/9 b 4g4s4n3l14p 1: Ok(["+7572NY", "-0086KE", "+7673RY"])
./tsumeshogi-solver --backend yasai   0.07s user 0.01s system 95% cpu 0.084 total

現時点で shogi backend を利用すべき場面はほぼ無いとは思うが、指し手の列挙順が異なるために探索順序が変わり、未解決の証明数2重カウント問題に嵌まるような入力に対しては違う挙動になったりするかもしれない。異なる探索ライブラリでの結果がすぐに比較できるのは利点と言える。

さらに Position trait として抽象化したことで dfpn探索のロジック部分からは完全に「将棋」に関する依存が消えたので、理論上はもはや将棋でなく他の類似したボードゲームの場合でも 前述のtraitを実装できるものであれば「どう逃れても最終的に詰ますことが出来るか否か」の探索に使える、ということになる。

探索打ち切りのための拡張

証明数2重カウント問題で無限ループになってしまったり、とにかく長手数や難解な問題の場合など、探索が一向に終わらないことがある。どこかで区切りをつけて「解くのを諦める」ことができる機能が欲しい、と考えた。 分かりやすい区切りが時間経過で、「何秒以上探索続けても終わらなかったら打ち切り」といったもの。

探索を続けるプログラムに対してそういった割り込みを入れられるようにするとなると普通はまず探索処理を並列化・並行化させて 別の処理から何らかのinterrupt信号を送って止められるように… となりそう。 頑張ってそれを実装してみてもよかったのだけど、まずは「決まった時間経過で止める」という制約で考えて、それであれば事前に設定しておけばちょっとした変更だけで実現できた。

反復深化を続ける loop の部分に判定処理を入れて、元の dfpn::Search traitを拡張したものを作った。

     // ノード n の展開
     fn mid(&mut self, hash: u64, phi: U, delta: U, node: Node) -> (U, U) {
         // 1. ハッシュを引く
         ...
         // 2. 合法手の生成
         ...
         // 3. ハッシュによるサイクル回避
         ...
         // 4. 多重反復深化
-        loop {
+        while !self.cancel() {
             ...
         }
     }

あとは最初の探索開始時に Instant::now() を取っておいて、 self.cancel() が呼ばれるたびに経過時間をチェックして閾値を超えていないか判定を入れれば良い。

これによって 探索時間制限を設定可能になり、「timeout Errorを返すこともあるが、n秒以内に必ず何らかの結果を返す」というものを作ることができた。

$ ./tsumeshogi-solver --timeout 1 --backend shogi '9/9/3pp4/+r2k1p3/2L1+p4/2+R6/B8/B8/9 b 4g4s4n3l14p 1'
9/9/3pp4/+r2k1p3/2L1+p4/2+R6/B8/B8/9 b 4g4s4n3l14p 1: Err(Timeout)
$ ./tsumeshogi-solver --timeout 1 --backend yasai '9/9/3pp4/+r2k1p3/2L1+p4/2+R6/B8/B8/9 b 4g4s4n3l14p 1'
9/9/3pp4/+r2k1p3/2L1+p4/2+R6/B8/B8/9 b 4g4s4n3l14p 1: Ok(["+7572NY", "-0086KE", "+7673RY"])

WebAssembly化

何がしたかったかと言うと、WASMにしてブラウザ上で動作するようにしたかった。 terminal上で動くならCtrl+Cで停止できるが ブラウザ上で動かすとなるとそうもいかないので、数秒程度で必ず何らかの結果を返すようにした。

ただ、 std::time::Instant::now() を使っているとwasmで動かすと 'time not implemented on this platform' と出てエラーになってしまうらしい。ブラウザ上で動かす場合は performance.now() のようなもので代用する必要があるようだ。 とはいえWASM専用に作るわけでもないので普通に使うときには std::time::Instant::now() を使いたい…。

こういうケースのために instant crate というものが存在していて、通常のbuildでは std::time::Instant として動作しつつ、wasm-bindgen featureを指定して.wasmをbuildする場合には performance.now() を使うようにしてくれる、らしい。

これだけの対応で無事にWebAssembly化に成功した。

将棋Player (自作WebComponents)

あとは任意の局面を入力できるように、局面編集可能なUIが欲しかった。 JSで実装された将棋playerなどは幾つか公開されていたが、多くは棋譜再生のためのものだったりして、「自由に局面を編集できて、かつその局面情報を何らかの形で取り出せる」という機能を持つJavaScriptのライブラリやコンポーネントというものは見つからなかった。

唯一 理想に近いものが shogi-player だったが、Vue(2)に依存することになるのがイヤで採用を見送った。

となると欲しいものは自分で作れば良いか、ということで Lit でWebComponentsを自作してみた。

まだ必要最低限の機能しか実装できていないが、これを使えば

<shogi-player mode="edit"></shogi-player>

と Custom Elements として簡潔に利用できて、自由に局面編集しつつ その編集結果をeventとして受け取ることが出来る。あとはそれをWebWorkerで動くようにしたwasmに投げるだけ。フロントエンドのJSは数十行程度で実装完了した。

https://github.com/sugyan/tsumeshogi-solver-wasm/blob/d26db73608d93e288905602f11ca8d59fa52c2ac/www/index.js

まとめ

まだソルバとしては未完成ながら、とりあえずWebブラウザ上で動作する詰将棋Solverを作って公開することが出来た。

図らずも、「フロントエンドのUIライブラリ」「バックエンドの探索ロジック」「探索のための合法手ライブラリ」すべてを自作したことになる…。結果的には良いものが出来たと思うので無駄ではなかった、と思う。

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らしい書き方」だけでこれくらいまで出来たことは嬉しい成果だ。

Rustでつくる もう一つの将棋ライブラリ

昨年末に出版された「強い将棋ソフトの創りかた」という本を読んで、自分も将棋AIを作ってみたいと思った。

この本では主にPythonでの実装が紹介されていたが、自分は最近はRustが好きなのでRustで自分で実装してみたい、と考えた。

最近では自作詰将棋SolverもRustで書いている。

memo.sugyan.com

局面探索、パフォーマンス

まず、局面の探索について考えた。

詰将棋Solverの場合も同様だが、将棋ソフトを作る場合にも、とにかく「今の局面からこの先どのような局面が発生し得るか」を高速に大量に探索していく必要がある。 現局面を根とするゲーム木を、合法手を辿って次々と子ノードに移ったり戻ってきたりして探索することになる。

これは、「各局面における合法手の列挙」と「指し手の適用(また、その巻き戻し)による局面状態更新」を繰り返すことで可能なので、これらを高速に計算できる必要がある。

Rustには shogi crateという優れた将棋ライブラリがあって、前記事の詰将棋Solverなどもそれを使って実装していた。

https://crates.io/crates/shogi

ただこのライブラリ自体には「合法手の列挙」を行うメソッドは用意されていないので、列挙するためには自前で用意する必要がある。 例えば以下のような感じで、指し手の候補を列挙できる。

use shogi::{Move, Piece, PieceType, Position, Square};

fn generate_move_candidates(pos: &mut Position) -> Vec<Move> {
    let mut ret = Vec::new();
    let color = pos.side_to_move();
    // まず自軍の駒が存在する位置を列挙
    for from in *pos.player_bb(color) {
        let from_in_promotion_zone = from.in_promotion_zone(color);
        // 指定位置に存在する駒を取得
        if let Some(p) = pos.piece_at(from) {
            let can_promote = p.piece_type.promote().is_some();
            // 指定位置から指定駒が動ける位置を列挙
            for to in pos.move_candidates(from, *p) {
                // 移動元と移動先から駒の成りが可能か否かを判定
                let promotions =
                    if can_promote && (from_in_promotion_zone || to.in_promotion_zone(color)) {
                        vec![false, true]
                    } else {
                        vec![false]
                    };
                for promote in promotions {
                    ret.push(Move::Normal { from, to, promote })
                }
            }
        }
    }
    // 持駒がある場合
    for piece_type in PieceType::iter() {
        if pos.hand(Piece { color, piece_type }) > 0 {
            // 空いているSquareを探す
            for to in Square::iter() {
                if pos.piece_at(to).is_none() {
                    ret.push(Move::Drop { to, piece_type });
                }
            }
        }
    }
    ret
}

これはあくまでも駒の動きの「候補」であり、ここからさらに以下のような非合法手を除外する必要がある。

  • 王手放置、もしくは自玉を相手駒の利きにさらす手
  • 歩・香車・桂馬の動かせない位置への不成や打
  • 二歩、打ち歩詰め
  • 千日手

これらは実際に pos.make_move(m) を呼んでみると MoveError が返ってくるので判定することができる。

(少なくとも現時点で) shogi ライブラリを使う場合はこのような感じで合法手を列挙していくことになるはず。詰将棋Solverを作るときもこういった方法で合法手を生成していた(詰将棋の場合は攻方のときに王手かける必要があるのでそのチェックも必要になるが)。

shogi ライブラリはBitboardを使った実装で非常に速いのだけど、それでもまったく問題ないわけではない。

perft

局面探索の確認と測定に使えるものとして、 perft というものがある。

ある局面から指定した深さまで局面を探索していくと全部で幾つの局面が現れるか、を数え上げる。「手順違いで同一局面に合流」などは考慮せず、あくまでゲーム木を再帰的に探索していく際のノード数を数える、という感じ。もともとはチェスの世界で使われていたものなのかな?

当然ながら深さを増やすと指数関数的に局面数が増えていくわけで、平手の初期局面からの局面数などは以下の記事などでまとめられている。

qiita.com

やねうら王Rust版Apery などでは、USI拡張コマンドとして go perft 5 などで実行できるようになっている。

$ cd ~/.ghq/github.com/HiraokaTakuya/apery_rust
$ cargo run --release                                                                           Compiling apery v2.0.0 (/Users/sugyan/.ghq/github.com/HiraokaTakuya/apery_rust)
    Finished release [optimized] target(s) in 44.26s
     Running `target/release/apery`
isready
readyok
go perft 5
1g1f : 821423
2g2f : 763797
3g3f : 777353
4g4f : 727359
5g5f : 728065
6g6f : 722473
7g7f : 1099961
8g8f : 721424
9g9f : 879050
1i1h : 623123
9i9h : 721423
3i3h : 455271
3i4h : 495883
7i6h : 604467
7i7h : 643428
2h1h : 713800
2h3h : 687521
2h4h : 650175
2h5h : 647634
2h6h : 638030
2h7h : 666383
4i3h : 454476
4i4h : 534086
4i5h : 529913
6i5h : 524756
6i6h : 606016
6i7h : 596975
5i4h : 567032
5i5h : 614526
5i6h : 645667

Time duration: 468.879021ms
Searched: 19861490 nodes : 42359519 nps
(Moved: 746131 nodes : 1591308 nps)

これは合法手の列挙さえできれば単純なDFSで実装できるので、 前述のような shogi ライブラリを使った列挙関数を使う場合、以下のように簡単に試すことができる。

use shogi::bitboard::Factory;
use shogi::{Move, Piece, PieceType, Position, Square};
use std::time::Instant;

fn main() {
    Factory::init();
    let mut pos = Position::new();
    pos.set_sfen("lnsgkgsnl/1r5b1/ppppppppp/9/9/9/PPPPPPPPP/1B5R1/LNSGKGSNL b - 1")
        .expect("failed to set sfen");

    let now = Instant::now();
    let total = perft(&mut pos, 5, true);
    let duration = now.elapsed();
    println!();
    println!("Time duration: {:?}", duration);
    println!(
        "Searched: {total} nodes: {} nps",
        (total as u128) * 1_000_000_000 / duration.as_nanos()
    );
}

fn generate_move_candidates(pos: &mut Position) -> Vec<Move> {
    ...
}

fn perft(pos: &mut Position, depth: usize, is_root: bool) -> u64 {
    let mut ret = 0;
    for m in generate_move_candidates(pos) {
        if pos.make_move(m).is_ok() {
            let count = if depth == 1 {
                1
            } else {
                perft(pos, depth - 1, false)
            };
            pos.unmake_move().expect("failed to unmake move");
            ret += count;
            if is_root {
                println!("{m}: {count}");
            }
        }
    }
    ret
}

で、手元のMacbookで実際にこれを動かして試してみると。 深さが増えるにつれて激重になる…。 同じ環境で実行してみてもRust版Aperyと比較すると圧倒的に遅い。深さ 5 だと1000倍近くかかっている。

perft depth nodes elapsed time (by shogi crate) elapsed time (apery_rust)
1 30 497.517µs 335.881µs
2 900 12.958808ms 880.983µs
3 25,470 330.535013ms 1.986988ms
4 719,731 9.00854434s 18.815674ms
5 19,861,490 241.722585518s 328.217788ms

これは主な理由として pos.make_move(m) 内で指し手の試行をして前述したような王手放置や反則手になっていないかという判定を繰り返しているところがあり、一回あたりの処理はさほど重くないものの探索の繰り返しの中で積み重なって遅くなってしまっていると思われる。

この設計自体はまったく悪くなくて、例えば「何らかのUIを用意して将棋ゲームを作る」といった際にはユーザが不正な指し手を入力してきた際にエラーを検出して表示したりする必要があるので、毎回の指し手ごとにそういった判定するのが正しいはず。

一方で将棋ソフト(思考エンジン)を作る際には「指定局面から合法手のみを辿って探索していく」という限られた用途になるので、「合法手のみを正しく列挙する方法があり」「そうして生成された合法手のみを受け取る前提で局面状態を更新する」という組み合わせで計算する仕組みになっていると余計なチェックを省くことができ、高速な探索を実現できる。

自作してみた

ということで、 shogi crate とは別の「もう一つの将棋ライブラリ」を自分で書いてみることにした。

github.com

Aperyはまさに高速な探索ができるよう実装されているRust製のソフトウェアで素晴らしい、と思ったものの、これは全体として思考ルーチンも含んだUSIエンジンとして一つの製品で、ライブラリとして使う感じではない。 shogi crate のようにシンプルな構造と機能だけを持つ高速な局面探索ライブラリが存在していると嬉しい、と思ったのでそういったものを自作することにした。

主にAperyのコードを参考に、合法手生成部分を抽出しつつ自分なりに理解しながら書いている。現時点では「爆速!」までは目指さず、Aperyよりは多少遅くても仕方ないと割り切りつつ出来る限り正しく型安全で unsafeunwrap を極力使わない実装にするようにしてみている。

まだ完全に実装できていない部分もあるが、 perft 6 までは正しい局面数が出るのを確認している。 現時点ではパフォーマンスはAperyと比較して 〜数十% ほど遅い、という感じで、perft 5 が600ms程度で2倍近く時間かかるが何百倍も遅いということはない、というところ。 これからまだ足りていない部分を実装したり パフォーマンス改善に取り組んでいくつもり。

Bitboardメモ

今まで「Bitboardってのを使うと駒の利きを高速に計算できるらしい」くらいの何となくしか知らなくて、今回はじめてBitboardまわりを自分で書いてようやく理解したので備忘録的にメモ。

基礎

Bitboardは盤面上の何らかの情報を持つ位置を表現するデータ構造。各マスに1bitを割り当てて、その位置に駒が存在していれば1、存在していなければ0、として全体の情報を幾つかの整数値で保持しておく。チェスやオセロなら64bitでちょうどよく収まるのだけど将棋は81マスなので、64bit整数を2つ使ったり工夫する必要があるようだ。Aperyでは1〜7筋、8〜9筋で2つの64bit整数に分けて、右上から下に見ていく所謂「縦型Bitboard」という方式だったのでそれを真似した。

    v[1]|                   v[0]
   9  8 |  7  6  5  4  3  2  1
 -------|-----------------------
| 09 00 | 54 45 36 27 18 09 00 | 一
| 10 01 | 55 46 37 28 19 10 01 | 二
| 11 02 | 56 47 38 29 20 11 02 | 三
| 12 03 | 57 48 39 30 21 12 03 | 四
| 13 04 | 58 49 40 31 22 13 04 | 五
| 14 05 | 59 50 41 32 23 14 05 | 六
| 15 06 | 60 51 42 33 24 15 06 | 七
| 16 07 | 61 52 43 34 25 16 07 | 八
| 17 08 | 62 53 44 35 26 17 08 | 九
 -------|-----------------------

例えば将棋の盤面を表す場合はまず「先手の駒の位置を表すBitboard(以下、bb)」「後手の駒の位置を表すbb」をそれぞれ持っておき、それらと別に「各駒種に対応する位置のbb」をそれぞれ持っておく。 例えば「先手の銀」の位置を知ろうと思ったら「先手のbb」「銀のbb」の論理積(&)をとれば対応する位置のbitだけが立っているものを得られる。

color_bb[Color::Black.index()] & piece_type_bb[PieceType::GI.index()]

000000000   001000100    000000000
000000000   000000000    000000000
000000000   000000000    000000000
000000000   000000000    000000000
000000000 & 000000000 => 000000000
000000000   000000000    000000000
111111111   000000000    000000000
010000010   000000000    000000000
111111111   001000100    001000100

また、後述の飛び駒の駒の利きを求めるために「先手後手問わず何らかの駒の置いてある位置のbb」も保持しておくと良い。

指し手を適用して駒が動いた場合はそれぞれ対応するbbの移動元・移動先の位置のbitだけ反転することで更新できる。

で、Bitboardの整数値からマスの位置を取る方法。

u64::trailing_zeros() で lowest set bit の位置を一発で得ることができる。 取得後は n &= n - 1 でそのbitを落とせるので、複数bitが立っているときは値が0になるまで取得と更新を繰り返せば良い。

let mut n: u64 = 0x4000_0000_0400_0000;
assert_eq!(26, n.trailing_zeros());  // 26 => Square::SQ39
n &= n - 1;
assert_eq!(62, n.trailing_zeros());  // 62 => Square::SQ79
n &= n - 1;
assert_eq!(0, n);

CPU命令と簡単なbit演算で求められるので、全81マスぶんループしてチェックするより遥かに速いわけだ。

利きテーブル

ここまでは「駒の位置の求め方」。 で、重要なのはここからの「駒の利きの求め方」。

1. 歩兵・桂馬・銀将金将・王将 の場合

先手の銀が3九に居ることが分かったとして、ではこの駒がどこに動けるか?

単純に考えると銀は正面と斜め4方向へ移動可能なので、現在位置から各方向に1つ動かした場所を列挙すれば良いが、九段目にいる場合はもう後ろには下がれない、など状況によって結果は異なる。

とはいえ「どちらの手番で」「どの位置にいる場合に」どこに動けるかは一意に定まるので (ちなみに移動先に既に駒がある場合も動かせないが、どこかで「自陣の駒のbb」の否定(反転)との論理積をとれば除外できるのでここでは考慮する必要ない)、予め移動可能な位置を計算して 手番数(2) x マス数(81) のBitboardを格納した「利きテーブル」を用意しておけば良い。

そうすれば、表引き一発で移動可能な位置を示すbbを得ることができる。

let attack_table: [[Bitboard; Square::NUM]; Color::NUM] = ...;  // 事前計算

let bb = attack_table[Color::Black.index()][Square::SQ39.index()];
for to in bb & !color_bb[Color::Black.index()] {
    ...
}
2. 香車・角行・飛車 の場合

他の駒にぶつからない限り端まで移動できるこれらの駒の場合は、進路にどのように駒が存在しているかによって結果が異なるのでそう簡単にはいかない。

とはいえ進路の中での駒の存在パターンはそこまで多くはないので頑張ってテーブルを作ることができる。 「どちらの手番で」「どの位置にいる場合に」の他に「先後問わず駒の置いてある位置のbb(occupied_bb)」の情報を使って表引きすることになる。

香車の場合は対象位置の筋の、縦のラインの状態だけわかれば他はどうでも良い。さらに上下両端は駒があってもなくても関係ないので、見るべきは二〜八の段の7箇所のみ、となる。7箇所だけなら駒の存在パターンは 2 ** 7128 通りしか存在しない。ので、手番数(2) x マス数(81) x 127パターン のテーブルを事前計算しておけば良い。縦型Bitboardであれば連続しているbit maskで得られたパターンの部分の値を一定量shiftするだけでindexが簡単に計算できる。

例えば初期局面から 1九香車が動ける位置を計算するときは以下のようなイメージ。

occupied:       mask:
111111111   .........    .........
010000010   ........#    ........0
111111111   ........#    ........1
000000000   ........#    ........0
000000000 & ........# => ........0
000000000   ........#    ........0
111111111   ........#    ........1
010000010   ........#    ........0
111111111   .........    .........
let attack_table: [[[Bitboard; 127]; Square::NUM]; Color::NUM] = ...;  // 事前計算

let mask = Bitboard::mask_from(File::FILE1);
let index = (occupied_bb & mask).value() >> 1;  // => 0b0100010
let bb = attack_table[Color::Black.index()][Square::SQ19.index()][index];

飛車・角行は、手番による違いはないものの縦にも横にも動くので香車のように単純にはいかない。 各マスから届き得るパターン数も多く、例えば5五の位置からはどちらの駒の場合も4方向あわせると12マスのパターンを考慮する必要があり、それだけで 4,096 通りが必要。

KA from SQ55   HI from SQ55
.........      .........
.#.....#.      ....#....
..#...#..      ....#....
...#.#...      ....#....
.........      .###.###.
...#.#...      ....#....
..#...#..      ....#....
.#.....#.      ....#....
.........      .........

それ以外のマスでも同様で、幾つかは変化するものの合計すると 角行は 20,224 、飛車は 495,616 パターンの考慮が必要になる。今どきのコンピュータならこれくらいのデータは保持しておくのは問題ないが、事前計算するのが少し時間かかったりする。

そして、事前計算していたとしても各マスからのbit maskに対応するindexを計算するのが難しく。 香車のときのように縦に並んでいるわけではないのでshiftでは実現できず、どうにかして各箇所のbit情報を集めてくる必要がある。

その1つの方法が、BMI2命令セットの PEXT のようだ。

X86 Bit manipulation instruction set - Wikipedia

これがまさに前述のような指定したmaskに該当するbitだけを集めてきてくれるもの、のようだ。

参考: RustからCPU拡張命令を使ってみる | κeenのHappy Hacκing Blog

shogi crateでは bitintr というcrateを使っていて、これはどうやら対応しているCPUアーキテクチャか否かで振り分けてフォールバック処理をしてくれるっぽい。

とはいえ対応するのは64bit整数なので、一発で求めるためには2つの整数の論理和(|)を取ってやることになる。ここは7列2列で分割しているとmaskのbitが重複しないので便利。

fn occupied_to_index(occupied: Bitboard, mask: Bitboard) -> usize {
    (occupied & mask).merge().pext(mask.merge()) as usize
}

ちなみにPEXTは一部のアーキテクチャでは圧倒的に遅いという問題があるらしく、使えるからといって必ず使うようにするのはあまり良くないのかもしれない。難しい…

PEXTを使わずにbit maskからindexを計算するもう1つの方法として、magic tableを使うものがあるようだ。これは試していないのでちゃんと理解していないけど、何らかの整数を乗算してshiftしてやったりすることでPEXTしたときと同様の結果を得られる、というものらしい。そのための整数値がまさにマジックナンバーの羅列になるので、こういう実装をMagic Bitboardと呼ばれている、のかな?

ともあれ、利きテーブルを利用する場合は事前計算が少し大変なので、どのタイミングでそれをやるかという問題も生じる。 shogi crateでは shogi::bitboard::Factory::init() という関数を用意していてユーザが明示的にそれを呼ぶことを強制している。 一方でAperyでは once_cell crateを利用して once_cell::sync::Lazy でテーブルを初期化していた。

参考: lazy_static はもう古い!? once_cell を使おう

初期化のタイミングは指定しづらいが、Factory::init()を呼び忘れるといったことは起きずに済むので良いかもしれない。

その他

また、こうした利きテーブルから表引きせずに求める方法もあるようで、最近ではQugiyの手法が話題になっている、のかな? まだ原理をちゃんと理解できていないが実装して試してみたいところ。

高速探索のためのテクニック

Aperyから移植しながら、「なるほど〜」と思った部分が幾つかあったのでメモ。 (実際どこまで速度に影響するかは環境などによっても変化すると思うしちゃんと効果を計測したわけではない)

とにかく数値として扱う

例えば駒の種類なんかは数種類程度なので enum を使うのが設計としては妥当だと思うのだけど、そうすると例えば成り駒への変換などが面倒になる。

enum PieceType {
    FU, KY, KE, GI, KA, HI, KI, OU,
    TO, NY, NK, NG, UM, RY,
}

fn promoted(pt: PieceType) -> PieceType {
    match pt {
        PieceType::FU => PieceType::TO,
        PieceType::KY => PieceType::NY,
        PieceType::KE => PieceType::NK,
        PieceType::GI => PieceType::NG,
        PieceType::KA => PieceType::UM,
        PieceType::HI => PieceType::RY,
        pt => pt,
    }
}

一見きれいに書けてスッキリしているようだけど、 match 式がどれくらい効率的に動いてくれるかあやしい。実際には比較と分岐が多くなると思われる。

なので、型に数値を持たせるようにして、ある桁にflagを持たせるようにする。

struct PieceType(u8);

const FU: PieceType = PieceType(1);
const KY: PieceType = PieceType(2);
...
const TO: PieceType = PieceType(9);
const NY: PieceType = PieceType(10);

fn promoted(pt: PieceType) -> PieceType {
    if pt.is_promotable() {
        PieceType(pt.0 | (1 << 3))
    } else {
        pt
    }
}

と、内部の数値に論理和してやるだけで済むようになる。この場合はうっかり金将や王将が成ってしまわないよう判定が必要になったりするが…。

指し手を表現する Move なども enum などを使わず 32bit 整数の中に移動元、移動先、駒種などの情報を含めるようにしている。このへんは特に配列として格納したりするのもあってアラインメントにも関わってくるのかな?

とにかく無駄な計算をしない

例えば Square::SQ39 = Square(26) というマスの位置を示すものがあって このマスの筋と段を求めたいとき、縦型のレイアウトなら

fn file_rank(sq: Square) -> (u8, u8) {
    let file = sq.0 / 9 + 1;
    let rank = sq.0 % 9 + 1;
    (file, rank)
}

と除算と剰余で求めることができる。 が、これも無駄な計算であって表引きできるものなので、各マスから筋と段を求めるためのテーブルを用意してそこから引くようにしてやる。

const SQUARE_TO_FILE: [u8; Square::NUM] = [1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, ...];
const SQUARE_TO_RANK: [u8; Square::NUM] = [1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 2, 3, ...];

fn file_rank(sq: Square) -> (u8, u8) {
    (SQUARE_TO_FILE[sq.index()], SQUARE_TO_RANK[sq.index()])
}

とにかく事前に計算できるものは先に用意しておいて極力計算回数を減らす、という工夫が大事なようだ。

SIMD

Rust版Aperyは昨年末くらいに64bit整数2つの計算をSIMDを使用して行うよう変更していたようだ。

https://github.com/HiraokaTakuya/apery_rust/commit/465b5c6991716062ef16b704bb112513e6381435

これもアーキテクチャによって処理を分岐したりする必要があって少し面倒そうではあるが、nightlyで使えるportable_simdというfeatureがあるようだった。

https://github.com/rust-lang/portable-simd

一応これを使って入れ替えても動くことは確認できて、体感少し早くなったような気はするけど誤差の範囲内かもしれない。

Use `portable_simd` feature by sugyan · Pull Request #1 · sugyan/yasai · GitHub

まとめ

結局ライブラリ作りに一生懸命になってしまって、将棋ソフト作りにはまったく取り組めていない…。

Rustでつくる詰将棋Solver その後

memo.sugyan.com

の続き。1ヶ月ほど経ってちょこちょこ更新して進化した。

残課題が幾つかあったが、そのうち幾つかは解決した。

探索無限ループ

f:id:sugyan:20211111001858p:plain

上図のような問題で ▲4四飛成 △3二玉 ▲4一竜 △3三玉 ▲4四竜 △3二玉 ... を無限に探索してしまっていた問題。

結局これはプログラム中のhashに格納する値を間違えていたことに起因していたようで、そこを直すことで解決した。 また合わせて最適解の選択ロジックを修正していくことでその他の問題で起きていた不具合も解消することが出来た。

Issue: 連続王手の繰り返し · Issue #2 · sugyan/tsumeshogi-solver · GitHub

後手から始まる問題、kifファイル入力

やねうら王公式からクリスマスプレゼントに詰将棋500万問を謹呈 | やねうら王 公式サイト の問題を試してみようと思ったら後手番から先手玉を詰ませる問題が半数含まれていて対応が必要だった。 これは主に合法手生成の部分を修正することで解決した。

1行ごとにsfen文字列を読んで 解を出力していく、といったことも出来るようにした。

500万問すべては試せていないが、各ファイル先頭200問ずつの計1000問くらいは最短ではないが詰みを見つけることは出来た。 まだ解けないものもあるようなので一つ一つ調査して原因を潰していきたいところ…

また、kif形式のファイルも読み込んでparseし初期盤面を問題として解かせることが出来るように簡単なparserを書いた。 あまりに自由な形式なので完全には対応できないが…

日本将棋連盟まいにち詰将棋 で使われているkifファイルくらいならだいたい正しくparseできるようにはなっていると思う。

f:id:sugyan:20211210152939p:plain

tsumeshogi-solver/kif_converter.rs at 0.2.0 · sugyan/tsumeshogi-solver · GitHub

証明数二重カウント問題

前述の500万問のものを試していて見つかったもの。例えば以下のような問題

f:id:sugyan:20211210001433p:plain

解としては例えば △7九角成 ▲同玉 △5七角 ▲6九玉 △6八銀 ▲5八玉 △6九銀打 の7手詰になる。

これを自作solverでdfpn探索していると △7九角成 ▲5九玉 △6八角 の手順をまず探索していって、これに対しては ▲4八玉▲5八玉 があり、どちらの場合も △5七角成 ▲5九玉 で同じ局面になる。次は △6八馬引 で詰むのだけど、それを探索する前に △6八馬上 ▲4八玉 △5七馬 という筋を探索しようとする。その優先度を決める際に4手目からの ▲4八玉 △5七角成 ▲5九玉 の経路と ▲5八玉 △5七角成 ▲5九玉 の経路の両方から証明数を足し合わせることになり、両者のノードの証明数が交互に過剰に加算されて更新されていってしまい、いつまでも探索が進まない という現象が起きていた。

これに対する解決策として、元の論文では

我々は,各局面に親局面へのポインタを持たせ,場合によっては親局面をたどることで DAG を検出し, 証明数の二重カウントを回避した.

-- df-pnアルゴリズムの詰将棋を解くプログラムへの応用

といったad-hocな回避方法が本文中に書かれていた。が、これは該当する実装が末尾の疑似コードには記載されておらず 疑似コードを極力忠実に移植した今回の自作solverではそういったことをしていなかった。

1手詰の検出

書かれている通りに親局面へのポインタを持たせるように変更してみるか、、とも思ったが、そもそも上記の問題はまず6手目 ▲5九玉 になった時点で △6八馬 の1手詰を検出できていればその先のループにハマることないよね?と思い 各ORノード(攻方手番)で1手詰めの判定を挟んでみることにした。

     // ノード n の展開
     fn mid(&mut self, hash: P::T, phi: U, delta: U, node: Node) -> (U, U) {

         ...

         // 2. 合法手の生成
         let children = self.generate_legal_moves(node);
+        // 攻方の場合のみ 1手詰を探索する
+        if node == Node::Or {
+            let mut mate = false;
+            for &(m, h) in &children {
+                self.make_move(m).expect("failed to make move");
+                let len = self.generate_legal_moves(Node::And).len();
+                self.unmake_move().expect("failed to unmake move");
+                if len == 0 {
+                    self.put_in_hash(h, (INF, 0));
+                    mate = true;
+                } else {
+                    self.put_in_hash(h, (1, len as U));
+                }
+            }
+            if mate {
+                self.put_in_hash(hash, (0, INF));
+                return (0, INF);
+            }
+        }
         if children.is_empty() {
             ...
         }
         // 3. ハッシュによるサイクル回避
         self.put_in_hash(hash, (delta, phi));
         // 4. 多重反復深化
         loop {
            ...
         }
    }

元の実装では、各局面で合法手を生成した後にループしながら証明数・反証数の更新していくので 合法手の生成時点ではそれらの子ノードが詰んでいるか否かはループ内で選択されて探索されない限り判明しない。 しかしそうすると前述のように「既に詰んでいる子ノードが見えているのに 他の子ノードを無駄に探索してしまう」ということが起こる。

ので、攻方手番の場合の子ノード展開時のみ、それらの子ノードが既に詰んでいるかどうか(子ノードからさらに次の子ノードが生成できるかどうか。できないということは詰んでいる、ということになる)の判定を入れてみた。子ノードから生成される合法手数はそのまま証明数になるので、たとえ詰みが見つからなくてもその後のループでの子ノード選択時にも優先して詰みやすいノードを選択できるようになる効果もある、はず。

ただ勿論これはORノードを探索するたびに子ノードのさらに子ノードまで生成を試みることになるので 非効率にもなり得る。そのぶん早く詰みを見つけて探索を打ち切ることができる可能性もあるし、単純に余計な合法手生成とハッシュテーブルの記憶領域を消費するだけになる可能性もある。どうなるかは「問題による」。 ただ少なくとも前述のような問題はこれによって解けるようにはなるのでアリかな、と思っているが どうなんだろう…。逆にこれによって解けなくなる問題もあるっぽいので ちゃんとDAG検出するとか他の方法をとるべきかもしれない。。

Issue: Cannot solve · Issue #4 · sugyan/tsumeshogi-solver · GitHub

初手に戻るループ

前述のものに近いが、ちょっと違うパターン。下図のような問題が解けなかった。

f:id:sugyan:20211210144912p:plain

正解は ▲1八歩 △同玉 ▲1九歩 △同玉 ▲3九飛 △1八玉 ▲1九香 の7手詰で、5手目の ▲3九飛 に対して持駒の歩も香も合駒として打てない(前に進めない場所には打てない!)ので玉は逃げるしかない、というのが面白い。

それはともかく、探索していると ▲1九香 △1八香 ▲1六飛 △同玉 ▲1八香 △1七飛 ▲同香 △同玉 という手順でまったく同じ局面に戻ってくる。このとき この局面の証明数・反証数がともに ∞-1 という値でハッシュテーブルに保存されているので、ループ内での証明数の最小値と反証数の総和がともに ∞-1 になる。これによっておかしな結果になってしまっているようだったので、反証数の和が ∞-1 以上だった場合は証明数の和を強制的に 0 にすることで解決した。

Issue: Cannot solve · Issue #7 · sugyan/tsumeshogi-solver · GitHub

打ち歩詰めの誤判定

下図のような問題が不詰として判定されてしまっていた。

f:id:sugyan:20211210150309p:plain

正解は ▲2二歩 △1一玉 ▲2三桂 の3手詰なのだけど、この初手 ▲2二歩 が合法手として生成されていなかった。原因を探ってみると、使用していた shogi-rs ライブラリの中で打ち歩詰めの判定に問題があって この ▲2二歩 に対して玉が1一に逃げられないと判断してしまって打ち歩詰めのためこの歩は打てない、という結果を返してしまっていることが分かった。

修正のコードを提案して取り込んでもらって無事に解決した。

Pull Request: Fix Uchifuzume check by sugyan · Pull Request #41 · nozaq/shogi-rs · GitHub

残課題

とりあえずここまでの変更・修正でバージョン 0.2 としてTagを切っておいた。

GitHub - sugyan/tsumeshogi-solver at 0.2.0

試しに日本将棋連盟まいにち詰将棋 の2020年の問題366問を解かせてみたところ、かなり時間かかるものはあったが一応すべてに対して最短の正解ではないにしろ詰みを見つけることは出来ていた。

未着手の課題としては以下。

  • まだ解けていない問題が幾つか発見されているので、可能な限り修正していきたいところ
  • sfen形式ではない、棋譜表記の文字列で回答を出力したい
  • 最短最善解を導出できるように、は勿論していきたい
    • まずは深さ上限を指定しての探索から実装することになる、か
  • パフォーマンスの問題はまだあるので可能であれば高速化は試みたい
  • 長手数の問題はどのレベルなら解けるのか、または残り何手の状態なら現実的な時間で解けるのか、など知っておきたい
  • WASM buildしてWebアプリ上で動かしたい

Rustでつくる詰将棋Solver

f:id:sugyan:20211110195955p:plain

というわけで突然Rustで詰将棋ソルバを作りたくなり、作った。

github.com

現時点ではまだ完成度は低くて6割ほどかな…。

とはいえそこらの素直な詰将棋問題なら普通に解けると思う。 冒頭の画像は看寿賞作品の3手詰「新たなる殺意」を2秒弱で解いたもの。

先行事例

将棋プログラムの多くはC++で書かれていて 最近はRustも増えてきているのかな? しかし「詰将棋を解く」ことに特化しているものはあまり多くはなさそうだった。

なかでもRustで書かれているものはna2hiroさんによるものくらいしか無さそうで、

github.com

これを大いに参考にさせていただいた。

しかしこれはおそらく後述の盤面ハッシュ値を生成するために手元で変更を加えているものを使っているようで、手元ではビルドも出来ない。 また個人的にはsfenではなくCSAや他の形式を入出力に使いたいなどの要望もあり、そういった問題も解決しつつ自分の理解も深めるために自作してみることにした。

df-pnアルゴリズム

過去に、Goでも詰将棋ソルバを書こうとしてdf-pnアルゴリズムを使った探索プログラムを実装していた。今回はこれのリメイクということになる。

memo.sugyan.com

df-pnについては上記記事でも触れているが 他にも詳しい記事があるので貼っておきます

komorinfo.com

qhapaq.hatenablog.com

Rustにおける将棋ライブラリ

盤面の状態保持や合法手生成のために、何らかのライブラリが必要になる。

Goで作ったときは愚直にif文for文まみれで自作して使っていて、当然ながら速度も出なかった。 RustではBitboardベースの優れたライブラリが既に作られ公開されているので、これを使うことにした。

github.com

実装に必要なもの

さて、df-pnアルゴリズムは簡単にいうと「root node (初期盤面) から合法手で辿れる child nodes についてそれぞれ(証明数, 反証数) のペアを計算し保存し、それらの値を元に最良な(詰/不詰を判定しやすそうな) child node を優先的に選択して反復深化し探索していく」というもの。

玉方と攻方でそれぞれ AND/OR Tree を形成して詰か不詰を判定することにはなるのだけど、実装においては木構造を作る必要はない

盤面は各合法手を選んだ際に状態遷移して探索から戻ってきたら盤面も戻すことが出来れば良いだけで、重要なのは各盤面の状態における(証明数, 反証数)を保存・取得する方法さえあれば良い、ということ。

一般的には盤面の状態を何らかの方法でハッシュした値を計算し、そのハッシュ値によってテーブルに格納する、ということになる。

よって、

  • 盤面の状態を合法手で進めたり戻したりしつつ 各盤面の状態における一意な値を得ることが出来る
  • 各状態から得られる値を元に (証明数, 反証数)のペアを保存・取得することが出来る

というものがあれば良い。

実装

ということでここからはRustでの実装の話。

Trait

必要なもの、と前述した通りに2つの Trait を用意することにした。 証明数・反証数に関してはとりあえず u32 にしているが 一応変えやすいようにtype aliasで U としている。

use shogi::{Bitboard, Color, Move, MoveError, Piece, PieceType, Square};
use std::hash::Hash;

type U = u32;
pub const INF: U = U::MAX;

pub trait HashPosition {
    type T: Eq + Hash + Copy;
    fn hand(&self, p: Piece) -> u8;
    fn in_check(&self, color: Color) -> bool;
    fn make_move(&mut self, m: Move) -> Result<(), MoveError>;
    fn move_candidates(&self, sq: Square, p: Piece) -> Bitboard;
    fn piece_at(&self, sq: Square) -> &Option<Piece>;
    fn player_bb(&self, c: Color) -> &Bitboard;
    fn side_to_move(&self) -> Color;
    fn unmake_move(&mut self) -> Result<(), MoveError>;

    fn current_hash(&self) -> Self::T;
}

pub trait Table {
    type T;
    fn look_up_hash(&self, key: &Self::T) -> (U, U);
    fn put_in_hash(&mut self, key: Self::T, value: (U, U));

    fn len(&self) -> usize;
    fn is_empty(&self) -> bool;
}

HashPosition traitは基本的に shogi-rsshogi::Position をwrapして使うことを想定して shogi::Position で使うメソッドをほぼそのまま羅列。そこに current_hash(&self) を追加して盤面の状態からハッシュ値を取得できるようにした。

Table はまぁ値を格納したり取り出したりするだけ。途中で状態確認したりtestで使ったりすることもあるかと思い len(&self)is_empty(&self) も一応用意しておいた。

それぞれ Associated type を持つようにしていて、繋ぎこむときに利用している。

Implementations

最初から struct にせず Trait にしたのは、複数の実装方法が考えられたから。

まず Position のハッシュ方法としては、最も簡単に考えられるのが 盤面の状態を表すそれぞれの値をもとに std::hash::Hasher traitを実装したものを使って u64 の値を作る、というもの。盤面各マスの各駒や手番などを何らかの基準で数値化してしまえば計算することができる。

その他に挙げられるのが、Zobrist hashing を使う方法。将棋やチェスなどでは手番ごとの遷移はせいぜい駒が一つ動くだけなので その部分の差分だけ更新して新しいハッシュ値を作る方が効率が良い、という考えのもの。各マスにおける各駒に乱数で値を割り振っておいて、駒が移動した際には移動元と移動先の変化を XOR をとることで高速に計算できる。

Table については 最も簡単なのが std::collections::HashMap に格納する方法。これは文句なしに簡単。

より高速に処理できそうな方法として Vec に格納してしまう、という方法。 Zobrist hashing で usize の値を返すようにして その値をmaskしたものをindexとして利用するという方法が考えられる。

ということで、今回はそれぞれ2つの実装を用意してみた。

  • HashPosition の実装として DefaultHashPositionZobristHashPosition
  • Table の実装として HashMapTableVecTable

DefaultHashPositionPosition をwrapしつつ std::hash::Hash Traitを実装し、std::collections::hash_map::DefaultHasher を使ってハッシュ値を計算している。

use std::collections::hash_map::DefaultHasher;
use std::hash::{Hash, Hasher};

pub struct DefaultHashPosition {
    pos: Position,
}

...

impl HashPosition for DefaultHashPosition {
    type T = u64;

...

    fn current_hash(&self) -> u64 {
        let mut s = DefaultHasher::new();
        self.hash(&mut s);
        s.finish()
    }
}

impl Hash for DefaultHashPosition {
    fn hash<H: Hasher>(&self, state: &mut H) {
        Square::iter().for_each(|sq| {
            self.pos.piece_at(sq).map_or(28, p8).hash(state);
        });
        PieceType::iter().for_each(|piece_type| {
            Color::iter().for_each(|color| self.pos.hand(Piece { piece_type, color }).hash(state))
        });
        match self.pos.side_to_move() {
            Color::Black => 0.hash(state),
            Color::White => 1.hash(state),
        };
    }
}

fn p8(p: Piece) -> u8 {
    ...
}

一方、 ZobristHashPositionBitXorAssign ができ Standard: Distribution<T> の定義できるいくつかの数値型を使えるようGeneric Data Typesで定義している。 make_move() が成功したときのみ 最新のhashを元にMoveに関わる部分だけXORを取って新しいhashを計算する。

use rand::distributions::{Distribution, Standard};
use rand::rngs::SmallRng;
use rand::{Rng, SeedableRng};

pub struct ZobristHashPosition<T> {
    pos: Position,
    table_board: [[[T; 2]; 14]; 81],
    table_hand: [[[T; 19]; 2]; 14],
    table_turn: [T; 2],
    hash_history: Vec<T>,
}

impl<T> ZobristHashPosition<T>
where
    T: Default + Copy + BitXorAssign,
    Standard: Distribution<T>,
{
    pub fn new(pos: Position) -> Self {
        // init table
        ...
        // 初期hash値だけは全マス全持駒から計算する
        let hash = ...
        Self {
            pos,
            table_board,
            table_hand,
            table_turn,
            hash_history: vec![hash],
        }
    }
}

impl<V> HashPosition for ZobristHashPosition<V>
where
    V: Copy + Eq + Hash + BitXorAssign,
{
    type T = V;

    ...

    fn make_move(&mut self, m: Move) -> Result<(), MoveError> {
        match self.pos.make_move(m) {
            Ok(_) => {
                let mut h = self.current_hash();

                h ^= ...  // mに対応する部分だけXORとる

                self.hash_history.push(h);
                Ok(())
            }
            Err(e) => Err(e),
        }
    }
    fn unmake_move(&mut self) -> Result<(), MoveError> {
        match self.pos.unmake_move() {
            Ok(_) => {
                self.hash_history.pop();
                Ok(())
            }
            Err(e) => Err(e),
        }
    }

    fn current_hash(&self) -> V {
        *self.hash_history.last().expect("latest hash has not found")
    }
}

HashMapTableVecTable は以下のような感じ。 HashMapTableEq + Hash の任意の型をキーにでき、 VecTableusize のみ受け付けて key値にmaskをかけた値で Vec の内容にアクセスする。 占有率が上がってきたら古いエントリを捨てるなどの処理も入れるべきかもしれないが、ここでは特に何もしていない。

use std::collections::HashMap;

pub struct HashMapTable<T>
where
    T: Eq + Hash,
{
    table: HashMap<T, (U, U)>,
}

impl<T> HashMapTable<T>
where
    T: Eq + Hash,
{
    pub fn new() -> Self {
        Self {
            table: HashMap::new(),
        }
    }
}


pub struct VecTable {
    table: Vec<(U, U)>,
    mask: usize,
    len: usize,
}

impl VecTable {
    pub fn new(bits: u32) -> Self {
        Self {
            table: vec![(1, 1); 1 << bits],
            mask: (1 << bits) - 1,
            len: 0,
        }
    }
}

impl Table for VecTable {
    type T = usize;
    fn look_up_hash(&self, key: &Self::T) -> (U, U) {
        self.table[*key & self.mask]
    }
    fn put_in_hash(&mut self, key: Self::T, value: (U, U)) {
        if self.look_up_hash(&key) == (1, 1) {
            self.len += 1;
        }
        self.table[key & self.mask] = value;
    }
    fn len(&self) -> usize {
        self.len
    }
    fn is_empty(&self) -> bool {
        self.len == 0
    }
}

Solver

で、こうして用意した HashPositionTable を使って Solver を作る。

pub struct Solver<P, T> {
    pub pos: P,
    pub table: T,
}

impl<P, T> Solver<P, T>
where
    P: HashPosition,
    T: Table<T = P::T>,
{
    pub fn new(pos: P, table: T) -> Self {
        Self { pos, table }
    }
    pub fn dfpn(&mut self) {
        ...
    }
}

HashPositionTable のそれぞれの Associated type T が一致することが求められるので、以下のような組み合わせで作ることが出来る

    let p = DefaultHashPosition::new(pos);
    let t = HashMapTable::new();
    let mut solver = Solver::new(p, t);

DefaultHashPositionT = u64 なので自動的に u64HashMap のkeyに使われる

    let p = ZobristHashPosition::<u64>::new(pos);
    let t = HashMapTable::new();
    let mut solver = Solver::new(p, t);

ZobristHashPosition で指定可能な任意の型が使える

    let p = ZobristHashPosition::new(pos);
    let t = VecTable::new(20);
    let mut solver = Solver::new(p, t);

VecTableT = usize なので自動的に usizeZobristHashPosition になる

それぞれ速度に影響でたり hash計算方法や格納方法によって衝突が起きる可能性が違ってきたりするはず。 解かせたい問題によって実装を切り替えるなどもアリなのかもしれない。

df-pn

で、この Solver がdf-pnアルゴリズムで探索していく。 このコア部分だけだと100行ちょっとしか必要ない。

impl<P, T> Solver<P, T>
where
    P: HashPosition,
    T: Table<T = P::T>,
{
    ...

    pub fn dfpn(&mut self) {
        let hash = self.pos.current_hash();
        // ルートでの反復深化
        let (pn, dn) = self.mid(hash, &(INF - 1, INF - 1));
        if pn != INF && dn != INF {
            self.mid(hash, &(INF, INF));
        }
    }
    // ノードの展開
    fn mid(&mut self, hash: P::T, pd: &(U, U)) -> (U, U) {
        // 1. ハッシュを引く
        ...
        // 2. 合法手の生成
        let children = generate_legal_moves(&mut self.pos);
        // 3. ハッシュによるサイクル回避
        match self.pos.side_to_move() {
            Color::Black => self.table.put_in_hash(hash, (pd.0, pd.1)),
            Color::White => self.table.put_in_hash(hash, (pd.1, pd.0)),
        }
        // 4. 多重反復深化
        loop {
            ...

            let (best, ...) = self.select_child(&children);
            let phi_n_c = ...
            let delta_n_c = ...
            let (m, h) = best.expect("best move");
            self.pos.make_move(m).expect("failed to make move");
            match self.pos.side_to_move() {
                Color::Black => self.mid(h, &(phi_n_c, delta_n_c)),
                Color::White => self.mid(h, &(delta_n_c, phi_n_c)),
            };
            self.pos.unmake_move().expect("failed to unmake move");
        }
    }
    // 子ノードの選択
    fn select_child(&mut self, children: &[(Move, P::T)]) -> (Option<(Move, P::T)>, ...) {
        ...
    }
}


pub fn generate_legal_moves<P>(pos: &mut P) -> Vec<(Move, P::T)>
where
    P: HashPosition,
{
    ...
}

合法手の生成によって child nodes を展開していくことになるが、その時点でその遷移後のハッシュ値が計算できるので generate_legal_movesMove とそれが適用された後のハッシュ値のペアを返すようにして使い回すようにしている。

generate legal moves

ここは HashPosition さえあれば計算できるので Table は必要ない。

通常の Move::Normal については単純で、 player_bb() で盤上の自陣駒が列挙できて そこから move_candidates() で移動先の候補を列挙できるので、そこからのすべての組み合わせで一旦 make_move() を実行してみる。その結果、

  • 攻方の場合は 動いた後が玉方に対する王手になっている
  • 玉方の場合は 動いた後が自陣の王手が外れている

という条件を満たしていれば legal move として選択されることになる。

pub fn generate_legal_moves<P>(pos: &mut P) -> Vec<(Move, P::T)>
where
    P: HashPosition,
{
    let mut children = Vec::new();
    // normal moves
    for from in *pos.player_bb(pos.side_to_move()) {
        if let Some(p) = *pos.piece_at(from) {
            for to in pos.move_candidates(from, p) {
                for promote in [true, false] {
                    let m = Move::Normal { from, to, promote };
                    if let Ok(h) = try_legal_move(pos, m) {
                        children.push((m, h));
                    }
                }
            }
        }
    }
    
    ...

    children
}

fn try_legal_move<P>(pos: &mut P, m: Move) -> Result<P::T, MoveError>
where
    P: HashPosition,
{
    match pos.make_move(m) {
        Ok(_) => {
            let mut hash = None;
            if pos.side_to_move() == Color::Black || pos.in_check(Color::White) {
                hash = Some(pos.current_hash());
            }
            pos.unmake_move().expect("failed to unmake move");
            if let Some(h) = hash {
                Ok(h)
            } else {
                Err(MoveError::Inconsistent("Not legal move for tsumeshogi"))
            }
        }
        Err(e) => Err(e),
    }
}

Move::Drop についてはちょっと面倒で、盤上すべて眺めて空いているマスすべてに対して持駒に持っているものを置いてみる、というのが簡単に列挙はできるのだけど、例えば攻方は相手玉に届かない位置に打つのはすべて無意味だし 玉方は飛び駒以外で王手されている際に駒を打つ手は有り得ないので、そういったものは事前に除外しておかないとかなり非効率な探索になってしまう。

ともかく shogi::Position のinterface的に、合法手の判定は「何らかの Movemake_move() してみて それが Err を返さなかったら合法」と判定するのが基本になる。明らかに非合法な手は事前に除外した方が勿論良いが、処理の先頭で判定しているものもあるので二度手間にならない程度であれば良いようには思える。

benchmark

とりあえずここまででdf-pnアルゴリズムによる探索が動くので、実装による速度の違いを調べてみた。 nightly で使える cargo bench

  • DefaultHashPosition + HashMapTable
  • ZobristHashPosition + HashMapTable
  • ZobristHashPosition + VecTable

のそれぞれの組み合わせで Solver を作り 幾つかの入力に対して探索を実行。

% cargo +nightly bench
    Finished bench [optimized] target(s) in 0.13s
     Running unittests (target/release/deps/tsumeshogi_solver-9e8e57cabb9c5863)

running 1 test
test tests::test_solve ... ignored

test result: ok. 0 passed; 0 failed; 1 ignored; 0 measured; 0 filtered out; finished in 0.00s

     Running unittests (target/release/deps/bench-2ca32c22a0dba4e1)

running 3 tests
test bench_default_hashmap ... bench:  11,456,869 ns/iter (+/- 681,707)
test bench_zobrist_hashmap ... bench:  11,205,930 ns/iter (+/- 674,396)
test bench_zobrist_vec     ... bench:  11,280,294 ns/iter (+/- 749,866)

test result: ok. 0 passed; 0 failed; 0 ignored; 3 measured; 0 filtered out; finished in 10.41s

どれも大して変わらなかった!!

おそらく現状 generate_legal_moves のところが遥かに支配的で、ここが大きなボトルネックになっている限りはハッシュの計算や格納方法での差異は殆ど出てこない、のかな…。

もうちょっとprofilingとか試してしっかり見直したいところ。

最適解の導出

ところで solver.dfpn() の探索処理が完了したところで、詰将棋の「解答」が出てくるわけではない。 手元に残るのは root から探索した各盤面に対する (証明数(以下pn), 反証数(以下dn)) が記録された Table があるだけなので、ここからそれらの値を元に詰みの経路を見つける必要がある。

root の (pn, dn)(0, INF) になっていた場合に、その root が「詰み」であると判明したことになる。その child nodes には今度は (INF, 0) になっているものが存在しているはず。その child ではまた (0, INF) 、… と辿るたびに AND/OR が反転するが ともかく正しく詰みを見つけられた場合はそういった node を見つけられるので、葉(それ以降は合法手が無い、つまり詰み)までDFSで辿っていけば詰みの手順を列挙することが出来る。

fn solve(pos: Position) {
    let mut solver = Solver::new(...);
    solver.dfpn();

    let mut answers = Vec::new();
    search_all_mates(&mut solver, &mut Vec::new(), &mut answers);
}

fn search_all_mates<P, T>(
    s: &mut Solver<P, T>,
    moves: &mut Vec<Move>,
    answers: &mut Vec<Vec<Move>>,
) where
    P: HashPosition,
    T: Table<T = P::T>,
{
    let mut leaf = true;
    for &(m, h) in &generate_legal_moves(&mut s.pos) {
        let pd = s.table.look_up_hash(&h);
        if (s.pos.side_to_move() == Color::Black && pd == (INF, 0))
            || (s.pos.side_to_move() == Color::White && pd == (0, INF))
        {
            leaf = false;
            moves.push(m);
            s.pos.make_move(m).expect("failed to make move");
            search_all_mates(s, moves, answers);
            s.pos.unmake_move().expect("failed to unmake move");
            moves.pop();
        }
    }
    if leaf {
        answers.push(moves.clone())
    }
}

これによって得られる answersdfpn() の探索で見つけることができた詰み手順だが、最短であるとは限らない。このへんは難しいところで 余詰がある場合はまた他の手順で詰むかどうかも判定する必要がある…。ここはまだ実装できていない。

ただ「攻方のある手で詰む」というのは見えているので、その中での玉方の最善応手を見つけることは出来そう。玉方は最長で駒を余らせない応手を選ぶのが正解なので、列挙された answers の中から「詰みまでの手数が最長で かつ詰んだ後の攻方の持駒が少ない(無い)もの」を解として選ぶことが出来る。

また面倒なのが「無駄合駒」で、単純に手数の長いものを選択しようとするとこれに引っ掛かる。今回は

  1. 玉方が合駒として打った駒が後に取られて
  2. 最終的に詰んだときにそれが攻方の持駒に入っている

という場合に無駄合駒だったとみなして候補から外すようにした。合駒をせずに別の方法で王手回避した場合は必ず探索しているはずなので、単純に除外するだけで良いはず…。

これで、余詰の無い問題に対しては「玉方が最善の応手をして駒の余らない最長の手順」を選択できるようになっている。と思う。

残課題

と、ここまでは上手く解けた例の話で、まだまだ上手く解けていないケースが存在しているのを把握している。 例えば以下のような問題で、

f:id:sugyan:20211111001858p:plain

(出典: https://www.shogi.or.jp/tsume_shogi/everyday/20211183_1.html)

正解手順は ▲3四飛 △同玉 ▲4四飛成 なのだけど、dfpn() で探索していると ▲4四飛成 △3二玉 ▲4一竜 △3三玉 ▲4四竜 △3二玉 ... と無限に追いかけっこが発生して詰まないループを検出し、結果として root の (pn, dn)(1, INF) という値になる。正解の詰み手順である ▲3四飛 は探索されずに終わってしまている。

元の論文では GHI (Graph History Interaction) 問題を回避するために閾値を調整して二回探索する手法で解決しているように書いてあるが、その通りに実装しているつもりなのだけど上手くいっていないようだ…。 ここはもうちょっと深く追って調べてみる必要がある。

その他にも 上記のような連続王手の千日手になる手順に辿り着く可能性がある問題に対して うまく探索が完了していないケースがありそうだ。

やねうら王公式からクリスマスプレゼントに詰将棋500万問を謹呈 の問題を食わせて様々なエッジケースを拾えるかな、と思ったが まずそもそも先手から攻める実装しか考えていなくて「後手番から始まって先手玉を詰ませる」というケースを考えていなかった。そこも対応できるように直す必要がある。

あとは前述した通り余詰のチェックもまだ出来ていないので、探索深さ上限を指定して(?)別の手順を探索できるようにはしておきたい。

優越関係などを利用することでもっと長手数のものも解けるようになるだろうか。性能限界と改善の可能性はもう少し調べたい。 shogi-rs を変更してチューニングしてもっと早くなるだろうか?とか。

その他にも入出力の形式をもっと選べるようにconverterを作っておきたいと思っている。

creative codingに入門してみている

動機・目的

上記の通り、「子に喜んでもらえるものを作る」ことを目指す。 特にshort codingなどにチャレンジしたりはせず、またgenerative artのようなものよりはどちらかというと"触って遊べる"インタラクティヴなものを優先的に。

1歳半の我が子は最近はiPadの操作も慣れてきていて、幼児向けアプリなどで画面を指で触って楽しむことは出来るようになっている。複雑な操作はまだ難しいが 直感的に動かせるようなものなら楽しんでくれるのでは(という勝手な期待)。

…とはいえ 単純に自分が面白そうと思ったからやるだけなのだけど。@nagayamaさんなど 周りでやっている人もいて見ているととても楽しそうで興味を持ったので。

環境

iPadで簡単に動かせるのが良い、ということで p5.js を使用してブラウザ上で動くものを作る。

最近Rust触っている身としては Nannou も気になるところだったけど、どうもブラウザ上での動作はまだ対応中?で厳しそうな雰囲気があったので今はまだ手を出さずにいる。

作品

1. おえかき

f:id:sugyan:20211008215333g:plain

まずは単純に、指でなぞった軌道に色がつく、くらいのものをやってみた。 その色がカラフルに変化すればまぁ面白いかな?と時間経過でHSB空間上でのHue値だけを変化させるようにした。

リセットの必要なく幾らでも描き続けられるように、時間経過とともに古い円から消えるようにすることを考えた。透過させていったり小さくしていったり試していたけど、randomで座標を揺らしながら小さくしていったら何か面白い動きになった。 そこで @amagitakayosi さんから「noiseを使うといいですよ」とアドバイスをいただいた。noiseでユラユラと揺らしながらだんだん小さくなりつつ揺れ幅を増やしていくと 亡霊のような不思議な消え方をするようになったのでこれを採用することにした。

音も出た方が良いよね、ということで p5.soundOscillator を使って三角波の音を発生させ、早く動かして円が増えるにつれて音量と周波数が増えるようにしてみたところ より亡霊っぽくなった。

2. シャボン玉

f:id:sugyan:20211008220348g:plain

noise の性質が面白かったのでもっと色んなものを揺らしてみよう、と思い シャボン玉を作ってみた。 ellipse で縦横のサイズを指定した楕円が描けるので、その各方向のサイズを noise で変化させながら さらに noise の載った回転角で rotate してやることで 泡のようなユラユラした球体の動きを表現できた。

風に吹かれて飛んでいく動きを表現するために左下方向からランダムな向きで等速直線運動、わずかに上方向には等加速度で移動する軌道をつくり、そこにさらにxy方向それぞれに noiseで微妙に揺らす。フワーっと飛んでいるような動きになった気がする。

シャボン玉っぽさを表現するのは難しかった。干渉による虹色のような光り方はどうにもムリそうだったので、個々に色をつけてそのhue値を時間経過で変化させるくらいに留めた。が 意外にそれはそれで可愛くてポップな感じになったし悪くなかった気がする。ただ赤は鮮やかすぎて気持ち悪かったのであまり赤くはならないよう範囲を調整した。 球体っぽさを出すために内側にいくにつれてalpha値が強くなるよう段階を変えながら複数の楕円を描画し、あとは何となく左上の方に白い楕円を配置するだけでわりとそれっぽい感じになったと思う。

当然タッチしたら割れるようにはしたい、と思い とりあえず適当に当たり判定つけて簡単なエフェクトはつけてみたがなんか微妙だ。ここも表現方法を工夫したいところ… 音も必要か…?

実装

というわけで、こうして作ってみた p5.js のsketchはそれ単体としても取っておきたいし、Webアプリ上でそれぞれを見られるようにしたい、と思い それらを閲覧できるような置き場を Next.js で作ってみた。

https://cc.sugyan.com/

今回、Next.jsに初めて触った。create-react-appでも良いかと思ったけどroutingを自分で書きたくなかったというのがあり Nextのdynamic routingで1個だけファイル置いておけば良いのはラクで良かったと思う。利点はそれだけかもしれないけど。 とはいえ Vercel はpushしたものがすぐに反映されて開発体験は良かった。

p5.js のsketchをReactで扱うための react-p5-wrapper というComponent libraryはあったのだけど、どうも画面遷移した際にmouse eventなどが残ってしまっていたり うまく用途と合わなかったので結局wrapper部分は最低限の自作で間に合わせた。それでもsound周りでおかしな挙動が残っていたりしてまだ完全には解決していない…。

p5.js のsketchはNextでSSRできないので Dynamic Import を利用する必要がある、というところは書き方がなかなか理解できずだいぶ苦戦した。。

あと当然ながらすべてTypeScriptで書いているのだけど、どうも @types/p5 が少し古くて最新の p5.js に追従できていない部分があったり それを更新するためのツール? p5.ts がメンテ止まってしまっていたり また p5.sound まわりはTypeScriptで上手くimportできなかったり 、など問題は色々あるように感じた。余裕があればこのへんが改善されるようcontributeしていきたいが、、、

展望

まだまだよく知らない部分も多いので、他の人の作品なども見つつ 自分なりに楽しいものが作れるようにしていきたい。 子にはまだ難しいだろうけど各種アルゴリズムの可視化とかは個人的にやってみたいところ。

しかしcreative codingはわりと沼で、ちょっと表現を変えようとパラメータいじったりするだけで数時間もってかれたりするのでハマりすぎないようには注意したいところ…。

Repository

関連

ISUCON11予選のNode.js実装を書いた

ISUCON11 予選おつかれさまでした。

ここ数年は参加者として予選敗退を繰り返してきたのだけど、今年はちょっと違う関わり方をしてみるか、と思い 「参考実装の移植」に立候補してみました。

isucon.net

Node.js担当として採用していただき、ちょっと不安もあったので id:hokaccha 氏にレビュアーとしてついてもらって、言語移植チームとして加わりました。

Node.js 実装

github.com

中身としては素朴な express のアプリケーションで、TypeScriptで実装しました。 mysql clientには mysql2/promise を使うことで async/await で簡潔に書けそうだったのでそれでやってみました。

www.npmjs.com

行数としては元実装の Go 1262行に対し 1243行とほぼ同等、それなりに丁寧に型定義などを書きつつ 元実装を忠実に再現したものになったかと思います。

昨年のisucon10のリポジトリなどをとても参考にしつつ、今回の自分の実装が未来の実装者の参考にもなるように、と気をつけて書いたつもりです。

1組だけですがNode.js実装で本選にも残ったチームも居たようで良かったです。

isucon.net

開発環境

移植作業をする時点で既にGoの参考実装やbenchmarker、そして開発環境がある程度できあがっていて、作業を進めやすくてとても助かりました。このへんは作問チームのレベルの高さをすごく感じました。

複数のコンポーネントからなるそれなりに複雑なアプリケーションながらも、docker-compose.yml や Makefile がしっかり用意されていて、そこに自分の実装する言語用の環境を用意できればコマンド一発でWebアプリが起動できるし benchmarkerを走らせたりもできる。 benchmarkerは -no-load オプションで負荷走行前のアプリケーション互換性チェックシナリオを走らせるので、まずはそこがすべて通るようになれば大体の移植は出来ていると判断できる、という具合。

勿論CIでもテストが走るようになっていて、それらが通っていてさらに作問チームメンバーやアドバイザリーからレビューを受けた上でapproveされたらmergeできる、といったルールもしっかり整備されていて、とても体験の良い開発環境でした。

実装についての疑問や相談もSlack上でいつでも作問メンバーが素早く回答してくれて、とにかく素晴らしいチームだな、と思いました。 このチームの人たちと同じプロジェクトに取り組めたというだけで 今回応募してみて本当に良かったと思っています。

Contributions

Node.jsの実装も一通り出来たところで 他の言語実装も出揃ってきていたので試しに動かしてみて、細かいエラーが出ていたところを修正したりもしました。

「オレでなきゃ見逃しちゃうね」的な細かいものとか

あとはPerl書ける人が少なかったようなので「いちおう私も多少Perlの経験あるのでレビューくらいなら」とちょっと見てみたり

benchmarkerの細かい挙動について指摘したりライブラリのバグをついたりもしました

あと実際に本番前々日くらいにサーバ上で各言語の初期実装に対してbenchmarkしてみたところ、何故かNode.jsがGo実装よりも2倍以上高いスコアが出た(!)という謎現象が見つかり、調査の結果それはNodeがたまたまbenchmarkerの秘孔をつく動作をしていたことが分かり修正されたのですが、そういうのを見つけることが出来るという点でも複数言語での移植は意義があるのだなぁと思いました。

tagomorisバグ

余談。

Perlの実装を手伝っているときに、benchmarkerを走らせていると何故か予期せぬところで 401 を返していてチェックが失敗するという現象が起きていた。

401 ってことはcookie-sessionまわりだよな〜 でも特に変なところとか無いはずだしな〜 と id:kfly8 氏と一緒に見ていて、ところで Plack::Middleware::Session::Cookiesecret"tagomoris" とかじゃなくて 今回は "isucondition" (もしくは SESSION_KEY 環境変数) で統一するって話じゃないですかと指摘してそこだけ直してもらった

https://github.com/isucon/isucon11-qualify/pull/1099/commits/57f165c73f92bac69a449912d8cb8118b05bf38c

 builder {
     enable 'ReverseProxy';
     enable 'Session::Cookie',
-        session_key => $ENV{SESSION_KEY} // 'isucondition_perl',
+        session_key => 'isucondition_perl',
         expires     => 3600,
-        secret      => 'tagomoris';
+        secret      => $ENV{SESSION_KEY} || 'isucondition',
     enable 'Static',
         path => qr!^/assets/!,
         root => $root_dir . '/../public/';

この変更を入れたら 先述の 401 のエラーが出なくなり…。

「えっ cookie の secret key を "tagomoris" から違う文字列に変えただけでバグが直ったの!?」と混乱した、という出来事。

種明かしをするとこの変更は secret 指定の末尾が ; だったのを , に変えてしまっているというミスが含まれていて。

-MO=Deparse してみると 変更前は

&builder(sub {
    enable('ReverseProxy');
    enable('Session::Cookie', 'session_key', 'isucondition_perl', 'expires', 3600, 'secret', 'tagomoris');
    enable('Static', 'path', qr"^/assets/", 'root', $root_dir . '/../public/');
    $app;
}

というものだったのが変更後は

&builder(sub {
    enable('ReverseProxy');
    enable('Session::Cookie', 'session_key', 'isucondition_perl', 'expires', 3600, 'secret', 'isucondition', enable('Static', 'path', qr"^/assets/", 'root', $root_dir . '/../public/'));
    $app;
}

と解釈されてしまう。続く Static middleware を enable した結果が Session::Cookie の引数に並べられる形になり、内部ではその値は無視されるのだろうけど、何が起こっているかというと「enable が呼ばれる順番が変わる」。

ここでまた別の事象として、benchmarkerが「/assets/ 以下に含まれるファイルをGETした際に Set-Cookie ヘッダが含まれているとそれによってbenchmark scenarioを回しているagentが別人になってしまい その後のリクエストで 401 になってしまう」というバグがあった。

つまり このpsgiでは 先に Session::Cookieenable していると その後に呼ばれる Static のファイルたちにも Set-Cookie がつくことになり、そのbenchmarkerのバグをつくことになってしまっていた。 "tagomoris" を修正した際に間違えて ;, に変えてしまたことにより意図せず StaticSession::Cookie の順に enable する形に変わっていて そのバグをつかないように変更されたので エラーに遭遇しなくなった、というオチでした。

奇妙な挙動にとても戸惑ったけど 複数の不具合が密接に絡んで起きた奇跡のような現象でした。という話。

いやー数年ぶりに書いたけどやっぱりPerlむずかしい…。 一晩で解決できたのも奇跡だったのかもしれない

本選へ

…というわけで ともかく予選の移植は無事(?)に完遂し、本番でも特に言語実装依存の不具合なく終えられたようで何よりでした。

また本選に向けて頑張っていこうと思います。

よろしくお願いします。