縦型Bitboardの唯一の弱点を克服する

前回の続きです。

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

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

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

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

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

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

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

二つ目は、二歩にならない(歩の打てる場所の)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に死角なし」というのが私の結論です。

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

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

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

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

縦型Bitboardの唯一の弱点を克服する」への7件のフィードバック

  1. 二歩を見逃して続行した場合にpackedの範囲からオーバーフローする可能性がありますが、コンピュータ将棋では審判が絶対的に信頼できるものなのでしょうか?

    • 現局面のすべての合法手を生成して、その指し手のなかに含まれない指し手では局面を進められないようになっているのが普通です。ゆえに、非合法局面(二歩を見逃した局面)には到達しませんし、到達していないと仮定できます。

  2. 細かいところですがPEXT後の&0x1ffは不要では無いでしょうか?

    あとmask27もmask18(=011111111011111111b)で十分では無いでしょうか?

      • 追加でもう一つ気がつきました。

        id.p[0]の各packedの最下位ビットですがid.p[1] << 1との
        orを取る前にandでマスクを取ってクリアする必要があるんでは無いでしょうか?

        • あ、id.p[1] の各packedの最上位ビットもクリアしないといけないですね。
          素直にpextを2回して片方をシフトしてorを取ったほうがいい気もします。

          • おお、そうでした。
            > id = (occupied_bb[PAWN] + ~Mask)&Mask;

            こう修正しました。ここでやればxmmレジスタに割り付けられているならこのandは1命令で出来る気がします。

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です