Author: Gerd Isenberg
Date: 14:17:15 09/09/02
Go up one level in this thread
On September 09, 2002 at 16:51:24, Tony Werten wrote:
>On September 09, 2002 at 16:13:00, Gerd Isenberg wrote:
>
>>Hi all,
>>specially algorithm freaks,
>>
>>I'm currently looking for an efficient algorithm to determine whether two bits
>>in a bitboard are connected by "ones". Actually i use following recursive one,
>>but isn't there something smarter?
>
>I'm not sure this is what you mean, but maybe this will help you on your way.
>
>In XiniX I have a byte with bits set if there are pawns on that line. To check
>for isolated pawns I do:
>
>iso:=pawns and not((pawns shl 1) or (pawns shr 1));
>
>If you change the shifts to 8, then take out these isolated pawns from your
>bitmap and then do the same with the rotated bitmap it should give you what you
>want. ( I think)
>
>Tony
>
hmmm, i don't think so, Tony.
The "ones" in following bitboard tag squares a king may enter (not attacked by
enemy or occupied by own). It is an interesting question whether the king on a1
may reach b8?
0 1 1 1 1 1 1 1 fe
0 0 0 1 1 1 1 1 f8
0 0 0 0 1 1 1 1 f0
0 0 0 0 0 1 1 1 e0
0 0 0 0 0 0 1 1 c0
1 1 1 1 0 0 0 1 8f
1 1 1 1 1 0 1 0 5f (1f)
1 1 1 1 1 1 0 1 bf
Under the assumption that the o square is member of the initial "theBB" the
algorithm is shlightly improvable by checking the distance:
bool isConnected(BitBoard &theBB, int from, int to)
{
if (Distance(from, to) <= 1)
return true;
BitBoard adjacentBB = sKingAtta[from] & theBB;
theBB &= ~adjacentBB;
while (adjacentBB)
{
int sq = findLSBAndReset(adjacentBB);
if ( isConnected(theBB, sq, to) ) return true;
}
return false;
}
regards,
Gerd
>
>>
>>
>>bool isConnected(BitBoard &theBB, int from, int to)
>>{
>> BitBoard adjacentBB = KingAttacks(from) & theBB;
>> theBB &= ~adjacentBB;
>> while (adjacentBB)
>> {
>> int sq = findLSBAndReset(adjacentBB);
>> if (sq == to) return true;
>> if ( isConnected(theBB, sq, to) ) return true;
>> }
>> return false;
>>}
>>
>><snip>
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.