Author: Stuart Cracraft
Date: 07:10:01 07/09/04
Go up one level in this thread
On July 08, 2004 at 11:44:32, Robert Hyatt wrote:
>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.
I provided the caveat "substitute games-with-selves instead of problem
sets -- or games-with-FICS/ICS, etc." Having a lot of background in
neural nets in financial modeling, I am aware of curve-fitting more than most.
The obvious approach is the last item -- play the games online against
a large number of human players for each combination of the program's
major settings.
I don't know how many games would be required to get a good confidence
level for combination of settings. It is not outlandishly impossible a
number.
Also, I am not so sure that a large test suite wouldn't provide a good
proving ground for a run. I am not arguing in terms of true curve-fitting,
changing the chess program to maximize against the test -- I am
arguing for taking a large test case and running it against all combinations
of the major settings to simply find the best combination to use and then
going from there with other tests including vs. humans, etc.
I think the result would be stronger than most manual approaches for most
programmers. The thought of hand-tuning fills me with ennui. The approach
of Knightcap's group impresses me the most of all (TD(leaf)).
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.