Computer Chess Club Archives


Search

Terms

Messages

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

Author: Tord Romstad

Date: 15:25:34 01/14/04

Go up one level in this thread


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
>>>attractive.
>>>
>>
>>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.

This is not a *big* problem by any stretch of the imagination.  It does indeed
happen
that the last few moves of the PV are wrong or missing, but I have *never* seen
as obviously wrong move as the second move of the PV.  This does of course not
mean that it never happens, but it is clearly very rare.

On the other hand, it *does* happen that the PV contains only one move, and
there
is no move to ponder at all.  This happens maybe once every 5 or 10 games, but
usually when the game is already won or lost.

>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).

This is true.  The average branching factor is clearly lower when the initial
direction
of the search is downward.

>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).

Most of us extend the thinking time in such situations, and try to avoid making
a
move before the search fails high.

By the way, there are a few things you could try to solve the problem you
describe,
although I haven't yet tried them.  The main idea is to give up quickly if the
search
appers to fail low.  The easiest thing to do is to just abort the search if the
first move
at the root fails low, and immediately start a new search with a lower search
bound.

It is certainly possible to find refinements to this idea, but as I said I
haven't experimented
with it yet.

>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.

It is quite common that the search depth reached varies a lot from move to move
in Gothmog (a difference of 3 or 4 plies is not unusual), but usually this is
due to
DFP rather than MTD(f).  A sudden dramatic drop in search depth usually means
that most of the DFP is disabled for some reason.

And in general, if you want to knock MTD(f), you really need to base your
conclusions on
something more substantial than games against Gothmog, which undeniably is the
slowest, weakest and most buggy MTD(f) engine known to man.  Gothmog is nothing
but a clown, and although it occasionally shows some entertainment value, it is
not
a serious chess program and should not be evaluated as such.

The situation you describe can be observed in about every second game played
between a fast, strong engine and a slow, weak and buggy one.  You cannot make
any conclusions about the relative merits of the algorithms used based on such
games.
>
>---- 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.

Most MTD(f) programs use a two-limit hash table, but it is not a requirement.
I have also seen PVSers claim that a two-limit hash table works better than a
one-limit table for them.

>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.

There is.  It is possible that I will experiment with this in the near future.
MTD(f)
is obviously not suitable for devices with limited memory, I am therfore forced
to
evaluate alternative techniques before porting my engine to Palm OS.  The next
version of Gothmog will probably include the possibility of choosing between
MTD(f) and PVS in the init file.  There will also be an option to disable all
DFP.

Acronyms used in this post:

MTD(f) = "Memory-enhanced Test Driver with initial guess f"
PVS = "Principal Variation Search"
DFP = "Dubious Forward Pruning"

Tord



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