anyone with experience regarding bitboards?

[Zacariaz]

I was thinking about putting my limited skills to the test, writing a little chess engine. Nothing fancy, just a text ui and the basic structures and stuff. Ive allready done great deal of research and planing, and ive desided that i an gonna use the bitboard consept.
I havent been able to find as much information about the subject as i would have liked to, so if some of you guys has experience in that field, any input would be appresiated.

As a sidenote im gonna do it in c++ for starters.

Thanks

[Kevin McGuire]

For starters you might want to produce a base class for a board piece.

Code: Select all

class cBoardPiece{
  public:
  int_fast32_t Move(sMove *from, sMove *to);
  int_fast32_t GetPossibleMoveVectors(sMove *array);
};

Then get a move structure.

Code: Select all

struct sMove
{
  uint8_t x, y;
};

A board.

Code: Select all

class cBoard
{
  private:
  cBoardPiece *board;
  public:
  int_fast32_t PieceMove(sMove *from, sMove *to);
  int_fast32_t GetPossibleMoveVectors(sMove *for, sMove *array);
  cBoardPiece *GetPiece(uint_fast8_t x, uint_fast8_t y);
};

All calls form you go through cBoard not directly to Piece when moving a piece. However you may access a piece for say rendering the board by using GetPiece.


The functions (below) are essentially the same, except the board will negotiate the call instead of you making call to GetPiece.

int_fast32_t GetPossibleMoveVectors(sMove *array);
int_fast32_t GetPossibleMoveVectors(sMove *for, sMove *array);


The importance of these are for the AI. The artificial intelligence needs to have a array presented of all possible moves for this board piece. What you do is build a stack of all pieces and all their possible moves form the current board state. Then create a new board for each move as you transverse the stack -- making a whole bunch of boards.. Then do the exact same method for each of these boards. You might want a depth limitation here to prevent it from running to infinity.

What happens is when a new instance of cBoard is created for each board the AI can apply moves to create a new board state. This allows the board to do the checking on captures and such things.. or whatever you might like.

Also what happens is for each board instance created the turn is given to the other side (which would be you), but the AI moves for you and thus creates a whole bunch more boards.. then from these boards it takes a turn.

The AI might eliminate some boards if it loses too many pieces or something then again you might not if there is no significant performance impact by creating this couple thousand or ten thousand boards during the AI's thinking stage.

In the end the AI picks on of the best boards it likes, from there you either stored or can transverse back to the original move that started towards this board it liked and make the AI make a call to cBoard to make this move. PieceMove

Then AI only has minimal care for what type of piece something is. I say minimal because it has to care for the king and some other pieces possibly.. I dunno - not a chess master. Never the less it's main job is calculating all possible solutions and picking the one it likes by making a decision on if it loses the king, queen, ... such and such and what not.

You would most likely want to make the pieces with:

class cBoardPieceRook : public cBoardPiece;


And extend the board in the same way.

[Zacariaz]

At first the plan it just to get a board up and running, with of course a move function, possible moves, and so on. I wont be thinking about any AI stuff for now all though the goal is to have my two processor core battle each other. But thats not important right now.

You use the int_fast32_t, and that confuses me, as the whole idea of the bitboards, as far as i know, is to you 64 integers, bitsets or whatever, to represent the position of the pieces. Maybe there is something that i dont get here?

anyhow, thank you for the answer.

[Kevin McGuire]

I used int_fast32_t so that when compiling on a platform such as a 80386 it will use a register thirty-two bits in size, but hopefully if done right when compiling on a platform with registers larger than thirty-two bit it will use those thirty-two bit registers, unless a thirty-two bit operation can be performed faster in the larger register then it will use the larger one.

There are a bunch of types in <stdint.h> part of the Standard C Library (at least 2.5 which I have currently installed) with GCC.

[Brendan]

Hi,

You use the int_fast32_t, and that confuses me, as the whole idea of the bitboards, as far as i know, is to you 64 integers, bitsets or whatever, to represent the position of the pieces. Maybe there is something that i dont get here?

Well, the benefit of using bitboards confuses me...

