Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: algorithm question

Author: Robert Hyatt

Date: 19:58:54 09/09/02

Go up one level in this thread


On September 09, 2002 at 18:27:35, Gerd Isenberg wrote:

>On September 09, 2002 at 17:52:45, Robert Hyatt 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?
>>>
>>>
>>>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;
>>>}
>>
>>Precompute a table,  char connected[64][64].  If square I and J are connected,
>>for any value of I and J, set connected[I][J]=1, else set it to zero.
>>
>>Now you have a quick test.
>>
>>If you are wanting to see if a rook is connected to another rook, that is
>>a different issue...
>>
>
>Thanks Bob,
>
>Sounds great, have to think about...
>
>But as far i IMHO believe to understand you have to reinitialize the whole array
>if your position and the "allowed-set" changed . Isn't that too expensive, if
>you only want to know on the fly whether the king on a1 may walk to b8?
>
>Gerd
>
><snip>



First let's make sure I am answering the question you asked...

I am answering the question "how can I tell if two squares are on the same
diagonal, rank or file?"

There are multiple ways to do this.  If you are a real bitboard engine,
then one way is to take a bitmap of "all possible queen moves" from square
X, and AND this with a bitmap with just a 1 bit set on square Y.

You can also do this without bitmaps easier if you use 0x88 but I don't think
that is an option for you so, you can also do this:

Initialize an array connected[64][64] before starting the game.  It is
initialized such that if squares I and J are on the same rank, file or
diagonal (or any subset of those you want) then connected[I][J] is set to
1, else it is set to 0.  Now to ask if squares X and Y are "connected" you
just access "connected[X][Y]" and if it is non-zero, they are.

Another question:  "How can I tell if two pieces attack each other in the
sliding direction (are rooks connected, etc?)"

You simply have to compute a bitmap that connects the two squares, which
could be connected[X][Y] as above, but with a bit set for every square between
squares X and Y.  OR this with occupied squares and if you get a non-zero
value, there is something "blocking" the connection...

If you didn't ask either of those, ask again and I'll try again.. :)




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.