Computer Chess Club Archives


Search

Terms

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
		paddb	mm1, mm1	; right
		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
		paddb	mm1, mm1	; right
		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
	}
}






This page took 0.19 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.