Author: Sune Fischer
Date: 15:08:50 07/14/03
Go up one level in this thread
On July 14, 2003 at 17:56:52, Tim Foden wrote: >On July 14, 2003 at 17:36:52, Sune Fischer wrote: > >>On July 14, 2003 at 17:15:50, Bas Hamstra wrote: >> >>>Hi Gerd, >>> >>>A while ago, in Leiden, Frans mentioned you had a trick to reduce the rotated bb >>>lookup tables by a factor 2, without further disadvantages. It had something to >>>do with the edges of the board, some "ray-states" you can ignore. I didn't >>>understand his short explanation back then. Could you explain? >>> >>>Best regards, >>>Bas. >> >>It's quite simple; the state of the attack rank (or file) doesn't depend on the >>outermost squares/bits. Those squares are attacked (or not) no matter if there >>is a piece standing there. So actually it is a factor 4 you save, because you >>need only 6 bit entries. >> >>There are other tricks you can do to compact them even more, but then more >>shifting is needed to unpack the information. >> >>I have written a sample move generator that uses this trick: >>http://www.geocities.com/ruleren/crbmg.zip >> >>-S. > >Hi Sune, > >In another (very, very, early) chess program I'm writing (very, very, slowly!) I >have a bb movegen and makemove, and incheck test, etc., that uses tables >totalling about 15.5KB. The actual sliding pieces lookup tables total about >6.5KB. > > static BYTE s_patMoves[8][256]; // 2.00K [R/F][pattern] > static UINT64 s_extendVert[256]; // 2.00K [pattern] > static UINT64 s_extendHorz[256]; // 2.00K [pattern] > > static const UINT64 s_rankMask[8]; // 0.06K [file] > static const UINT64 s_fileMask[8]; // 0.06K [rank] > static const UINT64 s_diagAMask[15]; // 0.12K [diagA] > static const UINT64 s_diagHMask[15]; // 0.12K [diagH] > >Using the 6bit instead of 8bit trick this could be reduced by another 1.5KB. >Fun eh? I thought I'd try to be a bit more cache friendly in my newest prog. :) > >It's currently only at the stage where I can do a perft, where it is about 75% >the speed of GLC, but I haven't optimised it at all really (Whereas I've been >optimising GLC for years now :)). In fect the pure movegen looks to be about >90% the speed of GLC. > >Cheers, Tim. That is very impressive, I magine the "algorithm" to unwrap it is quite complex though? I tried just saving the bit-rank and then shifting it back out, it seemed to run slower. Though this probably depends on whether or not one is already running in cache. 130 kB seemed to be the fastest for me. On thing I thought about here, is what happens to such a table, if say, only half the entries are call? Will the whole table be stuck in cache or can it "fragment" the table in the cache? It seems to me that on a sparsely populated board, one will never index those attackboards with many bits set, so although the whole table is maybe 130 kB, I bet the search doesn't effectively use more than a fraction of it, hence my question of how that will affect the cache. -S.
This page took 0.01 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.