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