Author: Steffan Westcott
Date: 16:02:15 09/15/02
Go up one level in this thread
On September 15, 2002 at 10:39:03, Gerd Isenberg wrote:
>Hi all,
>
>Stimulated by all the nice flood fill routines posted by Stefan Westcott,
>
>http://www.talkchess.com/forums/1/message.html?252020
>http://www.talkchess.com/forums/1/message.html?252066
>
>i am currently thinking about using flood fill to generate attacks for sliding
>pieces, simply by doing seven floods unconditionally in each direction, without
>possible expensive memory access.
>
>I think the "Kogge-Stone parallel prefix algorithm" is not possible here.
Think again... :)
>BitBoard getRookAttacks(BitBoard freeSquares, BitBoard rooks)
>{
> BitBoard attck = 0;
> // 1. straight fill
> BitBoard left = ShiftLeft(rooks);
> BitBoard right = ShiftRight(rooks);
> BitBoard up = ShiftUp(rooks);
> BitBoard down = ShiftDown(rooks);
> attck |= left|right|up|down;
> // 2. straight fill
> left = ShiftLeft(left&freeSquares);
> right = ShiftRight(left&freeSquares);
> up = ShiftUp(up&freeSquares);
> down = ShiftDown(down&freeSquares);
> attck |= left|right|up|down;
> // 3..6. straight fill
> // repeat 2.fill code 4 times
> // ...............
> // 7. straight fill
> return attck
> | ShiftLeft(left&freeSquares)
> | ShiftRight(left&freeSquares)
> | ShiftUp(up&freeSquares)
> | ShiftDown(down&freeSquares);
>}
Gerd,
A faster routine to find all possible target squares for upward rook
moves/attacks might look like this :
---- CUT HERE ----
BitBoard FillUpOccluded(BitBoard g, BitBoard p)
{
g |= p & (g << 8);
p &= (p << 8);
g |= p & (g << 16);
p &= (p << 16);
return g |= p & (g << 32);
}
BitBoard RookAttacksUp(BitBoard rooks, BitBoard empty_squares)
{
return ShiftUp(FillUpOccluded(rooks, empty_squares));
}
---- CUT HERE ----
RookAttacksUp() is doing the same work as the part of your routine
getRookAttacks() which deals with upward rook attacks, but with less operations.
The routine FillUpOccluded() smears the set bits of bitboard g upwards, but only
along set bits of p; a reset bit in p is enough to halt a smear. RookAttacksUp()
uses this routine to find all squares rooks may occupy by either staying still
or moving up along empty squares (no captures allowed). Shifting this last
result up by 1 square gives the squares all rooks can attack by moving upwards
(which _does_ include captures).
A parallel prefix problem is of the sort :
Given the terms x1, x2, x3, ... , xN and an associative operator #
find the values q1 = x1
q2 = x1 # x2
q3 = x1 # x2 # x3
.
.
.
qN = x1 # x2 # x3 # ... # xN
Associative expressions can be bracketed any way you like, the result is the
same. To see why this is interesting for chess programming, let's define x1, x2,
... and # to be
xI = < gI, pI > (a two element tuple)
where gI = square aI has a rook on it
and pI = square aI is empty
for all I = 1, 2, 3, ... , 8
and xI # xJ = < gI, pI > # < gJ, pJ >
= < ((gI && pJ) || gJ), (pI && pJ) >
All this algebra looks very scary at first, so here's an example :
q2 = x1 # x2 = < rook_on_a1, a1_is_empty > # < rook_on_a2, a2_is_empty >
= < ((rook_on_a1 && a2_is_empty) || rook_on_a2),
(a1_is_empty && a2_is_empty) >
The first tuple of q2 tells us if a rook is on a2 or can move up to a2 along
empty squares.
The second tuple of q2 tells us if a rook could move up freely through a1-a2 ie.
a1-a2 are empty.
In general,
xI # x(I+1) # ... # xJ =
< a_rook_somewhere_on_aI_to_aJ_is_either_on_aJ_or_can_move_up_to_aJ,
all_squares_aI_to_aJ_are_empty >
and so
qJ = < a_rook_somewhere_in_file_a_is_either_on_aJ_or_can_move_up_to_aJ,
all_squares_a1_to_aJ_are_empty >
The tuples g and p are known as the "generator" and "propagator" terms in the
literature of fast carry propagation circuits. But we are not dealing with carry
bits in a carry propagate adder! Here, we are generating and propagating upward
rook attacks along a file of a chessboard.
Why all this theory? Well, prefix computation is a heavily researched area,
researched by many folk smarter than me :) Its of interest because it has many
applications, such as VLSI design, pattern matching, and others. There are many
different ways of going about it, with different implementation characteristics.
The method chosen in FillUpOccluded() is based on a Kogge-Stone parallel prefix
network, because it can be implemented very easily in software. The diagram
below (trust me, it really _is_ supposed to look like that) is an illustration
of how it works. The corresponding lines of program code are shown on the right.
The inputs are fed into the network at the top, pass along the connecting lines,
are combined by the # operator at various points, and the outputs appear at the
bottom.
x1 x2 x3 x4 x5 x6 x7 x8 Input : g, p
| | | | | | | |
V V V V V V V V
| | | | | | | |
| | | | | | | |
|\ |\ |\ |\ |\ |\ |\ |
| \| \| \| \| \| \| \|
| # # # # # # # g |= p & (g << 8);
| | | | | | | | p &= (p << 8);
|\ |\ |\ |\ |\ |\ | |
| \: \: \: \: \: \: |
| \ \ \ \ \ \ |
| :\ :\ :\ :\ :\ :\ |
| | \| \| \| \| \| \|
| | # # # # # # g |= p & (g << 16);
| | | | | | | | p &= (p << 16);
|\ |\ |\ |\ | | | |
| \: \: \: \: | | |
| \ \ \ \ | | |
| :\ :\ :\ :\ | | |
| | \: \: \: \: | |
| | \ \ \ \ | |
| | :\ :\ :\ :\ | |
| | | \: \: \: \: |
| | | \ \ \ \ |
| | | ;\ ;\ :\ :\ |
| | | | \| \| \| \|
| | | | # # # # g |= p & (g << 32);
| | | | | | | |
| | | | | | | |
V V V V V V V V
q1 q2 q3 q4 q5 q6 q7 q8 Output : g
To convince yourself this works, select any output qI and trace upwards from the
bottom of the diagram. You'll see it leads back to x1, x2, ... , xI, so qI is
formed by some computation of x1 # x2 # ... # xI.
[Implementor's note : The 2 program lines that assign to variable p are not
strictly correct. By the end of the routine, p1 and p2 have been trashed
(reset). However, they are trashed after they can affect the correctness of the
routine result.]
Cheers,
Steffan
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.