Computer Chess Club Archives


Search

Terms

Messages

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

Author: Dann Corbit

Date: 10:35:23 01/15/04

Go up one level in this thread


On January 15, 2004 at 09:50:18, Josť Carlos wrote:

>On January 15, 2004 at 02:41:40, Uri Blass wrote:
>
>>On January 14, 2004 at 19:48:14, Dann Corbit wrote:
>>
>>>On January 14, 2004 at 19:08:10, Uri Blass wrote:
>>>
>>>>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.
>>>>
>>>>I do not believe it.
>>>>
>>>>PostModernist also use MTD and I think that Gothmog is stronger than
>>>>PostModernist.
>>>>
>>>>I did not test Gothmog and my impression is based on results that I read that
>>>>suggest that Gothmog is at the same level of engines like Ktulu.
>>>
>>>I think you underestimate PostModernist.  It may be stronger than SOS (often
>>>considered the strongest MTD(f) engine), and so it is surely one of the
>>>strongest MTD(f) engines around.
>>
>>No
>>I do not underestimate PostModernist.
>>Your list suggest that it is weaker than Abrok or Anmon when the list that I
>>read suggested that Gothmog is stronger than them.
>>http://www.f11.parsimony.net/forum16635/messages/60395.htm
>>
>>I see that you test old SOS.
>>I am surprised to hear that SOS is often considered to be the strongest MTD
>>engine.
>>
>>I thought that this title is of one of the commercial(Shredder showed stupid
>>pv's so it may use MTD and I also remembered that the same happened with Fritz)
>>
>>I do not know how did you get that PostModernist is one of the strongest MTD
>>engines in the world.
>>
>>I do not know which engines use MTD and I simply mentioned the probably weaker
>>engine out of the only 2 free engines that I knew to use MTD except
>>Gothmog(PostModernist and Comet)
>>
>>Gothmog may be also stronger than Comet.
>>
>>Uri
>
>  Comet is MTD(f)? I haven't noticed it. However, Anmon clearly is.
>  BTW, Cilian looks like it is MTD(f) too, in which case it is the weakest
>MTD(f) engine that I know of.

It [Cilian] is also one of the first implementations.
Here's a fresh compile:
ftp://cap.connx.com/chess-engines/new-approach/CILIAN.exe



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.