Computer Chess Club Archives




Subject: Building the Principal Variation in MTD(f) searches

Author: Andrew Williams

Date: 06:52:08 07/18/99

My program, PostModernist, uses MTD(f) rather than the more common PVS.
MTD(f) proceeds by repeatedly probing the search space, asking the question
"is the score for this position higher or lower than guess?", until it has
homed in on the correct score. Each probe is a call to a normal alphabeta
search, with a window of 1 (eg alpha=g-1, beta=g). This works very well,
but there is a problem related to retrieving the Principal Variation.
In a normal alphabeta search, the PV is updated whenever a position is
encountered whose score is > alpha and < beta. Obviously, when the search
window is always 1, this never occurs.

The approach I use, therefore, is to just retrieve the Principal Variation
using the "best move" entries in the hash table. This works OK, but there
is the potential difficulty that positions towards the end of the search
(where drafts are low) are prone to being overwritten by positions further
up the tree. This is especially problematic with positions written out
during the qsearch. This means that my PVs are often truncated before the
qsearch, which can make debugging rather difficult. Also, I was hoping to
do some simple automatic tuning of PM over the Summer (assuming I find
time), but all the methods I can think of need access to the position at
the end of the PV from which the backed-up score was generated.

I have an idea about how to fix this, which involves creating an extra
hash table. Essentially, before each iteration at the root, I would go
through every move at the root and stuff the "PV" from each one into this
"PV hash table". Whenever a node is encountered in the tree which is also
in this extra table, I would update the extra table at the same time as the
main HTs. Suffice it to say, I'll have to give this a lot more thought
before trying it.

So the question is, has anyone who is using MTD(f) got any ideas on how
to retrieve the PV? Of course, I'm also interested in ideas/opinions from
those who aren't using MTD(f) - even if the opinion is "you should switch
to PVS"!



PS  A good description for MTD(f) is

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