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.