Bonanzaでは局面をどういうデータ構造で保持しているのか

■　posi_t構造体

Bonanzaでは局面を表現する構造体posi_tはshogi.hで定義されている。

構造体のそれぞれのメンバ変数がどういう意味を持つかについては、それが使われているところを見るのが一番手っ取り早く、具体的には、指し手生成(makemove.c)のソースを見るのが一番早い。

それぞれの変数が何を意味するか、補足用のコメントを追加しつつ引用すると次のようになっている。

// 局面
typedef struct {
  // 局面のhash値
  uint64_t hash_key;

  // --- 各駒のbitboard
  // b_ はblack(先手) , w_ はwhile(後手)

  // 先手/後手の駒の有無(駒があれば1)
  // このmaskには王も含まれる。
  bitboard_t b_occupied,     w_occupied;

  // ↑の駒の存在する位置を示すビットマップを90度、45度回転させたもの。
  // 飛車角香による利きを計算するときに用いる
  bitboard_t occupied_rl90,  occupied_rl45, occupied_rr45;

  //  馬龍王のビットマップの論理和(horse,dragon,king)
  bitboard_t b_hdk,          w_hdk;

  //  金および金と同様の利きをもつ成駒の位置を示すビットマップ(tgold = と金)
  //  tgoldのtはtotalのtか？equivalentのtか？
  bitboard_t b_tgold,        w_tgold;

  //  角馬の存在するビットマップの論理和(bishop,horse)
  bitboard_t b_bh,           w_bh;

  //  飛龍の利きビットマップの論理和(rook,dragon)
  bitboard_t b_rd,           w_rd;

  //  歩の利き
  bitboard_t b_pawn_attacks, w_pawn_attacks;

  // 各駒の存在するところが1であるビットマップ
  bitboard_t b_lance,        w_lance;  // 香
  bitboard_t b_knight,       w_knight; // 桂
  bitboard_t b_silver,       w_silver; // 銀
  bitboard_t b_bishop,       w_bishop; // 角
  bitboard_t b_rook,         w_rook;   // 飛 
  bitboard_t b_horse,        w_horse;  // 馬
  bitboard_t b_dragon,       w_dragon; // 龍

  bitboard_t b_pawn,         w_pawn;       // 歩
  bitboard_t b_gold,         w_gold;       // 金
  bitboard_t b_pro_pawn,     w_pro_pawn;   // と
  bitboard_t b_pro_lance,    w_pro_lance;  // 成香
  bitboard_t b_pro_knight,   w_pro_knight; // 成桂
  bitboard_t b_pro_silver,   w_pro_silver; // 成銀

  // 手駒
  unsigned int hand_black, hand_white;

  // 駒の損得(eval_materialでその計算がなされる)
  // 駒割り
  int material;

  // 盤81マス。そこに存在する駒の値が入っている。
  // 駒の移動に際しては、bitboardの他にこの配列の値も更新される。
  // nsquare = 9*9
  signed char asquare[nsquare];

  // 玉の位置、先手・後手
  // この数値が盤上のどこの位置を意味するかは、bitboardのFirstOneを参考にすること。
  unsigned char isquare_b_king, isquare_w_king;
} posi_t;

このposi_tは、shogi.hのtree構造体(探索木)がメンバとして持っている。

// 探索木
typedef struct tree tree_t;
struct tree {

  // 局面
  posi_t posi;

実際に局面のデータにアクセスするには、shogi.hで定義されている以下のマクロで行なう。
ptreeは、tree_t型(探索木)の変数で、これは関数の引数として渡されている。

 // 駒割り
#define MATERIAL            (ptree->posi.material)

 // 手駒
#define HAND_B              (ptree->posi.hand_black)
#define HAND_W              (ptree->posi.hand_white)

#define BB_BOCCUPY          (ptree->posi.b_occupied)
#define BB_BTGOLD           (ptree->posi.b_tgold)
#define BB_B_HDK            (ptree->posi.b_hdk)
#define BB_B_BH             (ptree->posi.b_bh)
#define BB_B_RD             (ptree->posi.b_rd)
#define BB_BPAWN_ATK        (ptree->posi.b_pawn_attacks)
#define BB_BPAWN            (ptree->posi.b_pawn)

(以下略)

指し手生成など、このマクロが多用してある。

一見すると最適化が阻害されるように思える。ptree->posiを辿るのは、アクセス時間的に無駄で

const posi_t& posi = ptree->posi;

のようにいったん参照をして、この変数経由でアクセスしたほうが早いように思う。

しかし、ptreeは、次のようにrestrictキーワードがついており、ptreeのポイント先のエイリアスが存在しないことを宣言している。

void
make_move_b( tree_t * restrict ptree, unsigned int move, int ply )

よって、上のようなマクロを使ってアクセスしてもこの部分は最適化されることを期待できる。

■　まとめ

Bonanzaではbitboardで局面を保持しているというのは広く知られているところだが、その正確なところはあまり知られていなかった。

上で見たように、先手、後手の各駒ごとのbitboardだけではなく、駒がそこに存在するのかというbitboard(occupied)や、それを90度、45度回転させたbitboard、そして「角馬」「飛龍」「馬龍王」「金に準ずる駒」のbitboardを持っている。

また、bitboardを持っているのに、盤上にどの駒があるかを保持するために別途asquare[nsquare]というメンバを持っている。これは指し手生成で駒を移動させて相手の駒をとったときにその捕獲した駒の種類を調べるときに便利だからである。