accelerating incremental attack tables with vector math: part 2

information in an attack table

For this example, we will use the same attack table format as in Rose and Clockwork.

In the above engines, attack table are defined like so:
attack_table[color][sq] gives us a list of pieces of color color that are attacking the square sq. This list of pieces is a piece mask, so if bit i in this 16-bit mask is 1, the piece with id i is attacking this square.
We also have two piece lists, defined like so:
piece_list_ptype[color][piece_id] is the type of the piece with id piece_id.
piece_list_square[color][piece_id] is location of the piece with id piece_id.

To generate a list of moves from an attack table, we just need to iterate over every possible attack and put that into a move list. This would give us all pseudolegal moves.

the naïve implementation

Here is a naïve implementation:

// Main movegen loop

for (u8 dest_sq = 0; dest_sq < 64; dest_sq++) {

  // stm is side to move

  u16 piece_mask = attack_table[stm][dest_sq];

  for (; piece_mask != 0; piece_mask &= piece_mask - 1) {

    // Do we have a friendly piece on this square?
    if (!board[dest_sq].isEmpty() && board[dest_sq].color() == stm) {
      continue;
    }

    const bool capture = !board[dest_sq].isEmpty() && board[dest_sq].color() != stm;

    // count trailing zeroes to get piece id
    const u8 piece_id = std::countr_zero(piece_mask);

    if (piece_list_ptype[stm][piece_id] == PieceType::pawn) {
      if (!capture) {
        // We can't diagonally move pawns unless its a capture
        continue;
      }

      // Generate capture-promotions
      if (dest_sq.rank() == stm.backRank()) {
        moves.push_back(Move::make(src_sq, dest_sq, MoveFlag::capture_promo_queen));
        moves.push_back(Move::make(src_sq, dest_sq, MoveFlag::capture_promo_knight));
        moves.push_back(Move::make(src_sq, dest_sq, MoveFlag::capture_promo_rook));
        moves.push_back(Move::make(src_sq, dest_sq, MoveFlag::capture_promo_bishop));
        continue;
      }
    }

    const Square src_sq = piece_list_square[stm][piece_id];

    const MoveFlag mf = capture ? MoveFlag::capture : MoveFlag::normal;

    moves.push_back(Move::make(src_sq, dest_sq, mf));
  }
}

// En passant
if (en_passant.isValid()) {
  u16 our_pawns = attack_table[stm][en_passant] & pawn_mask;
  for (; our_pawns != 0; our_pawns &= our_pawns - 1) {
    const u8 piece_id = std::countr_zero(our_pawns);
    const Square src_sq = piece_list[stm][piece_id].square();
    moves.push_back(Move::make(src_sq, en_passant, MoveFlag::en_passant));
  }
}

// Castling
if (position.canCastle()) {
  generateCastling();
}

// Quiet pawn moves (pawn push and double pawn push)
generateQuietPawnMoves();

This just splats out all possible attacks into our movelist regardless of legality. generateCastling and generateQuietPawnMoves are left as an exercise to the reader and use standard tech.

The problem with the above code is we can make it faster. The two if statements can be hoisted out of the loop.

hoisting the if statements

To hoist the friendly piece check out of the loop, we can just iterate over a bitboard empty or enemy squares.

To hoist the pawn check out of the loop, we can pre-mask piece_mask into seperate pawn / non-pawn piece masks, with diffierent bitboards.

We will focus on just the main movegen loop. With a helper function, this looks like:

void write(MoveList& moves, u64 dest_bb, u16 subset_piece_mask, MoveFlag mf) {
  for (; dest_bb != 0; dest_bb &= dest_bb - 1) {
    const Square dest_sq = std::countr_zero(dest_bb);

    u16 piece_mask = attack_table[stm][dest_sq] & subset_piece_mask;

    for (; piece_mask != 0; piece_mask &= piece_mask - 1) {
      const u8 piece_id = std::countr_zero(piece_mask);
      const Square src_sq = piece_list[stm][piece_id].square();
      moves.push_back(Move::make(src_sq, dest_sq, mf));
    }
  }
}

const u64 empty = board.zero8();
const u64 enemy = board.getColorBitboard(!stm);

const u16 valid_ids     = ~piece_list_ptype[stm].maskForPieceType(PieceType::none);
const u16 pawn_mask     = piece_list_ptype[stm].maskForPieceType(PieceType::pawn);
const u16 non_pawn_mask = valid_ids & ~pawn_mask;

const u64 promo_zone = 0xFF_u64 << (stm == Color::black ? 0 : 56);

// Pawn normal captures
write(moves, enemy & ~promo_zone, pawn_mask, MoveFlag::capture);

// Pawn captures-with-promotion
write(moves, enemy & promo_zone, pawn_mask, MoveFlag::capture_promo_queen);
write(moves, enemy & promo_zone, pawn_mask, MoveFlag::capture_promo_knight);
write(moves, enemy & promo_zone, pawn_mask, MoveFlag::capture_promo_rook);
write(moves, enemy & promo_zone, pawn_mask, MoveFlag::capture_promo_bishop);

// Non-pawn captures
write(moves, enemy, non_pawn_mask, MoveFlag::capture);

// Non-pawn quiets
write(moves, empty, non_pawn_mask, MoveFlag::normal);

you can make further optimizations

Some simple optimizations:

• Consider the king seperately. Only consider destinations that are not in danger. You can get a danger bitboard like so: u64 danger = attack_table[!stm].nonzero16(); This reduces the number of illegal king moves we generate!
• Only loop through squares that actually have attacks in them! You can get an “active square” bitboard like so: u64 active = attack_table[stm].nonzero16();
• Consider pawn / non-pawn active state seperately.
• Remove the piece mask loop by using the vpcompressw instruction.

next

Hopefully this was a gentle introduction to generating moves using an attack table. We will look into incrementally generating the attack table in the next part of this series.

navigation

1. part 1: non-incrementally generating attack tables
2. part 2: move generation
3. part 3: incrementally generating attack tables
4. part 4: pin detection and fully-legal movegen (TBD)