Author: Gerd Isenberg
Date: 13:44:21 03/23/04
Go up one level in this thread
On March 23, 2004 at 16:25:52, Gerd Isenberg wrote:
>On March 23, 2004 at 15:31:36, Gerd Isenberg wrote:
>
>>On March 23, 2004 at 13:21:33, Anthony Cozzie wrote:
>>
>>>After seeing Joachim's post that SMK solves this, I thought for about 5 seconds,
>>>and realized it isn't as hard as I thought.
>>>
>>>Step 1. Compute immovable pawnstructure. My guess is that he does this anyway.
>>>
>>>So here we recognize that that E3-F2-G3 is completely locked. This is not too
>>>hard to do, although I haven't worked out the mechanics completely.
>>>
>>>Step 2. Compute trappable squares.
>>>
>>>We simply floodfill from each square, and count the number of squares it can
>>>reach. This would be very slow, but we can speed it up as follows:
>>>
>>>We divide the board into 4 symmetric regions. (a piece will never get trapped on
>>>the center)
>>>
>>>Example: E1, F1, G1, H1, G2, H2, H3, H4
>>>
>>>We then check for at least 1 immoveable pawn, before floodfilling in that
>>>region.
>>>
>>>Step 3. Store into the pawn hash.
>>>
>>>And now we have a very quick test to determine if a piece can be trapped. This
>>>will cull out 99.999% of references.
>>>
>>>anthony
>>
>>Interesting idea to hash trappable squares by pawn structure!
>>
>>One has to distinguish between bishop-, rook- and queen-fills.
>>
>>What about this idea:
>>Two 90 degree rotated bishop or rook attack kogge-stone fills, excluding tabu
>>squares. If both sets are empty, there is a potentially trapped bishop square.
>>
>>Something like this:
>>
>>bool isTrappedBishopSquare(BitBoard singleSquareSet, BitBoard tabu)
>>{
>> BitBoard a1h8 = getA1H8Attacks(singleSquareSet) & ~tabu;
>> BitBoard h1h8 = getH1H8Attacks(singleSquareSet) & ~tabu;
>> // consider popCount (a1h8E | h1a8E)
>> BitBoard a1h8E = getH1H8Attacks(a1h8) & ~tabu;
>> BitBoard h1a8E = getA1H8Attacks(h1h8) & ~tabu;
>> return ( a1h8E == 0 && h1a8E == 0 );
>>}
>>
>>For all potentially squares of interest...
>
>
>BitBoard trappedBishopSquares = 0;
>BitBoard tabu = GetOwnNoneMovablePawns() | ...;
>BitBoard potb = ~tabu; // exclude tabu squares from the potential trapped
>while ( potb ) {
> BitBoard ssqs = potb & -potb;
> BitBoard a1h8 = getA1H8Attacks(ssqs) & ~tabu;
> BitBoard h1h8 = getH1H8Attacks(ssqs) & ~tabu;
> BitBoard a1h8E = getH1H8Attacks(a1h8) & ~tabu;
> BitBoard h1a8E = getA1H8Attacks(h1h8) & ~tabu;
> potb &= ~(a1h8 | h1h8 | ssqs);
> if ( a1h8E == 0 && h1a8E == 0 )
> trappedBishopSquares |= (a1h8 | h1h8 | ssqs);
>}
>
>
>Ok, there is still a lot to improve...
BitBoard trappedBishopSquares = 0;
BitBoard tabu = GetOwnNoneMovablePawns() | ...;
BitBoard potb = ~tabu; // exclude tabu squares from the potential trapped
while ( potb ) {
BitBoard ssqs = potb & -potb;
BitBoard a1h8 = getA1H8Attacks(ssqs) & ~tabu;
BitBoard h1a8 = getH1A8Attacks(ssqs) & ~tabu;
BitBoard a1h8E = getH1A8Attacks(a1h8) & ~tabu;
BitBoard h1a8E = getA1H8Attacks(h1a8) & ~tabu;
potb &= ~(a1h8 | h1a8 | a1h8E | h1a8E | ssqs);
if ( a1h8E == 0 && h1a8E == 0 )
trappedBishopSquares |= (a1h8 | h1h8 | ssqs);
}
This page took 0.01 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.