Computer Chess Club Archives


Search

Terms

Messages

Subject: sliding move generation idea with bitboards

Author: Gerd Isenberg

Date: 08:25:40 02/19/06


... 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



This page took 0.06 seconds to execute

Last modified: Thu, 07 Jul 11 08:48:38 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.