Computer Chess Club Archives




Subject: Re: calculating the PV using MTD

Author: martin fierz

Date: 17:42:04 09/12/02

Go up one level in this thread

On September 12, 2002 at 02:16:45, Fabien Letouzey wrote:

>On September 11, 2002 at 20:22:42, martin fierz wrote:
>>my whole interest in getting a pv out of the search rather than from the
>>hashtable was that i wanted a guarantee that i got to the end of my PV, for
>>debugging purposes, like if i want to find out why my program makes a certain
>>bad move with a high score - what the hell was it thinking there?
>>retrieving from the HT is ok most of the time, but obviously for this purpose,
>>it is not so good because sometimes it will not give me the full PV because
>>something was overwritten in the HT. in my implementation, i will also miss the
>>entire qsearch because i don't store that in the HT. so your way of doing this
>>really helps :-)
>Now that I read this, semi-PV is perhaps exactly what you want in this case.
>The key is that it shows you where the evaluation is from.  However you need
>to be careful when interpreting a single semi-PV (not combined), see below.
>>and if i understand you correctly, then i can just get your "semiPV" for my last
>>MTD test, and that actually IS what my program was thinking when it made the
>>move, right?
>Now it's tougher.  I'd rather say that it is what your program thinks in case
>of a fail-high, and what its opponent thinks in case of a fail-low.  Because
>MTD(f) search "direction" depends on the first estimate, I would interpret the
>last semi-PV differently in both cases.  I have never used MTD, but if I had
>access to only a single semi-PV, I would prefer to see the last fail-high
>semi-PV (I might be wrong here, programmers with MTD experience are welcome).
>Let's take an example.  If I understand well, you use strict MTD(f) (no
>accelerator).  Let's pick an "upward" MTD search (you underestimated the true
>value).  All the searches except the last one are fail-highs.  They are proofs
>that your "best" move is good (and it selects a new move from time to time).
>So in your debug example, if you know this move is bad, a semi-PV could show
>you why Cake thinks it is good (I think this is what you want).  Now comes the
>last search.  It fails low.  Interpretation is completely different here.  It
>first proves the value of your first move, then shows the other moves are not
>better.  Think about the semi-PV content in this case.  It starts with your
>best move (making the semi-PV *look* like a PV), then contains good opponent
>moves showing why you cannot improve its value.  I believe this is not what you
>want (only you can tell me).
>I can only repeat.  Semi-PVs might or might not be what you want.  Just make
>sure you interpret them carefully, they are different from PVs.  We can talk
>further about the non optimal moves they contain in the general case (it is
>move-ordering and fail-soft dependant).

salut fabien

thanks again for your remarks. i started printing out normal hashtable PVs for
all MTD searches and looking at them. there's a lot to look at, and i guess i'll
need some time to understand what they mean. then i can try to get your
semi-pv's along with the hashtable pvs and see if and how they differ. and once
i understand these things, i'll come back with the next round of questions :-)

i just tried another thing which might help me understand my program better: for
the sake of the argument, assume that my eval can only return even integers
(grain size 2). my modified MTD now calls negamax like this:

do an MTD loop over this:
  alpha = guess-1
  beta = guess+1
  value = -negamax(-beta, -alpha)
  if (value == guess)
  guess = value

like this, as long as the search fails, it behaves like MTD. but finally it will
succeed once, and for that last iteration i can get a normal pv. at least that's
what i think i can do. i just tested this to see how big the performance hit is,
and it searches about 2-4% more nodes on average than the "real" MTD - but that
is a small price to pay for better debug info IMO.


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