daruma3940の日記

理解や文章に間違い等あればどんなことでもご指摘お願いします

ビットボードさんなのじぇ

f:id:daruma3940:20160520223745p:plain
まいちゃ「ゆっくりしていくのじぇ
今日はコンピューター将棋で使われるビットボードさんについてなのじぇ
やねうら王のソースコードさんを見ながらべんきょうしていくのじぇ」

f:id:daruma3940:20160520223530p:plain
れいみゅ「ゆゆっ!?すごくむずかしそうだよ!」

f:id:daruma3940:20160520223745p:plain
まいちゃ「まいちゃじしんもそんなにビットボードさんを理解しているわけじゃないのじぇ
今リアルタイムで理解しながら記事を書いているのじぇ」

f:id:daruma3940:20160520223745p:plain
まいちゃ「今回は難しいことは考えずbitboardにはどんな種類があるのかを見ていくのじぇ
初期化や更新詳しい利用法はまたこんどなのじぇ」

f:id:daruma3940:20160520223745p:plain
まいちゃ「ビットボードさんはコンピューター将棋やコンピューターチェスで用いられる盤面を表すデータ構造なのじぇ
普通はban[9][9]やban[9*9]といった配列さんを使いたくなるところを64bit整数を二つまたは128bit整数を用意して0と1の組み合わせでそのマスに駒があるのかないのかを表現していくのじぇ」

f:id:daruma3940:20160521003616p:plain
ありす「でもすべてのデータを0か1で表現するのはすごくたいへんそうね。。。」

f:id:daruma3940:20160520223745p:plain
まいちゃ「ゆゆっ!まいちゃも昔は盤面のすべてのデータさんをbitboardであらわすのだろうと勘違いしてたのじぇ
でもすべてのデータをbitboardで持つわけではないのじぇ!」
f:id:daruma3940:20160520223530p:plain
「どういうこと?」
f:id:daruma3940:20160520223745p:plain  
「positionクラスの Piece board[SQ_NB]をみるのじぇ
これは16bit整数型の配列なのじぇ!ここに「このマスにはどの種類の駒があるか」が格納されているのじぇ!
ここは配列型と変わらないのじぇ!

ちなみにAperyにもPosition構造体に
Piece piece_[SquareNum]というのがちゃんと用意されているのでやねうら王だけの仕様というわけではないと思うのじぇ! 」

f:id:daruma3940:20160521003616p:plain
「ちゃんと配列型のデータ構造も持っていたのね
なんだか恐怖心がうすらいだわ♪」
f:id:daruma3940:20160520223745p:plain
「難しく考えすぎず
利きを高速に作ったり、駒を移動させる場所移動させる前の場所を決めたり、王手の高速な判断のためのテーブルを用意しておくために
128bitという超ミニマムサイズでテーブルを作ることができるbitboardが使われると思っておけばOKだとと考えられるのじぇ!

f:id:daruma3940:20160520223745p:plain
「ちなみにboard[SQ_NB]は盤面の出力や、
Piece piece_on(Square sq) const { return board[sq]; }と関数で包まれて、
駒を置いた時の利きの計算のための駒の種類の取得や王手をかけた駒の種類の取得、hashの計算
指し手の合法性チェックやSEE(static exchange evaluation)等といった
sqにある駒の種類を取り出したいときにつかわれているのじぇ!

f:id:daruma3940:20160520223745p:plain
「簡単なbitboardのおさらいをしておくのじぇ

bitboard自体は

 union
  {
    uint64_t p[2];//64bit型2つ             
    __m128i m;  //128bit型                    
  };

で構成されているのじぇ

チェスだと盤面が88なので64bitで収まるけれど
将棋は9
9なので81bit整数なんてないので(2進数の関係)128bit整数を使うのじぇ

f:id:daruma3940:20160520223745p:plain
じゃあここからは今日の本題bitboardテーブルの種類について説明していくのじぇ

Position::occupied[COLOR] 
先手か後手か、いずれかの駒がある場所が1であるBitboard(駒の種類は考えない)
駒をとらない移動を生成するときに移動先(target)の候補としてこれを反転させてもちいる
駒をとる手を生成するときに相手の駒がどこにいるのかの情報を与える
飛び利きの範囲を計算するときに障害物の位置として用いる


  
Position::piece_bb[PIECE_TYPE_BITBOARD_NB][COLOR_NB];
駒種別のその種類の駒が存在する升を表すBitboard
これを用いて指し手のfromを生成する
 pos.pieces(Us, Pt)
