Pawn move generation in bitboards

[mphuget]

Hello all,

I try to modify my engine to use Bitboards (currently 10x12 board representation) and I am stuck in understanding what is the most efficient for pawn move generation.

I have a U64 representation for all the pieces on the board
I have a U64 pawn representation for one side
For every bit set in the pawn representation, I check whether the next square is set to 1, and the same for two squares after, it gives me the two pseudo-legal moves (I don't consider En Passant rule for the moment)

Now, this is a mix between bit operations and conditions, for instance:
sq = next_bit(position, current)
//one step forward (consider this is white)
if !check_nth_bit(position, sq+8) {
//one more pseudo-move
}

Does it sound correct?
Do I need more bit operations?

Thanks in advance for your help

mph

[Pio]

Hello all,

I try to modify my engine to use Bitboards (currently 10x12 board representation) and I am stuck in understanding what is the most efficient for pawn move generation.

I have a U64 representation for all the pieces on the board
I have a U64 pawn representation for one side
For every bit set in the pawn representation, I check whether the next square is set to 1, and the same for two squares after, it gives me the two pseudo-legal moves (I don't consider En Passant rule for the moment)

Now, this is a mix between bit operations and conditions, for instance:
sq = next_bit(position, current)
//one step forward (consider this is white)
if !check_nth_bit(position, sq+8) {
//one more pseudo-move
}

Does it sound correct?
Do I need more bit operations?

Thanks in advance for your help

mph

Hi!

I am by no means an expert in bitboards since I am using a combination of my own tri board representation, 10x12 and some bit manipulations. I would however first generate all one moves at once by using the original bitboard for the pawns, do the operation (in your case +8) on the 64 bit pawns bitboard that will result in a bitboard for all your pawns one move forward. I would then probably XOR the result with the bitboard of all your and opponent pieces (and by pieces I mean all pieces and pawns) to remove the moves that are hindered by other pieces. I would then extract bit by bit each bit from that as each pawn move. I would then do something similar for the pawns that can go two moves forward but of course you will first have to get those by take your pawn bitboard and and it with the bit pattern for the second row first, change the operand to +16 and then XOR with all pieces and lastly extract bit by bit. The nice thing is that you will not need to use any branches. I hope I have not written something really bad since I am just doing it in my head and have not done it myself.

My board representation has the benefit to be extremely compact 3x64 bit, colour agnostic and the rotation of side is completely branchless if I would use intrinsics in C# . But of course my representation is really slow. Gerd had some really smart suggestions how to speed up my representation and if you want to see some really smart bit handling you should read all the bit handling stuff he does in the chess programming wiki. It is awesome.

Good luck!
/Pio

[Gerd Isenberg]

With bitboards you should do it set-wise, specially with pawns. All single push targets are the intersection of pawns shifted one square (i.e. << 8 for white >> 8 for black, dependent on your square mapping) with all empty squares. To generate moves, you traverse these target sets and with the unique source-target relationship, this is how it works for say white pawn pushes:

Code: Select all

   
   U64 wPawnTargets = (wpawns << 8) & empty;
   while (wPawnTargets) {
     int toSquare = bitScanForward( wPawnTargets );
     int fromSquare = toSquare + 8;
     addMove ( fromSquare, toSquare, SINGLE_PAWN_PUSH);
     wPawnTargets &= wPawnTargets - 1; // reset least significant bit
   }

https://www.chessprogramming.org/Pawn_P ... Properties
https://www.chessprogramming.org/Pawn_P ... Bitboards)
https://www.chessprogramming.org/Pawn_A ... Bitboards)
https://www.chessprogramming.org/Bitboard_Serialization

[AlvaroBegue]

Just a note on C++ style. Using a few features from modern C++, you can make the code look quite clean. For instance, you can write wrappers around basic integer types to represent squares and bitboards, so you can print then naturally with `std::cout <<'. You can also make use of range-based for loops to iterate over the bits in a bitboard. I just put something together for your example of moving white pawns forward one step:

Code: Select all

#include <iostream>
#include <cstdint>

struct Square {
  int x;

  Square(int x) : x(x) { }
};

std::ostream &operator<<(std::ostream &os, Square sq) {
  if (sq.x >= 0 && sq.x < 64)
    os << char('h' - (sq.x % 8)) << char('1' + (sq.x / 8));
  else	
    os << "??";
  return os;
}

struct Bitboard {
  struct Iterator {
    uint64_t x;

    Iterator(uint64_t x) : x(x) { }
    Square operator*() const { return Square(__builtin_ctzll(x)); }
    Iterator &operator++() { x &= x - 1; return *this; }
    bool operator==(Iterator other) { return x == other.x; }
    bool operator!=(Iterator other) { return x != other.x; }
  };
  
  uint64_t x;
  
  Bitboard(uint64_t x) : x(x) { }

  Iterator begin() const { return Iterator(x); }
  Iterator end() const { return Iterator(0ull); }
};

Bitboard operator&(Bitboard bb1, Bitboard bb2) {
  return Bitboard(bb1.x & bb2.x);
}

Bitboard South(Bitboard bb) { return Bitboard(bb.x >> 8); }
Bitboard North(Bitboard bb) { return Bitboard(bb.x << 8); }
Bitboard East(Bitboard bb) { return Bitboard((bb.x & 0xfefefefefefefefeull) >> 1); }
Bitboard West(Bitboard bb) { return Bitboard((bb.x & 0x7f7f7f7f7f7f7f7full) << 1); }

Square South(Square sq) { return Square(sq.x - 8); }
Square North(Square sq) { return Square(sq.x + 8); }
Square East(Square sq) { return Square(sq.x - 1); }
Square West(Square sq) { return Square(sq.x + 1); }

int main() {
  Bitboard white_pawns = 0x000000000000ff00ull, empties = 0x0000ffffffff0000ull;
  
  for(auto from_square : white_pawns & South(empties))
    std::cout << from_square << North(from_square) << '\n';
}