Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: algorithm question

Author: Gerd Isenberg

Date: 00:15:05 09/10/02

Go up one level in this thread


On September 10, 2002 at 02:18:55, Gerd Isenberg wrote:

>On September 09, 2002 at 22:58:54, Robert Hyatt wrote:
>
>><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?"
>
>No, sorry for the misapprehension by my unclear question. I was looking for a
>"king path" through an "allowed"-set, eg. like finding a bottleneck-path in pawn
>endings. See Steffans answer about the "floodfill"-algorithm.
>
>Eg. with following "allowed"-bitboard (see Vincents post):
>
>0x18201e010911221c
>
>0 0 0 1 1 0 0 0  18
>0 0 0 0 0 1 0 0  20
>0 1 1 1 1 0 0 0  1e
>1 0 0 0 0 0 0 0  01
>1 0 0 1 0 0 0 0  09
>1 0 0 0 1 0 0 0  11
>0 1 0 0 0 1 0 0  22
>0 0 1 1 1 0 0 0  1c
>^a0
>
>Is there a "1-connection" or king path from d4 to d8?
>
>One drawback of the recursive algorithm i mentioned, is the order traversing
>bits from LSB to MSB and therefore not necessarily looking for "shortest" path
>if there a more alternatives for the king to walk.
>
>eg.: from d4 to d8
>
>0 0 0 1 1 0 0 0  18
>0 0 0 0 0 1 0 0  20
>0 1 1 1 1 0 1 0  5e
>1 0 0 0 0 0 0 1  81
>1 0 0 1 0 0 0 1  89
>1 0 0 0 1 0 1 0  51
>0 1 0 0 0 1 0 0  22
>0 0 1 1 1 0 0 0  1c
>
>
>>
>>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.. :)
>
>Thanks again, Bob, use already several 64*64-arrays. One bitboard array with all
>bits set "between" two squares on same ray - or an other with 8bit-values i call
>Uniform Distance Relationship:
>
>rankdist ::= absolute rank distance
>filedist ::= absolute file distance
>distance ::= the maximum of rankdist and filedist
>minidist ::= the minimum of rankdist and filedist
>
>Bit 765 - distance
>Bit 4   - rankdist == filedist
>Bit 321 - minidist * (rankdist != filedist)
>Bit 0   - set if both squares on opposite color
>

a bit confused today, not Uniform but Unique Distance Relationship:

udr[0]
  16  33  64  97 128 161 192 225
  33  48  67  98 131 162 195 226
  64  67  80 101 132 165 196 229
  97  98 101 112 135 166 199 230
 128 131 132 135 144 169 200 233
 161 162 165 166 169 176 203 234
 192 195 196 199 200 203 208 237
 225 226 229 230 233 234 237 240

 x10 x21 x40 x61 x80 xA1 xC0 xE1
 x21 x30 x43 x62 x83 xA2 xC3 xE2
 x40 x43 x50 x65 x84 xA5 xC4 xE5
 x61 x62 x65 x70 x87 xA6 xC7 xE6
 x80 x83 x84 x87 x90 xA9 xC8 xE9
 xA1 xA2 xA5 xA6 xA9 xB0 xCB xEA
 xC0 xC3 xC4 xC7 xC8 xCB xD0 xED
 xE1 xE2 xE5 xE6 xE9 xEA xED xF0

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.