What's the right approach of storing moves generated using bitboards?

Question

I am building a chess engine from scratch using bitboards and, so far I am able to generate pawns moves. But, I am stuck on what should I do after finding all possible moves for pawns.

Right now the current function is generating QUIETS moves pushing pawns ONE or TWO squares. Later i will deal with en passant and validations.

My question is, Am I doing right generating all pawns moves at once? And, I would like to know what is the right approach of storing the moves? What information need to saved and what data type should I use?

Here my code (C++):

#include "moves.h"

//Pawns moves
Bitboard single_push(Color color, Bitboard pawns, Bitboard empty) { // EmptyBoardBB
   return color == WHITE ?  north(pawns) & empty : 
                            south(pawns) & empty;
}

// also used for en-passant 
Bitboard double_push(Color color, Bitboard pawns, Bitboard empty) {
   return color == WHITE ?  north_north(pawns) & empty & Rank4BB : 
                            south_south(pawns) & empty & Rank5BB;
}

// Right now just testing pushing pawns 1-2 squares
Bitboard generate_pawn_moves(Color color, GenType type, Bitboard Us, Bitboard Them)
{
    Bitboard bb, empty;
    empty = ~Them;

    if (type == QUIETS) 
    {
        bb = single_push(color, Us, empty);
    }

    return bb;
}

Thanks in advance for any info that can take me on the right path.

Answer 1

Q1: Should I generate all pawn moves at once?

Yes. There's no reason not to do that. But... your code wouldn't work because you're returning a bitboard in your function. You should instead return a list, Stockfish does that:

https://github.com/official-stockfish/Stockfish/blob/master/src/movegen.cpp

ExtMove* generate_pawn_moves(const Position& pos, ExtMove* moveList, Bitboard target);

The function generate_pawn_moves takes a position object and append new pawn moves into a list (ExtMove*). You shouldn't just return a bitboard because:

• It's not a convenient data structure for looping over moves (you'll need to loop over moves while doing your engine search)
• It doesn't tell you where you pawn starts and thus you can't undo a move
• By squeezing all the pawn moves into a single integer, you lose important information. For example, if you have a pawn on c4 and e4 and you can capture on d5. You need to save c4-d5 and e4-d5, not just d5.

Your function should look like:

void generate_pawn_moves(List *moves, Color color, GenType type, Bitboard Us, Bitboard Them);
{
    if (type == QUIETS) 
    {
        for (... all single push ...)
           moves++ = <single push move>

        for (... all double push ...)
           moves++ = <double push move>
    }
    else
    {
        for (... all captures ...)
           moves++ = <captures move>
    }
}

You will need to allocate enough memory for the moves pointer, there're other ways to do that but C++ discussion is off-topic here.

Later on, you'll need to do a search (otherwise why'd you generate the moves?). Like this:

  for (auto move : moves)
  {
       <make the move to the internal board>

       ..... search and evaluate the position after the move ....

       <undo the move>
  }

You see, you'll need to undo the move and it's only possible if you know where your pawn starts.

Q2: What do I need to save a move?

Let's take a look at Stockfish.

https://github.com/official-stockfish/Stockfish/blob/master/src/types.h

/// A move needs 16 bits to be stored
///
/// bit  0- 5: destination square (from 0 to 63)
/// bit  6-11: origin square (from 0 to 63)
/// bit 12-13: promotion piece type - 2 (from KNIGHT-2 to QUEEN-2)
/// bit 14-15: special move flag: promotion (1), en passant (2), castling (3)
/// NOTE: EN-PASSANT bit is set only when a pawn can be captured
///

• Destination
• Origin
• Promotion
• En Passpant
• Castling

Answer 2

I really appreciate the response from our contributors, but still there is a question unanswered floating on air. How do I implement the “MOVE” structure? Based on Bitboard approach?

In reality, there is no a common ground among chess engines. Some programmers will tell you go with a structure and store any move’s detail within, but, on the other side, others will tell you, go simple with just one data type (Integer, String, etc).

To be honest, in simple English means, USE whatever flavor you feel comfortable with and, not a subject related to best performance. So, based on that assumption, I will provide you how to implement both cases.

To make this simple, let’s break down what kind of information is needed to encode a move.

