Bonanzaの指し手生成ルーチン完全解読(5)

■ Bonanzaの指し手生成ルーチン完全解読(5)


指し手生成のソースを解読するには利き関係のマクロの解読が必須ということがわかったところで、利き関係のマクロの解読を続けていこう。


■ AttackFile , AttackRank


前回、香の利きを生成するマクロとして次のものが出てきた。

// 香の利き
#define AttackBLance(bb,i)  bb = abb_minus_rays[i] & AttackFile(i)
#define AttackWLance(bb,i)  bb = abb_plus_rays[i] &  AttackFile(i)

ここで使われているAttackFileは、BoardPosの位置の上下の利きのある場所が1であるbitboardを求めるものだ。
当然、自駒か敵駒に当たるとそこで利きは止まるのでそこまでの利きでなければならない。


Fileは筋 , Rankは段を意味する。AttackFileは筋に関するもので、段に関するAttackRankというマクロもある。こちらは左右方向の利きのある場所が1であるbitboardを求めるものだ。


これらの利きをどうやって高速に求めるかはbitboardを使ってコンピュータ将棋を実装している者にとっては必修課題なので詳しく解説する。まず、これらの定義から。

// iの筋の利き。上下の端が駒にぶつかるまで。
// 香などの縦の利きを求めるのに使う。
// 香が9段目にいるとして、1段目に利きが到達できるかどうかを調べるには、
// 1段目の駒の状態は関係なく、2〜8段目に駒があるかだけが問題なので結局、その7bit
// を調べるだけで済む。要するに、
// abb_file_attacksは[nsquare][7bit = 128個]でこと足りるという仕組み。
// occupied_rl90は先後両方の駒が含まれる盤面を90度回転させたbitboard
#define AttackFile(i)  (abb_file_attacks[i]                               \
                         [((ptree->posi.occupied_rl90.p[aslide[i].irl90]) \
                            >> aslide[i].srl90) & 0x7f])

// iの段の利き。左右の端が駒にぶつかるまで。
// 先後の両方の駒と判定する必要があるのでb_occupiedとw_occupiedと
// bitwise ORをとる必要がある。
#define AttackRank(i)  (ai_rook_attacks_r0[i]                             \
                         [((ptree->posi.b_occupied.p[aslide[i].ir0]       \
                            |ptree->posi.w_occupied.p[aslide[i].ir0])     \
                             >> aslide[i].sr0) & 0x7f ])

ソース中にコメントを私が補っているのでそれ以上の解説はしない。どんどんソースを見ていこう。このマクロにaslideというテーブルが出てきた。aslideのaはarrayを意味する。


Bonanzaのソースでは配列名にはa、整数型の変数名にはnを先頭につける。ループ変数ならiがつくこともある。構造体名には _tを末尾につけてある。ポインタはpが先頭についている。premainingとか書いてあって、premainという単語があるのかと思って辞書を引いたが、よく見たらポインタのp + remaining(残り)を意味する変数名だった、なんてことのないようにこの命名規則をしっかり頭に入れておく必要がある。

// スライドテーブルのentry
// 斜めの利きなどを計算するのに使う。
// 詳しい意味はini.cppのini_attack_tablesを参照のこと。
struct slide_tbl
{
  u8		ir0,   sr0;
  u8		irl90, srl90;
  u8		irl45, srl45;
  u8		irr45, srr45;
};

// スライドテーブル
// abb_file_attacksなどで使うためのテーブル。
// 詳しい意味は、ini.cppのini_attack_tablesを参照のこと。
extern slide_tbl aslide[ nsquare ];


