Author: Gerd Isenberg
Date: 11:58:35 06/03/04
Go up one level in this thread
On June 03, 2004 at 10:58:36, Volker Böhm wrote:
>Hi,
>
>thanks verry much for all your postings. Thought I know something about
>optimizing code, but have to see now that I know nothing! The "-q >> 31" is a
>verry good trick, have to try it!
>The parallelisatzion of the code is not such a big problem as I have other
>precalculated values mixed without the need to swap datas out of registers. One
>other value I calculate here is an attack signature I get or-ing all 8 fields
>around the king. But I´ll try this one this evening.
>
>Perhaps you have an Idea about another problem:
>
>I whant to know if a special piece is attacking a field and no opponent piece is
>defending this field by one check. For queen it is simple as I am only using one
>bits for queens:
>
>if ((attackfield[pos] & (whitequeenbit + blackbits)) == whitequeenbit)
> // ... check if queen can mate on pos
>
>for rooks I have 2 bits. Thus this check does not work:
>if ((attackfield[pos] & (whiterookbits + blackbits)) == ???
Hmm, i guess "+" is meant like bitwise or?
So you have a set of white rooks combined with all other black pieces attacking
a square. And you want to know whether this set is an not empty subset of the
white rooks.
someSet = attackfield[pos] & (whiterookbits + blackbits);
1. condition someSet is not empty.
2. condition the Intersection of someSet and blackbits is empty
if ( (someSet != 0) && ((someSet & blackbits) == 0) )
or probably to relax the branch target buffer a bit, assuming compiler is able
to use setCC instructions:
if ( (someSet != 0) + ((someSet & blackbits) == 0) == true+true )
To build an unconditional -1|0 mask of set not empty, assuming all 32 bit are
used as members (including sign), one must use (someSet|-someSet)>>>31.
Probably too expensive ;-)
>
>the problem here is to check if one or more of whiterookbits are set and none of
>the blackbits.
>
>Thanks, Volker
>
>On June 02, 2004 at 09:14:38, Gerd Isenberg wrote:
>
>>One more note ...
....
>>May be an alternative solution to frickle an inner six square occupied state
>>from a ray to index precalculated attack tables without rotated bitboards,
>>specially if your piececodes are already negative, but empty is null ;-)
>
>Opps I don´t understand "six square occupied state". Maybe I don´t know enough
>about bitboards.
The idea is for sliding pieces to get raywise precalculated attacks bitboards
from an array by indexing with the occupied state of the ray and the square
index, e.g. for ranks:
BitBoard CNode::getRankAttacks(int sq)
{
int occupiedState = getOccupiedSetOfRank(Rank(sq));
return rankAttacks[occupiedState][sq]; // precalculated
}
getOccupiedSetOfRank(0..7) leaves a word (Byte is enough) with consecutive bits
of that rank, where a one-bit indicates any piece, but zero-bit an empty square.
In this position the occupied state of the first rank is:
[D]1r1r2k1/p4pp1/1p5p/2p5/2Pp3P/6P1/1P3PB1/3NR2K w - -
A B C D E F G H
0 0 0 1 1 0 0 1
i have to reverse it due to my mapping A0 = LSB, crafty does it invers.
10011000B = 98H
Now the precalculated rankAttacks[98H][e1] leaves a bitboard in board wise
order:
A8
0 0 0 0 0 0 0 0 00h
0 0 0 0 0 0 0 0 00h
0 0 0 0 0 0 0 0 00h
0 0 0 0 0 0 0 0 00h
0 0 0 0 0 0 0 0 00h
0 0 0 0 0 0 0 0 00h
0 0 0 0 0 0 0 0 00h
0 0 0 1 0 1 1 1 e8h
= 0x00000000000000e8 with my square-digit mapping.
a bitset of all rank attacks for a rook on e1.
Due to outer squares of a ray have no more squares behind, the occupied state of
those squares don't cares for their attack state. Eg. in the above position, h1
is attacked whether there is a piece on it or not.
Therefore you only need the "inner" six occupied bits (or max(raylength-2, 0)).
Saving two bits for the occupied index make the lookup tables four times
smaller:
BitBoard rankAttacks[ 64][64]; // 8*4K = 32KByte
instead of
BitBoard rankAttacks[256][64]; // 128KByte
For files and diagonals you need similar tables,
so that simply saves some memory.
6-Bit index now for the same rook on e1 case is
A B C D E F G H
0 0 0 1 1 0 0 1
10011000B = 98H
_001100_B
001100B = 0CH
and rankAttacks[0CH][e1] must now contain the same bitboard as above.
The idea with rotated bitboards is to have consecutive occupied bits for each of
four directions and to shift and mask the appropriate six bits for that ray.
Now instead of using rotated bitboards, but 64sq or 0x88 board arrays, the
pack2bits(int ray[6]) comes in mind, to build that six-inner occupied state:
int pack6Squares2OccupiedState(
int sq1, int sq2, int sq3, int sq4, int sq5, int sq6) {
return
(
(
(-s1 & 0x10)
| (-s2 & 0x20)
| (-s3 & 0x40)
| (-s4 & 0x80)
) >> 4
) |
(
(-s5 & 0x10)
| (-s6 & 0x20)
);
}
And to call pack6Squares2OccupiedState(b1,c1,d1,e1,f1,g1) for above case.
If the piece codes were already negative (-2...-14) one would even safe the six
negates ;-)
12 instructions, three cycles?
Ok, i guess still too expensive, if you like to call bitboard sliding
attack-getters on the fly.
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.