Author: Dann Corbit
Date: 16:53:36 05/31/02
Go up one level in this thread
On May 31, 2002 at 18:50:18, Omid David wrote:
>I forgot to change "negascout" to "AlphaBeta" in 7th line for better
>illustration. Here is the correction:
>
>int AspWin(int estimate, int delta, int depth)
>{
>int alpha = estimate - delta;
>int beta = estimate + delta;
>int best;
>
>best = AlphaBeta(alpha, beta, depth);
>
>/* re-search */
>if(best <= alpha)
>best = AlphaBeta(-10000, beta, depth);
>else if(best >= beta)
>best = AlphaBeta(alpha, 10000, depth);
>
>/* is there any better way to handle this very rare case? */
>if(best >= beta || best <= alpha)
>best = AlphaBeta(-10000, 10000, depth);
>
>return best;
>}
Gerbil does this:
// - - - - - - - - - - - - - - - - - - -
//
// Gerbil
//
// Copyright (c) 2001, Bruce Moreland. All rights reserved.
//
// - - - - - - - - - - - - - - - - - - -
//
// This file is part of the Gerbil chess program project.
//
// Gerbil is free software; you can redistribute it and/or modify it under
// the terms of the GNU General Public License as published by the Free
// Software Foundation; either version 2 of the License, or (at your option)
// any later version.
//
// Gerbil is distributed in the hope that it will be useful, but WITHOUT ANY
// WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
// FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
// details.
//
// You should have received a copy of the GNU General Public License along
// with Gerbil; if not, write to the Free Software Foundation, Inc.,
// 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
//
// - - - - - - - - - - - - - - - - - - -
#include "gproto.h"
#include "engine.h"
#include <stdlib.h>
#ifdef DEBUG
static char const s_aszModule[] = __FILE__;
#endif
// - - - - - - - - - - - - - - - - - - -
// The "Think" function is an important part of the engine. The engine
// thread spends most of its time in here.
// The basic idea is that it will sit in a loop and call the search function
// over and over, each time with one more ply of depth, until the search
// runs out of time. This is called "iterative deepening". One advantage of
// this is is that this is easily interruptable, since the first few plies
// take so little time that you'll always have *some* move to make, even if
// you interrupt after a few milliseconds.
// The most important reason to do iterative deepening is that it's faster
// than just calling the search with some larger final depth. The reason is
// that the PV from the previous iteration is passed along to the subsequent
// iteration. The moves in this PV are searched first. The previous PV is
// probably an excellent line, and alpha-beta is much more efficient if you
// search a good line first, so you end up searching a smaller tree.
// After the search has timed out, it will pass the best move to the
// interface. If the PV was two moves or more long, it will then go into
// "ponder" mode, which means that it will execute the second move in the PV
// on its internal board, and go into an infinite duration think about this
// move. This is called "pondering".
// The the opponent makes the move the program is guessing that they'll make,
// the engine will seamlessly switch from "ponder" mode to "thinking" mode,
// as if the opponent really did make their move immediately after the
// engine's last move.
// It's possible that the opponent may have been thinking a long time on
// their move, and by the time they are done, the engine will have already
// used up its normal time allocation for this move. If that's the case,
// the engine will move instantly.
// If the opponent doesn't make the move the engine is guessing, the search
// will be aborted and a new search started.
// Aborting incorrect pondering, and switching from ponder into think mode if
// the engine guesses the right move, aren't a part of this function, but it
// makes some sense to explain this here.
#define plyMAX 120 // Maximum number of iterations. This seems huge, but it
// is sometimes reached.
void VThink(PCON pcon, TM tmRemaining)
{
Assert(pcon->smode == smodeIDLE);
//
// Set up time-out, and remind myself that I'm not dead.
//
pcon->ss.tmRemaining = tmRemaining;
pcon->fAbort = fFALSE;
pcon->smode = (tmRemaining == tmANALYZE) ? smodeANALYZE : smodeTHINK;
//
// This loop is going to execute at least once. It might execute for the
// whole game, if the program continuously ponders correctly.
//
for (;;) {
char aszMove[32];
char aszPonder[32];
char aszSanHint[32];
PSTE pste = &pcon->argste[0];
int i;
SAN sanHint;
CM cmHint;
CM cm;
int valCur; // Value returned by search.
int valLow; // Alpha-beta search window.
int valHigh;
BOOL f;
pcon->fTimeout = fFALSE; // I'm not timed out yet.
pcon->ss.tmStart = TmNow(); // Record when I started.
if (pcon->smode == // If I'm pondering, I don't set the
smodeTHINK) // time control stuff. This will be
VSetTime(pcon); // handled at the point it's clear
// that I picked the correct move.
pste->ccmPv = 0; // Clear PV.
VSetRepHash(pcon); // Pump game history into rep hash.
if (pcon->smode == smodeTHINK)
VDrawCheck(pcon); // Try to claim appropriate 50-move
// and 3x rep draws before examining
// moves.
//
// During the first 20 moves of the game I will try to find a book
// move. If I find one I will play it.
//
if ((pcon->smode == smodeTHINK) && (pcon->fUseBook) &&
(pcon->gc.ccm < 40) && (FBookMove(pcon, &cm))) {
char asz[16];
BOOL f;
VCmToSz(&cm, asz); // Make book move.
f = FAdvance(pcon, asz);
Assert(f);
VPrSendMove(asz); // I am not going to bother checking for draws
// and mates that occur while in book. If by
// weird chance one of these happens, if
// we're hooked up to the chess server, the
// server might call it.
break;
}
// Increment sequence number. The transposition hash system will
// overwrite nodes from old searches, and this is how it knows that
// this is a new search, rather than just more of the old one.
//
VIncrementHashSeq();
//
// Search the position via iterative deepening.
//
pcon->ss.nodes = 0; // Global node counter.
pcon->ss.nodesNext = 2000; // Time (in nodes) of next callback to
// interface.
valCur = 0;
valLow = valMIN; // Initial window is wide open.
valHigh = valMAX;
for (i = 0; i < plyMAX; i++) {
pste->valAlpha = valLow;
pste->valBeta = valHigh;
pste->plyRem = i;
pcon->ss.plyDepth = i + 1;
VSetPv(pcon); // This remembers the current PV so that the
// search can search its elements first.
valCur = ValSearch(pcon, pste);
if (pcon->fAbort)
break;
if (pcon->fTimeout)
break;
//
// This checks for a result outside the window, and if it finds
// one it re-searches with the window wide open.
//
if ((valCur <= valLow) || (valCur >= valHigh)) {
if (valCur <= valLow) // Record a fail-low (fail-high is
// handled inside "ValSearch").
//
// This function needs the root moves generated, and the
// are, because "ValSearch" does it.
//
VDumpPv(pcon, pcon->ss.plyDepth, valCur, '-');
pste->valAlpha = valMIN;
pste->valBeta = valMAX;
VSetPv(pcon);
valCur = ValSearch(pcon, pste);
if (pcon->fAbort)
break;
if (pcon->fTimeout)
break;
}
// Mated now or this move mates, drop out of here.
//
if ((valCur == valMATE - 1) || (valCur == -valMATE))
break;
//
// Depth-restricted search. Check for "timeout", meaning target
// depth met.
//
if ((pcon->smode == smodeTHINK) &&
(pcon->tc.plyDepth > 0) &&
(pcon->ss.plyDepth >= pcon->tc.plyDepth)) {
pcon->fTimeout = fTRUE;
break;
}
// Set up for next iteration, which will use a window centered
// around the current position value.
//
valLow = valCur - 50;
valHigh = valCur + 50;
}
// If abort or doing pondering, I'm done, because I don't need to
// make any moves or set up the next search.
//
// NOTE: None of the stuff below happens in analysis mode, because
// the next line exits the routine! This means that results won't
// be posted (draws, mates, etc.) if the game is in analysis mode,
// which seems to be the right thing to do according to Tim Mann,
// circa 26-Apr-2001 on the Yahoo chess engines mailing list.
//
if ((pcon->fAbort) || (pcon->smode != smodeTHINK))
break;
//
// If there is a move in the first element of the PV, I can make it.
// I don't make it now, because I want to look at the second element
// of the PV for a pondering move, and if I execute the first move,
// it will destroy the PV.
//
aszMove[0] = aszPonder[0] = '\0';
if (pste->ccmPv >= 1)
VCmToSz(&pste->argcmPv[0], aszMove);
if ((pste->ccmPv >= 2) && (pcon->fPonder)) {
VCmToSz(&pste->argcmPv[1], aszPonder);
cmHint = pste->argcmPv[1];
}
// As of this point, I have move to make in "aszMove", move to ponder
// in "aszPonder". If I can't move, or I can't ponder, these strings
// are nulled out.
//
// Check to see if I'm mated or stalemated, which will be the case
// if I can't move.
//
if (aszMove[0] == '\0') {
if ((!pcon->fTimeout) && (valCur == -valMATE)) {
VMates(pste->coUs ^ 1);
break;
}
VStalemate(pste->coUs);
break;
}
// Make the move.
//
f = FAdvance(pcon, aszMove);
Assert(f);
VPrSendMove(aszMove);
//
// The score from the last search might indicate that this is mate.
//
if ((!pcon->fTimeout) && (valCur == valMATE - 1)) {
VMates(pste->coUs ^ 1);
break;
}
// Check for 50-move or 3x repetition draws.
//
if (pcon->smode == smodeTHINK)
VDrawCheck(pcon);
//
// Check to see if I stalemated my opponent, and report the result as
// appropriate.
//
if (FStalemated(pcon))
VStalemate(pste->coUs ^ 1);
//
// If I can't ponder, I'm done, otherwise set up pondering and loop
// back around.
//
if (aszPonder[0] == '\0')
break;
//
// Get the algebraic so I can send a hint.
//
VGenMoves(pcon, // Pseudo-legal is okay, because the SAN
pcon->argste, fFALSE); // routines can handle it.
VCmToSan(pcon, pcon->argste, &cmHint, &sanHint);
VSanToSz(&sanHint, aszSanHint);
strcpy(pcon->aszPonder, aszPonder);
//
// Execute the move. I'm now one move ahead of the game, which is
// tricky. After that, send the hint move.
//
f = FAdvance(pcon, aszPonder);
Assert(f);
if (pcon->fPost)
VPrSendHint(aszSanHint);
pcon->smode = smodePONDER;
}
// If I broke out, and I'm in ponder mode, back up the search and pretend
// that I never pondered. I could do some sneaky stuff having to do with
// remembering the move that would have been made if the pondered search
// had been converted into a normal search soon enough, but this would be
// annoying to do and it's kind of rare and pointless.
//
if (pcon->smode == smodePONDER)
VUndoMove(pcon);
pcon->smode = smodeIDLE;
}
// - - - - - - - - - - - - - - - - - - -
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.