前置き
Rustで将棋の高速合法手生成ライブラリを作り始めていて、
その後 shogi_core というライブラリが出来てきたのでそれを使うように変更したりした。
それまでは基本的に Rust版Apery の実装を参考にしていたが、駒の利きを求めるところで改善したいところがあり、Qugiyの手法を取り入れてみようと検討した。
そこで色々試したり考えているうちに別のやり方を思いついたのでメモしておく。
先にオチを書いておくと、チェスの世界では既出の手法でした。
飛び利き計算いろいろ
基礎知識
基本的にBitboardを使っての駒の利きは表引きすることで求める。 事前に「この位置にいるこの手番のこの駒は、ここに動ける」というのを全パターン計算してあれば、テーブルから引いてくることで一発で移動先が求まる。
struct PieceAttackTable([[Bitboard; Color::NUM]; Square::NUM]); impl PieceAttackTable { fn new() -> Self { ... // 事前計算 } pub fn attack(&self, sq: Square, c: Color) -> Bitboard { self.0[sq.array_index()][c.array_index()] } }
これを全駒種に対して用意しておけば良い。 …のだが、香車・角行・飛車の3種の「飛び駒」(という名称が正しいのかよく分かっていない) についてはそうはいかない。これらは「最初に他の駒にぶつかるまで一方向にどこまでも動ける」ので、利きの届く範囲は他の駒の位置に依存する。 ので簡単な表引きでは求めることができず、様々な手法が考案されてきていた。
以下、利きを求めるために使われる「盤上に(自陣敵陣問わず)駒が存在している位置」を表すBitboardをOccupancyと呼ぶことにする。
縦型Bitboardでの香車の利き
利きはOccupancy依存とは言っても、考慮すべきは進む方向のSquareだけで良い。一段目にいる後手香車が駒の存在を意識すべきは同じ筋の二段目〜八段目だけ(九段目は居ても居なくてもそこまで届く、と考えられる)なので、7つのSquareにそれぞれ駒が居るか居ないかの情報だけあれば良い。
ということはその7つのSquareの状態は全パターン列挙しても高々128(1 << 7)通りなので、それくらいならテーブルを用意しておいて引ける、という考え方。
pub struct LanceAttackTable(Vec<Vec<Vec<Bitboard>>>); impl LanceAttackTable { const MASK: usize = (1 << 7) - 1; fn new() -> Self { let mut table = vec![[[Bitboard::empty(); 1 << 7]; Color::NUM]; Square::NUM]; ... // 事前計算 } pub fn attack(&self, sq: Square, c: Color, occ: &Bitboard) -> Bitboard { let index = Self::MASK & ((occ.value() >> ((sq.file() * 9) + 1)) as usize); self.0[sq.array_index()][c.array_index()][index] } }
少しテーブルのサイズは大きくなるが、それほど影響ない範囲で事前計算しておける。
ここで、縦型にレイアウトしているBitboardだとOccupancyの状態からindexに変換する際に利点が出てくる。 縦の動きの場合は対象の筋のbitが連続して並ぶので、これを適当にshiftしてmaskかければパターンのindexを簡単に求めることができる。
角行・飛車の利き (Magic Bitboard / PEXT)
そして角行・飛車でも同じように全パターンを列挙して表引きしたいが、香車の場合と違って
- パターンの数が多く巨大なテーブルが必要、事前計算にも時間がかかる
- 具体的には 角行が
20,224パターン、飛車が495,616パターン
- 具体的には 角行が
- 対象bitが連続して並ばないのでindexの計算が容易ではない
といった問題が出てくる。
前者については apery_rust は once_cell crateを使うことで最初に呼ばれたときにだけ初期化の計算する方式をとっている。
後者について。 前述の通り、一直線に並んでいる香車のような動きなら全体をshiftすることで簡単にindexを計算できるが、横や斜めの動きに関しては注目すべきbitが飛び飛びになるので同じようにはできない。 何とかして対象となるmaskの位置のbitだけの値をかき集めてきて数値を得たい。
.##.#.#. ##.#.#.# | occupancy
..#..#.. #..#..#. | mask
( 1 0 1 1 0 )
----------------------
10110 | f(occupancy, mask)
これをまさしく実現してくれるのが BMI2のPEXT命令。これを使うことで香車の利きのindex算出と同様のことができるので、一発で表引きできるようになる。
ただしPEXTは64bit整数にしか適用できないので、Bitboard内部で2つの64bit整数に分けて状態保持している場合は p[0] | p[1] のようにmergeした上でPEXTにかけるなどの工夫が必要になる。この方法が問題なく動作するためには縦型でも1〜7筋と8,9筋で分ける必要が出てくる、など制限が生まれる。
歴史的にはこのPEXT方式が出てくる前にMagic Bitboardが発明されていた、のかな。PEXTと同様の処理をMagic Numberを乗算することで実現する、というもの。
PEXTの方がMagic Numberを用意する必要がないという利点がある一方、
- 特定の命令セットに依存することになる
- 全環境での動作をサポートするには何らかのfallbackは必要
- 一部のCPUアーキテクチャでは異常に遅いらしい
といった問題はある。また巨大なテーブルが必要という問題は依然として残り続ける。 このあたりは以下の記事などのBitboard関連シリーズがとても詳しく、勉強になりました。
Qugiyの手法
近年の将棋ソフトウェアではおそらく前述のMagic Bitboard/PEXTでの表引きが主流となっている(要出典)が、2021年のWCSC31で登場したQugiyが新しい手法を考案して話題になったらしい。以下の記事が詳しい。
要するに加減算での桁上げ/桁借りの伝搬を利用して最初に立っているbitまでのmaskを作る、というのが基本概念のようだ。
(.##.#.#. ##.#.... | occupancy) #..#.#.# ..#.#### | !occupancy #..#.#.# ..##.... | !occupancy + 1 --------------------- ............##### | !occupancy ^ (!occupancy + 1)
減算ならより簡潔で
.##.#.#. ##.#.... | occupancy .##.#.#. ##..#### | occupancy - 1 --------------------- ........ ...##### | occupancy ^ (occupancy - 1)
この概念でいうと飛び飛びのmaskになる角行・飛車でも同様に考えることができ、
.##.#.#. ##.#.... | occupancy ..#..#.. #..#..#. | mask --------------------- ..#..... #..#.... | masked = occupancy & mask ..#..... #...#### | masked - 1 --------------------- ........ ...##### | masked ^ (masked - 1) ..#..#.. #..#..#. | mask --------------------- ........ ...#..#. | mask & (masked ^ (masked - 1))
と、mask上で最初にoccupancyにぶつかるまでの利きをbit演算だけで求めることができる。
ただし、この方法は桁上げ/桁借りが伝搬する方向にしか適用できず、つまり上から下にレイアウトされている縦型Bitboardでは下方向か左方向にしか使えない。ので、上方向や右方向に対してはbyte swapやunpackを使うなどの工夫をしている、とのこと。
あとは4方向にそれぞれ別々に求める必要があるところを、左下方向の2つと右上方向の2つそれぞれをAVX2命令で並列処理するようにしているらしい。
Leading/Trailing Zerosを使う
Qugiyの手法を実装しようとしたものの、もうちょっと簡単に同じようなことを実現できないかな、と考えていて、この方法を思いついた。
「要するに加減算での桁上げ/桁借りの伝搬を利用して最初に立っているbitまでのmaskを作る」というのが肝だったので、つまり最初に立っているbit(rightmost set bit)を見つければそこまでのmaskを作ってかけてやれば良いだけではないか、と。
.##.#.#. ##.#.... | occupancy ..#..#.. #..#..#. | mask --------------------- ..#..... #..#.... | masked = occupancy & mask ........ ...#.... | r = rightmost set bit of masked ........ ..#..... | r << 1 ........ ...##### | (r << 1) - 1 ..#..#.. #..#..#. | mask --------------------- ........ ...#..#. | mask & ((r << 1) - 1)
結局、知りたいのはoccupancyなりoccupancy & maskなりの「最初に立っているbitの位置」だった。これは最下位から見る場合はBitboardからSquareを取り出すときにも使われている Trailing Zeros そのもの。
で、同様のことは逆方向でも考えることができて、こちらは Leading Zeros を使ってleftmost set bitを求めることが出来る。作るmaskが反転する必要あるだけ。
.#..###. ##.#.... | occupancy ..#..#.. #..#..#. | mask --------------------- .....#.. #..#.... | masked = occupancy & mask .....#.. ........ | l = leftmost set bit of masked ......## ######## | l - 1 ######.. ........ | !(l - 1) ..#..#.. #..#..#. | mask --------------------- ..#..#.. ........ | mask & !(l - 1)
ということで、実はこんなコードで簡単に両方向の利きを計算することが出来た。
const BB_1A: Bitboard = Bitboard::single(Square::SQ_1A); const BB_9I: Bitboard = Bitboard::single(Square::SQ_9I); fn sliding_positive(occupancy: Bitboard, mask: Bitboard) -> Bitboard { let tz = (occupancy & mask | BB_9I).to_u128().trailing_zeros(); mask & unsafe { Bitboard::from_u128_unchecked((1 << (tz + 1)) - 1) } } fn sliding_negative(occupancy: Bitboard, mask: Bitboard) -> Bitboard { let lz = (occupancy & mask | BB_1A).to_u128().leading_zeros(); mask & unsafe { Bitboard::from_u128_unchecked(!((1 << (127 - lz)) - 1)) } }
occupancy & mask がemptyになるとleading/trailing zeroの値がはみ出てしまうので便宜上 端っこのbitを立ててしまって、それぞれ正方向なら .trailing_zeros()、負方向なら .leading_zeros() で最初に立っているbit位置を求められる。あとはその位置から両端までのmaskを作って元のmaskと論理積とったものを返すだけ。両端までのmaskは事前に作っておいて表引きするだけでも良いかもしれない。
ソフトウェア的に実装すると .leading_zeros() は .trailing_zeros() と比較してコストがかかる処理になったりもするらしいが、プロセッサよっては lzcnt など専用命令があったりもするのでコンパイルオプションなどを適切に使用すればそれほど気にしなくても良さそう…？
実験と考察
ということで、巨大テーブルも必要なく、PEXTのような特定の命令セットに依存することもなく、それほど負荷がかからない処理で飛び利きを計算することが出来た。
自分のライブラリで実装してみたところ、PEXTでの表引きと比較すると少し遅くなる、程度の差異となった。
やはり4方向それぞれ計算することになるのはPEXTの表引き一発と比較すると遅くはなってしまうと思われる。巨大テーブルが不要になり多少時間かかっていた初期化処理をする必要が無くなったのは恩恵だが…
Qugiyと同様に、同じ方向のものはSIMDで同時に計算する、などの工夫を入れることで多少は改善されるだろうか。
ただこの例ではshogi_coreのインタフェースとして内部の値に触れるのがu128だったからこうしているが、SIMDを使って実装しているとleading/trailing zerosは簡単には求められないかもしれない…。そのへんの相性の悪さもあって今まで採用されてこなかった、とかもあるのだろうか…？
この手法を思いついて、今までこういう手法なかったでしょうか？と開発者Discordで尋ねたところ最初に書いた通りチェスの世界では "Classical Approach" として知られていたものだった。 実装が簡単な反面、速度的には限界があるのかもしれない。
とはいえそこまですごい遅いわけでもなく簡単に実装できる手法ではあるので、知っておいて損は無いと思う。Classicalではあったが自分でこの手法を思いつくことができたのは良かった。
bitboardでの飛び利き計算のことばかり考えていて、子ゃーんとのお風呂で指折り数字をかぞえていてもビット列に見えてしまう
— すぎゃーん💯 (@sugyan) June 14, 2022
