Computer Chess Club Archives


Search

Terms

Messages

Subject: Question for the MTD(f) experts

Author: Dann Corbit

Date: 00:30:22 04/14/04


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.

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.09 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.