Author: Ernst A. Heinz
Date: 13:15:48 10/06/98
Go up one level in this thread
On October 06, 1998 at 15:06:32, John Coffey wrote:
>
>What if you want to know who has the greatest mobility? (i.e. the most
>number of legal moves) You would have to count bits would you not?
>Is there a fast way to count bits by have table look ups? (i.e.
>take 16 bits at a time and look up the bit count in a table?)
Next quote from my article about "How DarkThought Plays Chess" as published
in the ICCA Journal 20(3) and available electronically on the WWW page of
"DarkThought" at URL <http://wwwipd.ira.uka.de/Tichy/DarkThought/> ...
[John, I think you should read the article as it may be of interest for you.]
*******************************************************************************
Bitboard Infrastructure
DARKTHOUGHT makes extensive use of bitboards stored as 64bit unsigned
integers where each bit represents a square of the chess board numbered
from a8 = 63 to h1 = 0. Because the bit length of integers differs between
compilers, machines, and operating systems, DARKTHOUGHT defines a set
of portable data types like unsigned 8, ..., unsigned 64 that are
automatically mapped to the appropriate types of the target platform (e.g.
unsigned 64 defaults to unsigned long long in GNU C).
In order to simplify the handling of bitboards, DARKTHOUGHT contains an
abundant collection of functions and macros that provide efficient
implementations of all the needed bitboard operations. Beside the basic
bitwise AND, OR, XOR etc. the collection includes cascaded combinations
thereof because they are frequently used and may even be executed in one
cycle on some machines. The expression (x & ~y), for instance,
corresponds to a single DEC Alpha instruction. Other important bitboard
operations enjoy marvelously simple yet non-obvious formulations due to the
wonders of binary subtraction and the two's-complement. Two famous
members of this class are the expressions (b & -b) which clears all but the
least significant 1-bit of a bitboard and (b & (b - 1)) that clears only the
least significant 1-bit.
Unfortunately, the central find-bit and population-count operations have
higher algorithmic complexity. Although a few CPUs like Motorola
PowerPC, Sun UltraSparc and the forthcoming DEC Alpha-21264 feature
instruction-level support of these operations, most current machines still
require software implementations. The efficiency of the implementations in
terms of speed and memory consumption is of crucial importance for
bitboard-based chess programs because it tends to limit their overall
performance. In this respect, the short expression for clearing the least
significant 1-bit gives rise to a neat formulation of an iterative
population-count function.
unsigned int iterative_popcount(unsigned_64 b) {
unsigned int n;
for (n = 0; b != 0; n++, b &= (b - 1));
return n;
}
If the given bitboard contains few 1-bits, the loop terminates quickly thus
making this short and easily inlinable function run fast. Otherwise,
DARKTHOUGHT prefers the following non-iterative formulation that stems
from the well-known ``Hacker's Memory'' collection of programming tricks.
It performs better than intuitive methods with lookup tables because the
tables get either too large or need too many lookups.
#define m1 ((unsigned_64) 0x5555555555555555)
#define m2 ((unsigned_64) 0x3333333333333333)
unsigned int non_iterative_popcount(const unsigned_64 b) {
unsigned_32 n;
const unsigned_64 a = b - ((b >> 1) & m1);
const unsigned_64 c = (a & m2) + ((a >> 2) & m2);
n = ((unsigned_32) c) + ((unsigned_32) (c >> 32));
n = (n & 0x0F0F0F0F) + ((n >> 4) & 0x0F0F0F0F);
n = (n & 0xFFFF) + (n >> 16);
n = (n & 0xFF) + (n >> 8);
return n;
}
The idea of this population-count trick can also be applied to the find-bit
problem yielding a find-function without any memory accesses.
Unfortunately, however, this find-bit function is slower than fine-tuned table
lookups. As executed by DARKTHOUGHT the lookups generate negligible
memory traffic and compile to roughly 15 machine instructions on a DEC
Alpha while relying on the conditional data-move capabilities of modern
CPUs. This clever find-bit implementation further exploits the fact that the
number of the least significant 1-bit of a bitboard is equal to the number of
the most significant 1-bit of the bitboard xor'ed with itself minus one:
FIND LSB(b) = FIND MSB(b ^ (b - 1)).
*******************************************************************************
=Ernst=
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.