Computer Chess Club Archives




Subject: Re: Couple of chess programming questions

Author: Dann Corbit

Date: 14:08:23 09/10/02

Go up one level in this thread

On September 10, 2002 at 16:18:35, Gian-Carlo Pascutto wrote:

>On September 10, 2002 at 15:35:48, Dann Corbit wrote:
>>On September 10, 2002 at 14:19:24, Gian-Carlo Pascutto wrote:
>>>On September 10, 2002 at 13:11:02, Dann Corbit wrote:
>>>>The MTD(f) algorithm basically does a binary search between two bounds (on
>>>>average -- it might be faster or slower in individual cases).
>>>MTD(n,f) _as descibred by Plaat_ does not do a binary search.
>>>It will take a first guess, and then always fail in the same
>>>direction till it converges.
>>Normally, assuming your first guess is a very good one.  The idea is still
>>roughly the same.  Let's suppose that the first guess is exactly right -- then
>>the initial second guess (normally negative infinity)
>This is not MTD(n,f). As I already said, you seem to have something
>else in mind.

function MTDF(root : node_type; f : integer; d : integer) : integer;

g := f;
upperbound := +INFINITY;
lowerbound := -INFINITY;

if g == lowerbound then beta := g + 1 else beta := g;
g := AlphaBetaWithMemory(root, beta - 1, beta, d);
if g < beta then upperbound := g else lowerbound := g;

until lowerbound >= upperbound;
return g;

Since it searches until upperbound and lowerbound converge, evidently, they can
exchange roles.  This is the binary search analog that I am referring to:
"if g < beta then upperbound := g else lowerbound := g;"

I think we are not on the same page for some reason.  Or (more likely) I am
simply not expressing myself clearly.

This page took 0.02 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.