Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Question for the MTD(f) experts

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.06 seconds to execute

Last modified: Thu, 07 Jul 11 08:48:38 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.