Author: Gerd Isenberg
Date: 03:45:49 07/15/03
Go up one level in this thread
On July 14, 2003 at 18:20:33, Tim Foden wrote:
>On July 14, 2003 at 18:08:50, Sune Fischer wrote:
>
>>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?
>
>inline int Rank( Sq sq ) { return sq >> 3; }
>inline int File( Sq sq ) { return sq & 0x7; }
>
>inline BYTE PatMoves( int rf, int pat )
> { return CStatics::s_patMoves[rf][pat]; }
>inline UINT64 ExtVert( int pat ) { return CStatics::s_extendVert[pat]; }
>inline UINT64 ExtHorz( int pat ) { return CStatics::s_extendHorz[pat]; }
>
>inline UINT64 RankMask( int r ) { return CStatics::s_rankMask[r]; }
>inline UINT64 FileMask( int f ) { return CStatics::s_fileMask[f]; }
>
>inline UINT64 CBoard::GenRAttacksBitmap( Sq sq ) const
>{
> int r = Rank(sq);
> int f = File(sq);
> BYTE movesR = PatMoves(f, m_rot[cHorz].bytes[r]);
> BYTE movesF = PatMoves(r, m_rot[cVert].bytes[f]);
> UINT64 bitmap = (ExtVert(movesR) & RankMask(r)) |
> (ExtHorz(movesF) & FileMask(f));
> return bitmap;
>}
>
Hi Tim,
i have it - a code snippet helps a lot ;-)
A few cache friendly lookups - looks promising.
I like your m_rot[cVert].bytes[f] - much more readable than my cast monster!
>>
>>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.
>
>As I say, I haven't yet tried it in a real chess search, just in perft. I'm not
>yet at all sure whether it is worth the trouble, but I hope so. I have come to
>the stage where I have a lot of ideas that don't fit with the way GLC works, so
>over time I plan to try them out by writing a new engine.
Same for me, hammer and KoggeStone in mind.
Regards,
Gerd
>This is just the
>start. :)
>
>Cheers, Tim.
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.