Author: Robert Hyatt
Date: 10:33:38 04/14/04
Go up one level in this thread
On April 14, 2004 at 03:30:22, Dann Corbit wrote:
>I decided to toss an MTD(f) search into TSCP, and I've got something wrong, but
>I can't quite see what it is.
There is a lot more to do.
1. you need to modify the hash table to store 2 bounds, not 1.
2. the search must be fail-soft. TSCP isn't.
3. PV has to be yanked from the hash table and that makes it flakey at times as
has been discussed many times. There is another way to get the PV, but it is a
special case solution only for mtd...
4. the convergence has to be accelerated. IE on a fail high searching v and
v+1 won't cut it.
IE this is not a "drop in and go" it is a "rewrite and test" thing to do. :)
>
>Can one of the MTD(f) Guru's point out where I went off? This is the stuff I
>modified from search.c, and you just define MTDF to compile it for MTDF...
>
>I'm sure that it is something simple.
>
>/*
> * SEARCH.C
> * Tom Kerrigan's Simple Chess Program (TSCP)
> *
> * Copyright 1997 Tom Kerrigan
> */
>
>
>#include <stdio.h>
>#include <string.h>
>#include "defs.h"
>#include "data.h"
>#include "protos.h"
>
>
>/* see the beginning of think() */
>#include <setjmp.h>
>jmp_buf env;
>BOOL stop_search;
>
>
>
>/* MTD(f) is an alternative search to pvs */
>int mtdf(int f, int depth)
>{
> int beta;
> int smallest = -10000;
> int greatest = 10000;
>
> do {
> if (f == smallest)
> beta = f + 1;
> else
> beta = f; /* beta is starting with a first best guess */
> f = search(beta - 1, beta, depth);
>
> if (f < beta)
> greatest = f;
> else {
> int j;
> smallest = f; /* performs a cut-off */
> if (smallest >= greatest) {
> pv[ply][ply] = gen_dat[depth].m;
> for (j = ply + 1; j < pv_length[ply + 1]; ++j)
> pv[ply][j] = pv[ply + 1][j];
> pv_length[ply] = pv_length[ply + 1];
> }
> }
> } while (smallest < greatest);
> return f;
>}
>
>/* think() calls search() iteratively. Search statistics
> are printed depending on the value of output:
> 0 = no output
> 1 = normal output
> 2 = xboard format output */
>
>void think(int output)
>{
> int i,
> j,
> x = 0;
>
> /* try the opening book first */
> pv[0][0].u = book_move();
> if (pv[0][0].u != -1)
> return;
>
> /* some code that lets us longjmp back here and return from think() when
> * our time is up */
> stop_search = FALSE;
> setjmp(env);
> if (stop_search) {
>
> /* make sure to take back the line we were searching */
> while (ply)
> takeback();
> return;
> }
> start_time = get_ms();
> stop_time = start_time + max_time;
>
> ply = 0;
> nodes = 0;
>
> memset(pv, 0, sizeof(pv));
> memset(history, 0, sizeof(history));
> if (output == 1)
> printf("ply nodes score pv\n");
> for (i = 1; i <= max_depth; ++i) {
> follow_pv = TRUE;
>#ifdef MTDF
> x = mtdf(x, i);
>#else
> x = search(-10000, 10000, i);
>#endif
> if (output == 1)
> printf("%3d %9d %5d ", i, nodes, x);
> else if (output == 2)
> printf("%d %d %d %d",
> i, x, (get_ms() - start_time) / 10, nodes);
> if (output) {
> for (j = 0; j < pv_length[0]; ++j)
> printf(" %s", move_str(pv[0][j].b));
> printf("\n");
> fflush(stdout);
> }
> if (x > 9000 || x < -9000)
> break;
> }
>}
This page took 0.01 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.