5

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.

  • @Glorfindel Why'd you remove the engine tag? This question has everything related to chess engine??? The question even started off with "I' am ... engine ..." – SmallChess Sep 29 '17 at 10:48
  • @SmallChess I was mainly cleaning up other tags ([move]). It makes sense to reserve the [engine] tag for either end-user questions about chess engines, or e.g. questions about how engines should be connected to SCID or something similar. Basically all [programming] questions are about engines. – Glorfindel Sep 29 '17 at 10:50
  • @Glorfindel I don't agree... This is programming about chess engines. Chess programming is more than just engines, it can be GUI. High level should goto computer-chess. Can you please add the tag back or ask it on meta exchange? – SmallChess Sep 29 '17 at 10:52
  • Sure, no problem. – Glorfindel Sep 29 '17 at 10:52
4
+50

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
1

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

enter image description here

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?

enter image description here

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 :)

  • man you did a good job. I was lost trying to find the info, but most programmer just tell you part of the response. thanks a lot man! – Chale CS Jul 19 '17 at 16:56
  • Strange that you answered your own question, although it is a verbose form of other answers. The question still unanswered is which memory do you want to use. Trying to cram all information into a integer wastes static memory, while using a large structure wastes dynamic memory. The right approach depends upon which you think memory is more valuable. – Fred Knight Jul 21 '17 at 19:09
  • @FredKnight Chess moves cost very little memory. – SmallChess Jul 22 '17 at 0:30
  • @SmallChess: If you put all the move information into an integer, you save space in storing the move, but you waste computer instructions, static memory, by "compressing" and "decompressing" the move. If you use a structure which uses integers for the from square, to square, EP, castling, double pawn move, promotion, piece to which is promoted, capture, piece captured..., you reduce the number of instructions, but increase the amount of dynamic memory. Either way you trade one memory for another. – Fred Knight Jul 23 '17 at 11:35
  • Memory issue come in transposition table, not move lists. @Fred_Knight – SmallChess Jul 23 '17 at 11:40
0

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.

  • do you have any specific URL where I can find information on how to store the generated moves? The chessprogramming.wikispaces.com is not organized, it is a huge spaghetti with good information, but difficult to find what you want. – Carlos Jul 11 '17 at 12:02
  • Stockfish converts the bitboard square to a number 0-63. Then it stores a move into an integer "to | (from << 6)." It does add special bits for castling, promotion, and capturing after the basic make_move function. I can provide a list of bitboard engines, but I don't have the energy to search which are valid. – Fred Knight Jul 15 '17 at 16:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.