Author: Roberto Waldteufel
Date: 15:41:28 11/02/98
Go up one level in this thread
On November 02, 1998 at 17:58:06, John Stoneham wrote: >In my program GrimReaper, I use a simple function consisting of a pre-calculated >mask value and a pre-calculated shift value (more pertinent to diagonal >rotations, but still usefull to the 90 degree rotation) to extract the 8-bit >code necessary for accessing the (again) pre-calculated attacked squares for the >given rotation (Queen/Rook or Queen/Bishop). Obviously, for unrotated >orientations, or 90 degree rotations, the masks and shifts are simple. But >diagonals are more complicated, and the use of an array of precalulated shifts >and masks for the given orentation seems necessary. Since these are calculated >before the engine is started, it seems simple to calculate the 90 degree shifts >and masks as well. Then all you need is a ((Bitboard & mask) << shift) type of >routine to get the 8-bit has value, regarless of the rotation. (More information >on my routines is available in my GrimReaper journal at >www.geocities.com/SiliconValley/Lab/4714/index.html). Does any handle this >calculation differently? Hi John, I recently ran some experiments with rotated bitboards, and I did it just as you describe. However, I think the utility of the rotated bitboards is highly dependent on your architecture. The main alternative to rotated bitboards is of course the ordinary (unrotated) bitboard, which is what I use at present, but it is still possible to generate all the diagonal and lateral attacks with logical operations and no looping. Crucial to the efficiency is the availability of a findbit() CPU instruction, which is absent on many machines. This instruction alone can make a big difference to a CPU's suitability for handling bitboards, whether rotated or not, efficiently. The other important issue is the size of the native machine word: ideally you want a 64-bit word size, like on an Alpha for example. If you use 32-bit architecture, you normally have to process your bitboards in 2 32-bit chunks. Now that is not to say that bitboards are not efficient on any 32-bit architecture, but a 64-bit machine is almost certain to be faster. That said, the other thing to think of with the Pentium CPU's is how good they are at findbit(). The intels have two very handy instructions on 486 and all Pentiums, bit scan forward and bit scan reverse, which find the first or last one-bit in a 32-bit number. All well and good, but wait until you know the execution speed of these instructions. If you are running a PII or a PPro, these instructions execute in either one or two clocks (depending on pipelining issues), which is excellent, but on all other machines (486, Pentium plain and Pentium MMX) the bit scan instructions are highly inefficient, and it would appear that you do better to avoid them. When I ran my tests I did not know this, and I was surprised to find that I could calculate attack maps for bishops more than 25% faster with an assembly routine built around the bit scan instructions than I could with rotated bitboards. You may guess I was using a PII. So for this machine, the old form of (unrotated) bitboard is better than the rotated bitboard method, but run it on an older Pentium machine and the rotated bitboards are bound to do much better because of the slow bit scans. Another thing I discovered was that I generate attack maps for queens in only very slightly more time than I would for bishops or for rooks. With rotated bitboards you have to take double the time for queens, since you have to examine all 4 directions instead of only 2. So in the light of all this, I would suggest that you stick with your rotated bitboards if you don't intend to use the PII or PPro platform, but if you do intend to use these processors, try doing it the old fashioned way and compare them. You may find, as I did, that this can beat the rotated bitboards now that bit scans are fast. Of course, it's a big decision, as it affects all sorts of program design decisions, but if you want to maximise the power of the PII/PPro box, bit scans are the key strength to tap. Hope some of this is of use to you. Good luck with Grim Reaper. Roberto
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.