Bitboard question

Programming Topics (Computer Chess) and technical aspects as test techniques, book building, program tuning etc

Moderator: Andres Valverde

Re: Bitboard question

Postby Gerd Isenberg » 15 Mar 2006, 15:19

Ok, Uri already posted it from CCC archives.

The fill up/down idea was introduced by Steffan Westcott.
The same guy who recently posted the enumeration all subsets of a set algorithm in CCC:

Code: Select all
 subset = 0;
 do {
   // do something with subset
   subset = (subset - set) & set;
 } while (subset);

The parallel prefix Kogge-Stone routine

Code: Select all
BB _NorthFill(BB gen) {
   gen |= (gen <<  8);
   gen |= (gen << 16);
   gen |= (gen << 32);
   return gen;

is identical to the occluded fill with empty board propagator (pro == -1, no blockers).

Code: Select all
BB _NorthOccl(BB gen, BB pro) {
   gen |= pro & (gen <<  8);
   pro  = pro & (pro <<  8);
   gen |= pro & (gen << 16);
   pro  = pro & (pro << 16);
   gen |= pro & (gen << 32);
   return gen;

To get half-isolanis, candidates etc. it makes sense to compute and keep (for a while) six span-sets for all white and black pawns:
Front-span and back-span of all pawns,
front-span and back-span of "east" pawn attacks, and
front-span and back-span of "west" pawn attacks.
This is also nice to get sets of files with halfopen and open-properties.

Those sets might be ored if needed for passed pawns.
A pawn which intersects opposite front-spans is mechanically blocked, otherwise open. A pawn which intersects opposite attacks or front-spans of those attacks has opposite guards and is also not passed even if open. Only if the intersection of a pawn with all front-attacks-spans is empty the pawn becomes a passer.

Particular nice, specially for pawn-endings, is to have precalculated sets of all "squares of the king", indexed by square index of the opposite king and side to move (for the tempo). Thus one needs only one "and" to get a set of all passers "outside the king square".

Gerd Isenberg
Posts: 285
Joined: 31 Jan 2005, 20:31
Location: Hattingen, Germany

Re: Bitboard question

Postby Gerd Isenberg » 19 Mar 2006, 00:33

Alessandro Scotti wrote:
Tord Romstad wrote:That would work, but I am considering to drop the pawn hash table altogether. Some of the bitboard experts claim that bitboards make pawn structure evaluation so fast that there is no need for a pawn hash table.

Hey no objection to this... except for passed pawns I'm considering to drop pawn evaluation altogether! :wink:

Tord Romstad wrote:Where do I find Gerd's routines for this?

This is from Kiwi sources... I think you will find many in this forum and also in the CCC archives...
BTW Gerd told me he's not the original author once, but I got this code from his postings and wouldn't know who else to credit.

for the popcount see ... es%20Count)
SIMD (Single Instruction stream, Multiple Data stream) Within A Register (SWAR) isn't a new idea. Given a machine with k-bit registers, data paths, and function units, it has long been known that ordinary register operations can function as SIMD parallel operations on n k/n-bit field values. For example, a fast population count (number of 1 bits) operation is often implemented using a SWAR reduction algorthm. A larger example is in the 1992 PhD thesis of (my former student) M. Liou, Efficient Algorithms for Fractional Factorial Design Generation, which made extensive use of SWAR techniques to speed-up a class of optimization algorithms... but even that was obscure stuff.

see also

Software Optimization Guide for AMD64 Processors
Page 180 Integer Optimizations
8.6 Efficient Implementation of Population-Count
Function in 32-Bit Mode

The folded bitscan is by Matt Taylor. I did the very slight improvement in bitSearchAndReset by using the common (bb - 1) expression.

Gerd Isenberg
Posts: 285
Joined: 31 Jan 2005, 20:31
Location: Hattingen, Germany

Re: Bitboard question

Postby Jean-Francois Romang » 11 Jun 2006, 15:58

Uri Blass wrote:
Here is one of the post of Gerd from that discussion
He later gave correction for not defendable
from that thread:

notDefendable[WHITE] = pawnBB[WHITE] & ~fillup(pawnAttacks[WHITE]);
Backward pawns:

First we need all squares dominated by sides pawn attacks:

pawnDomination[side] = (pawnDblAttacks[side] & ~pawnDblAttacks[other(side)])
| (pawnAttacks[side] & ~pawnAttacks[other(side)]);

backWard1[WHITE] = notDefendable[WHITE] & (pawnDomination[BLACK] >> 8);
backWard2[WHITE] = backWard1[WHITE] & openPawns[WHITE];


How do you compute pawnDblAttacks ?
Something like
& FillUpBoard(pawnattacksHA[LIGHT]) ?

I cant read the CCC thread from your link, perhaps can someone re-explain the correction for the 'notDefendable' calculation ?

Calculating the pawnfacts actually takes 20% of the total time in my engine (with hashing)...seems too much
Jean-Francois Romang
Posts: 6
Joined: 11 Jul 2005, 21:01
Location: France/Paris

Re: Bitboard question

Postby Jean-Francois Romang » 11 Jun 2006, 18:01

Mhhh, finally I found the answer here :

Thanks Gerd & Uri...your posts are helping newcommers like me 4 years after :D
Jean-Francois Romang
Posts: 6
Joined: 11 Jul 2005, 21:01
Location: France/Paris


Return to Programming and Technical Discussions

Who is online

Users browsing this forum: Bing [Bot] and 6 guests