として使われる



Bitboard FILE1_BB = Bitboard(UINT64_C(0x1ff) << (9 * 0), 0);//p[0]について
Bitboard FILE2_BB = Bitboard(UINT64_C(0x1ff) << (9 * 1), 0);
Bitboard FILE3_BB = Bitboard(UINT64_C(0x1ff) << (9 * 2), 0);
Bitboard FILE4_BB = Bitboard(UINT64_C(0x1ff) << (9 * 3), 0);
Bitboard FILE5_BB = Bitboard(UINT64_C(0x1ff) << (9 * 4), 0);
Bitboard FILE6_BB = Bitboard(UINT64_C(0x1ff) << (9 * 5), 0);
Bitboard FILE7_BB = Bitboard(UINT64_C(0x1ff) << (9 * 6), 0);
Bitboard FILE8_BB = Bitboard(0, 0x1ff << (9 * 0));//p[1]について
Bitboard FILE9_BB = Bitboard(0, 0x1ff << (9 * 1));
筋を表すBitboard
0x1ff=511は9bitすべて1でありやねうら王は縦型bitboardであるのでこれで筋は表現出来る


Bitboard RANK1_BB = Bitboard(UINT64_C(0x40201008040201) << 0, 0x201 << 0);
Bitboard RANK2_BB = Bitboard(UINT64_C(0x40201008040201) << 1, 0x201 << 1);
Bitboard RANK3_BB = Bitboard(UINT64_C(0x40201008040201) << 2, 0x201 << 2);
Bitboard RANK4_BB = Bitboard(UINT64_C(0x40201008040201) << 3, 0x201 << 3);
Bitboard RANK5_BB = Bitboard(UINT64_C(0x40201008040201) << 4, 0x201 << 4);
Bitboard RANK6_BB = Bitboard(UINT64_C(0x40201008040201) << 5, 0x201 << 5);
Bitboard RANK7_BB = Bitboard(UINT64_C(0x40201008040201) << 6, 0x201 << 6);
Bitboard RANK8_BB = Bitboard(UINT64_C(0x40201008040201) << 7, 0x201 << 7);
Bitboard RANK9_BB = Bitboard(UINT64_C(0x40201008040201) << 8, 0x201 << 8);
段を表すbitboard
0x201= 513 は1bit目1 10bit目1

0x402010080402012進数にすると 1000000001000000001000000001000000001000000001000000000 9おきに1が入っているので段を表すbitboardとして用いることができる



Bitboard FILE_BB[FILE_NB] = { FILE1_BB,FILE2_BB,FILE3_BB,FILE4_BB,FILE5_BB,FILE6_BB,FILE7_BB,FILE8_BB,FILE9_BB };
Bitboard RANK_BB[RANK_NB] = { RANK1_BB,RANK2_BB,RANK3_BB,RANK4_BB,RANK5_BB,RANK6_BB,RANK7_BB,RANK8_BB,RANK9_BB };
各筋、段を表現するBitboard配列をまとめたもの



Bitboard StepEffectsBB[SQ_NB_PLUS1][COLOR_][16];
近接駒の利きを格納している
16というのは近接駒の種類(敵8自分8)
事前に駒がどこにいるときに盤のどこに利きが生まれるのかのすべての組み合わせを格納しているテーブル




CheckCandidateBB[sq][Pt][color]
相手王がsqに居るときcolor側の駒がどこに居れば相手に王手をかけることができるかのテーブル
これによってすぐに王手鏡面かどうかを判断できる
Bitboard::init()の(9)で初期化されている
[81][8][2]
ptが7までしかないがこれは同じ動きをする駒を一つにまとめているからである
check_candidate_bb()として使われる。
generate_checks()で
 x = 直接王手となる候補
 const Bitboard x =
    (pos.pieces(Us, PAWN) & check_candidate_bb(Us, PAWN , themKing)) |
    (pos.pieces(Us, LANCE) & check_candidate_bb(Us, LANCE, themKing)) |
   (pos.pieces(Us, KNIGHT) & check_candidate_bb(Us, KNIGHT, themKing)) |
   (pos.pieces(Us, SILVER) & check_candidate_bb(Us, SILVER, themKing)) |
  (pos.pieces(Us, GOLD) & check_candidate_bb(Us, GOLD, themKing)) |
   (pos.pieces(Us, BISHOP) & check_candidate_bb(Us, BISHOP, themKing)) |
  (pos.pieces(Us, ROOK) ) | // ROOK,DRAGONは無条件全域
  //TODO なんで無条件全域?
  (pos.pieces(Us, HDK) & pos.pieces(Us, BISHOP) & check_candidate_bb(Us, ROOK, themKing)); // check_candidate_bbにはROOKと書いてるけど、HORSE //TODO どいうこと?
