Author: Robert Hyatt
Date: 06:20:05 10/26/98
Go up one level in this thread
On October 25, 1998 at 23:19:09, Roberto Waldteufel wrote: > >On October 25, 1998 at 19:28:54, Robert Hyatt wrote: > >>On October 25, 1998 at 19:16:05, Roberto Waldteufel wrote: >> >>>Hi all, >>> >>>Has anyone tried this, or thought of trying this before? >>> >>>The main drawback of 32-bit CPU's for bitboards is that each time you need to >>>step through the bits in a bitboard you have to step through two 32-bit values, >>>since that is all that will fit in a register. I have an idea that partially >>>overcomes this problem. It is based on the observation that many of the >>>bitboards used in move generation are mono-chromatic, by which I mean that the >>>1's are either all light squares or all dark squares. For example, bishop moves, >>>pawn captures and double pawn moves are always to a square of the same colour as >>>the origin square, and knight moves and single pawn moves are always to a square >>>of opposite colour to the origin square. I therefore propose a bitboard >>>structure consisting of two 32-bit unsigned integers, one for the light squares >>>and the other for the dark squares. If rotated bitboards are to be used, then >>>the bits could be aligned for one set of diagonals, and a second pair of >>>bitboards aligned for the other diagonals (ranks and files would be done same as >>>before, only diagonals would need reorganising). Then when polling the bits of >>>an attack map to find the moves for minor pieces, only one 32-bit bitboard is >>>needed to hold all the destination squares, and generating pawn captures by >>>means of shifting and logical ANDing can easily be divided into light-square >>>captures and dark-square captures. I have not yet tried this, but I see no >>>reason why it should not work. Of course, it does nothing to help rook-moves >>>(including rook-type queen moves) or king moves, but these could be generated >>>with no more work than is needed in a normal a1-h1,a2-b2,......a8-h8 ordering of >>>the squares. Nevertheless, if some of the generation can be compressed to 32-bit >>>operations instead of 64, it must surely help to some extent. Any comments? >>> >>>Roberto >> >> >> >>it's interesting to think about this... but it does break the "rotated bitmap" >>idea which is to get all squares along a rank/file/diagonal into adjacent bits. >>This would mean we'd need a few more bitmaps to work around this... >> >>certainly worth trying, however... > >I don't see how it breaks the rotated bitboards. You store all the light-squared >diagonals in two distinct 32-bit bitboards, one for each direction of diagonal, >and all the dark-squared diagonals in two similar 32-bit bitboards exactly like >you do at present, except instead if interleaving the light- and dark-squared >diagonals, you just have to keep them separate (4 x 32 bits instead of 2 x 64 >bits). The rank and file bitmaps can stay as they are. That way, you still have >all the bits on any one diagonal adjacent in the appropriate 32-bit bitmap. This >would of course require that you first test the origin or target square to see >whether it is light or dark, but thereafter you get your index from 32-bit >operations instead of 64-bit ones. Unless you are using the rotated bitmaps in >some other way I do not realise, I think this would work OK for generating the >bishop moves, diagonal queen moves and knight moves, regardles of whether you >generate based on to-square (eg MVV/LVA capture generation) or on to-square. Of >course, it is pretty pointless on your 64-bit machine, but you have 32-bit >Crafty versions as well that might benefit from splitting the diagonals into two >sets of 32 bits. I don't know if it would make a big difference or not, but I >can't see how it would interfere with your current implementation to split the >diagonals like this - you would just have to recalculate the attack arrays once >and it should work right away. Then, if all runs well, you could start trying to >speed up the access code for 32-bit versions without needing to have a different >data structure from the 64-bit Crafty. > >I think I will fool around with some of this stuff to see if I can make it work >OK. I never feel happy with an idea until I see it up and running....:-) the problem is the ranks/files.. because they won't be adjacent in such bitmaps, and the "rotated" approach depends on this being true so that you can find the state of one rank or file in 1 eight-bit "chunk"...
This page took 0.02 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.