続) Haswell以降専用だと何が嬉しいのですか？

前回の続きです。

「Haswell以降専用命令を使っても速くならない！」とお嘆きの将棋ソフト開発者救済のために記事を書いたのだけど、この記事の続きに興味のある人がどれくらいいるか知りたいので続きが読みたい人はこのツイートをRTしてくれませぬか。 http://t.co/cJpUm5okdj

— やねうら王 (@yaneuraou) October 9, 2015

意外と反響があったので、今日もだらだらと書いていきます。

確かに、面倒なことをせずにまずシフト演算を入れるべきだったか。 https://t.co/H9xUiB6TR4

— 久保亮介 (@RyosukeKubo) October 10, 2015

今回は話を整理するために、Bitboardとは何なのかというところから進めていきます。

Bitboardというのは、将棋の盤面において、駒のある場所に対応するbitが1になっているビット列のことです。
将棋の盤面は81升あるので81bit必要になります。通例、64bit変数2つか、128bit変数一つ(SSE2以降)として扱います。

駒がある場所のBitboardのことをoccupied bitboardと呼びます。Bitboardを用いる将棋ソフトでは複数のoccupied bitboardを使います。

例)
・先手の駒のある場所を示すBitboard
・後手の駒のある場所を示すBitboard
・先手の歩のある場所を示すBitboard
・後手の歩のある場所を示すBitboard
…

このようにいろんなBitboardを状況に応じて使い分けます。
ちなみにoccupyは、「オキュパイ」と読みます。

( ﾟ∀ﾟ)o彡゜オキュパイオキュパイ

とテンションが上がってきたところで、それでは例題として、先手の銀で後手の駒を捕獲できる指し手を生成してみましょう。

1) 先手の銀のある場所を示すBitboard(b_silver_occupied)
2) 盤上のsqの地点にある銀の利きを示すBitboard(b_silver_effect[sq])
3) 後手の駒のある場所を示すBitboard(w_occupied)

があるものとします。

まず、1)を持ってきて、ここから1bitずつ取り出します。1bit取り出したものを盤上の位置を示す変数(Square型)に変換して、この銀による利きを2)のテーブルを用いて調べます。この利きの先に敵の駒があれば捕獲できるわけですから、この利きと3)とをandを取ります。そうすると、捕獲になる移動先の升目を示すBitboardが得られます。

Bitboardを直列化する、すなわち、1bitずつ取り出してそれをSquare型に変換するのですが、まず1bit取り出すのは次のようにbsf(bit scan forward)かbsr(bit scan reverse)を用います。

腹立たしいことに、128bit変数に対してbsf/bsrをする命令はHaswellにも存在しません。仕方がないので64bitごとにわけて行ないます。さらに腹立たしいことに、x86だと64bit単位ですらなく、32bit単位でしかbsf/bsr出来ません。まあ、x86のことはいまは考えずにx64のことのみ考えます。

FORCE_INLINE int32_t lsb(uint64_t b) {
unsigned long index;
_BitScanForward64(&index, b);
return index;
}

この取り出したbitを0にしないといけないのですが、これは元の数から1引いたものとandを取ると最下位bitがクリアされるというビット演算のテクニックを用いてクリアします。(このテクニック自体は、ハッカーのたのしみ―本物のプログラマはいかにして問題を解くかにも載ってます。興味がある人はそちらを是非。)

FORCE_INLINE Square pop_lsb(uint64_t* b) {
assert(*b != 0); // ゼロなら呼び出し条件を満たしていない。

const Square s = (Square)lsb(*b);
*b &= *b – 1;
return s;
}

これを128bit(64bit 2つ)に対して行えばSquare型になるということですね。

inline Square pop_lsb(Bitboard* b)
{
if (b->p[0] != 0)
{
return pop_lsb(&b->p[0]);
}
// if (b->p[1] != 0)
assert(b->p[1] != 0);
{
return Square(pop_lsb(&b->p[1]) + 64);
}
// return SQUARE_ERROR; // もう知らん
}

