Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Couple of chess programming questions

Author: Omid David

Date: 10:59:26 09/10/02

Go up one level in this thread


On September 10, 2002 at 13:36:13, Vincent Diepeveen wrote:

>On September 10, 2002 at 13:11:02, Dann Corbit wrote:
>
>>On September 10, 2002 at 12:07:37, Vincent Diepeveen wrote:
>>[SNIP]
>>>>(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,
>Vincent

Has anyone compared NegaScout vs. MTD(f) on a set of tactical test suites? It
seems to be interesting to test the behavior of MTD(f) in real complicated
positions.

Omid.




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.