昨年末に出版された「強い将棋ソフトの創りかた」という本を読んで、自分も将棋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 {
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よりは多少遅くても仕方ないと割り切りつつ出来る限り正しく型安全で unsafe や unwrap を極力使わない実装にするようにしてみている。
まだ完全に実装できていない部分もあるが、 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());
n &= n - 1;
assert_eq!(62, n.trailing_zeros());
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 ** 7 の 128 通りしか存在しない。ので、手番数(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;
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()])
}
とにかく事前に計算できるものは先に用意しておいて極力計算回数を減らす、という工夫が大事なようだ。
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
まとめ
結局ライブラリ作りに一生懸命になってしまって、将棋ソフト作りにはまったく取り組めていない…。
