というわけで突然Rustで詰将棋ソルバを作りたくなり、作った。
github.com
現時点ではまだ完成度は低くて6割ほどかな…。
とはいえそこらの素直な詰将棋問題なら普通に解けると思う。
冒頭の画像は看寿賞作品の3手詰「新たなる殺意」を2秒弱で解いたもの。
先行事例
将棋プログラムの多くはC++で書かれていて 最近はRustも増えてきているのかな？
しかし「詰将棋を解く」ことに特化しているものはあまり多くはなさそうだった。
なかでもRustで書かれているものはna2hiroさんによるものくらいしか無さそうで、
github.com
これを大いに参考にさせていただいた。
しかしこれはおそらく後述の盤面ハッシュ値を生成するために手元で変更を加えているものを使っているようで、手元ではビルドも出来ない。
また個人的にはsfenではなくCSAや他の形式を入出力に使いたいなどの要望もあり、そういった問題も解決しつつ自分の理解も深めるために自作してみることにした。
過去に、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-rs の shogi::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 の実装として DefaultHashPosition と ZobristHashPositionTable の実装として HashMapTable と VecTable
DefaultHashPosition は Position を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 {
...
}
一方、 ZobristHashPosition は BitXorAssign ができ 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 {
...
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 ^= ...
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")
}
}
HashMapTable と VecTable は以下のような感じ。 HashMapTable は Eq + Hash の任意の型をキーにでき、 VecTable は usize のみ受け付けて 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
で、こうして用意した HashPosition と Table を使って 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) {
...
}
}
HashPosition と Table のそれぞれの Associated type T が一致することが求められるので、以下のような組み合わせで作ることが出来る
let p = DefaultHashPosition::new(pos);
let t = HashMapTable::new();
let mut solver = Solver::new(p, t);
↑ DefaultHashPosition が T = u64 なので自動的に u64 が HashMap の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);
↑ VecTable が T = usize なので自動的に usize の ZobristHashPosition になる
それぞれ速度に影響でたり 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) {
...
let children = generate_legal_moves(&mut self.pos);
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)),
}
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_moves は Move とそれが適用された後のハッシュ値のペアを返すようにして使い回すようにしている。
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();
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的に、合法手の判定は「何らかの Move で make_move() してみて それが Err を返さなかったら合法」と判定するのが基本になる。明らかに非合法な手は事前に除外した方が勿論良いが、処理の先頭で判定しているものもあるので二度手間にならない程度であれば良いようには思える。
benchmark
とりあえずここまででdf-pnアルゴリズムによる探索が動くので、実装による速度の違いを調べてみた。
nightly で使える cargo bench で
DefaultHashPosition + HashMapTableZobristHashPosition + HashMapTableZobristHashPosition + 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())
}
}
これによって得られる answers は dfpn() の探索で見つけることができた詰み手順だが、最短であるとは限らない。このへんは難しいところで 余詰がある場合はまた他の手順で詰むかどうかも判定する必要がある…。ここはまだ実装できていない。
ただ「攻方のある手で詰む」というのは見えているので、その中での玉方の最善応手を見つけることは出来そう。玉方は最長で駒を余らせない応手を選ぶのが正解なので、列挙された answers の中から「詰みまでの手数が最長で かつ詰んだ後の攻方の持駒が少ない(無い)もの」を解として選ぶことが出来る。
また面倒なのが「無駄合駒」で、単純に手数の長いものを選択しようとするとこれに引っ掛かる。今回は
- 玉方が合駒として打った駒が後に取られて
- 最終的に詰んだときにそれが攻方の持駒に入っている
という場合に無駄合駒だったとみなして候補から外すようにした。合駒をせずに別の方法で王手回避した場合は必ず探索しているはずなので、単純に除外するだけで良いはず…。
これで、余詰の無い問題に対しては「玉方が最善の応手をして駒の余らない最長の手順」を選択できるようになっている。と思う。
残課題
と、ここまでは上手く解けた例の話で、まだまだ上手く解けていないケースが存在しているのを把握している。
例えば以下のような問題で、
(出典: 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を作っておきたいと思っている。
