Author: Gerd Isenberg
Date: 15:09:26 05/06/04
Go up one level in this thread
On May 06, 2004 at 13:00:06, Mathieu Pagé wrote:
>Hi,
>
> Actualy my engine use pre-calculated bitboards to generate the moves. and I was
>asking myself if compressing them, in order to keep them in cache would make my
>move generator faster. I tought about two techniques to compress them.
>
>1. Use a 7 bits mask as a representation of the occupancy of the line as we
>always know that the position where the piece that we want to move is occupied.
>I already use this and it cut the space used by the index by a factor of two.
>I'm sure you were all aware of this trick.
For precalculated move lists to save bitscans rather than attack bitboards the
7bit trick is fine and suggested by Dann Corbit some time ago. Eg. something
like this:
struct MovesOnOneRay
{
int nMoves;
int nPotCapures;
MOVE moves[7]; // or better 8 for alignment reasons
MOVE potCaptures[2]; // requires an additional target check
};
MovesOnOneRay movesOnRank[64][128]; // [square][compressedOccupiedState]
...
>
>2. Use a set of mask in order to store more than one pre-calculated bitboard in
>a 64 bits bitboard since we know that all the bits sets are always on a same
>line/col/diag. as an exemple: If I want to generates the moves on a row by the
>white queen in the folowing diagram:
>
<snip>
>using this "algorithm" I think I can cut the space of the pre-calculated
>bitboard under 25 Ko and probably keep it in cache.
>
>My question for you is: Do you think the gain from keeping this in memory will
>be worth extra computation ?
>
Always this fight between computation versus huge or (cascaded) lookup.
With today's super pipelined processors with out of order execution and a lot of
heuristics and huge caches and prefetchers it's hard to say. It depends for
instance how much other memory traffic inside your program pullutes your cache,
and whether the additional register computation "hides" some memory latency.
And it may change from time to time, as you change your program.
Cheers,
Gerd
>Hope my english will not give you headach.
>
>Mathieu P.
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.