Computer Chess Club Archives

Messages

Subject: flood fill attack bitboards

Author: Gerd Isenberg

Date: 07:39:03 09/15/02

```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.

The mmx code for rooks is 320 Bytes long, which is about as twice as the
table-lookup code (OK with hammer it's a bit more). But no need for lookup
tables and no need for rotated bitboards anymore!

At least two direction floods may processed simultaniously due to the two
mmx-integer pipes, and no need to save any (32-bit) register in calling
function!

The routine may generate attacks for multiple rooks (or straight attacks from
queens) simultaniously, therefore the BitBoard rooks parameter!

I think the "Kogge-Stone parallel prefix algorithm" is not possible here. May be
it can be combined with the x ^= (x-2) trick for ranks.
Worth to try?

Cheers,
Gerd

similar c-code:

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);
}

prefered mmx code:

BitBoard getRookAttacksMMX(BitBoard freeSquares, BitBoard rooks)
{
static const BitBoard eight = 8;
static const BitBoard notH = 0x7f7f7f7f7f7f7f7f;
__asm
{
movd	mm6,   [freeSquares]
punpckldq mm6, [freeSquares+4]
movd	mm1,   [rooks]
punpckldq mm1, [rooks+4]
pxor	mm0, mm0	; rookAttacks := 0
movq	mm5, [eight]; saves some bytes in unrolled loop
movq	mm7, [notH]	; saves some bytes in unrolled loop
movq	mm2, mm1	; left
movq	mm3, mm1	; up
movq	mm4, mm1	; down
// 1. straight fill in each direction
psrlq	mm2, 1		; left
psllq	mm3, mm5	; up
por	mm0, mm1	; rookAttacks |= right
pand	mm2, mm7	; clear left h-file wraps
pand	mm1, mm6	; clear right occupied
por	mm0, mm3	; rookAttacks |= up
psrlq	mm4, mm5	; down
por	mm0, mm2	; rookAttacks |= left
pand	mm3, mm6	; clear up occupied
por	mm0, mm4	; rookAttacks |= down
pand	mm2, mm6	; clear left occupied
pand	mm4, mm6	; clear down occupied
// 2-6. straight fill in each direction
// repeat above fill code 5 times
// .........
// 7. straight fill in each direction
psrlq	mm2, 1		; left
psllq	mm3, mm5	; up
por	mm0, mm1	; rookAttacks |= right
pand	mm2, mm7	; clear left h-file wraps
por	mm0, mm3	; rookAttacks |= up
psrlq	mm4, mm5	; down
por	mm0, mm2	; rookAttacks |= left
por	mm0, mm4	; rookAttacks |= down

pswapd	mm1, mm0	; highboard athlon only
movd	eax, mm0	; return low board in eax
movd	edx, mm1	;       high board in edx
}
}

```