Author: Walter Faxon
Date: 14:34:03 01/26/03
Go up one level in this thread
On January 25, 2003 at 23:03:51, Matt Taylor wrote: >On January 25, 2003 at 17:54:58, David Rasmussen wrote: > >>On January 25, 2003 at 17:28:23, Russell Reagan wrote: >> >>> >>>As far as implementing a FirstOne() and PopCount(), I don't think it matters >>>about the order of the bits or what they mean. Certainly the PopCount() doesn't >>>matter, since it is just the count of the set bits, and the order doesn't matter >>>at all. FirstOne() will *usually* not matter, but it might sometimes. For >>>instance, when generating moves (like Crafty does), it calls the FirstOne() >>>function just to say, "tell me where another piece is". Crafty doesn't really >>>care where that piece is, so FirstOne() *could* return any of the indexes that a >>>piece is on (instead of the least significant bit or most significant bit) and >>>it would still work fine. Sometimes you might actually need to know the least >>>significant bit or most significant bit, so it might matter there. In general it >>>isn't going to matter though, and in general, it isn't going to affect the >>>strength of your engine unless these functions are just horribly inefficient. >>>Otherwise, maybe 1-2 elo. >> >>Of course it doesn't matter for PopCount(), that was my mistake. But it's >>certainly important very often to know where a piece is, so it is certainly a >>good idea for FirstOne() to return something that matches your indexing. And >>orientation is definitely important here. >> >>On the other hand, it would be interesting to know if one could make an even >>faster function (called SomeBit()) than a normal FirstBit() in IA-32 assembly, >>if the order of the returned bits did not matter. For movegen a function returns >>the index of such a bit and also clears it, would be useful, if it meant that it >>could be done even faster. >> >>/David > >It is a good question, but I can think of no good answer. Isolating the bit >makes it easier to index, and isolating the LSB is easiest on x86 because of bb >& -bb. Of course, the P6 family is the x86 exception here with the ability to >find MSB or LSB equally fast without needing bb & -bb. (Yay for priority >encoders!) > >For "portable" performance, the SomeBit() idea is superb. You could implement >SomeBit() in terms of whatever is most efficient for a particular architecture >-- i.e. Dr. Hyatt has pointed out many times that Cray is most efficient with >the MSB. The x86 would use LSB (no penalty on P6, better performance on all >others). > >-Matt Hi, All. In Crafty at least, there are sometimes reasons for scanning from a particular end. For example, finding the most advanced passed pawn for black requires a search from the opposite end from finding the most advanced passed pawn for white. As of version 18.10, all such side-dependent code is isolated in MOVGEN.C. (And of course, ranks must have the minor order in the bitboard for this to work: e.g., a1-h1 are contiguous bits.) So: for Crafty on any particular architecture, one would want three routines: FirstOne(), LastOne(), and say, NextOne(), using the faster/smaller/"better" of the two when it doesn't matter which way you scan (like when adding up feature-weights). -- Walter
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.