前回の続きです。

今回は、いいこと尽くめに思えるAperyのような縦型Bitboardの弱点について考えていきましょう。

そうそう。Sunfishも縦型Bitboardを採用しているそうです。てっきり横型かと思っていました。お詫びして訂正しておきます。

今回は縦型Bitboardの唯一の弱点である、歩の打てる場所を探す処理について考えていきましょう。

将棋では二歩は禁則なので自分の歩のある筋に歩を打つことは出来ません。Bonanzaの指し手生成部では、この処理は次のようになっています。

上記のコードは２つの意味で良くないです。

一つ目は、指し手生成時に打ち歩詰め判定をしていることです。指し手を生成してもそのあと、オーダリングを行ないます。オーダリングというのは、よさ気な指し手から順番に調べていくことで、枝刈りなどにより、生成した指し手で局面を進めないままその局面の処理が終わってしまうことも多々あります。

そこで、打ち歩詰めであるかどうかは、その指し手で局面を進めるときまで遅延させるべきで、指し手生成において打ち歩詰めを判定するのは無駄になる可能性が高いのです。ゆえに、ここでやるべきではありません。

二つ目は、二歩にならない(歩の打てる場所の)Bitboardを結局得られていないことです。空いている升をひとつずつ調べて、aifile[](Square型に対してそれが何筋であるかを返すテーブル)から筋に変換して、その筋に歩があるのかを表す配列(ais_pawn[])をチェックしています。

幸い、Bonanzaでは盤面を3段ごとに32bit変数に格納してあるため、BBToU()でこのそれぞれの32bit変数のorを取れば1～3段目、4～6段目、7～9段目が合成されたBitboardのようなものが得られます。

であれば、このあとこの3段に重ね合わされたBitboardをさらに1段になるまで重ねあわせて、それで表引きするのが現代風でしょう。

ibb_pawn_cmp = ibb_pawn_cmp | (ibb_pawn_cmp >> 9) | (ibb_pawn_cmp >> 18);
pawn_dropable = pawn_drop_table[ibb_pawn_cmp & 0x1ff];

横型Bitboardの場合、このように段を重ねあわせるのは、shiftとorで出来ます。横型Bitboardに利点があるとすればここですね。

では、縦型Bitboardでは、この部分の処理はどうなるのでしょうか？
Aperyのソースコードを見てみましょう。

盤上の自分の歩はたかだか9枚しかありませんから、1枚ずつどの筋にあるかを調べています。歩が打てる升を表すBitboard(toBB)を得るためにforeachBBで回しています。

toBB.set(…)の部分はわかりにくいですが、partというのは歩がp[0]かp[1]かのどちらに属するかが格納されているとして、toBBには最初、空いている升が格納されているので、

toBB.p[part] &= ~FILE_BB[pawnsSquare].p[part];

の意味です。つまり、pawnsSquareの筋に駒が打てないのでtoBBから除外しています。縦型Bitboardなので、一つの筋(9升)は、occupied bitboardのp[0]かp[1]かどちらかのみに存在するので、片側のみの操作で済むということです。

このコード、なかなか考え尽くされていて、平岡さんのセコさ(褒め言葉)が滲み出ているように思います。もっとも、p[1]の対してアクセスするためには、toBBのxmmレジスタへの割当てが阻害されてしまうので本当に速くなるのかは微妙です。

やはり、ここは表引きで済むなら表引きで済ませたいところです。縦型Bitboardで唯一、横型Bitboardに負けるとしたらこの部分なので。

ところが、表引きしようにも縦型Bitboardですと横型Bitboardのときのようにshiftとorでなんとかすることは出来ません。

ここで、いま仮に、次のような操作が存在するとしましょう。

操作A) 0bit目から8bit目まで(1筋)のいずれかのbitが1であれば(歩があれば)、8bit目を1にするような操作。同様に9bit目から17bit目まで(2筋)のいずれかのbitが1であれば17bit目を1にします。以下同様。

そういうオペレーションが存在すると仮定したとき、あとは、Haswellのpext命令を用いれば、これらのbitを集めてくることが出来ます。

例えば、Aperyのようにp[0]に63升格納している場合は、以下のようになります。
pawn_dropable = pawn_drop_table[pext( p[0] | (p[1] << 1) , … ) & 0x1ff];

結局、操作Aを簡単に行えれることが示せれば、pext()が使えるということですね。

実はこれを一発で行う命令があります。それはadd(足し算)です。

いま9桁(9升)あると話がややこしいので単純化して3桁で考えます。3桁の2進数で000b(歩なし),001b(1段目の歩),010b(2段目の歩),100b(3段目の歩)の4通りの状態があります。歩なしか、それ以外かを判別できればいいので、ここに011b(10進数で言う3)を足します。

そうすると000bのときは011bになり、それ以外のときは、1XXb(Xはdon’t care)となります。つまり、歩の有無がMSB(最上位bit)に反映されるということですね。

このように連続するbitに対して、たかだか、どこか1つのbitしか1でないことがわかっている場合にそれを検知するには、addが使えます。addによってこの情報をMSBに移動させることが出来るのです。

いまの例で言うと、packed 9bitとみなしてparallel addが行えます。

つまり、次のような定数があったとして、

p[0] += mask63;
p[1] += mask18;

とするだけでそれぞれのpacked bitのMSB(8bit目、17bit目、26bit目、…)にその筋に歩があるかどうかの情報がやってきます。これをpext()で回収するというわけですね。

この下位bitの情報をsoftware packed addでMSBに持ってくる話、何かデジャヴだなーと思っていたら、これはソフトウェアによる飽和加算(http://bm98.yaneu.com/rsp/rspB9toC0.html)で使うテクニックでした。

15年前の記事ですが、当時、MMX対応CPUがまだ十分普及していなくて、ソフトウェアで加色合成をする必要があったために一部のプログラマーの間でさかんに研究されていました。

当時、私は自分の本にも詳しく書いた覚えが…。
[amazonjs asin=”4798006033″ locale=”JP” tmpl=”Small” title=”Windowsプロフェッショナルゲームプログラミング2【CD-ROM付】 (Game developer books)”]

話が少し逸れました。

結局、縦型Bitboardでもpext()を用いれば、以下のようにして表引きできるということです。

※ (Mask.p[0] | Mask.p[1] << 1)の部分は、コンパイル時に定数になるものとします。また、Bitboardに対するaddとandはSSEの命令を用いて実装してあるものとします。

そんなわけで、縦型Bitboardの唯一の弱点である歩の打てる升のbitboardを得る部分もpext()を使えば、このように高速化できてしまうので(全体の速度に与える影響は0.1%すらないでしょうけど..)、「(Haswell以降にとって)縦型Bitboardに死角なし」というのが私の結論です。

まさか、二歩にならない升を計算するのにsoftware packed addが使えるとは誰も思うまいて…。15年前のテクノロジーが現代に復活した瞬間である。

縦型Bitboardの唯一の弱点を克服するhttp://t.co/P61vK4cZ2m

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

次回は今回のフォロー記事です。

[2021/05/05 13:30 追記]

Qugiyのコード、テーブルを用いずにbit演算のみで処理しているので、そちらのほうが優れていますね。

WCSC31 Qugiy PR文書 : https://www.apply.computer-shogi.org/wcsc31/appeal/Qugiy/appeal.pdf