上の実装はp[0]を64bitフルに使い(7段×9升 + 1升 = 64)、p[1]の下位17bitを使う場合のものです。

道具は揃ったので、先手の銀で後手の駒を捕獲する指し手だけ生成してみましょう。

occ = b_silver_occupied; // 先手の銀の場所
while (from = pop_lsb(occ))
{
// fromの位置にある銀を移動させて、後手の駒が取れる場所
effect = b_silver_effect[from] & w_occupied;
while (to = pop_lsb(effect))
// fromからtoへ銀を移動させる指し手を生成する。
*moves++ = make_move(from,to);
}

簡単ですね。Bitboardを用いると極めてシンプルに記述することが出来ます。

将棋ソフトにはGPS将棋のように非Bitboard型のものとBonanzaのようにBitboard型のものとがあり、「Bitboardを用いる場合、シンプルに記述できるのが利点で、Bitboardを使わない場合と比べてそんなに速くなるわけではない(ほとんど変わらない)」と長らく言われてきましたが、SSEやAVXの登場によって、Bitboardのほうが確実に速いという状況になっていると私は思います。

さて、ここで問題です。

Bitboardからpop_lsb()してSquare型の値を得るわけですがSquare型において0の値は盤面のどこの升を指すのでしょうか？

何と上のソースコードではその部分が隠蔽されていてここだけ見てもわからないのですね。
つまり、Bitboardの0bit目を盤面のどの升に対応させるかは恣意性があるわけです。

では、どのように対応させると良いのでしょうか？

各将棋ソフトがどのようなBitboardのレイアウトにしているかこれから見ていきましょう。ちなみに将棋ソフトでBitboardを最初に採用したのはBonanzaだと思いますが、そのBonanzaのソースコードの礎となっているのはCraftyというチェスのソフトです。チェスでは盤面は64升であるためちょうど64bit変数に収まります。将棋では81升であるため、いろいろソフトごとに工夫が見られるわけですね。

Bonanza = 盤面の1～3段目、4～6段目、7～9段目をそれぞれ32bit変数に。

Bonanzaはx86用に開発されていたため(?)、盤上の81升(81bit)を収めるために32bit変数を3つ使ってあります。そのため、1つの変数に盤面の3段ずつを担う形になっています。

やねうら王(2014) = 盤面の上64升(1～7段目と8段目の1升)が64bit変数ひとつ。盤面の下17升が64bit変数ひとつ。

いまどきの将棋ソフトはx64をターゲットにしているので、Bonanzaのように割り当てるとpop_lsb()のときにちょっと手間がかかるのでこう割り当てるのがストレートな実装だということですね。

旧やねうら王 = RBB

旧やねうら王は、RBBという盤面上から64升をp[0]、盤面の下から64升をp[1]に持つ(一部領域が被覆する)という面白い構造でした。

64bit環境向けBitboard、RBBの提案
http://d.hatena.ne.jp/LS3600/20091225

こう持つメリットは、先手の非敵陣への移動を生成するときにp[1]に盤面の下から64升(2段目の1升と、3段目～9段目)が格納されているのでp[1]だけを調べれば良いということです。これはこれで面白いのですが、指し手生成のコードが複雑化するので普通のC++ templateで乗り切るのはちょっとしんどく、当時はYaneLispという特殊なプリプロセッサを自作して私はコードを書いていたのですが、なかなか保守が大変なのでやねうら王(2014)では採用しませんでした。

Sunfish = 盤面1～5段(64bit変数)と6～9段(64bit変数)に分けて。

このように実装しても速度的にはやねうら王とほぼ同じです。

Sunfish(新) = 盤面1～7段(64bit変数)と8～9段(64bit変数)に分けて。

新しいSunfishが上のように持ち方を変更したという話が前回ありました。この意図は、pext()を用いてbitをかき集めるときに有利になるからだということは前回説明しました。

