Decision concerning board representation.

[Gerd Isenberg]

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 ...

The point is an array with const indices may be treated as homogeneous struct of elements of the same type, but not vice versa. For an example with struct fields and switch/cases rather than indices, see Beowulf.

I like Evert's dense approach to have a struct of two arrays, one for six piece-type- and one for the two color bitboards. In cpw, I have proposed pieceBB[8] with appropriate combined (anonymous) enum for the same purpose:

Code: Select all

enum enumPieceColorOrType  {
   eWhite, // 0
   eBlack, // 1
   ePawn,  // 2
   eKnight,// 3 
   eBishop,// 4 
   eRook,  // 5
   eQueen, // 6
   eKing   // 7
};

Evert's disjoint color/piece-type enum index is more stringent, and it is probably best to define disjoint types for piece color, piece type and piece code with appropriate enum converters and type-safe interfaces. But I like arrays sized power of two, with following piece encoding (pppc) intended, where if (piece != empty) piece-code div 2 (piece >> 1) as well as piece-code mod 2 (piece & 1) may act as index of pieceBB[8]:

Code: Select all

enum enumPieceCode  {
   ePCEmpty = 0,
   ePCwhitePawn   = 2 * ePawn   + eWhite, // 4
   ePCblackPawn   = 2 * ePawn   + eBlack, // 5
   ePCwhiteKnight = 2 * eKnight + eWhite, // 6
   ePCblackKnight = 2 * eKnight + eBlack, // 7
   ePCwhiteBishop = 2 * eBishop + eWhite, // 8
   ePCblackBishop = 2 * eBishop + eBlack, // 9
   ePCwhiteRook   = 2 * eRook   + eWhite, // 10
   ePCblackRook   = 2 * eRook   + eBlack, // 11
   ePCwhiteQueen  = 2 * eQueen  + eWhite, // 12
   ePCblackQueen  = 2 * eQueen  + eBlack, // 13
   ePCwhiteKing   = 2 * eKing   + eWhite, // 14
   ePCblackKing   = 2 * eKing   + eBlack  // 15
};

[OneTrickPony]

Btw, do you also keep square to piece array in a position ?
It just occurred to me that if I have a move like e2e4 I need to know what is on e2 to remove it from correct bitboard and also I need to know what was on e4 to remove it from corresponding bitboard as well. I can iterate over all bitboards bitscanning them but that sounds suboptimal.

Solutions I see are either:
a)square to piece array (like char[64])
b)keeping all the info in a move (but then it won't fit into 16bits in the future)

Help ?

[Evert]

Btw, do you also keep square to piece array in a position ?
It just occurred to me that if I have a move like e2e4 I need to know what is on e2 to remove it from correct bitboard and also I need to know what was on e4 to remove it from corresponding bitboard as well. I can iterate over all bitboards bitscanning them but that sounds suboptimal.

Solutions I see are either:
a)square to piece array (like char[64])
b)keeping all the info in a move (but then it won't fit into 16bits in the future)

I use copy/make, I don't use (a) because it would be too costly (although that will probably not be as bad as it seems from just looking at perft data, which is what I did back when I benchmarked it; Don may have something to say about this too, since Komodo uses copy/make as well). So I do (b) and have a function

Code: Select all

int get_piece(board_t *board, int square)
{
   for (int n=PAWN; n<KING; n++)
      if (board->bbp[n] & (1ull<<square))
         return n;

   assert(board->bbp[KING] & (1ull<<square));

   return KING;
}

for when I need to guery the piece-type on the board. This is really only for capture victims though, since I know I'm dealing with a rook (say) when I'm generating rook moves.

This does mean that my move type is 32 bits rather than 16 bits, but that's ok. You can make good use of the extra bits to store more information there (and probably should if you're using 32 bits anyway, otherwise it's just wasted space). As always, it's a trade-off between storing stuff and (re)calculating it on the fly...

[Gerd Isenberg]

Btw, do you also keep square to piece array in a position ?
It just occurred to me that if I have a move like e2e4 I need to know what is on e2 to remove it from correct bitboard and also I need to know what was on e4 to remove it from corresponding bitboard as well. I can iterate over all bitboards bitscanning them but that sounds suboptimal.

Solutions I see are either:
a)square to piece array (like char[64])
b)keeping all the info in a move (but then it won't fit into 16bits in the future)

Help ?

Yep, it is intended to have a redundant but common board[64] array of piece-codes and to use those div/mod 2 to index the bitboard[8] array, i.e. in make and unmake. In my latest (suspended) copy/make attempt alá DirGolem color flipper (only white to move), I only use one quad-bitboard, and "extended" 32-bit moves including moving and captured piece, still storing only 16-bits kind/from/to in the TT.

[hgm]

To do captures efficiently I store the piece number rather than the piece type in the board[64] array. This number can then be used directly to index the piece list (to mark the captured piece as absent), where you can also find the type (if needed). I hardly ever use the type itself, however; the piece list contains type-dependent data such as piece value (or pointers to it, such as PST or Zobrist tables) directly.

[PK]

I use two-dimensional array unsigned long long [2][6] and int[64] for easy testing of a piece on a given square. twice I have tried to combine this representation with piece lists, and twice I failed. once it was just more complexity for no speed gain, the second time implementing piece lists broke move ordering, losing 10-15 Elo (out of 2600+).

understanding the reason came to me as a minor revelation. no matter how sophisticated move ordering algorithm You will use, in case of equal values the order of generating moves acts as a tie breaker. piece list, assuming no exchanges, always starts with the same piece of a given kind, irrespectively of its current position. scanning bitboards gives far more control over it.

in fact, Crafty uses *only* bitscan order for ordering of non-captures, but it uses different bitscan functions for generating white and black moves, so that it prefers moving forward rather than backwards. I switched to some variation of this idea after piece list disaster.

[lucasart]

in fact, Crafty uses *only* bitscan order for ordering of non-captures, but it uses different bitscan functions for generating white and black moves, so that it prefers moving forward rather than backwards. I switched to some variation of this idea after piece list disaster.

Crafty does not use a history table ?

[hgm]

Indeed. Bob claimed that Fruit also became stronger when he took out the history stuff.

[Evert]

Crafty does not use a history table ?

I haven't been able to make history work (in the traditional sense) in Jazz either. I tried enabling it again just the other day and it was a clear loss.

I do have Ed Schroeder's "history reduction" stuff though, which does seem to help a bit, but I'll be testing that again soonish too.

Leonidas does use a fairly standard history move ordering and it measured as an improvement there. Clearly this is all very engine specific.

I think Bob made a reference to trying out different forms of history in Crafty again recently, don't know what's come of that. Don also mentioned that it was a bit tricky to get to work in Komodo (or maybe that's just my interpretation of what he said), but they found a way to make it work.

[lucasart]

Indeed. Bob claimed that Fruit also became stronger when he took out the history stuff.

Then I have some serious doubts about that claim. Removing history from Fruit also means removing history pruning.

In my experience a good history table is very useful. And there are several for several reasons:

- move ordering of quiet moves is important. it's not just a binary problem of putting the best first and anything else after, for which perhaps killers would be partially sufficient.

- move ordering of quiet moves is even more important that with LMR you reduce quiet moves more as they have lower and lower history scores.