Author: Roberto Waldteufel
Date: 10:20:45 10/29/98
Go up one level in this thread
On October 29, 1998 at 08:06:37, Robert Hyatt wrote: >On October 28, 1998 at 22:38:41, Roberto Waldteufel wrote: > >>Hi all, >> >>Here is another way of mapping the diagonals for rotated bitboards, which might >>enhance the efficiency slightly for diagonal attacks. Instead of one bitboard >>for all a1-h8 oriented diagonals and one for the a8-h1 oriented diagonals, would >>it not be feasible to map the light squares twice on one bitboard and the dark >>squares twice on the other, so that on each bitboard the least significant 32 >>bits hold diagonals with one orientation and the most significant 32 bits hold >>the same squares in the other orientation. Then, given an origin square, we only >>have to AND its key with a single bitboard (instead of two), and we get the >>squares in two sets of contiguous bits, one in the top 32 bits and one in the >>lower 32 bits. Using two shifts,one mov (register to register) and one OR we can >>move these bits to form one contiguous set of bits at the least significant end. >> >>For any given source square, the occupancy of squares on the diagonals through >>that square cannot affect the attacks from that square if they are on the edge >>of the board, so there can never be more than 9 squares that could affect the >>result. Thus no square's diagonal key need have more than 9 bits set, so we can >>produce an index of at most 9 bits, ie in the range 0-1023, which we can use to >>look up the attack map in a table, thus retrieving both sets of diagonal attacks >>in one go. >> >>When making/unmaking moves, it would perhaps help again. Normally when a >>square's occupancy changes it would be necessary to xor a square's bitmask with >>each of the 4 rotated bitboards, with one bit set in each of the 4 masks for >>that square. Now, however, we find that each square has two bits set in one >>diagonal bitboard and none in the other, so the masking can be done with 3 >>operations instead of 4. >> >>In the evaluation function, it might also be handy to have all squares of the >>same colour in a 32-bit contiguous cluster to evaluate things like good/bad >>bishops or weak colour complexes. >> >>Any comments? >> >>Roberto > > >sounds doable... only issue I see is it represents info for bishops and 1/2 of >a queen, only... the rooks and other half of the queen moves isn't affected... That's right - the rank and file bitboards would stay exactly as they are, only the diagonals would be stored with a different bit-square mapping. It would not be likely to do more than shave one or two CPU instructions from the diagonal attack generation, but this code is used many, many times, so maybe a tiny saving here would be noticeable in the context of a full search. Now that I come to think of it, the bit for the source square is going to lie in the middle of the "key" bits, so you would either need 4 shifts instead of two (yuk!), or better you could allow the look-up table to have 4098 entries instead of 1024. However, 4098 is still not excessive. Also the time saved from not having to consult one of the four bitboards is going to be smaller if the 4 bitboards get loaded into cache when you access the first one, and you also would need to determine every time whether you were dealing with a light source square or a dark source square. I used a representation rather like this in a checkers program I once wrote. I didn't think of it as being a "rotated" bit-board at the time, since the diagonals are the *only* directions of relavance in checkers. There I only had one colour of squares to worry about, and ranks and files did not enter into things at all. I stored the 32 squares twice in a 64-bit bitboard with exactly the type of square-bit mapping I have described here, so I generated all the moves efficiently with shifts, AND etc. It meant that instead of 4 generation cycles for the 4 directions, I only needed 2 (forward and backward), but of course there were no tables of legal moves, since checkers does not allow sliding. But it worked in that simplified setting, and seems quite applicable for diagonal moves in chess. ___________________________________________________________ Incidentally, there is another interesting, but less efficient way to generate moves for sliding pieces on diagonals which I used in my early bitboard experiments. Here is how it worked: I used only standard a1-h1,a2-h2....a8h8 square ordering. To calculate bishop attacks, I did two identical steps, one for each diagonal (like you do with rotated bitboards). For a given diagonal, I ANDed a key for that square and direction with my occupied-squares bitmap to get a set of occupied squares on the diagonal. Again I used the trick of not including the squares at the ends of the diagonals, since they cannot effect the result. Now I needed to produce an index number to look up the attacks for the bishop, Ie I needed somehow to map these bits to the least significant byte of my bitboards, precisely the task that the rotated bitboards accomplish, which I did as follows: index=bitboard mod 255 The effect is to shift each square along its file to the corresponding square on the first rank, eg e4 goes to e1, g5 goes to g1 etc. This only works becarse I know in advance that no edge-square bits will ever be set (it would fail for squares on the h-file, but the a-file,1st rank a1-g1and 8th rank a8-g8 would be OK), and also that at most 1 bit is set in any one file. The mod operation is a bit slow, however. I would have liked to do both diagonals at once, but that would have violated the second condition of only 1 bit per file. However, this certainly does work, even if it is not the most efficient way. I even had the slight handicap of only having signed 64-bit integers (mod gives some problems with negative numbers), but the sign bit was square h8, an edge square, so all my keys were positive numbers. I think that the interaction of modular arithmetic and logical operations is very interesting. In early versions of my program, before I used any assembler, I used to determine the square number corresponding to a one-bit bitboard using modular arithmetic. index=bitboard mod 67 Every square gives a different value in the range 0-66, whereupon I did a table look-up to get the square number. Of course, once I started using assembler on the intel CPU, the bsf and bsr instructions were a god-send and I stopped all this nonsense with modular arithmetic....:-) Best wishes, 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.