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

- direction fill vs. Kogge-Stone
**Gerd Isenberg***15:28:29 09/16/02* - Re: flood fill attack bitboards
**Gerd Isenberg***23:05:29 09/15/02*

This page took 0.03 seconds to execute

Last modified: Thu, 07 Jul 11 08:48:38 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.