Author: Tim Foden
Date: 15:20:33 07/14/03
Go up one level in this thread
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;
}
>
>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. This is just the
start. :)
Cheers, Tim.
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.