将棋の局面(手番+盤面+手駒)をハッシュ化する方法はいくつかあり、Zobrist Hashやハフマン符号を用いた完全ハッシュが知られています。
ハフマン符号を用いると256bitの完全ハッシュを作ることができます。やねうら王ではPackedSfenという名前で実装されているので、以後PackedSfenと呼びます*1。
PackedSfenでは、玉以外の7種の駒を次のように符号化することで256bitに収めることに成功してます。
| Piece Type | bit1 | bit2 | bit3 | bit4 | bit5 |
|---|---|---|---|---|---|
| Pawn | 0 | - | - | - | - |
| Lance | 1 | 0 | 0 | - | - |
| Knight | 1 | 0 | 1 | - | - |
| Silver | 1 | 1 | 0 | - | - |
| Gold | 1 | 1 | 1 | 0 | - |
| Bishop | 1 | 1 | 1 | 1 | 0 |
| Rook | 1 | 1 | 1 | 1 | 1 |
この方法は、盤面を空き升を含めて順に符号化するためかなり遅く、ハッシュテーブル用のハッシュ関数には、差分更新の軽いZobrist Hashを用いることがほとんどです。
今回、256bitに収まる完全ハッシュを比較的高速に求める方法(SSPFv1*2と呼ぶことにしました)を実装したので紹介します。
SSPFv1の仕組み
実は、今回の手法もハフマン符号を用いています。そればかりか、駒種を符号化する規則もPackedSfenと同一です。異なるのは、それを計算してビット列として詰める方法です。
PackedSfenでは盤面を1升目の1ビット目、1升目の2ビット目、…、2升目の1ビット目、…、81升目の最後のビット、の順で格納します。
これをSSPFv1では1升目の1ビット目、2升目の1ビット目、…、81升目の1ビット目、1升目の2ビット目、…、81升目の2ビット目、1升目の3ビット目、…の順で格納します。
ハフマン符号では駒ごとに必要となるビット数が異なりますが、必要ないビットは格納せずに飛ばします。 1ビットごとに飛ばす・飛ばさないを見て格納すると余計に遅くなりそうですが、ここで近年のx86_64CPUに実装されているPEXT(Parallel Bit EXTract)という命令を使うことができます。
PEXT命令はdata, maskの2オペランドを取り、dataのうちmaskで1が立っている桁のビットを下位に詰めたビット列を得ることができます。
ハフマン符号の2ビット目を得たい場合、2ビット目が必要な香桂銀金角飛のorをとったビットボードをmaskとし、銀金角飛のorを取ったビットボードをdataとして、81bitのpextを行うことができればよいです。
PEXT命令は32bit, 64bitの入力にのみ対応していますが、64bit*2のビットボードに対するpext操作もpopcount命令を併用すれば数命令で求まります*3。
同様にして、ビットボードの操作とpextですべての駒に対応するビット列を順次求めることができるため、非常に高速に完全ハッシュを求められるという仕組みです。
実装はリポジトリのsrc/sspfv1.rsにあります。
ベンチマーク
速いというからにはベンチマークを取らねばなりません。必ず。 今回PackedSfenとSSPFv1をそれぞれ実装し、速度を比較しました。チューニングの結果、PackedSfenの実装もやねうら王のものより高速になっています。
- CPU: Ryzen 9 7950X3D
- OS: WSL2 on Windows11
- Compiler: rustc 1.94.0-nightly (fe98ddcfc 2026-01-17)
| flags | PackedSfen (ns/iter) | SSPFv1 (ns/iter) | Speedup |
|---|---|---|---|
| target-cpu=native | 106.36 | 10.23 | 10.3x |
10倍以上速く、指し手生成等と比べても十分高速です。
