Computer Chess Club Archives




Subject: Re: QSearch() as PVS() ?

Author: Robert Hyatt

Date: 09:11:41 01/15/04

Go up one level in this thread

On January 14, 2004 at 17:20:46, Filip Tvrzsky wrote:

>On January 14, 2004 at 16:56:20, Anthony Cozzie wrote:
>>On January 14, 2004 at 16:26:42, Ed Trice wrote:
>>>>Have you considered trying MTD(f) instead of PVS?  I am not sure it is any more
>>>>efficient in practice, but it is easier to code, and has the additional benefit
>>>>of making you feel different, original, interesting, intelligent, handsome and
>>>Well Aske Plaat would love to hear that :)
>>>But doesn't MTD(f) trigger a great deal of researches? I remember trying that
>>>once and it bloated the tree.
>>---- opinion mode on ----
>>MTD(f) has two big problems.
>>1, you ponder the wrong move occasionally because your PVs are less accurate.
>>If you are pondering the wrong move 20% of the time that is equivalent to a 10%
>>time loss.
>>2, MTD(f) is at its worst when the score is dropping.  A fail high in MTD(F) is
>>much faster than a fail low (1 child node vs all child nodes).  Unfortunately,
>>this is when you need your search the most: you are in trouble, and you need to
>>make exact moves to win/draw (you might already be lost, but thats just the way
>>it goes).  I remember some Zappa-Gothmog games where Gothmog had been searching
>>8 ply, got in a tight spot, made a 6 ply search, played a huge blunder, and went
>>from -1 to -5 the next move.
>>---- opinion mode off ----
>>Most people that try MTD(f) will give up very fast because it requires a
>>two-limit hash table rather than a bound hash like most people implement.
>I have noticed this in several postings before but still do not follow: why is
>with MTD(f) necessary to store two limits in hash table instead of only one?

Because of how the search works. Since you search the tree multiple times,
sometimes you will fail high at a node, other times you will fail low at the
same node since you are adjusting the initial window each time you re-start the
search.  You need to remember both bounds so that if possible, you can fail high
or low as needed with no searching.  If you bounce around in the tree, and only
store one bound, many times that bound won't help while if you knew the other
bound you could stop searching here right now...

It's important for mtd(f), and if you don't do it (and if you don't do
fail-soft) it probably is not going to look reasonable at all.  Even when you do
it right, it is not a wonderful speedup, it is just sometimes faster sometimes
not, which is expected.  IE PVS over non-PVS is not a 2x speedup in general,
it is just "somewhat faster" and that's actually good enough.

>>Its a
>>difference of style, but in my opinion worst case performance is key when for
>>search.  There is some interesting room for work IMHO with MTD(f)/PVS hybrids.

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