Bonanzaのbitboardのbit layout - Bonanzaソース完全解析ブログ

■　Bonanzaのbitboardのbit layout

Bonanzaでは局面をbitboardで持っていることは前回触れた。

しかし問題となるのは、このbit layoutである。典型的なbitboardに対するオペレーションとして、次のようなことをしたい。

bitboard bb;
i = 0;
foreach_bit (sq in bb)
  koma[i++] = square[sq];

上の疑似コードは、bitboardから1の立っているビットを1ビットずつ取り出して、そのビット位置をsqに代入し、ループを回るという意味である。

指し手生成などでこの手のループを書きたいのは自然なことである。

MSB(最上位ビット)/LSB(最下位ビット)から順に1である最初のbitを見つけるのは、x86/x64系ではbsr/bsf(bit scan reverse/bit scan forward)という命令がある。当然、これを使わなければならない。さもなくばお話にならない。

MSCなら、_BitScanReverse(MSBから)、_BitScanForward(LSBから)というマクロ(?)を用いれば、bsr/bsfに展開されることが保証されているので、これを用いる。

ただし、bsr/bsfは、最初に1になっているbitを見つけ出すだけであり、そのあとそのビットをクリアしてくれるわけではない。よって、次のように書く必要がある。

  bb = BB_BPAWN;
  while ( BBToU(bb) ) {
    sq = FirstOne( bb );
    Xor( sq, bb );

    list0[nlist] = f_pawn + sq;
    list2[n2]    = e_pawn + Inv(sq);
    score += kkp[sq_bk0][sq_wk0][ kkp_pawn + sq ];
    nlist += 1;
    n2    += 1;
  }

上のソースは、Bonanzaのevaluate.cの一部である。BBToUはbitboard全体が0かどうかを判定している。これはマクロで、単に内部で保持している3つのdwordのbitwise ORをとっているだけである。

FirstOneもマクロであり、実際はfirst_one012が呼び出される。FirstOneは、MSBからscanして最初に1であるbitを見つける。

その直後にXorしているが、これもマクロで、一見するとbitboard型同士のXorに見えるが、よく見るとsqはbitboard型ではなく整数型であり、指定した位置のbitをXorするものである。しかし、そのbitはすでに1なのでそれとXorすれば、そのビットのみがクリアされる。

要するに、BBToU〜FirstOne〜Xorというコンボによって、先ほどの疑似コードとして示した foreach_bit (sq in bb) が達成できているということである。

FirstOneで検索したときについでにそのビットを0にしてしまえば、わざわざbitboard(12バイトもある)とxor用のテーブル(12バイト)をlookupしてxorをする手間が省ける。

これにより、数命令ほどはしょれて思考ルーチンを0.5%ほど高速化できる。まあ、細かいチューニングの話はいったん置いておこう。

bitboardは3つのdwordから成る合計12バイトの構造体である。8×12 = 96bitある。将棋盤は81枡だから、15bit余る。ではどこを余らせるのかという問題がある。

常識的には、上位15bitを余らせて、下位81bitだけ使ったほうがいいように思う。64bit OSで動かしたときに、64bit型に対するbsr + 32bit型に対するbsrというように2回のbsrで動作を完了させることが出来て少しお得だからである。

Bonanzaではどうなっているだろうか。ソースを読んでいこう。

int
first_one012( unsigned int u0, unsigned int u1, unsigned int u2 )
{
  unsigned long index;

  if ( _BitScanReverse( &index, u0 ) ) { return 26 - index; }
  if ( _BitScanReverse( &index, u1 ) ) { return 53 - index; }
  _BitScanReverse( &index, u2 );
  return 80 - index;
}

このfirst_one012は、bitop.cで書かれている。(何故、inline化されるようにbitop.hに書かないのかは知らないが。ちなみにbitop.hにbitop.cで書かれている関数を移動させると思考ルーチンが0.5%ほど高速化できる。)

見ての通り、offsetとして、26引いてあることからもわかるように、盤面の3段ごとにdwordひとつである。(3×9 - 1 = 26)

つまり、それぞれのdword変数の上位32-27 = 5bitずつは余らせてある。

また、first_one123の返す値は、
・ひとつ目のdword変数の26bit目が1のときに0
・ひとつ目のdword変数の0bit目が1のときは26
・ふたつ目のdword変数の26bit目が1のときは27
・ふたつ目のdword変数の0bit目が1のときは53
・みっつ目のdword変数の26bit目が1のときは54
・みっつ目のdword変数の0bit目が1のときは80
となっている。

上のfirst_one123の実行フローを見れば、first_one123は、二つ以上のbitが立っている場合は、小さなほうの値を返すことがわかる。

では、ここで返された値が盤上でどの位置を意味するのだろうか。

それは、shogi.hにある次のenumのA9〜I1がそれである。コメントは私が付与した。

// 各マスに対する文字列
// 上が後手側(A9 = 9一 , I1 = 1九)
enum { A9 = 0, B9, C9, D9, E9, F9, G9, H9, I9,
           A8, B8, C8, D8, E8, F8, G8, H8, I8,
           A7, B7, C7, D7, E7, F7, G7, H7, I7,
        // x < A6の範囲が後手陣。先手にとって駒が成れるのはこの範囲。
           A6, B6, C6, D6, E6, F6, G6, H6, I6,
           A5, B5, C5, D5, E5, F5, G5, H5, I5,
           A4, B4, C4, D4, E4, F4, G4, H4, I4,
        // x > I4の範囲が先手陣。後手にとって駒が成れるのはこの範囲。
           A3, B3, C3, D3, E3, F3, G3, H3, I3,
           A2, B2, C2, D2, E2, F2, G2, H2, I2,
           A1, B1, C1, D1, E1, F1, G1, H1, I1 };
        // FirstOneは小さな値から探すので、この盤面で言えば左上からのスキャンになる。
        // LastOneは大きな値から探すので、この盤面で言えば右上からのスキャンになる。

I1が(将棋盤の)1九の位置。

よって、bitboardの3つのdword変数のうち、
・1つ目のdword変数の26bit目が1なら、FirstOneは0を返し、これはA9を意味して、A9は将棋盤上の9一の地点である。
・1つ目のdword変数の0bit目が1なら、FirstOneは26を返し、これはI7を意味して、I7は将棋盤上の1三の地点である。
・2つ目のdword変数の26bit目が1なら、FirstOneは27を返し、これはA6を意味して、A6は将棋盤上の9四の地点である。
…
・3つ目のdword変数の26bit目が1なら、FirstOneは80を返し、これはI1を意味して、I1は将棋盤上の1九の地点である。

■　まとめ

Bonanzaのbitboardのbit layoutがどうなっているのかは意外と知られていない。今回は、bit layoutについて詳しく調べた。

3段ごとにdwordをひとつ割り当てるのは、コーディングは容易になるかも知れないが、64bit OSで動かすなら、変にpaddingがされているのは速度的に損だと思う。(Bonanzaのbitboardまわりは、64bit環境で動作させることを前提にして、かつソースを何ヶ所か変形するだけで、思考ルーチンを10%程度高速化できることが私にはわかっている。)

Bonanzaのソース上には、64bit用に特化したようなコードが存在しないが(例えばbitop.hは64bit変数で書き換えれば64bit環境で高速化が期待できる)、それは64bit環境が普及する前に書かれたコードなのである意味仕方がないのかも知れない。

新規にbitboardを使ってコンピュータ将棋プログラムを書こうという人は、Bonanzaのbitboardの処理は大いに参考になると思うが、Bonanzaのbitboardのbit layoutまでは真似しないほうがいいと思う。