成果物
局面を編集し指定し、その局面からの詰み手順を探索する。クエリパラメータにSFEN文字列を入れることで初期局面を指定することもできる。(例)
現時点での仕様は
- 探索結果の指し手はCSAの文字列配列
- 最短・最善の解を返すとは限らない
- 探索しきれない場合は5秒で打ち切り
Repository: https://github.com/sugyan/tsumeshogi-solver-wasm
以下はこれが出来るまでの過程のメモ。
Rust製ソルバの改良
昨年末に、Rustでdf-pn探索を実装して詰将棋のソルバを作った。
ある程度動作していて そこそこの探索もできていたが、まだちょっと遅いので改善したい、という状態だった。
その後、今年に入ってから将棋AIを作成しようと挑戦を始め、その第一歩として合法手生成と局面探索を高速に実行するためのライブラリを自作することになった。
これは詰将棋ソルバのために作ったわけではなかったが、これを使うことでソルバの方も改善されそうだな、と思ったので組み込んでみることにした。
結果として、簡単なベンチマークで100倍ほど速くなるという予想以上の改善になった。
探索部の抽象化
以前は 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は数十行程度で実装完了した。
まとめ
まだソルバとしては未完成ながら、とりあえずWebブラウザ上で動作する詰将棋Solverを作って公開することが出来た。
図らずも、「フロントエンドのUIライブラリ」「バックエンドの探索ロジック」「探索のための合法手ライブラリ」すべてを自作したことになる…。結果的には良いものが出来たと思うので無駄ではなかった、と思う。