Author: Stuart Cracraft
Date: 18:37:34 07/07/04
Go up one level in this thread
On July 07, 2004 at 19:54:30, GuyHaworth wrote:
>
>These are not difficult algorithms to concoct or find in the literature.
>
>If you want to go to 'the bible', it's TAOCP by Knuth, see:
>
>http://www-cs-faculty.stanford.edu/~knuth/taocp.html
>
>and scan down to pick up 'pre-fascicle 2a' on 'Generating all n-tuples'
>
>... or maybe there's something in 'Fundamental Algorithms', v1.
>
>
>g
This was actually rather annoying to have to code. The thought of wading
through Knuth and Tom Mix did not appeal. Besides, I don't have Knuth
around and don't like Westerns (or whatever the latest pseudo-code is.)
What is usually offered, or that I could find, didn't do the exhaustive
combinations I need.
I want for objects c, b, a:
c b a
c b
c a
c
b a
b
a
none
or for any number of objects.
The four things that helped were: bit counting code in GNU and Crafty
a suggestion to count in binary, and some binary printing code. This
may be all non-optimal but I couldn't simply find anything with
everything here.
Here's the code. Call with "combo a b c" (or combo a b c d, etc.)
See the end of this email for reasoning
#include <stdio.h>
#define SETBIT(b,i) ((b) |= BitPosArray[i])
#define CLEARBIT(b,i) ((b) &= NotBitPosArray[i])
#define MAXSTRINGS 100
#define MAXSIZESTRING 100
char p[MAXSTRINGS][MAXSIZESTRING];
typedef long long BitBoard;
unsigned char lzArray[65536];
BitBoard BitPosArray[64];
BitBoard NotBitPosArray[64];
#define NBITS 16
void InitLzArray (void)
/***************************************************************************
*
* The lzArray is created. This array is used when the position
* of the leading non-zero bit is required. The convention used
* is that the leftmost bit is considered as position 0 and the
* rightmost bit position 63.
*
***************************************************************************/
{
int i, j, s, n;
s = n = 1;
for (i = 0; i < NBITS; i++)
{
for (j = s; j < s + n; j++)
lzArray[j] = NBITS - 1 - i;
s += n;
n += n;
}
}
static inline unsigned char leadz (BitBoard b)
/**************************************************************************
*
* Returns the leading bit in a bitboard. Leftmost bit is 0 and
* rightmost bit is 63. Thanks to Robert Hyatt for this algorithm.
*
***************************************************************************/
{
if (b >> 48) return lzArray[b >> 48];
if (b >> 32) return lzArray[b >> 32] + 16;
if (b >> 16) return lzArray[b >> 16] + 32;
return lzArray[b] + 48;
}
void InitBitPosArray (void)
/***************************************************************************
*
* BitPosArray[i] returns the bitboard whose ith bit is set to 1
* and every other bits 0. This ought to be faster than doing
* shifting all the time (I think).
* Also compute the NotBitPosArray = ~BitPosArray.
*
***************************************************************************/
{
BitBoard b;
int i;
b = (BitBoard) 1;
for (i = 63; i >= 0; i--, b <<= 1)
{
BitPosArray[i] = b;
NotBitPosArray[i] = ~b;
}
}
void bitsset(int n)
{
register i;
BitBoard b;
b = n;
while (b) {
i = leadz(b);
CLEARBIT (b, i);
printf("%s ",p[64-i]);
}
printf("\n");
}
char *binString(int value);
char *binString(int value)
{
static char bin[17];
int index;
for(index=0;index<16;index++)
{
if(value & 0x8000)
bin[index] = '1';
else
bin[index] = '0';
value = value << 1;
}
bin[16] = 0x00;
return(bin);
}
main(argc,argv)
int argc;
char *argv[];
{
int i;
BitBoard c;
BitBoard d;
d = 0;
for (i = 1; i < argc; i++) {
strcpy(p[i],argv[i]);
}
InitLzArray();
InitBitPosArray();
c = argc-1;
for (i = 1; i <= c; i++) {
d = d | BitPosArray[64-i];
}
for (i = d; i > 0; i--) {
printf("%s ",binString(i));
bitsset(i);
}
printf("%s none\n",binString(0));
}
The point of this code with regards to computer chess is: make your
computer chess program conditionally compilable with #ifdef THIS
or #ifdef THAT for major options options (transposition,
null move, etc.)
Run combo such as
combo "-DTRANSPO" "-DNULLMOVE" "-DASPIRATION" ... etc.
Take the output, strip off the leading column, use the remaining
columns on each line as additional parameters to your C compiler
when compiling your code, to produce a custom version of your code,
run it against a monolithic problem set, iterate across all output
from combo with decent-sized search times and come back in a few
hours or days or weeks and voila you have have an ordered set of
the versions with parameters that produce the best results -- or
substitute games-with-selves instead of problem sets -- or
games-with-FICS/ICS, etc.
Enjoy,
Stuart
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.