Author: Steffan Westcott
Date: 17:41:10 10/26/02
Go up one level in this thread
On October 26, 2002 at 17:06:53, Peter Fendrich wrote:
>That's what I intended to do but when I started to collect material I discovered
>that too much of the old posts are missing and I'm not familiar with terms like
>Kogge-Stone parallel prefix algorithm , hammer and dumb7fill and maybe others.
>They are frequently referred to and without this basic material it doesn't seem
>to make sense to publish the rest. If someone can't supply me with code or
>definitions I have to wait until the archives are updated.
>Peter
Peter,
Let me provide a summary :
The general discussion here is about generation of attack/move bitboards for
sliding pieces by direct calculation. Each routine considers moves/attacks in
one direction only. Each routine considers all pieces on the board ie. generates
data for all moving pieces simultaneously. The routines do their work by direct
manipulation of the basic bitboards. No lookup tables or rotated bitboards are
used. All of these properties may make this approach attractive for some
architectures, with careful engine design. Mention has been made of the imminent
64-bit Hammer core CPU by AMD, which may benefit bitboard algorithms.
Two methods have been examined. The conceptually easier method has been dubbed
here as a 'flood fill' (a term borrowed from computer graphics), where the fill
proceeds in one direction only. A simple example, showing an upward flood fill :
BitBoard ShiftUp(BitBoard b)
{
return b << 8;
}
BitBoard FillUpOccluded_flood(BitBoard g, BitBoard p)
{
for(int n = 0; n < 7; n++)
g |= ShiftUp(g) & p;
return g;
}
BitBoard RookAttacksUp(BitBoard rooks, BitBoard empty_squares)
{
return ShiftUp(FillUpOccluded_flood(rooks, empty_squares));
}
BitBoard RookMovesUp(BitBoard friendly_rooks, BitBoard friendly_pieces,
BitBoard empty_squares)
{
return RookAttacksUp(friendly_rooks, empty_squares) & ~friendly_pieces;
}
The other method is inspired by parallel prefix circuits, a hardware design for
fast carry propagation in adders. The Kogge-Stone method lends itself to
convenient implementation in software, here used to propagate sliding chess
pieces rather than carry bits.
On closer inspection of Russell's code, I spotted some errors, alas. So, here is
the correct version, in full :
// Uses this ordering for bits <-> squares
//
// 56 57 58 59 60 61 62 63
// 48 49 50 51 52 53 54 55
// 40 41 42 43 44 45 46 47
// 32 33 34 35 36 37 38 39
// 24 25 26 27 28 29 30 31
// 16 17 18 19 20 21 22 23
// 8 9 10 11 12 13 14 15
// 0 1 2 3 4 5 6 7
typedef unsigned __int64 BitBoard;
///////////////////////////////////////////////////////////////////////////
BitBoard ShiftRight (BitBoard b) { return (b<<1) & 0xfefefefefefefefe; }
BitBoard ShiftLeft (BitBoard b) { return (b>>1) & 0x7f7f7f7f7f7f7f7f; }
BitBoard ShiftUp (BitBoard b) { return b<<8; }
BitBoard ShiftDown (BitBoard b) { return b>>8; }
BitBoard ShiftUpRight (BitBoard b) { return (b<<9) & 0xfefefefefefefefe; }
BitBoard ShiftUpLeft (BitBoard b) { return (b<<7) & 0x7f7f7f7f7f7f7f7f; }
BitBoard ShiftDownRight(BitBoard b) { return (b>>7) & 0xfefefefefefefefe; }
BitBoard ShiftDownLeft (BitBoard b) { return (b>>9) & 0x7f7f7f7f7f7f7f7f; }
///////////////////////////////////////////////////////////////////////////
BitBoard FillRightOccluded(BitBoard g, BitBoard p)
{
p &= 0xfefefefefefefefe;
g |= p & (g << 1);
p &= (p << 1);
g |= p & (g << 2);
p &= (p << 2);
return g |= p & (g << 4);
}
BitBoard FillLeftOccluded(BitBoard g, BitBoard p)
{
p &= 0x7f7f7f7f7f7f7f7f;
g |= p & (g >> 1);
p &= (p >> 1);
g |= p & (g >> 2);
p &= (p >> 2);
return g |= p & (g >> 4);
}
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 FillDownOccluded(BitBoard g, BitBoard p)
{
g |= p & (g >> 8);
p &= (p >> 8);
g |= p & (g >> 16);
p &= (p >> 16);
return g |= p & (g >> 32);
}
BitBoard FillUpRightOccluded(BitBoard g, BitBoard p)
{
p &= 0xfefefefefefefefe;
g |= p & (g << 9);
p &= (p << 9);
g |= p & (g << 18);
p &= (p << 18);
return g |= p & (g << 36);
}
BitBoard FillUpLeftOccluded(BitBoard g, BitBoard p)
{
p &= 0x7f7f7f7f7f7f7f7f;
g |= p & (g << 7);
p &= (p << 7);
g |= p & (g << 14);
p &= (p << 14);
return g |= p & (g << 28);
}
BitBoard FillDownRightOccluded(BitBoard g, BitBoard p)
{
p &= 0xfefefefefefefefe;
g |= p & (g >> 7);
p &= (p >> 7);
g |= p & (g >> 14);
p &= (p >> 14);
return g |= p & (g >> 28);
}
BitBoard FillDownLeftOccluded(BitBoard g, BitBoard p)
{
p &= 0x7f7f7f7f7f7f7f7f;
g |= p & (g >> 9);
p &= (p >> 9);
g |= p & (g >> 18);
p &= (p >> 18);
return g |= p & (g >> 36);
}
In the above, g = moving piece(s); p = empty squares
I posted here a long article on the definition of parallel prefix problems, and
how they could be applied to chess programming. Also, in other threads I've
illustrated algorithms featuring direct calculation with bitboard terms, such as
all shortest path finding. If you want them, I have those posts on file, but
none of the thread context they appeared in.
Feel free to use this material.
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.