Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: MTD(f) and Wikipedia

Author: Vasik Rajlich

Date: 05:55:18 01/20/06

Go up one level in this thread


On January 19, 2006 at 15:01:04, Joachim Rang wrote:

>Hi,
>
>after a question below regarding the "superiority" of MTD(F) and the article on
>Wikipedia about that I decided to modify the entry and added a sentence in which
>I question the "superiority" of MTD(f) over PVS since it has "practical issues".
>Naturally some guys over in Wikipedia now want to see proof of my statement and
>want to know what kind of practical issues there really are. So I have two
>questions:
>
>1.) Would you support the statement that MTD(F) is _not_ superior to PVS and
>while save in some circumstances a few % of nodes has "practical issues" which
>make it a less desirable choice?
>
>2.) Could you (briefly) name some of the "practical issues"?
>
>regards Joachim
>
>P.S.: If someone feels encourage to reformulate the article on MTD(F) and
>Negascout (PVS) more knowledgeable please feel free to do so. ;-)

Joachim,

you've got the perfect guy to ask on your team - Fabien knows this stuff like
the back of his hand.

The simplest way to summarize the practical issues is that you don't have true
search bounds during node visits. Let me give an example:

[D] r2q1r2/pp1n1ppk/2b1p3/N1ppP2p/3P4/2P4N/PP3PPP/R2Q1RK1 b - - 0 1

We want our search to understand that 1. .. Qxa5 is losing here. Now, to make
the illustration as simple as possible, let's assume the following:

1) We are doing a material-only search
2) We have a quiescence search of captures only
3) We use no extensions/reductions

Finally, in our hypothetical search, we are using MTD (f) and use null move
"normally", ie. it only has to fail high.

So, at iteration == 7, we start by looking (at the root) for a score of -1 (ie.
one pawn advantage for black), and we succeed:

move           node type   depth remaining
----           ---------   ------
1. .. Qxa5     fail high   6
2. Qxh5+       fail low    5
2. .. Kg8      fail high   4
3. Ng5         fail low    3
3. .. null     fail high   0

We likewise succeed looking for a score of -2 with the first move 1. .. Qxa5,
while failing looking for a score of -3. So, 1. .. Qxa5 is the move, and -2 the
score.

Of course, in a PVS search, iteration == 7 would be enough to avoid 1. .. Qxa5,
because after 1. .. Qxa5 2. Qxh5+ Kg8 3. Ng5 we are not yet doing a null-window
search and hence won't allow a null move. (Or allow it only if it fails high
above the full root upper bound.)

If you think about the problem, it is that during the MTD (f) search, when we
reached the node after 1. .. Qxa5 2. Qxh5+ Kg8 3. Ng5, we had no idea that this
was going to be the critical node whose score would eventually become the final
search score. This is the so-called "true bound information" which MTD (f) takes
away from you. In other words, in MTD (f), you don't know what the important
nodes are until you have finished the entire search.

BTW - as you can probably guess, I haven't totally written off these null-window
type tricks, they have their uses. Rybka WinFinder 1.0 uses a 99% MTD (f)-type
search, and the latest Rybka versions (ie. Beta 10 & 11) are using some pretty
wild null-window-search ideas, you might be able to figure them out a bit from
playing around.

Vas




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