Author: Gerd Isenberg
Date: 03:08:50 01/11/04
Go up one level in this thread
On January 10, 2004 at 20:45:32, Chris Hull wrote: >On January 10, 2004 at 15:25:51, Russell Reagan wrote: > >I want to use this for sliding attacks in my bitboards. The bits represent >pieces so I want to know the nearest piece to the rook. > >Chris The cheap FindNearestHigherBit may also performed with the x^(x-2) trick. Y = X & (X^(X-2M)); X = 0101000100000101 M = 0000000100000000 X-M = 0101000000000101 // or X & ~M, specially if (M is not subset of X) X-2M = 0100111100000101 X = 0101000100000101 X^(X-2M)= 0001111000000000 // rook attacks in LSB->MSB direction Y = 0001000000000000 Because a binary addition overflow occurs from low to to high and there is no "reversed" math, FindNearestLowerBit is more expensive. There was the idea of "reversed" bitboards, to perform that cheap x^(x-2) trick for the MSB->LSB direction too. For sliding piece attack generation, there are other alternatives. 1. As Russell already mentioned, rotated bitboards. You index precalculated lookup tables (one of four directions) with the square index and an occupied state of that ray. Because none rotated occupied bitboards, have consecutive bits rank-wise, it is necessary for files and both diagonal directions to have 90,45,135 degree rotated occupied bitboards as well. 2. Fill Algorithms Considering 64-bit register files, fill-algorithms are another alternative to determine attacks in one of eight sliding piece directions. They are able to generate attacks multiple sliding pieces. 2.1. Dumb7fill shift M in the direction (left/right 1,7,8,9) eg. for rank MSB->LSB (with my mapping H->A) shift right one. attacks = 0; p = ~(occupied | A_FILE); M >>= 1; attacks |= M; M &= p; M >>= 1; attacks |= M; M &= p; M >>= 1; attacks |= M; M &= p; M >>= 1; attacks |= M; M &= p; M >>= 1; attacks |= M; M &= p; M >>= 1; attacks |= M; M &= p; M >>= 1; attacks |= M; 2.2. Kogge-Stone parallel prefix algorithm by Steffan Westcott the idea is to perform a SWAR algorithm and to do only three fill iterations instead of seven: p = ~occupied & ~H_FILE; M |= p & (M>>1); p &= p>>1; M |= p & (M>>2); p &= p>>2; M |= p & (M>>4); attacks = (M >> 1) & ~H_FILE;
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.