Decision concerning board representation.

[OneTrickPony]

So I am coding chess (in C)
First problem I encountered is about board representation. I am going for bitboards. I have two choices how to keep bit boards in my position struct:

a)as separate fields (one int64 for every bit board)
b)as 2 dimensional array (say [2][6] for pieces bitboards)

It's difficult to predict for me (not having any experience in chess programming) what will be more convenient.
I plan to go for copy make (to avoid any trouble with backtracking moves), that makes a) preferable because copy will be just one memcpy (while copying arrays requires deep copy as only pointers are stored in a struct) or even 0 (as I can just pass whole struct by value). On the other hand I may need to iterate and/or find corresponding bitboards (say bitboard for a piece type). It might require some ugly hacks, especially iterating over all bitboards.

Any advice for a novice here ?

[Steve Maughan]

I have both. The beauty of C is you can have a single piece list which is viewed either as board->pieces[color][type] or board->piecelist[piecetype]. Take a look at my "board.cpp" and "defs.h" files at Chess Programming.

Steve

[kbhearn]

two dimensional arrays in C are a bit of a mess. declared as a fixed length array variable the compiler will fix them for you into a 1d array. allocated dynamicly you'd need to do multiple allocations (an array of arrays). and the two ways of creating a 2d array are not interchangeable unlike 1d arrays. Consequently I'd recommend sticking with a 1d array and writing an inline helper function that takes color and piece and returns an array index if you want it to look prettier.

[AlvaroBegue]

Similarly to what's proposed here, I use a 1D array and my pieces are encoded like this:

Code: Select all

enum Color {White, Black};

enum Piece {
  Pawn, WhitePawn = Pawn, BlackPawn,
  Knight, WhiteKnight = Knight, BlackKnight,
  Bishop, WhiteBishop = Bishop, BlackBishop,
  Rook, WhiteRook = Rook, BlackRook,
  Queen, WhiteQueen = Queen, BlackQueen,
  King, WhiteKing = King, BlackKing,
  Empty, NPieces = Empty
};

Now I can access my 1D array as bb[BlackBishop] or bb[Black + Bishop], or bb[enemy + Bishop]. I am happy with that choice.

[lucasart]

I have both. The beauty of C is you can have a single piece list which is viewed either as board->pieces[color][type] or board->piecelist[piecetype]. Take a look at my "board.cpp" and "defs.h" files at Chess Programming.

Steve

This representation is redundant, which is error prone (and potentially inefficient though negligibly so). How do you ensure that the board invariant are always respected ? In DiscoCheck, I simply use something like:

Code: Select all

uint64_t by_color[2], by_piece[6];

For example black knights are given by something like

Code: Select all

by_color[BLACK] & by_piece[KNIGHT]

obviously you wrap that into (inlined) functions to access all you need by staying high level.

Another advice I can give is to write two functions:
- set_square(): put a given piece of a given color on a given square. assert() that the square is empty first, that the piece, square and color arguments are correct.
- clear_square(): empties a given square. assert() that the square was indeed occupied.

These functions should modify all there is to modify: the bitboard representation (the 2 arrays mentionned above), as well as the zobrist key, PSQT sums and whatever else you may need to compute dynamically.

No other code should *ever* touch the board representation directly. If these functions are correct and maintain the board invariants, you know that anything that screws up the board is going to trigger an assert() squeel in these two functions. And you know you're not going to screw things up because you basically cannot, so long as you never manipulate the board structure directly. Use some accessors for whatever you may need to access.

This abstraction is fundamental and has saved me countless hours of debugging pain and tears. You can trust my advice on this.

As an optimisation you can use a stack and put some dynamically computed on the stack. You'll need a stack for undo information anyway. This means you only really do calculation when you make a move, and undo_move() simply shifts the stack pointer. That was a nice speed gain at the time when I was very competitive about my perft() raw speed. At the scale of a polished engine with lots of other things to calculate, these meager optimizations are drops in the ocean though.

[OneTrickPony]

Thanks, this is helpful.
Both of you didn't address one of my questions though: is it better to have arrays (for example like the ones you presented) or just fields, like this:

typedef struct {
BitBoard kBB;
BitBoard qBB;
...
...
BitBoard pBB;
BitBoard Black;
BitBoard White;
} Position;

(implementing your idea)
Now I don't have an array which means I can write: newposition = oldposition to clone a game state while if I have:

typedef struct{
BitBoard by_color[2];
BitBoard by_piece[6];
} Position

I would have to construct new struct by first allocating:

newby_color[6];
newby_piece[2];
Then do:
newposition = oldposition;
newposition.by_color = newby_color
newposition.by_piece = newby_piece;
memcpy(newposition.by_color, old.position_bycolor, 2*sizeof(BitBoard));
memcpy(newposition.by_piece, old.piece_bypiece, 6*sizeof(BitBoard));

That looks like more expensive than previous example.

[Evert]

Both of you didn't address one of my questions though: is it better to have arrays (for example like the ones you presented) or just fields,

Doesn't matter, it's personal preference. I use arrays though.
A description of what I use in Jazz is here: http://www.eglebbk.dds.nl/program/chess-design.html , but it comes down to

Code: Select all

struct board_t {
   bitboard_t bbp[6]; /* Piece bitboards */
   bitboard_t bbc[2]; /* Colour bitboards */
};

so

Code: Select all

black_queens = board->bbp[QUEEN] & board->bbc[BLACK];

Now I don't have an array which means I can write: newposition = oldposition to clone a game state while if I have:

typedef struct{
BitBoard by_color[2];
BitBoard by_piece[6];
} Position

I would have to construct new struct by first allocating:

newby_color[6];
newby_piece[2];
Then do:
newposition = oldposition;
newposition.by_color = newby_color
newposition.by_piece = newby_piece;
memcpy(newposition.by_color, old.position_bycolor, 2*sizeof(BitBoard));
memcpy(newposition.by_piece, old.piece_bypiece, 6*sizeof(BitBoard));

That looks like more expensive than previous example.

I don't really understand what you're trying to say, to be honest. In Jazz I do

Code: Select all

memcpy(&new_board, &old_board, sizeof(board_t));

which works fine and I don't see how doing it any differently would make any difference (whatever you do, you need to copy sizeof(board_t) bytes, and you're unlikely to do so more efficiently by hand than by using memcpy).

[OneTrickPony]

Ignore me. I had some major brain malfunction. I should really actually sleep sometimes.
Thanks for the answers all, this is very helpful

[lucasart]

is it better to have arrays or just fields

You *must* use arrays. Otherwise how do you plan to make piece and/or color loops efficiently ?

But, if you think it's useful (I don't), you can have fields too, using an "union". So you can use fields if/when you want to use fields.

[OneTrickPony]

I was just brain dead (as Evert Glebbeek's post made me realize).
Fortunately I was lucky to make this thread as I will use your idea for representation. Thanks.