Author: Stuart Cracraft
Date: 07:52:54 07/08/04
Enclosed please find code that can be used to brute-force find
the optimal settings given suitable test cases (position test,
self-test, ICS test) for a reasonably small range of settings
on a chess program (or any program.)
For me, fine-tuning has always been a pain in the *rse and was
one resaon why I abandoned my last program a few years ago. It
just seemed too damn boring to hand-tune and we are after-all
using computers which are supposed to save manual effort.
I used the enclosed code last night to optimize across the following
settings in my program:
transposition table
null move R = 2 with verification
compiler optimization
futility in quiescence search
futility in main search
pawn extensions to 6th and 7th ranks
recaptures
check extensions in main search
check extensions in quiescence search
The run was about 10 hours and against a series of 140 test positions
and had to be terminated a little early due to not putting in a fudge
factor for the overshoot on my time algorithm. This is now factored in
within the calling script. Originally there were 256 combinations of the above
settings, so I searched about 75% of the search space (190) before terminating.
Results ranged from from 63% correct to 24% correct. The run took about
10 hours while I slept. Sure beats manual-tuning. The winner's subset
of the above feature set are listed below.
A calling script (a QA of sorts) asks for the total time of the
test and how many seconds per position. It then figures out how many
positions can be tested per instantiation of the possible combinations
using the program below, subtracts off a fudge factor that corrects for
a time issue in my program, and fires off the run. At the end, the log file
can be examined to find the winning combination.
The winning combination was
transposition table
null move R = 2 with verification
compiler optimization
futility in quiescence search
pawn extensions to 6th and 7th ranks
check extensions in quiescence search
(I did not optimize for other settings of R nor without verification
but the code does not preclude this however I'd have to make my
null move and null move with verification independent rather than
dependent compiler settings (i.e. #ifdef NULLMOVE, #ifdef VERIFYNULLMOVE).
Right now, I have to include both if I want verify null move and that
is counter to the style of the combo program and conditional compilation.)
Note that discarded were:
recapture
check extensions in the main search
The winning combination represents the best "team" of settings producing
the best result.
I feel fairly good that this code can be included in any program
or to assist any program with minor tweaks to brute-force across
a manageable search space to find the best settings given the
environment of the test itself which is the fitness factor. For larger
search spaces such as evaluation terms, use genetic algorithms /
evolutionary computing, TDleaf, or the Deep Blue / Deep Thought
style of regression against high quality games. Oh, be sure to use
a fast computer. Your results will be more meaningful.
The code assumes that you can generate a specific version of a
chess program with a combination of settings from the command line or by
including a set of strings within a configuration file that would determine
the features used within the program and that you can run this and other
versions of the program independently against test suites, self play,
etc. and collect up the results and tabulate. The program does not
include that since those are specific to your environment.
Here's the code. Call with "combo a b c" (or combo a b c d, etc.)
The code combines stuff from GNU Chess, Crafty, an idea I once
read, and some other things. There may be a simpler way to do it
but I couldn't find it pre-prepared on the net.
#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.
An assumption of the code is that your implementation of the
conditional features is good. If your implementation of the
RECAPTURE algorithm is lousy, well, of course it won't be
included. So you get to spend more time on individual
implementation rather than hand-tuning and balancing, the
former being a lot more fun in my book.
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.