このaslideはini_attack_tablesで次のように初期化されている。ソース中にコメントを補ってあるので解説は不要だろう。

	// 以下、aslideのテーブル初期化コード
  for ( i = 0; i < nsquare; i++ )
    {
			// そのnsquareが何番目のbitboardに属するのか
      aslide[i].ir0   = (u8)(i/(nfile*3));
			// 000000000
			// 000000000
			// 000000000
			// 111111111
			// 111111111
			// 111111111
			// 222222222
			// 222222222
			// 222222222

      aslide[i].sr0   = (u8)((2-(i/nfile)%3)*9+1);
      // bitboardのp[N]から、その段の2〜8筋(7bit)を取り出すのに必要なシフト回数
      // 何故7bitで良いかというと、駒を捕獲しない指し手の生成だから、
      // 例えば飛車が5筋にいて、2,3,4筋に駒がなければ1筋まで行けるのは確定で、
      // 1筋に仮に駒があれば、それは捕獲する移動だから自動的に除外されるから、
      // 飛車の利きを最初に調べるときに1筋まで考慮する必要はないのである。
      // よって、2〜8筋の駒の状態だけ調べれば十分。
      //
      // 19 19 19 ..
      // 10 10 10 ..
      //  1  1  1 ..
      // 19 19 19 ..
      // 10 10 10 ..
      //  1  1  1 ..
      // 19 19 19 ..
      // 10 10 10 ..
      //  1  1  1 ..

			// ir0を90度回転させたもの。
			// あるBoardPosが occupied_rl90の何番目のu32にあるかを
			// 確定させるのに使う。
      aslide[i].irl90 = (u8)(2-(i%nfile)/3);
			// 222111000
			// 222111000
			// 222111000
			// 222111000
			// 222111000
			// 222111000
			// 222111000
			// 222111000
			// 222111000
			
			// ↑で求めたoccupied_rl90のu32から、その筋(2〜8筋の7bit)を取り出すときに必要な
			// shiftの回数。srl90はShift number to Rotate turn to the Left 90゜の意味か。
      aslide[i].srl90 = (u8)(((i%nfile)%3)*9+1);
      //  1  1  1 ..
      // 10 10 10 ..
      // 19 19 19 ..
      //  1  1  1 ..
      // 10 10 10 ..
      // 19 19 19 ..
      //  1  1  1 ..
      // 10 10 10 ..
      // 19 19 19 ..
      
    }

  // 少しややこしいが斜めも同様。  
  for ( irank = 0; irank < nrank; irank++ )
    for ( ifile = 0; ifile < nfile; ifile++ )
      {
          // 将棋盤に斜めのラインは9+8=17本あって、45度回転させた盤面が
          // 9*9に入りきらないので、それを詰め込むために共有しているラインがある。
          // そこで盤面の右下半分なのか左上半分なのかで意味を変えることにする。
        if ( irank >= ifile )
          {
            // 何番目のbitboardのu32か。
            aslide[ irank*nfile+ifile ].irl45
              = (u8)((irank-ifile)/3);

						// そこを取り出すのに必要な右shift回数。
            aslide[ irank*nfile+ifile ].srl45
              = (u8)((2-((irank-ifile)%3))*9+1);
          }
        else {
          aslide[ irank*nfile+ifile ].irl45
            = (u8)((9+irank-ifile)/3);
          aslide[ irank*nfile+ifile ].srl45
            = (u8)((2-((9+irank-ifile)%3))*9+1);
        }
      }

  for ( irank = 0; irank < nrank; irank++ )
    for ( ifile = 0; ifile < nfile; ifile++ )
      {
        if ( ifile+irank >= 8 )
          {
            aslide[ irank*nfile+ifile ].irr45
              = (u8)((irank+ifile-8)/3);
            aslide[ irank*nfile+ifile ].srr45
              = (u8)((2-((irank+ifile-8)%3))*9+1);
          }
        else {
          aslide[ irank*nfile+ifile ].irr45
            = (u8)((irank+ifile+1)/3);
          aslide[ irank*nfile+ifile ].srr45
            = (u8)((2-((irank+ifile+1)%3))*9+1);
        }
      }