• Index of square destination
• Index of square origin
• Type of move (quiet, captures, evasions, en passant, castling, …)

Structure Approach

If you decide to go with a structure approach, you will have something similar to this:

struct Move {
    Int from;
    Int to;
    Int moveType;
};

That will work if we have an enum for our moveType:

enum MoveType {
    QUIET, CAPTURE, EVASION, ENPASSANT, CASTLING  
};

The structure approach will do the work and, then you just need to create an array with that structure to store the list of generated moves. And that’s it; you have your container to store moves.

Single Data Type Approach

Suppose we decide to go with Integer type. How we can store the move information in one single integer? The response is, Bit manipulation (Duh!, we are using bitbaord representation).

The idea is really simple, let’s use partial portion of the Integer to store the “square origin”, and next to it, use it to store the “square destination” and last, insert the “Move Type” (call it flag if you want).

If we have an Integer that holds 16 bits, we can dissect it into the following:

0000 0000 0000 0000 – index of square origin

0000 0000 0000 0000 – index of square destination

0000 0000 0000 0000 – move type (flag)

We can use the first 6 bit to store the square origin.

0000 0000 0011 1111 – 6 bit for square origin

We can do the same with the rest. At the end you will have something like this:

0000 0000 0011 1111 – index of square origin

0000 1111 1100 0000 – index of squire destination

0011 0000 0000 0000 – move type (flag)

To put this into a better context, let assume we have a structure that represent each square:

enum Square {
SQ_A1, SQ_B1, SQ_C1, SQ_D1, SQ_E1, SQ_F1, SQ_G1, SQ_H1,
SQ_A2, SQ_B2, SQ_C2, SQ_D2, SQ_E2, SQ_F2, SQ_G2, SQ_H2,
SQ_A3, SQ_B3, SQ_C3, SQ_D3, SQ_E3, SQ_F3, SQ_G3, SQ_H3,
SQ_A4, SQ_B4, SQ_C4, SQ_D4, SQ_E4, SQ_F4, SQ_G4, SQ_H4,
SQ_A5, SQ_B5, SQ_C5, SQ_D5, SQ_E5, SQ_F5, SQ_G5, SQ_H5,
SQ_A6, SQ_B6, SQ_C6, SQ_D6, SQ_E6, SQ_F6, SQ_G6, SQ_H6,
SQ_A7, SQ_B7, SQ_C7, SQ_D7, SQ_E7, SQ_F7, SQ_G7, SQ_H7,
SQ_A8, SQ_B8, SQ_C8, SQ_D8, SQ_E8, SQ_F8, SQ_G8, SQ_H8
};

Imagine you have a pawn sitting on f2 and you need to move it to f4, and there is an enemy pawn on e4. This will raise the en passant flag, isn’t it?

So, we need to encode our pawn move from f2 to f4 and flag it as enpassant availability.

Pseudo code will be like this:

move = enpassant-flag + destination + origin;

Now we need to translate this to bit manipulation (shifting bits).

unsigned int move;

//insert square origin using 6 bits
move  = (origin & 0x3f << 6); -the hex to mask 6 bits.

// insert square destination using also 6 bits
move = (destination & 0x3f);

//insert the flag
move = ((flag & 0xf) << 12);

// now putting everything together…
Move make_move(Square from, Square to, unsigned int flag) {
    Return move = ((flag & 0xf) << 12) | (destination & 0x3f) | (origin & 0x3f) << 6;
}

Now you can call the method as follow:

moveList  = make_move(SQ_F2, SQ_F4, ENPASSANT);

I hope this information will be useful to the public :)

Answer 3

The Chess Programming Wiki has all the resources you should need.

1. Since you have all the pawns represented, it makes sense to generate all their moves at once.
2. The way to store the moves is what you are most comfortable with. The basic information you need is just the two squares involved. Back in the old days, people would compress all the information into an integer. Seven bits would represent the "from" square (0-63), and seven bits for the "to" square. Most would include extra information to make it easier to actually make and store the move. These include: promotion piece (4), EP (1), EP possible (1 or 4), captured piece (4), castling (1 or 4).

I prefer the old methods of representing the board, since it's easier for me to visualize the board and methods. However, Stockfish is one of the best engines and you can freely download its source.