Author: Gerd Isenberg
Date: 15:35:28 10/15/02
Go up one level in this thread
On October 15, 2002 at 13:24:37, Steffan Westcott wrote:
>Gerd,
>
>You may remember in my previous posts I gave algorithms for finding attacks in
>just one direction, and gave an example of rook attacks moving up the board. I
>notice in your posts that you combine the attacks in all directions as they are
>calculated. Your approach is good (although uses many working variables) however
>it loses information by combining the intermediate results too early.
>
Hi Steffan,
Yes i remember well. You gave me the ultimate lession in flood fill and
Kogge-Stone algorithms.
Hmm, too early? I don't understand, may be i miss something. I use dumb7fill for
diagonals, because it makes it easier to handle the wraps with 8 mmx registers
in total, it only needs two constants, notA and notH.
I use four mmx-registers for each diagonal direction. _Before_ i do the first
shifts with the four registers, i "and" them with the appropriate masks so that
they don't wrap. After the shifts i "or" all direction bits into the result set.
Then they are anded with empty Squares "and" notA resp. notH. So the second and
following "and" terminate the ray in case of occupied piece or reaching the
appropriate rook files. What is wrong with this? It includes attacks to the "ray
terminators".
With respect to the eight mmx registers, i mix Kogge-Stone (for files and left
attacks) with "occupied ^ (occupied - 2*rooks)" for right attacks
together with dumb7fill for diagonals.
>The lost information could have been of use, in things like move generation for
>example. Consider the following code fragment :
>
>---- 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));
>}
>
>
>BitBoard RookMovesUp(BitBoard friendly_rooks, BitBoard friendly_pieces,
> BitBoard empty_squares)
>{
> return RookAttacksUp(friendly_rooks, empty_squares) & ~friendly_pieces;
>}
>
>---- CUT HERE ----
>
>
>There is a 1-1 correspondence between set bits in the bitboard returned by
>RookMovesUp() and all friendly (read: "white" or "black") rook moves (including
>captures) going up the board. This is because at most 1 upward rook move is
>possible for each square. So this bitboard can serve as part of a unsorted
>movelist.
>
Yes, i think, that is exactly what i do.
This routine gets all bishop attacks including the ray terminators, friendly or
opponent pieces, like Kogge-Stone for rooks. Of course, to generate captures you
have to and them with opponent pieces, to generate quite moves with empty
squares.
Regards,
Gerd
// input: mm1 bishops
// mm6 emptySquares
// output mm0 bishopAttacks
//===========================
BitBoard BishopAttacks ()
__asm
{
pcmpeqd mm7, mm7 ; 0xffffffffffffffff
pxor mm5, mm5 ; 0
movq mm2, mm1 ; leftup
psubb mm5, mm7 ; 0x0101010101010101
movq mm3, mm1 ; leftdown
psubb mm7, mm5 ; 0xfefefefefefefefe notA
movq mm4, mm1 ; rightdown
movq mm5, mm7 ; 0xfefefefefefefefe notA
pand mm2, mm7 ; clear leftup occupied or a file
psrlq mm5, 1 ; 0x7f7f7f7f7f7f7f7f notH
pand mm3, mm7 ; clear leftdown occupied or a file
pand mm1, mm5 ; clear rightup occupied or h file
pand mm4, mm5 ; clear rightdown occupied or h file
pand mm7, mm6 ; to clear left occupied or a-file
pand mm5, mm6 ; to clear left occupied or h-file
// 1. diagonal dumbfill in each direction
psllq mm1, 9 ; rightup
psrlq mm4, 7 ; rightdown
psllq mm2, 7 ; leftup
psrlq mm3, 9 ; leftdown
movq mm0, mm1 ; bishopAttacks |= rightup
por mm0, mm4 ; bishopAttacks |= rightdown
por mm0, mm2 ; bishopAttacks |= leftup
por mm0, mm3 ; bishopAttacks |= leftdown
pand mm1, mm5 ; clear rightup occupied or h file
pand mm4, mm5 ; clear rightdown occupied or h file
pand mm2, mm7 ; clear leftup occupied or a file
pand mm3, mm7 ; clear leftdown occupied or a file
// 2. diagonal dumbfill in each direction
psllq mm1, 9 ; rightup
psrlq mm4, 7 ; rightdown
psllq mm2, 7 ; leftup
psrlq mm3, 9 ; leftdown
por mm0, mm1 ; bishopAttacks |= rightup
por mm0, mm4 ; bishopAttacks |= rightdown
por mm0, mm2 ; bishopAttacks |= leftup
por mm0, mm3 ; bishopAttacks |= leftdown
pand mm1, mm5 ; clear rightup occupied or h file
pand mm4, mm5 ; clear rightdown occupied or h file
pand mm2, mm7 ; clear leftup occupied or a file
pand mm3, mm7 ; clear leftdown occupied or a file
// 3. diagonal dumbfill in each direction
//....
// 7. diagonal dumbfill in each direction
psllq mm1, 9 ; rightup
psrlq mm4, 7 ; rightdown
psllq mm2, 7 ; leftup
psrlq mm3, 9 ; leftdown
por mm0, mm1 ; bishopAttacks |= rightup
por mm0, mm4 ; bishopAttacks |= rightdown
por mm0, mm2 ; bishopAttacks |= leftup
por mm0, mm3 ; bishopAttacks |= leftdown
}
}
// input: mm1 rook(s)
// mm6 emptySquares
// output mm0 fileAttacks
//===========================
void FileAttacksBB()
{
__asm
{ // up/down up/dn Kogge Stone
movq mm2, mm1 ; generator upg
movq mm4, mm1 ; generator dng
movq mm5, mm6 ; propagator upp
movq mm7, mm6 ; propagator dnp
psllq mm2, 8 ; upg << 8
psrlq mm4, 8 ; dng >> 8
psllq mm5, 8 ; upp << 8
psrlq mm7, 8 ; dnp >> 8
pand mm2, mm6 ; upp & (upg << 8)
pand mm4, mm6 ; dnp & (dng >> 8)
pand mm5, mm6 ; upp &= upp << 8
pand mm7, mm6 ; dnp &= dnp >> 8
por mm2, mm1 ; upg |= upp & (upg << 8)
por mm4, mm1 ; dng |= dnp & (dng >> 8)
movq mm0, mm2 ; upg
movq mm3, mm4 ; dng
psllq mm2, 16 ; upg << 16
psrlq mm4, 16 ; dng >> 16
pand mm2, mm5 ; upp & (upg << 16)
pand mm4, mm7 ; dnp & (dng >> 16)
por mm2, mm0 ; upg |= upp & (upg << 16)
por mm4, mm3 ; dng |= dnp & (dng >> 16)
movq mm0, mm5 ; upp
movq mm3, mm7 ; dnp
psllq mm5, 16 ; upp << 16
psrlq mm7, 16 ; dnp >> 16
pand mm5, mm0 ; upp &= p << 16
pand mm7, mm3 ; dnp &= p >> 16
movq mm0, mm2 ; upg
movq mm3, mm4 ; dng
psllq mm0, 32 ; upg << 32
psrlq mm4, 32 ; dng >> 32
pand mm0, mm5 ; upp & (upg << 32)
pand mm4, mm7 ; dnp & (dng >> 32)
por mm0, mm2 ; upg |= upp & (upg << 32)
por mm4, mm3 ; dng |= dnp & (dng >> 32)
psllq mm0, 8 ; final shift up
psrlq mm4, 8 ; final shift dn
por mm0, mm4
}
}
// input: mm1 rook(s)
// mm6 emptySquares
// output mm0 rankAttacks
//===========================
void RankAttacksBB()
{
__asm
{
pcmpeqd mm7, mm7 ; 0xffffffffffffffff
pxor mm5, mm5 ; 0
movq mm4, mm6 ; empty squares
movq mm2, mm1 ; rooks
psubb mm5, mm7 ; 0x0101010101010101
pxor mm4, mm7 ; not empty ==> occupied
movq mm3, mm5 ; 0x0101010101010101
paddb mm2, mm1 ; 2*rooks
paddb mm3, mm5 ; 0x0202020202020202
movq mm0, mm4 ; occupied
paddb mm3, mm5 ; 0x0303030303030303
psubb mm4, mm2 ; occupied - 2*rooks
psubb mm7, mm5 ; 0xfefefefefefefefe notA
pxor mm0, mm4 ; occupied ^ (occupied - 2*rooks)
psllq mm5, 7 ; 0x8080808080808080
movq mm4, mm3 ; 0x0303030303030303
psllq mm3, 2 ; 0x0c0c0c0c0c0c0c0c
movq mm2, mm7 ; notA
por mm3, mm4 ; 0x0f0f0f0f0f0f0f0f ABCD
movq mm4, mm7 ; notA
psubb mm7, mm5 ; 0x7e7e7e7e7e7e7e7e notAH
pand mm4, mm1 ; generator leg, but no wrap
pand mm7, mm6 ; propagator lep, but no wrap
psrlq mm4, 1 ; leg >> 1
psrlq mm7, 1 ; lep >> 1
pand mm4, mm6 ; lep & (leg >> 1)
pand mm7, mm6 ; lep &= lep >> 1
por mm4, mm1 ; leg |= lep & (leg >> 1)
movq mm5, mm4 ; leg
psrlq mm4, 2 ; leg >> 2
pand mm3, mm7 ; lep
pand mm4, mm7 ; lep & (leg >> 2)
psrlq mm7, 2 ; lep >> 2
por mm4, mm5 ; leg |= lep & (leg >> 2)
pand mm7, mm3 ; lep &= lep >> 2
movq mm3, mm4 ; leg
psrlq mm4, 4 ; leg >> 4
pand mm4, mm7 ; lep & (leg >> 4)
por mm4, mm3 ; leg |= lep & (leg >> 4)
pand mm4, mm2 ; but no wrap
psrlq mm4, 1 ; final shift left
por mm0, mm4
}
>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.