Removing the need for separates evaluation/generation functs

[mathmoi]

Hi,

After I red a post on CCC by Anthony, I thought about a solution to the recurent need of different functions for the white and black pieces.

Thoses doubled functions are needed to avoid the overhead of branching where the code need to be different depending on witch side is on move.

As an example we can see something like this in the move generation function for the pawns :

Code: Select all

void genPawnsMoves()
{
  // stuff

  BitBoard toSquares;
  if (sideToMove == white)
  {
    toSquares <<= 8;
  } 
  else
  {
    toSquares >>= 8;
  }

  // stuff
}


In order to avoid this engine's programmer often (tell me if i'm wrong) use two differents function for the withe and black on move:

Code: Select all

void genWhitePawnsMoves()
{
  // stuff

  BitBoard toSquares;
  toSquares <<= 8;

  // stuff
}

void genBlackPawnsMoves()
{
  // stuff

  BitBoard toSquares;
  toSquares <<= 8;

  // stuff
}


This will make the engine more efficient since all the test about the colors are removed and raplaced by a single test in the calling function. However this duplication of code has some well know draw backs. Principaly, we have to make any change to the function two times, this make such code prone to errors.

This is essentially what Anthony was trying to avoid (I think). While reading his post it appear to me that the first function could be made as a template like this :

Code: Select all

template <int color>
void genPawnsMoves()
{
  // stuff

  BitBoard toSquares;
  if (color == white)
  {
    toSquares <<= 8;
  } 
  else
  {
    toSquares >>= 8;
  }

  // stuff
}


then the calling code would be like this :

Code: Select all

if (sideToMove == white)
{
  genPawnsMoves<WHITE>();
}
else
{
  genPawnsMoves<BLACK>();
}


This way we have the best of both worlds. We only have one function to maintain and the conditional branching are eliminated by compiler optimisations because he know at compile time the vallue of sideToMove. The compiler actually compile two function.

I don't think this solution has any drawbacks/overhead, but I never tried it. What is your opinion ?

Mathieu Pag

[Alvaro Begue]

I have tried this type of thing, and it works really well. You can even be a little more sophisticated and define a class ColorTraits that defines many common values for one side or the other. Using template specialization, you can make it as neat as this (I provide a sample complete program so you can see it working):

Code: Select all

#include <iostream>

enum Piece {wp,wn,wb,wr,wq,wk,bp,bn,bb,br,bq,bk};

enum Color {White,Black};

template <Color color> struct ColorTraits{};

template<> struct ColorTraits<White>{
  static const Color Enemy=Black;
  static const int pawn_advance=+16;
  static const Piece p=wp;
  static const Piece k=wk;
  //...
};

template<> struct ColorTraits<Black>{
  static const Color Enemy=White;
  static const int pawn_advance=-16;
  static const Piece p=bp;
  static const Piece k=bk;
  //...
};

template <Color C> void generate_moves(void){
  typedef ColorTraits<C> CT;
  std::cout << CT::pawn_advance << std::endl;
}

int main(){
  generate_moves<White>();
}



[Alvaro Begue]

My example didn't include any functions as part of ColorTraits, but you can easily define something like `BitBoard AdvancePawns(BitBoard)' that will do the shifting of 8 bits to the appropriate side. Then your code would just call that function of CT. I can code it if that wasn't clear enough.

[H.G.Muller]

Isn't it more logical to consider the white and black pawns simply two distinct kind of pieces (making the fact that black only possesses pawns that move like black pawns a coincidental conseqence of the initial board setup)? The problem is then generalized to what to do when a certain piece type is missing for one of the opponents (or altogether)?

I have no experience with bitboard move generation, but it seems silly (and inefficient) to generate the bit patterns for knight moves if it is known that there are no knights on the board. So I assume that in such a case the particular piece of code should be skipped, just as one can skip the code for white-pawn moves when generating moves for black. Something similar to compacting the piece list of my 0x88 move generator by removing all the captured pieces at the game level.

[mathmoi]

My example didn't include any functions as part of ColorTraits, but you can easily define something like `BitBoard AdvancePawns(BitBoard)' that will do the shifting of 8 bits to the appropriate side. Then your code would just call that function of CT. I can code it if that wasn't clear enough.

Hi Alvaro,

That's clear, thank you. I like the idea of a ColorTraits template, this will make the functions using it even more cleaner.

Can you confirm my assuption that there is no overhead ?

Mathieu Pag

[Alvaro Begue]

Can you confirm my assuption that there is no overhead ?

I am a suspicious type of guy, so I would check the assembly output of the compiler, but I am 99% sure that there is no overhead, since all the work is done at compile time.

[Ilari Pihlajisto]

At first my engine had two functions for almost everything, but later I managed to get rid of all color-dependent code. The nps speed dropped about 8% but that was far outweighed by the code being easy to maintain.

I'm using bitboards and I have the move masks in arrays like knightMoves[2][64] which can be used like knightMoves[WHITE][E4] (WHITE = 0 and BLACK = 1).

The functions like "search" have the argument "color", which is either 0 (WHITE) or 1 (BLACK). So I can call "inCheck(color)" to find out if the side to move is in check, or "inCheck(color ^ 1)" to see if the opponent is in check. I never have to do checks like "if (color == WHITE)".

[Gerd Isenberg]

Isn't it more logical to consider the white and black pawns simply two distinct kind of pieces (making the fact that black only possesses pawns that move like black pawns a coincidental conseqence of the initial board setup)? The problem is then generalized to what to do when a certain piece type is missing for one of the opponents (or altogether)?

I have no experience with bitboard move generation, but it seems silly (and inefficient) to generate the bit patterns for knight moves if it is known that there are no knights on the board. So I assume that in such a case the particular piece of code should be skipped, just as one can skip the code for white-pawn moves when generating moves for black. Something similar to compacting the piece list of my 0x88 move generator by removing all the captured pieces at the game level.

Good idea - you have the switch by piece type anyway.

The enlarged value range with two redundant zero-holes is probably not that worse. With bitboards, to do it that generally and stringent, you probably have two disjoint allways zero bitboards for white "black" pawns and black "white" pawns - which looks like some waste of space, specially if you have ply-stacks of those bitboards.

So trying to save some memory ressources, implies color dependent code for pawns. Whether written separately or with compilers help using
integer template parameter where color is a compile time parameter.

All tables (also swich tables with indirect jump targets) indexed by Piece or ColoredPiece are a bit larger, but i like 8 or 16 entry alignment for piece tables, instead of arrays of 7 or 14.

You may have some conditional jumps in your code:

Code: Select all

if ( whitePawns[color] ) ....
if ( blackPawns[color] ) ....


which are never taken with the appropriate color - so most likely alternating taken-not taken pattern which is rather simple for todays branch prediction heuristics.

Your idea is worth to think about...

[Gerd Isenberg]

At first my engine had two functions for almost everything, but later I managed to get rid of all color-dependent code. The nps speed dropped about 8% but that was far outweighed by the code being easy to maintain.

I'm using bitboards and I have the move masks in arrays like knightMoves[2][64] which can be used like knightMoves[WHITE][E4] (WHITE = 0 and BLACK = 1)..

hmm, if you don't alias your knightMoves array, why using an redundant index?

[Ilari Pihlajisto]

Oh, I posted that in haste. I should've used pawnMoves as the example, I don't really have a two-dimensional knightMoves array.