Author: Gerd Isenberg
Date: 06:14:52 08/24/04
Go up one level in this thread
On August 24, 2004 at 07:06:14, Tony Werten wrote:
>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.
>>
>>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 ...
>
>Hmm, aren't there easier things for doing this ?
Probably - as i said a vague idea, i'm not sure. It requires some huge register
file (G5, Itanium) or some "fast" memory for the combined attacks.
I like the idea with minimal 256-bit board representation and minimal incemental
update during make(unmake) move with all unique move indizies instead of from/to
squares and separate piece/captured piece information ;-)
The idea is to do all eight kogge-stone fills only once per node only for all
pieces and to extract the piece wise attack informations by three "and" or
"notand".
{g0,g1,g2,gb} or g[4] -> 8 KoggeStones produce
0 fillUp {g[4]}
1 fillRightUp {g[4]}
2 fillRight {g[4]}
3 fillRightDown {g[4]}
4 fillDown {g[4]}
5 fillLeftDown {g[4]}
6 fillLeft {g[4]}
7 fillLeftUp {g[4]}
==> combined[8][4] // 8==direction, 4==piecebits
Since you have eight disjoint directions it is probably cheaper to detect pinned
pieces and remove checkers this way:
(i like it to have the pinned direction as well)
pinnedByBlackOrBlackRemoveCheckers[ver] = allPieces & (
(asBRookOrQueen(combined[up]) & asWKing(combined[down]) )
| (asBRookOrQueen(combined[down]) & asWKing(combined[up]) )
);
pinnedByBlackOrBlackRemoveCheckers[hor] = allPieces & (
(asBRookOrQueen(combined[left]) & asWKing(combined[right]) )
| (asBRookOrQueen(combined[right]) & asWKing(combined[left]) )
);
pinnedByBlackOrBlackRemoveCheckers[dia1] = allPieces & (
(asBBishopOrQueen(combined[leftUp]) & asWKing(combined[rightDown]) )
| (asBBishopOrQueen(combined[rightDown])& asWKing(combined[leftUp]) )
);
pinnedByBlackOrBlackRemoveCheckers[dia2] = allPieces & (
(asBBishopOrQueen(combined[leftDown]) & asWKing(combined[rightUp]) )
| (asBBishopOrQueen(combined[rightUp]) & asWKing(combined[leftDown]) )
);
>
>checking squares:
>
>BishopCheckingSquare=bishop_attacks(bishopsq) & bishop_attacks(kingsq)
>( you can use for kingsq whatever piecesquare you want )
Yes, but bishop_attacks requires four disjoint kogge-stones or two rotated
lookups. And as far i can see your code handles only one bishop.
>
>pieces pinned by bishop:
I am not quite sure about your the polymorph bishop_attacks(sq,all_pieces).
Is it a kogge Stone with ~all_pieces as propagator?
Or is it the intersection of bishop attacks from sq and all_pieces?
So i have some problems to follow your pinned piece code ;-(
Can you elaborate a bit more on that?
Looks interesting.
Thanks,
Gerd
>
>direct_attacks_squares=bishop_attacks(sq,all_pieces)
>
>less_pieces=all_pieces & ~(direct_attacks_squares);
>indirect_attacks_squares=bishop_attacks(sq,less_pieces)
> & ~(direct_attacks_squares)
>
>pinned_pieces=indirect_attacks_squares
> & less_pieces & ~(own_pieces)
>
>
>Tony
>
>
>>
>>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.