として直接王手となる候補を求めるために使われる




PAWN_DROP_MASK_BB[512][COLOR_NB];
// 歩が打てる筋を得るためのBitboard
// bit0..9筋に歩が打てないなら1 ,
 bit1..8筋に , … , bit8..1筋に歩が打てないなら1
というbit列をindexとして、歩の打てるBitboardを返すためのテーブル。
2歩判定に使われる


InFrontBB[COLOR][RANK];
// color == BLACKのとき、RANK段目よりWHITE側(1からn-1段目)を表現するBitboard。
// color == WHITEのとき、RANK段目よりBLACK側(n+1から9段目)を表現するBitboard。
これを用いてc側の香の利き = 飛車の利き & InFrontBB[c][rank_of(sq)]とすることができる。
香車の利きに関して使われている
これを利用して敵陣と自陣が1になっているBitboardを表現することが出きる。



extern Bitboard LineBB[SQ_NB_PLUS1][SQ_NB_PLUS1];
2升を通過する直線を返すためのテーブル
 line_bb(Square sq1, Square sq2) { return LineBB[sq1][sq2]; }のようにして使われる
空き王手判断に使う



BetweenBB[SQ_NB_PLUS1][SQ_NB_PLUS1];
 2升に挟まれている升を返すためのテーブル(その2升は含まない)
bitboard::init()で全マスとの関係に関して値が入れられる。
between_bb()関数に包まれていて、この関数を呼び出されることで使われる
飛び駒に王手をされているときにその間に駒を打つ処理をするときに使われる
more_than_one((between_bb(from, ksq) & occ))により
駒をfromに置いた時にfromからksq(王の位置)までの間にほかの駒が存在しないかどうかのチェックに使われる(occはほかの駒がいる位置)
 b = between_bb(ksq, pinners.pop()) & pieces();により
ksqと大駒とで挟まれている駒を列挙しpinされているかどうかのチェックに使う
大体は飛びゴマの王手処理にために使われる
また
inline const Bitboard around24_bb(Square sq) { return check_candidate_bb(BLACK, HDK, sq); }として
あるマスの24近傍を返すためにもつかわれる
これはやねうら王の長い利きの更新のために使われる(別に使わなくてもよい)

f:id:daruma3940:20160520223530p:plain
「つかれたよ!あまあまさんがたべたいよ!」

f:id:daruma3940:20160520223745p:plain
「もうちょっとだけ続くのじぇ
がまんするのじぇ
ここからは利きが格納されたbitboardなのじぇ」

Bitboard StepEffectsBB[SQ_NB_PLUS1][COLOR_NB][PIECE_TYPE_BITBOARD_NB2];
// 近接駒の利き
// 3番目の添字がPIECE_TYPE_BITBOARD_LANCE,PIECE_TYPE_BITBOARD_BISHOP,PIECE_TYPE_BITBOARD_ROOK
// のときは、盤上の駒の状態を無視した(盤上に駒がないものとする)香・角・飛の利き。
// また、PIECE_TYPE_BITBOARD_QUEEN,PIECE_TYPE_BITBOARD_CROSS00,PIECE_TYPE_BITBOARD_CROSS45
// は、馬+龍,十字方向に1升,×字方向に1升となる。

// 王の利き
inline Bitboard kingEffect(const Square sq) { return StepEffectsBB[sq][BLACK][PIECE_TYPE_BITBOARD_HDK]; }
のようにして関数に包まれながら使われる。
使用法としては一般的に利きが使用される目的通りの使用法である
駒の移動先の候補targetをしぼるために使われたりもする
おそらくStepとは 盤上の駒を考慮しない利きにつけられる記号である。



Bitboard LanceEffect[COLOR_NB][SQ_NB_PLUS1][128];//128とはなに? ANS。64*2 邪魔ゴマの位置
香車の利き (occupiedを考慮している)
bitboard::init()の(5)で求められる




