Author: Robert Hyatt
Date: 14:23:19 06/25/02
Go up one level in this thread
On June 24, 2002 at 22:19:53, Filip Tvrzsky wrote: >On June 24, 2002 at 20:33:32, Russell Reagan wrote: > >>I am not an experienced bitboard user. I've been thinking about trying them out >>just to see how they work in comparison with my current 0x88 implementation. Is >>there any potential problem in mixing the two approaches? One problem that I can >>see would be that if you have an index for a bitboard, it's not going to index >>into the same square in your 0x88 array. I suppose the only real reason to keep >>0x88 would be for efficient edge detection. Do bitboards offer a solution to >>edge detection? Or do they even need edge detection when using bitboards (ex. >>using the BSF asm instuction would seem to avoid edge detection altogheter)? >> >>Thanks, >>Russell > >I am not an experienced bitboard user too ... :-), but I have tried to mix both >approaches in my program, so I think it is possible very well. I assume x86 CPU >architecture farther, because I have no another expierence. My goal was to take >advantage of bitboards anywhere if it could be more efficient then pure 0x88 >representation, so I choose the way of improvement of my originally 0x88 program >step by step. It is simple with knights and pawns, somewhat more complicated >with rooks and most of all with bishops (I do not use bitboards here yet, but I >work on it now). Something is possible to do with MMX instructions, but this >instruction set has unfortunately many limitations. Generally I use bitboards by >move generator, check detector and in evaluation function too. The cost of >simultaneous keeping both 0x88 and bitboard representations is, in my opinion, >more then outweighted by gains. The pure bitboard representation seems to me to >be rather unefficient on x86 architecture, but I am not sure, I do not know it >in detail. >And regarding indexes for bitboards and 0x88 board, the mapping of one on other >is not complicated, just 3 or 4 CPU instructions, no memory acces is needed: > >A - bitboard index (range 0-63), >B - 0x88 index (range 0-7, 16-24, ... 112-119). > >Now, A == (B + (B & 7)) >> 1, and B == A + (A & ~7). > >Greeting you, Filip. We did both in Cray Blitz. We used a 64-word array for the board, but we also had an occupied_squares bitmap. That made it easy to detect attacks for sliding pieces in the InCheck() function. There is an array of bitmasks, blocked[sq1][sq2]. For sliding pieces, it contained 1 bits on the squares between sq1 and sq2 if they were on the same diagonal. If they were not, the bitmask was simply all 1 bits. If you want to know if a piece on square 1 attacks square 2, you simply take blocked[square1][square2], AND it with the occupied squares bitmap, and if the result is zero, there is an attack since no intervening squares are blocked. If you get a non-zero result, either the ray is blocked or the two pieces are simply not on the same ray. Simple and efficient on a vector machine, just load up all those blocked[king][piece] values for every piece on your side, do the ANDS in a vector op, and test to see if any results were zero (in a vector op). This made InCheck() take almost zero time...
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.