Author: Andrew Williams
Date: 14:41:49 08/16/99
Go up one level in this thread
On August 16, 1999 at 16:37:09, Thorsten Czub wrote:
>Uli said this it could be anmon uses the
>MTD ("best first") algorithm .
>he says this comes out of the Cilkchess-corner (Aske Plaat); also other
>programs (maybe SOS use it).
>
>Can somebody explain this to us non-programmers. would be interesting
>for me because i am using programs for mail-chess and the better
>i do understand the programs methods the better i can use them in for
>analysing ...
Hi Thorsten,
Normal alphabeta approaches work by establishing an upper bound and a
lower bound on the score for a position. They then search in order to
narrow these bounds down until they meet. This point where the upper and
lower bounds meet is the score for the position. MTD achieves basically
the same thing (establishing a score for a position) in a different manner.
MTD proceeds by making successive "guesses" at the score for the position.
MTD uses an alphabeta search to answer the question "is the score for this
position higher or lower than my guess?". If the guess is too low, it is
increased and the question is asked again. If the guess was too high, the
guess is reduced a bit and the test is carried out again.
MTD stands for Memory Test Driver. "Test" means test the score for the
position to see if it's higher or lower than the guess. Memory is the hash
table, which is required to support the multiple searches. The Driver is
the approach taken to ensure that the guesses eventually converge on the
actual score for the position. In chess I've only seen the variant of MTD
called MTD(f). I think the f stands for "first guess". The idea is that you
use something sensible, like the score from the previous search, as the first
guess - in general, the more accurate your first guess the less time will be
required to find the actual score.
Having said all this, I'm afraid it doesn't answer your question. There's no
reason why the emitted scores from an MTD program should progress more smoothly
than those from a PVS implementation. The reason might be that AnMon's eval
doesn't include any large terms (I think Vincent might suggest this). But the
only way to be sure is to ask the author. If you email him, try to encourage
him to answer here. I'm sure I'm not the only one who would be interested to
hear his response.
Regards
Andrew
PS There's a link to Aske Plaat's paper on the links page of the CCR.
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.