Computer Chess Club Archives




Subject: Re: Couple of chess programming questions

Author: Vincent Diepeveen

Date: 10:36:13 09/10/02

Go up one level in this thread

On September 10, 2002 at 13:11:02, Dann Corbit wrote:

>On September 10, 2002 at 12:07:37, Vincent Diepeveen wrote:
>>>(3) Reading Aske Plaat's search & re-search paper, it really seems like mtd(f)
>>>is something of a magic bullet.  But I note it seems that more programs don't
>>>use it than do (for example Crafty).  What is wrong with mtd(f) which Plaat
>>>doesn't say?
>>There is nothing wrong with it. However a softwareprogram must have certain
>>conditions to let it work well (in hardware other issues play a role)
>>  a) it must be a static evaluation with a small granularity;
>>     if pawn=32 it will work great, if pawn=1000 like in DIEP it won't
>>     work at all, other things aren't interesting then.
>I have found this to be true also with experiments, and the reason is obvious.
>The MTD(f) algorithm basically does a binary search between two bounds (on
>average -- it might be faster or slower in individual cases).  If the interval
>varies from 3276700 to -327600 you have between 22 and 23 searches to resolve
>it.  If the interval varies from  3276 to -3276 you have between 12 and 13
>searches to resolve it.
>Therefore, you have a paradox.  The more accurately you search, the slower
>MTD(f) will become.  I can't see any solution to it, unless you use progressive
>accuracy to quickly narrow the search.  If you went to long double accuracy in
>your evaluation function, it will take a very long time to resolve the search
>with MTD(f), unless you double the accuracy with each iteration.  So for the
>first search, only (ugh) one significant digit is used.  Then two digits of
>accuracy, then 4, etc.

Exactly, but i feel by far the biggest problem of MTD is its
worst case behaviour. In difficult positions i see SOS needs sometimes
40 researches at each ply, It takes like 10 minutes to get to the
next ply.

of course the average search depth is still ok then, but compare next
a program A getting next search depths

Difficult moves are move  11,14,19 :

movenr searchdepth
9         14
10        14
11        12
12        17 (recapture)
13        15
14        13
15        16
16        17
17        16
18        15
19        12 (had mispredicted move)

The above is typical behaviour for SOS

Now compare that with something that gets 13 ply at moves 11 and 19
and 14 or 15 at the other positions.

Worst case behaviour, of course majority of people posting here
has never played himself last 10 years a tournament, completely
opposite to Rudolf Huber.

Ask him after SOS-DIEP world champs 2002. I remember that
the 2 big mistakes in the game SOS had a very small search
depth, or no clue.

It was simply researching and researching and researching and researching.
I do not understand why no one ever mentions 'worst case behaviour'.

Best regards,

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