Bitboard question

[Gerd Isenberg]

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

[Gerd Isenberg]

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!

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.

Thanks,
for the popcount see
http://aggregate.org/MAGIC/#Population% ... es%20Count)
from
http://dynamo.ecn.purdue.edu/~hankd/SWAR/

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.

Thanks,
Gerd

[Jean-Francois Romang]

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];

Uri

How do you compute pawnDblAttacks ?
Something like
pawnDblAttacks[LIGHT]=FillUpBoard(pawnattacksAH[LIGHT])
& 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]

Mhhh, finally I found the answer here :
http://www.stmintz.com/ccc/index.php?id=271102

Thanks Gerd & Uri...your posts are helping newcommers like me 4 years after