Author: Zach Wegner
Date: 12:12:49 02/19/06
Go up one level in this thread
On February 19, 2006 at 11:25:40, Gerd Isenberg wrote:
>... or serializing bitboards direction wise.
>
>I actually use fillbased disjoint attack sets per sliding piece for all four
>straight (rook, queen) directions (east, south, west, north) and four diagonal
>(bishop,queen) directions (ne, se, sw, nw).
>
>Each straight direction for all 64 source squares have 224 possible none empty
>target sets (same number as the number unique rook moves in one direction).
>
>For instance a rook on a1 has the maximum of 7 east target sets:
>h8 h1 a1 n
>0...11111110 7
>0...01111110 6
>0...00111110 5
>0...00011110 4
>0...00001110 3
>0...00000110 2
>0...00000010 1
>
>Each diagonal direction for all 64 source squares have 140 possible none empty
>target sets. There are enough 64-bit De Bruijn (and even more none De Bruijn)
>constants to implement a "bitscanlike" hash-functions to get unique indices:
>
>uniqueIndex ::= (straightAttacks*DeBruijn) >> (64-10); // 224 to 1024
>uniqueIndex ::= (diagonalAttacks*DeBruijn) >> (64-9); // 140 to 512
>
>The idea to to have 140 or 224 pointers (or indices) in appropriate lookup
>tables. They point to structures containing the number of target squares (up to
>7) and arrays with the squares itself ("to" as well as "from").
>
>The preinitialized square lists should sorted by distance, so that be the first
>(or last) square is a possible capture target.
>
>Pseudo code for east-diretion:
>
>BB east = getEastAttacks(rook) & ~ownPieces;
>uint idx = (east*0x02432bd4fcd16ec7)>>54;
>copySquares(target, eastLookup[idx].pSquares, eastLookup[idx].n);
>
>Isn't that great?
>
>Cheers,
>Gerd
Very interesting. I have been looking for some way to get rid of bit-traversing
for so long. First off, some questions, then some comments.
I understand that there is one DeBruijn for each direction. How are these
calculated, besides brute force? Would you mind explaining DeBruijn to me in
more depth? I see how they work when multiplied by a power of two, but how on
earth do you get the result to be unique for an arbitrary number of bits set?
I notice that you mention non-empty. Could you change the DeBruijn to output
something greater than 0 for all real attack maps, then you could also skip a
conditional when there are no attacks in that direction (which is probably
pretty often).
I used to use rotated bitboards. I don't like keeping all the tables and
bitboards around, but it allowed for some neat things, and it was fast. One
thing I liked was serialized attack tables. I wasn't able to serialize move
generation effectively because of the capture squares, but with attack tables,
you attack friendly pieces, so its a nice compact loop.
I like using bitboards, but haven't been able to make them fast without
rotation. One idea I tried is to find the last square attacked on a ray, compute
the distance, and loop back towards the piece moving, just adding a step value.
This however, is much slower than rotated, and not very practical.
This technique is very intriguing though. It serializes bitboards after friendly
pieces are removed, so it is practical for move generation. How do you compute
the bitboards exactly? You can fill, but you have to do it in each direction,
and if you do pieces together, then you have to somehow "demux" them. What if
you combined them with rotated bitboards, do you think that could create an
additional speedup?
Anyways, thanks very much for this and all of the other great ideas you post
here. I love reading them.
Zach
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.