Apery = 盤面の90度回転。盤面1～7筋(64bit変数)と8～9筋(64bit変数)に分けて。

Aperyは盤面の90度回転させて、縦方向にレイアウトされています。しかも盤面の右上(将棋の符合で言う１一)がSquare 0、12が1、13が2、…、左下(将棋の符合で言う９九)がSquare 80。
つまり盤面の1～7筋(64bit変数。63bit使用)と8～9筋(64bit変数)という持ち方をしてあります。

また、私の推測ですがPonanzaもAperyと同じではないかと思います。

このメリットは複数あります。これについて、ざっと解説します。

まず、p[0]の63bitだけを使う。つまり、p[0]を1bit余らせる。このメリットについては、前回説明しました。pext()で遠方駒の利き求めるときに違ってくるからです。

次に、Bitboardのレイアウトを縦型にしているメリットですが、歩の利きを求めるときのシフトにSSEの命令が使えるのです。

ここでまた少し脇道にそれるのですがSSEのシフト命令について解説せねばなりません。

太古のCPU(Z80とか)には、複数回シフトの命令は存在しませんでした。シフトと言えば1回と決まっていました。FPGAなどでCPUを設計したことのある人ならわかると思いますが、複数回シフトする命令を実装するのはCPUの回路がとても複雑になるのです。そのあとに出てきた複数回シフトをサポートしているCPU(例えば8086)でも複数回シフトの場合、シフト回数に比例したCPU時間が必要でした。

このように複数回シフトが一発(≒定数オーダーのCPUサイクル)で実行できるようになるにはずいぶんCPUの進化を待たねばならなかったわけです。それは現代でも同じで、AVX256で256bitが1命令で扱える時代になったというのに、いまだに128bitのシフト命令は搭載されていません。

では、SSEで搭載されているシフト命令は一体何なのか。これは、128bitを64bitレジスタ2つとみなしてシフトする命令にすぎません。_mm_slli_epi64/_mm_srli_epi64ですね。

このような64bit parallel shiftで歩の利きを求めようとしたときちょっと困ったことが起きるのです。

歩は次の段に移動できますから、7段目の後手の歩は8段目に移動します。7段目はp[0]、8段目はp[1]に格納されている場合、上記のような仕様のシフト命令だと歩の移動できる先を求めることが出来ないのです。

そこで盤面のBitboardを縦型に持つという発想に至ります。将棋のルール上、先手の歩は1段目に存在できませんし(行き場のない駒)、後手の歩も9段目には存在できません。つまり、AperyのようにSquare型を設計した場合、p[0]とp[1]をまたがるような歩の移動は存在しなくなるため、このSSEのシフト命令で歩の移動先が正しく求められるということです。

他にも縦型にするメリットはあります。例えば香の利きです。香の利きを確定するためにApery型Bitboardであれば、occupied bitboardの連続するbitを持ってきて調べるだけで済むのです。まあ、Haswellであればpextが使えるのですが、pextを使わなくとも済むという意味があります。また、香の利きを求めるのに必要なのは必ずp[0]かp[1]のどちらか片側だけですから、片側の変数からだけbitを集めてくればいいという点もメリットでしょう。

Bitboardを縦型にするメリットは概ね伝わったかと思います。

では、盤面の右上の升をSquare 0にするメリットとは何でしょうか？左上の升(将棋の符合でいう９一)が0では駄目なのでしょうか？

これはプログラム上、大したメリットはなくて、単に1筋が9筋より先にあるべき(square = file*9 + rankのように計算できるべき)という程度だと思います。

以上でBitboardのレイアウトの違いによる実装への影響をざっと説明できました。

こうして見るといいこと尽くめに見えるAperyのBitboardレイアウトですが、それなら何故Sunfishのようにpextを使っても速くならない(?)という声が聞こえてくるのでしょうか？

次回はこのことについて考えていきます。