Author: Robert Hyatt
Date: 13:07:16 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. What about using a 5-bit mask then. You don't need the two endpoint bits anyway as you attack those squares whether they are occupied or not. I use 6 bit myself as squeezing out the square the piece is on is not convenient... > >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: > >[D]8/8/1p1pQ1p1/8/8/8/8/8 w - - 0 1 > >I will have to take a look at >MovesOnLine[PosOfTheQueen][IndexOfTheOccupancyOfTheLine] > >and it will look like this (black pawns are bits sets to 1): >[D]8/8/3pppp1/8/8/8/8/8 w - - 0 1 > >This bitboard could be compressed with 7 others bitboards that are translations >of this one and we get this: > >[D]3pppp1/3pppp1/3pppp1/3pppp1/3pppp1/3pppp1/3pppp1/3pppp1 w - - 0 1 > >now if I want to generate the moves for the withe queen in the first diagram I >will have to access the bitboard like this > >MovesOnLine[ColumnOfTheQueen][IndexOfTheOccupancyOfTheLine] & >MaskOfRows[RowOfTheQueen] > >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 ? > >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.