Author: Gerd Isenberg
Date: 00:03:21 08/25/04
Go up one level in this thread
On August 24, 2004 at 06:01:01, Gerd Isenberg wrote:
>Hi all,
>
>only a vague idea about the possible use of Kogge-Stone-Fill Algorithms...
>
>See Steffan Westcott's original routines:
>http://chessprogramming.org/cccsearch/ccc.php?art_id=261956
>
>The idea is to use multiple bitwise combined generators but only one propagator
>(empty squares) per direction. So with four generators one may get up to 2**4 ==
>16 target sets.
oups, only 2**4 - 1 == 15 possible target sets, because the fill pattern
must be != zero (indicates no attack e.g. after some blocking piece).
>
>Consider this compact 256-bit board representation with four bitboards and
>therefore four bits per square:
>
>g0,g1,g2,gB
>
>Three corresponding bits in the three bitboards g0-g2 determine piece if any,
>e.g. in this way (g0 == sliding piece):
>
>gb g2 g1 g0
> 0 0 0 empty square
> 0 0 1 not used or redundant single rook, see below
> 0 1 0 pawn
> 0 1 1 bishop
> 1 0 0 knight
> 1 0 1 rook
> 1 1 0 king
> 1 1 1 queen
>
>pB determines black pieces.
>
>allPieces = g0 | g1 | g2;
>white = allPieces& ~gb;
>
>pawns = ~g0 & g1 & ~g2;
>bishops = g0 & g1 & ~g2;
>knights = ~g0 & ~g1 & g2;
>rooks = g0 & ~g1 & g2;
>kings = ~g0 & g1 & g2;
>queens = g0 & g1 & g2;
>
>Now if you do eight (for each queen direction) Kogge-Stone-Fills with these four
>bitboards as generators (or two 128-bit XMM words), you have all possible
>sliding attacks from all pieces as if they are queens.
>
>The resulting vector of 8*4 = 32 bitboards provides all attack information
>needed for move generation and eval, e.g. all pinned piece detected, remove
>checkers, checking target squares for bishops or rooks, target squares for
>attacking rooks or knights by bishop etc ...
The most relevant pattern for disjoint sliding attacks are:
white/black lsb rook
white/black msb rook
white/black bishops on different square colors
white/black queen
white/black king as meta queen
With disjoint single bitboards rather than four combined that would take four
eight-direction fills (w/b queen/king) and six four-direction fills (w/b 2*rook,
bishops).
The combined 256-bit vector fill with eight directions is about the same effort
than four eight-direction fills for b/w queen/king with same propagator.
So the combined fill approach safes approx. the six four direction fills for
rooks and bishops, but has to deal with a lot of and/andnot to get the piece
codes out of the combined pattern.
So the whole win of the combined multiple Kogge-Stone-Fill seems rather
negligible. But due to knights and pawns (rooks and bishops too) are processed
as meta queen sliders too, without any additional costs with their unique piece
patterns, there are a few additional informations about some targets of sliding
pieces. E.g. whether a bishop attacks a rook or knight, or even whether a rook
may attack a pawn horicontally on the seventh rank.
Xray attacks might be processed easily with this information too without further
fill-cycles. E.g. for right direction on some rank we have following white rook
pattern:
gb: 0 0 0 0 0 0 0 0
g2: 0 0 0 1 0 0 0 0
g1: 0 0 0 0 0 0 0 0
g0: 1 0 0 1 0 0 0 0
| |
| msb rook on d-file
lsb rook on a-file
fill g[4] right:
gb: 0 0 0 0 0 0 0 0
g2: 0 0 0 0 1 1 1 1
g1: 0 0 0 0 0 0 0 0
g0: 0 1 1 1 1 1 1 1
The g2 change from 0->1 (or vice versa) while g0 is still 1 and g1 0, indicates
the beginning of an xray attacks. All msb rook attack pattern (0101) are
lsb-rook xrays attacks here.
Cheers,
Gerd
>
>Since Kogge-Stone fill works setwise, one may have some problems to associate
>one member of a target directionwise attack set to the piece (rook/bishop/queen)
>attacking this square in this particular direction. More than one queen or
>light/dark colored bishop per side is uncommon and good predictable by some
>conditional jumps, but with rooks that is quite common.
>
>Therefore the idea to isolate the least significant rook per side before doing
>the fill cycles and to get disjoint target sets per rook. Additional effort to
>map source from target squares is only necessary if more than two rooks per side
>are involved.
>
>Cheers,
>Gerd
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.