Computer Chess Club Archives


Search

Terms

Messages

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

Author: Anthony Cozzie

Date: 17:11:02 01/14/04

Go up one level in this thread


On January 14, 2004 at 18:25:34, Tord Romstad 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
>>>>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.

I base this on my own experiments with Zappa and MTD(f).  The exact same
scenario happened in a game vs the Baron.  Score falls, takes Zappa extends time
ilke crazy, still gets only 8 ply in 1 minute (!!) makes bad move, loses.

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

How much RAM does a Palm have?

anthony



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