Author: Russell Reagan
Date: 11:27:03 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. > >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. You might find this discussion interesting: http://chessprogramming.org/cccsearch/ccc.php?find_thread=306442 You could use at few as 5-bits per rank/file/diagonal, since you can ignore the ends and the square that the attacking piece resides on. It will be more cache friendly, but less CPU friendly because you will have to do some extra bit fiddling. As for whether it will be faster, it probably just depends. Using the 6-bit trick doesn't really cost anything, so it is almost surely a speedup. If you start doing more and more bit twiddling to cut down the size of your lookup tables, it becomes more and more unclear. It may be different for every bitboard program. You may have small attack tables, but for some reason that is specific to your engine only, it may not result in a speedup. The same size reduction of lookup tables in my program may result in a big speedup. So unfortunately, the answer is "try it and see". I always hated when people told me to try it and see, but when it comes to issues regarding cache (and modern processors in general), that is often the only right answer.
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.