// --- 角の利き
extern Bitboard BishopEffect[20224+1];
extern Bitboard BishopEffectMask[SQ_NB_PLUS1];
extern int BishopEffectIndex[SQ_NB_PLUS1];
// --- 飛車の利き
extern Bitboard RookEffect[495616+1];
extern Bitboard RookEffectMask[SQ_NB_PLUS1];
extern int RookEffectIndex[SQ_NB_PLUS1];
この二つはinit()の(4)で初期化される

f:id:daruma3940:20160520223745p:plain
次はinfo内なのじぇ

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~stateinfo内
 
 // 現局面で手番側に対して王手をしている駒のbitboard。Position::do_move()で更新される。
  
Bitboard checkersBB;


~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~checkinfo内
 // 動かすと敵玉に対して空き王手になるかも知れない自駒の候補
  
// チェスの場合、駒がほとんどが大駒なのでこれらを動かすと必ず開き王手となる。
 
 // 将棋の場合、そうとも限らないので移動方向について考えなければならない。
 
 // ※ dcはdouble check(両王手)の意味。
  
Bitboard dcCandidates;


  // 自分側(手番側)の(敵駒によって)pinされている駒
  
Bitboard pinned;




  // 自駒の駒種Xによって敵玉が王手となる升のbitboard
  
Bitboard checkSq[PIECE_WHITE];

  

// 敵王の位置
  
Square ksq;

f:id:daruma3940:20160520223745p:plain
最後に差し手生成部なのじぇ
x(直接王手),yとかは省いたのじぇ

~~~~~~~~~~~~~~~~~~~~~~~差し手生成
移動先の候補の場所が1になっているbiboard
Bitboard target
generate_general()内にある

const Bitboard target =
    (GenType == NON_CAPTURES) ? pos.empties() : // 捕獲しない指し手 = 移動先の升は駒のない升
    (GenType == CAPTURES) ? pos.pieces(~Us) :   // 捕獲する指し手 = 移動先の升は敵駒のある升
   (GenType == NON_CAPTURES_PRO_MINUS) ? pos.empties() : // 捕獲しない指し手 - 歩の成る指し手 = 移動先の升は駒のない升 - 敵陣(歩のときのみ)
    (GenType == CAPTURES_PRO_PLUS) ? pos.pieces(~Us) : // 捕獲 + 歩の成る指し手 = 移動先の升は敵駒のある升 + 敵陣(歩のときのみ)   //TODO pieces(~US)だけでいいの?歩の成りは?ANS歩以外をここでは考えてる
    (GenType == NON_EVASIONS) ? ~pos.pieces(Us) : // すべて = 移動先の升は自駒のない升
    (GenType == RECAPTURES) ? Bitboard(recapSq) :  // リキャプチャー用の升(直前で相手の駒が移動したわけだからここには移動できるはず)
   ALL_BB; // error

のように生成される




auto target2
駒が移動できる場所 つまり利きのある場所
 を格納して置くbitboard 
targetをしぼるために使われる    

auto target2 =
 Pt == LANCE ? lanceEffect(Us, from, occ) :
Pt == KNIGHT ? knightEffect(Us, from) :
Pt == SILVER ? silverEffect(Us, from) :
 ALL_BB; // error

target2 &= target;//上の条件でtargetを絞る

f:id:daruma3940:20160520223530p:plain
「結構おおいんだね!」
f:id:daruma3940:20160520223745p:plain
「この分章では説明が長かったのでおおく見えるけど種類としてはそこまで多くはないのじぇ
ここで紹介したbitboardの種類だけをリストアップすると

occupied
piece_bb
SquareBB
FILE
RANK
StepEffectsBB
PieceEffect
ALL_BB
ZERO_BB
CheckCandidateBB
PAWN_DROP_MASK_BB
InFrontBB
LINEBB
BetweenBB
checkersBB
dcCandidates
pinned
checkSq
Ksq
target 
target2

見落としはあるかもしれないしあまり重要でないものは省いたけどこのくらいなのじぇ」

f:id:daruma3940:20160520223530p:plain

「ゆゆっ!?れいみゅからしたら3つ以上はたくさんなんだよ!ゆっくり理解してね!」

f:id:daruma3940:20160520223745p:plain
(...)

「次回はこれらのビットボードがどのように初期化されるかbitboard::init()の中を見ていくのじぇ
楽しみにするのじぇ!」