Author: Russell Reagan
Date: 21:29:28 01/15/04
Go up one level in this thread
On January 15, 2004 at 11:01:46, Robert Hyatt wrote:
>I am not sure that my current
>implementation is "optimal" either. So even if I did a comparison, I'm not
>sure it would be valid.
Tim Foden showed an interesting method that was very cache friendly. Something
like this.
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]
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;
}
inline int DiagA( int rank, int file ) { return 7 + rank - file; }
inline int DiagA( Sq sq ) { return DiagA(Rank(sq), File(sq)); }
inline int DiagH( int rank, int file ) { return rank + file; }
inline int DiagH( Sq sq ) { return DiagH(Rank(sq), File(sq)); }
inline UINT64 DiagAMask( int a ) { return CStatics::s_diagAMask[a]; }
inline UINT64 DiagHMask( int h ) { return CStatics::s_diagHMask[h]; }
inline UINT64 CBoard::GenBAttacksBitmap( Sq sq ) const
{
int r = Rank(sq);
int f = File(sq);
int a = DiagA(r, f);
int h = DiagH(r, f);
BYTE movesA = PatMoves(f, m_rot[cDiagA].bytes[a & 7]);
BYTE movesH = PatMoves(f, m_rot[cDiagH].bytes[h & 7]);
UINT64 bitmap = (ExtVert(movesA) & DiagAMask(a)) |
(ExtVert(movesH) & DiagHMask(h));
return bitmap;
}
I'm not sure if this is necessarily faster (especially if you have a big cache),
but it seems like a novel approach. Maybe it will give you some new ideas, if
you hadn't seen it already.
Then there are the reversed bitboards which take advantage of the x^(x-2) trick
that Gerd uses. The only bad thing about those is that you end up having a
reversed bitboard for each direction (as opposed to three rotated bitboards), so
you have significantly more to update. One thing that I kind of like about it is
that you can generate attacks in single directions (as opposed to generating
rook attacks in all four directions), which might be useful for some things. The
rotated bitboards are pretty fast, and doing x^(x-2) four or eight times might
be slower than the lookup tables used by the rotated approach.
And of course, there are the filler routines that Gerd uses. That requires a
_whole_ new way of thinking about a chess program. It takes a person a while to
"think bitboards", and then you start from scratch again trying to figure out
how to get those fillers to work efficiently. I tried it for a while, and...I
have a new appreciation for Gerd's accomplishments :)
Basically my point is, there is probably still nontrivial room for improvement
with all of these very different approaches to bit twiddling.
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.