A bit can only hold a 1 or a 0. This means you'd end up with a 64-bit bitfield for each piece - a maximum of 128 bytes per board, where you need something else to determine if the piece is still on the board or not. In this case you'd need to do a lot of "is this piece dead" conditional branches everywhere.

Using a 3-bit Y position and 3-bit X position only costs 1 byte per piece (or 16 bytes per board) and one of the other 2 bits in the byte can be used to determine if the piece is dead or not. This means you can check if the piece is at (X, Y) and if it's alive with a single conditional branch - i.e. "if( piece == (y << 3) | x ) { then piece is at X, Y and it is still alive }".

The only benefit I can see for bitfields is that you can OR them together and do one test to see if any piece in a group is at a location. This would be good for something like Othello/Reversi where all pieces are the same, but it'd be mostly useless for something like chess where there's a huge difference between a king and a prawn.

To compare approaches, consider a routine to find out what piece is at X, Y. For bitfields you'd need something like:

Code: Select all

Input
   edx:eax = bit mask for the encoded (X, Y) position we're interested in

Output
   ecx = piece number at this position (32 if the position is empty)

getPiece:
     xor ecx,ecx
.nextPiece:
     bt [is_it_alive_bitfield],ecx
     je .skip
     test [position_bitfield_table + ecx * 8], eax
     jne .done
     test [position_bitfield_table + ecx * 8 + 4], edx
     jne .done
.skip:
     inc ecx
     cmp ecx,32
     jb .nextPiece
.done:
     ret

The equivelent code for the one byte encoding would be:

Code: Select all

Input
   al = the encoded (X, Y) position we're interested in

Output
   esi = piece number at this position (32 if the position is empty)

getPiece:
     mov ecx,position_byte_table
.nextPiece:
     cmp [ecx],al
     je .done
     inc ecx
     cmp ecx,position_byte_table+32
     jb .nextPiece
.done:
     sub ecx,position_byte_table
     ret

The difference is that the first option has up to 48 conditional branches and the data being read uses 4 cache lines (and may cause 4 cache misses). The second option has up to 16 conditional branches and all the data fits in a single cache line. Of course you'd probably want to unroll these loops to get rid of instruction dependancies, but hopefully you see what I mean...


Cheers,

Brendan

[Zacariaz]

Of course theres pros and cons to the concept, but i believe that it will be the right aproach, especially considering that im running a 64 bit cpu.

I have no intentions of having a 64 bit vars, bitsets or simular for every piece. Ill have one for any type of piece, split up in colors, e.g. 12 in total.

Determining if a piece is still in play, is only a question of clearing bit when pieces are taken by the opponent.

x/y pisitioning is neither nessacery nor complicated.

example:

Code: Select all

+--+--+--+
|b6|b7|b8|
+--+--+--+
|b3|b4|b5|
+--+--+--+
|b0|b1|b2|
+--+--+--+

x = bit_number % 3
y = floor(bit_number / 3)

this should be right, and im sure that theres load of other ways, this was the only one i could think of right now.

granted, bitboards take up more space, and the code might seem a little more complicated, but there are definently pros.

did a little googling too:
http://en.wikipedia.org/wiki/Bitboard
http://www.answers.com/topic/bitboard

[Kevin McGuire]

I read about the bit board in one of the links you posted. Yes, apparently it would be quite nice to use and maybe very simple compared to something else.

I also noticed it said each piece get it's own bit board which is where you most likely confused Brendan, and especially me.

It definitely is a much higher performance method. Good Luck, and let us know how you do it too.

[Zacariaz]

I also noticed it said each piece get it's own bit board which is where you most likely confused Brendan, and especially me.

Maybe you should try and read it again?

There are twelve types of pieces, and each type gets its own bitboard. Black pawns get a board, white pawns, etc. Together these twelve boards can represent a position.

There are twelve types of pieces, and each type gets its own bitboard. Black pawns get a board, white pawns, etc. Together these twelve boards can represent a position.

(you might notice that the quotes is exactly the same except for the source, seems like osmeone has coppied someone )

Anyway, i do agree that it is worth considering giving each individual piece a board.

12 * 8 Byte = 96 Bytes
32 * 8 Byte = 256 Bytes

As you see there is some difference, but still, 256 bytes when you have maybe a GB to play around with...

What im most concerned about is this:

