Author: Robert Hyatt
Date: 08:44:32 07/08/04
Go up one level in this thread
On July 08, 2004 at 10:52:54, Stuart Cracraft wrote:
>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
One fatal flaw. This will produce a set of values that will optimize your
results against a test set. But that's not the same thing as producing a set of
values that will optimize your results in actual OTB games.
This is a common mistake.
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.