Computer Chess Club Archives


Search

Terms

Messages

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

Author: Anthony Cozzie

Date: 08:15:28 01/15/04

Go up one level in this thread


>OK, but I don't think you played with MTD(f) long enough to make it work
>really well.  You cannot simply replace PVS with MTD(f) and expect that
>your engine will play as well as or better than before; it takes a long
>time to learn all the tricks.  Many techniques which work well with PVS
>are less effective with MTD(f), and the same holds true in the opposite
>direction.  This, of course, makes it very difficult to make an objective
>comparison of the two algorithms.

1. I did the full upper/lower bound hash rather than limit/type.

2. I tried probing in qsearch

3. I experimented quite a bit with heuristics for varying the window, as opposed
to plaat's next_try = current try-1.

I probably spent about a week on it.  I think in the _average_ case MTD(f) can
even be better than PVS() [my implementation was about equal] with some tuning.
It can find tactical shots much faster, because it goes through the entire move
list sooner than PVS().  It is the _worst_ case where MTD(f) falls apart; in my
personal opinion the worst cast is more important.

What I found was that a fail high in MTD(f) is very fast, while a fail low is
very slow.  In a fail high, only 1 child node is searched, while in a fail low
_all_ nodes must be searched.  So it was quite common for me to see stuff like
this:

searching [19,20] -> 20 [n=4000]
searching [21,20] -> 20 [n=200,000]

I am not exaggerating 4,000 vs 200,000.  It is easily a difference of 30 and
sometimes 50.

The thing I ended up doing was a combination of binary search, fixed low, and
simple up.  So Zappa's search looked like this:

searching [4,5]    ->  4 [n =2,000,000] [first search always by far the longest]
searching [-10,-9] -> -9 [n = 20,000]   [zero window fail highs are crazy fast]
searching [-9, -8] -> -8 [n = 20,000]
searching [-8, -7] -> -7 [n = 20,000]
searching [-7, -6] -> -6 [n = 20,000]
searching [-6, -5] -> -6 [n = 1,000,000] [fail low -> way more nodes]

Now you have a troublesome tradeoff to make.  You want to have a reasonable
number of searches, but you also don't want to fail low.  Suppose your position
is tight, and your score suddenly goes from -.2 -> -1.5 (you discover a mating
sequence where you must throw a pawn).

Now your MTD(f) search looks like this:

searching [-20, -19]   ->  -20 [n = 2,000,000]
searching [-40, -39]   ->  -40 [n = 1,000,000]
searching [-60, -59]   ->  -60 [n = 1,000,000]
searching [-80, -79]   ->  -80 [n = 1,000,000]
searching [-100, -99]  -> -100 [n = 1,000,000]
searching [-120, -119] -> -119 [n = 20,000]
searching [-119, -118] -> -119 [n = 1,000,000]

So while the best case performance in my example was 3.1 MLN nodes, the
performance in the fail low case was 7 MLN nodes.  I know I am pulling these
numbers out of the air, but this is what I saw in test positions and game - it
might be even worse than what I am describing.

Now, writing all this has given me an idea.

You start out trying an MTD(f) window at prev_score - 8.  If it fails high, than
 you continue your MTD(f) ways.  If it fails low, you switch over to PVS().
This is fresh off the neurons so it may not work/be stupid/make you feel less
handsome/etc.

anthony



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