Author: Robert Hyatt
Date: 06:23:19 10/26/98
Go up one level in this thread
On October 25, 1998 at 19:58:08, Peter Fendrich 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... > >It certainly doesn't break up my rotated bitboards. >When rotating 90 degrees, I pack the diagonals together in 8-bit chunks like >this: >h1 + b1-h7 >f1-h3 + d1-h5 >a2-g8 + a8 >a4-e8 + a6-c8 >g1-h2 + c1-h6 >and so on > >all the adjecent squares are together and it works fine for me. > >I don't try to access these 8-bit chunks - it's merely a way of visualising the >board for myself... > >//Peter I agree there. But what about the _files_ and _ranks_??? they won't be adjacent in this scheme... which is the part that will take some fiddling to make it work... BTW, the current scheme is *not* bad on 32 bit architectures, because most of what is done is AND/OR/XOR, and it simply takes two instructions no matter what. And since the current processors (pentium and on) do at least two instructions/cycle, there really isn't any overhead, except for those cases where a shift is needed... and I bet that while that is going on there are other instructions that the super-scalar units can grab to execute anyway...
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.