Author: Russell Reagan
Date: 14:23:37 01/13/03
Go up one level in this thread
On January 13, 2003 at 16:50:57, Bas Hamstra wrote:
>Well in fact it is interesting. But I have no experience with it. From what I
>understand the X & (X-2) does a sort of floodfill left-up so you keep a reversed
>bitboard to get a floodfill right-down. I have to experiment with it to be sure
>what it does... Back in 2 minutes, after which I will give you advice for the
>next 2 years...
I actually used this little trick (well, one of them) to write a bitboard
program that made no use of a bit index extraction function (like FirstOne() or
LastOne() in Crafty, or bsf/bsr, etc.). I modeled the moves as something like:
struct Move {
Bitboard * SideBoard;
Bitboard * OponnentBoard;
Bitboard * MiscBoard;
Bitboard SideMask; // used to update the piece for side to move
Bitboard OpponentMask; // used to update opponent's piece (eg. capture)
Bitboard MiscMask; // used to update other (eg. promotion, castling)
};
Then I just set the pointers to which bitboards to modify, and then created
masks that I would XOR onto the appropriate bitboard. Using the x & -x trick
(which returns a bitboard with only it's least significant bit set) I was able
to create the masks easily. What I liked about it was that make/unmake were
basically the same function, since XOR will do the making and unmaking. So
something like:
void MakeMove (Move * m) {
m->SideBoard ^= m->SideMask;
m->OpponentBoard ^= m->OpponentMask;
m->MiscBoard ^= m->MiscMask;
// ...
};
It wasn't terribly fast though. It got about 70 knps to maybe 100 knps, compared
to Crafty at 300-500knps. I don't know that the lack of speed was due to this
however. I used the KoggeStone attack generation routines written in pure C, and
that surely was not very fast on 32-bit hardware. So this method might be able
to work if you wanted to use bitboards without the need for a bit index
extraction routine. But, beware that it makes implementing a hashing scheme
difficult, since you don't have 'from' and 'to' squares to work with. But it was
interesting to write at least.
Russell
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.