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"! Thanks. Andrew PS A good description for MTD(f) is http://www.cs.vu.nl/~aske/mtdf.html
This page took 0.11 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.