compact bitboard move generator

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
rreagan
Posts: 102
Joined: Sun Sep 09, 2007 4:32 am

Re: compact bitboard move generator

Post by rreagan » Tue Feb 26, 2008 2:46 am

This is what I've done (from memory). It's not quite as compact (plus I'm a little more long winded with my names), but it removes the bulk of the repetition. It's C++, but you could probably achieve the same with macros.

Code: Select all

template <class ATTACK_FUNCTION>
void gen_moves &#40;BITBOARD source_pieces, BITBOARD destination_mask, int move_type, MOVE_LIST & move_list&#41; &#123;
  while &#40;source_pieces&#41; &#123;
    source_square = first_one&#40;source_pieces&#41;;
    clear_bit&#40;source_pieces, source_square&#41;;
    moves = ATTACK_FUNCTION&#40;source_square&#41; & destination_mask;
    while &#40;moves&#41; &#123;
      destination_square = first_one&#40;moves&#41;;
      clear_bit&#40;moves, destination_square&#41;;
      move_list.add_move&#40;MOVE&#40;source_square, destination_square, move_type&#41;);
    &#125;
  &#125;
&#125;

void generate_moves &#40;MOVE_LIST & move_list&#41; &#123;
  gen_moves<knight_attacks>&#40;friendly_knights, enemy_pieces, CAPTURE, move_list&#41;;
  gen_moves<knight_attacks>&#40;friendly_knights, empty_squares, NONCAPTURE, move_list&#41;;
  gen_moves<bishop_attacks>&#40;friendly_bishops | friendly_queens, enemy_pieces , move_list&#41;;
// and so on...
&#125;

Aleks Peshkov
Posts: 882
Joined: Sun Nov 19, 2006 8:16 pm
Location: Russia

Re: compact bitboard move generator

Post by Aleks Peshkov » Tue Feb 26, 2008 12:07 pm

Using magic bitboards method, you need only 3 functions:
1) kings, knights, pawns with an argument pointer to attack table.
2) bishops, rooks with a pointer to uniform magic data structure.
3) queen case, one may unroll it to separate rooks+bishops, but I do not.

3-way switch or indirect call have better prediction rate.

bob
Posts: 20914
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: compact bitboard move generator

Post by bob » Tue Feb 26, 2008 4:59 pm

Aleks Peshkov wrote:Using magic bitboards method, you need only 3 functions:
1) kings, knights, pawns with an argument pointer to attack table.
2) bishops, rooks with a pointer to uniform magic data structure.
3) queen case, one may unroll it to separate rooks+bishops, but I do not.

3-way switch or indirect call have better prediction rate.
The prediction rate is not the issue, until you eliminate the branch completely. The main problem is the cache footprint causes different pieces of that generator function to be used/skipped each pass through the thing, which simply increases the cache miss rate unacceptably. The indirect function call was too expensive because of lack of inlining, the switch has two extra branches to test for the proper range of the switch variable, all of which drive up the cost...

I'm still playing with options, but so far the "unrolled" approach I currently use has been the fastest.

Post Reply