Author: Roberto Waldteufel
Date: 20:19:09 10/25/98
Go up one level in this thread
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....:-)
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.