Author: Dann Corbit
Date: 16:08:48 01/14/03
Go up one level in this thread
On January 14, 2003 at 18:34:44, Gerd Isenberg wrote: >On January 14, 2003 at 17:13:29, Gerd Isenberg wrote: > >>On January 14, 2003 at 16:09:57, Dann Corbit wrote: >> >>>[SNIP] >>>>the x^x-2 trick is absolutely great. >>> >>>Can someone give me the ten cent explanation of how a parabola is useful? >>> >>>I want to get either a mathematical or geometric understanding. >> >>Hi Dann, >> >>One of the miracles of two's complement ;-) >>Complementing bits in MSB direction until the first "one" is complemented. >> >>One sample of all rook attacks in right board direction: >>(bottom left is bit 0) >>X - any Piece >>R - Rook (or Queen) >> >>- - - - - - - - >>- - - - - - - - >>- - - - - - - - >>- X - R - - X - >>- - - - - - - - >>- R X - R - X - >>- - - - - - - - >>R - - - - - - - >> >>BitBoards: - is zero for better reading. All operations byte- or rankwise. >>0 1 2 3 4 5 6 7 >> >> Occupied Rooks Occupied-Rooks Occupied-2Rooks...^Occupied >>- - - - - - - -|- - - - - - - -|- - - - - - - -|- - - - - - - -|- - - - - - - - >>- - - - - - - -|- - - - - - - -|- - - - - - - -|- - - - - - - -|- - - - - - - - >>- - - - - - - -|- - - - - - - -|- - - - - - - -|- - - - - - - -|- - - - - - - - >>- 1 - 1 - - 1 -|- - - 1 - - - -|- 1 - - - - 1 -|- 1 - 1 1 1 - -|- - - - 1 1 1 - >>- - - - - - - -|- - - - - - - -|- - - - - - - -|- - - - - - - -|- - - - - - - - >>- 1 1 - 1 - 1 -|- 1 - - 1 - - -|- - 1 - - - 1 -|- 1 - - 1 1 - -|- - 1 - - 1 1 - >>- - - - - - - -|- - - - - - - -|- - - - - - - -|- - - - - - - -|- - - - - - - - >>1 - - - - - - -|1 - - - - - - -|- - - - - - - -|1 1 1 1 1 1 1 1|- 1 1 1 1 1 1 1 >> x 1 x-1 x-2 x^(x-2) >> > >The first subtraction "resets" the rook bits. >The second subtraction toggles the bits from the rook bit positions until the >first occupied is toggled and becomes zero. >The final xor resets the remaining rook bits, but sets all occupied bits that >became previously reset by the second subtraction. > >For single attackers the trick also works in other positive (or reversed >negative) directions with some additional ray masks and 64-bit arithmetic. Thanks for that excellent explanation.
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.