If you have a bitboard for every type of piece, you would only have to OR 6 boards to get fx. the position of all the white pieces, however if you have a board for every piece that number is up to 16! That is 5 cycles vs. 15!

[Kevin McGuire]

I am sorry. I meant each piece type.
Let me know when I do that. It will make me proof read my postings much better.

[Zacariaz]

I really have trouble just figuring out a basic structure and initilisation of the bit board, lack of emagination i guess.

Heres what ive thought about so far:

Code: Select all

class T {
    enum {P, B, N, R, Q, K}; // just for the convinience of it.
    std::bitset<64> White[6], Black[6];
public:
  T() {
    for(int i = 1; i < 64; i += 8)
      White[P][i] = 1;
    for(int i = 6; i < 64; i += 8)
      Black[P][i] = 1;
    White[R][0] = 1;
    White[R][56] = 1;
    Black[R][7] = 1;
    Black[R][63] = 1;
    White[N][8] = 1;
    White[N][48] = 1;
    Black[N][15] = 1;
    Black[N][55] = 1;
    White[B][16] = 1;
    White[B][40] = 1;
    Black[B][23] = 1;
    Black[B][47] = 1;
    White[Q][24] = 1;
    Black[Q][31] = 1;
    White[K][32] = 1;
    Black[K][39] = 1;
  }
  ~T() {}
} BitBoard;

I really dont like the way this is going and other ideas will be greatly appreciated.

[Zacariaz]

Hmm, seems that no many people are interested in the subject, but ill continue posting anyway.

I had this problem with bitsets that i was unable to asing them a value greater that 32 bit directly:

Code: Select all

std::bitset<64> a, b;
a = 0xffffffff00000000ll; // doesnt work, only the 32 least significant bits are affected.
b = 0xffffffffll << 32; // same story;

So i have been forced to use long longs instead, which i dont much like, but let se how it goes. I've only just begun figuring out a proper structure, but it seems that im on the right track:

Code: Select all

class {
  enum {P, B, N, R, Q, K};
  unsigned long long White[6], Black[6];
public:
  void Init_Board() {
    White[P] = 0xff00ll;
    White[B] = 0x24ll;
    White[N] = 0x42ll;
    White[R] = 0x81ll;
    White[Q] = 0x08ll;
    White[K] = 0x10ll;
    Black[P] = 0xffll << 48;
    Black[B] = 0x24ll << 56;
    Black[N] = 0x42ll << 56;
    Black[R] = 0x81ll << 56;
    Black[Q] = 0x08ll << 56;
    Black[K] = 0x10ll << 56;
  }
  unsigned long long Get_White_Board() {
    return White[P] | White[B] | White[N] | White[R] | White[Q] | White[K];
  }
  unsigned long long Get_Black_Board() {
    return Black[P] | Black[B] | Black[N] | Black[R] | Black[Q] | Black[K];
  }
} BitBoard;

Comments anyone?

[Zacariaz]

Yet another messy function:

Code: Select all

  void Print_Board() {
    for(int i = 63; i >= 0; i--) {
      if (i % 8 == 7) std::cout << std::endl;
      if(White[P] & (1ll << i)) std::cout << " WP";
      else if(White[B] & (1ll << i)) std::cout << " WB";
      else if(White[N] & (1ll << i)) std::cout << " WN";
      else if(White[R] & (1ll << i)) std::cout << " WR";
      else if(White[Q] & (1ll << i)) std::cout << " WQ";
      else if(White[K] & (1ll << i)) std::cout << " WK";
      else if(Black[P] & (1ll << i)) std::cout << " BP";
      else if(Black[B] & (1ll << i)) std::cout << " BB";
      else if(Black[N] & (1ll << i)) std::cout << " BN";
      else if(Black[R] & (1ll << i)) std::cout << " BR";
      else if(Black[Q] & (1ll << i)) std::cout << " BQ";
      else if(Black[K] & (1ll << i)) std::cout << " BK";
      else std::cout << " --";
      if (i % 8 == 0) std::cout << std::endl;
    }
  }

Just to check that the board is initialized right and all, but if anyone can think of a better way of doing this, i am listening cause this is messy.
Otherwise it only has one problem, its mirrored.