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

以前は 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を自作してみた。

https://sugyan.com/shogi-player-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ライブラリ」「バックエンドの探索ロジック」「探索のための合法手ライブラリ」すべてを自作したことになる…。結果的には良いものが出来たと思うので無駄ではなかった、と思う。