さきほどのマクロで出てきたabb_file_attacksとai_rook_attacks_r0も同様にini_attack_tablesで初期化されている。この意味ならびに使い方は、ソースを引用するのでそのコメントを読んで理解していただきたい。

	// abb_file_attacksとは、
  // file = 筋 , file_attacks =  縦方向の利き
  // の意味。
  // abb_file_attacks[boardPos][w]
  // を与えると、boardPosから上下に対する利きが一発で求まる。
  // 
	// また、
  // w = そのboardPosの属する列の、駒がある位置が1であるbit pattern(7bit)
  //  2の段 = 0 bit目
  //   …
  //  8の段 = 8 bit目
  // に相当するので1,9の段にある障害駒は無視されるが、
  // それらの駒は利きには関係ないので考慮する必要がない。
  // ※なぜなら、1段目に駒があろうとなかろうと下から2段目までに利きが伸びていて2段目に駒が
  // なければ利きは当然1段目にも到達しているからで、結局、1段目まで利きが到達するかどうかを判定するために
  // 1段目に駒があるかないかという情報は必要ないのである。
  //
	// あと、特に w == 0 のときは、boardPosの位置の上下に発生している利きを表現する。
  // これは詰み判定のときに役立つ。
  // 
  for ( irank = 0; irank < nrank; irank++ )
    for ( ifile = 0; ifile < nrank; ifile++ )
      for ( pcs = 0; pcs < 128; pcs++ )
      // pcsはbit pattern (7bit) = 0〜127の任意の数
        {
          bb = 0;
          // irank + iの範囲は、1..8。すなわち2筋から8筋までの7bit
          for ( i = -1; irank+i >= 0; i-- )
            {
              bb.Xor( ifile , irank+i);
              // iを-1から引き算していくということはこれは上方向のスキャン

              if ( (pcs<<1) & (1 << (8-irank-i)) ) { break; }
            }
          for ( i = 1; irank+i <= 8; i++ )
            {
              bb.Xor( ifile , irank+i );
              // iを+1から足し算していくということはこれは下方向のスキャン

              if ( (pcs<<1) & (1 << (8-irank-i)) ) { break; }
            }
          abb_file_attacks[irank*nfile+ifile][pcs] = bb; 
        }

  for ( irank = 0; irank < nrank; irank++ )
    for ( ifile = 0; ifile < nrank; ifile++ )
      for ( pcs = 0; pcs < 128; pcs++ )
        {
          bb = 0;
          // ifile + iの範囲は、1..8。すなわち2段から8段までの7bit
          for ( i = -1; ifile+i >= 0; i-- )
            {
              bb.Xor( ifile+i , irank );
              if ( (pcs<<1) & (1 << (8-ifile-i)) ) { break; }
            }
          for ( i = 1; ifile+i <= 8; i++ )
            {
              bb.Xor( ifile+i , irank );
              if ( (pcs<<1) & (1 << (8-ifile-i)) ) { break; }
            }
          // 横の両サイドのスキャン。[irank/3]しか関係ないので、bitboardではなく
          // 単なるu32のテーブルになっている。
          // ai_rook_attacks_r0は、abb_file_attacksの横版で、abb_rank_attacksに相当する。
          ai_rook_attacks_r0[irank*nfile+ifile][pcs] = bb.p[irank/3]; 
        }

  for ( irank = 0; irank < nrank; irank++ )
    for ( ifile = 0; ifile < nrank; ifile++ )
      for ( pcs = 0; pcs < 128; pcs++ )
        {
          bb = 0;
          if ( ifile <= irank )
            {
		          // ifile + iの範囲は、1..8。すなわち2段から8段までの7bit
              for ( i = -1; ifile+i >= 0; i-- )
                {
                  bb.Xor( ifile+i , irank+i );
                  if ( (pcs<<1) & (1 << (8-ifile-i)) ) { break; }
                }
              for ( i = 1; irank+i <= 8; i++ )
                {
                  bb.Xor( ifile+i , irank+i );
                  if ( (pcs<<1) & (1 << (8-ifile-i)) ) { break; }
                }
            }  
          else {
	          // ifile + iの範囲は、1..8。すなわち2段から8段までの7bit
            for ( i = -1; irank+i >= 0; i-- )
              {
                bb.Xor( ifile+i , irank+i );
                if ( (pcs<<1) & (1 << (8-ifile-i)) ) { break; }
              }
            for ( i = 1; ifile+i <= 8; i++ )
              {
                bb.Xor( ifile+i , irank+i );
                if ( (pcs<<1) & (1 << (8-ifile-i)) ) { break; }
              }
          }
          abb_bishop_attacks_rl45[irank*nfile+ifile][pcs] = bb; 
        }

  for ( irank = 0; irank < nrank; irank++ )
    for ( ifile = 0; ifile < nrank; ifile++ )
      for ( pcs = 0; pcs < 128; pcs++ )
        {
          bb = 0;
          if ( ifile+irank >= 8 )
          // 将棋盤に斜めのラインは9+8=17本あって、45度回転させた盤面が
          // 9*9に入りきらないので、それを詰め込むために共有しているラインがある。
          // そこで盤面の右下半分なのか左上半分なのかで意味を変えることにする。
            {
		          // ifile + iの範囲は、1..8。すなわち2段から8段までの7bit
              for ( i = -1; irank-i <= 8; i-- )
                {
                  bb.Xor( ifile+i , irank-i );
                  if ( (pcs<<1) & (1 << (irank-i)) ) { break; }
                }
              for ( i = 1; ifile+i <= 8; i++ )
                {
                  bb.Xor( ifile+i , irank-i );
                  if ( (pcs<<1) & (1 << (irank-i)) ) { break; }
                }
            }  
          else {
		          // ifile + iの範囲は、1..8。すなわち2段から8段までの7bit
            for ( i = -1; ifile+i >= 0; i-- )
              {
                bb.Xor( ifile+i , irank-i );
                if ( (pcs<<1) & (1 << (irank-i)) ) { break; }
              }
            for ( i = 1; irank-i >= 0; i++ )
              {
                bb.Xor( ifile+i , irank-i );
                if ( (pcs<<1) & (1 << (irank-i)) ) { break; }
              }
          }
          abb_bishop_attacks_rr45[irank*nfile+ifile][pcs] = bb; 
        }

■ まとめ


今回は飛車、角の利きをbitboardを用いて高速に求めるための仕組みを解説した。長くなったので今回はここまで。