Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Building the Principal Variation in MTD(f) searches

Author: Robert Hyatt

Date: 10:00:24 07/18/99

Go up one level in this thread


On July 18, 1999 at 12:16:40, Vincent Diepeveen wrote:

>On July 18, 1999 at 09:52:08, Andrew Williams wrote:
>
>>My program, PostModernist, uses MTD(f) rather than the more common PVS.
>>MTD(f) proceeds by repeatedly probing the search space, asking the question
>>"is the score for this position higher or lower than guess?", until it has
>>homed in on the correct score. Each probe is a call to a normal alphabeta
>>search, with a window of 1 (eg alpha=g-1, beta=g). This works very well,
>>but there is a problem related to retrieving the Principal Variation.
>>In a normal alphabeta search, the PV is updated whenever a position is
>>encountered whose score is > alpha and < beta. Obviously, when the search
>>window is always 1, this never occurs.
>>
>>The approach I use, therefore, is to just retrieve the Principal Variation
>>using the "best move" entries in the hash table. This works OK, but there
>>is the potential difficulty that positions towards the end of the search
>>(where drafts are low) are prone to being overwritten by positions further
>>up the tree. This is especially problematic with positions written out
>>during the qsearch. This means that my PVs are often truncated before the
>>qsearch, which can make debugging rather difficult. Also, I was hoping to
>>do some simple automatic tuning of PM over the Summer (assuming I find
>>time), but all the methods I can think of need access to the position at
>>the end of the PV from which the backed-up score was generated.
>>
>>I have an idea about how to fix this, which involves creating an extra
>>hash table. Essentially, before each iteration at the root, I would go
>>through every move at the root and stuff the "PV" from each one into this
>>"PV hash table". Whenever a node is encountered in the tree which is also
>>in this extra table, I would update the extra table at the same time as the
>>main HTs. Suffice it to say, I'll have to give this a lot more thought
>>before trying it.
>>
>>So the question is, has anyone who is using MTD(f) got any ideas on how
>>to retrieve the PV? Of course, I'm also interested in ideas/opinions from
>>those who aren't using MTD(f) - even if the opinion is "you should switch
>>to PVS"!
>>
>
>well before explaining my bad experiences with MTD,
>first a tip how to get the pv.
>
>Just get the Principal variation from the hashtable.
>
>What i use is 8 probe in DIEP, so for every PV
>diep can garantueed get 8 out of the hashtable.
>
>However, considering the fact that hashtable is
>around 150mb or something, which means roughly 8 million entries,
>the chance that one overwrites principal variation entries
>is rather small.
>
>As you write "near the leafs" one might fear such things,
>but those worst case scenario's (that positions near
>leafs get overwritten) only occur in diep after overnight
>searches using a rather small hashtable (4 million
>entries or something).
>

I disagree here a bit.  In crafty, between iterations, I "stuff" the PV
moves into the hash table so that I am sure that I will follow the PV first
in the next iteration.  I once put a check in to see if the PV move was
already there, and it wasn't a significant amount of the time, having been
overwritten somewhere along the way...

>Another condition which hurts even more that i use in DIEP is
>that i don't allow a hashtable move when depth is bigger than
>previous depth (which was retrieved from hashtable).


Why?  It was good then, it is most likely good now...


>
>Example is the current experimental version,
>where i in order to accurately compare node counts
>have turned off all forward pruning, just using nullmove R=3.
>
>Seems to me that only problem here is that i disallow retrievement
>of hashtablemoves when depth is bigger than previous depth that
>came out of hashtable.
>
>Hashtable size: 60mb (from which around 35 for transpositiontable
>which means about 2.5M tuples.
>
> r = - = r b k =   ...       1    ...
> = - q b = o o n   ...       2    ...
> o = - o - = - o   ...       3    ...
> = o = O o - = -   ...       4    ...
> O O o = O = - =   ...       5    ...
> = - O - B - N O   ...       6    ...
> - = B = Q O O =   ...       7    ...
> R - R - = - K -   ...       8    ...
>white timeleft=27:46.40.00
>white to move
>
>clean
>Clearing all Hashtables...
>anal
>Analysis mode is on
>process 0: engineflags = 0 denktime=10000000 maxtime=10000000
>00:00 7 (0) 1 0.87 a4xb5 a6xb5
>00:00 20 (0) 1 1.21 Ng3-f5
>00:00 92 (0) 2 0.63 Ng3-f5 Bd7xf5 e4xf5
>++ a4-b5
>00:00 167 (0) 2 0.87 a4xb5 a6xb5
>00:00 316 (0) 3 1.29 a4xb5 a6xb5 Ng3-f5
>00:00 1805 (0) 4 0.93 a4xb5 a6xb5 f2-f4 f7-f6
>00:00 3682 (0) 5 0.94 a4xb5 a6xb5 f2-f4 Nh7-f6 f4xe5 Ra8xa1 Rc1xa1 Re8xe5
>00:00 10305 (0) 6 0.94 a4xb5 a6xb5 f2-f4 Nh7-f6 f4xe5 Ra8xa1 Rc1xa1 Re8xe5
>++ a1-a2
>00:02 47870 (0) 6 1.00 Ra1-a2 b5xa4 Rc1-a1 Bf8-e7 Bc2xa4 Bd7xa4 Ra2xa4
>00:03 65425 (0) 7 1.03 Ra1-a2 Nh7-f6 a4xb5 a6xb5 Rc1-a1 Ra8xa2 Ra1xa2
>00:08 148221 (0) 8 0.77 Ra1-a2 Bf8-e7 a4xb5 a6xb5 Rc1-a1 Ra8xa2 Ra1xa2 Be7-h4
>++ a4-b5
>++ f2-f4
>00:16 276743 (0) 8 0.78 f2-f4 e5xf4 Be3xf4 f7-f6 a4xb5 a6xb5 Rc1-f1 Nh7-g5 Ra1xa
>8 Re8xa8
>++ c1-d1
>00:50 828674 (0) 9 0.82 f2-f4 e5xf4 Be3xf4 b5xa4 Qe2-f2 Bf8-e7 Bc2xa4 Bd7xa4 Ra1
>xa4
>++ a1-a2
>00:58 981597 (0) 9 0.89 Ra1-a2 Bf8-e7 Rc1-a1 Be7-g5 a4xb5 Bd7xb5 Ng3-f5 Bg5xe3 Q
>e2xe3
>++ a4-b5
>01:01 1039445 (0) 9 1.03 a4xb5 a6xb5 f2-f4 Ra8xa1 Rc1xa1 e5xf4 Be3xf4 Nh7-f6 Qe2
>-f3
>01:14 1275076 (0) 10 0.80 a4xb5 a6xb5 f2-f4 e5xf4 Be3xf4 Nh7-f6 Ra1xa8 Re8xa8 Ng
>3-h5 Bf8-e7
>++ a1-a2
>01:23 1439123 (0) 10 0.81 Ra1-a2 Bf8-e7 a4xb5 a6xb5 Rc1-a1 Ra8xa2 Ra1xa2 Be7-h4
>Ng3-h5 g7-g6 Nh5-g3
>03:38 3778580 (0) 11 0.80 Ra1-a2 Bf8-e7 a4xb5 Bd7xb5 Ng3-h5 Be7-g5 f2-f4 e5xf4 N
>h5xf4 Nh7-f6 Rc1-a1
>++ a4-b5
>03:53 4046967 (0) 11 0.86 a4xb5 a6xb5 f2-f4 e5xf4 Be3xf4 Nh7-f6 Ra1xa8 Re8xa8 Ng
>3-h5 Bf8-e7 Rc1-f1 Nf6xh5 Qe2xh5
>05:23 5733524 (0) 12 0.84 a4xb5 a6xb5 f2-f4 e5xf4 Be3xf4 Nh7-f6 Ra1xa8 Re8xa8 Rc
>1-d1 g7-g5 Bf4-e3 Bf8-g7
>11:51 12490703 (0) 13 1.03 a4xb5 a6xb5 f2-f4 e5xf4 Be3xf4 Nh7-f6 Qe2-f2 Qc7-b7 Q
>f2-f3 Ra8xa1 Rc1xa1 Re8-a8
>26:30 28000771 (0) 14 0.65 a4xb5 a6xb5 f2-f4 e5xf4 Be3xf4 Bf8-e7 Ra1xa8 Re8xa8 e
>4-e5 d6xe5 Bf4xe5 Be7-d6 Be5xd6
>++ a1-a2
>34:17 35887650 (0) 14 0.97 Ra1-a2 g7-g6 a4xb5 Bd7xb5 Rc1-a1 h6-h5 Bc2-a4 Qc7-b7
>Ng3-f1 Bf8-g7 Nf1-d2 Nh7-f6
>++ a1-a3
>49:44 51057764 (0) 14 1.04 Ra1-a3 Bf8-e7 Rc1-a1 Be7-g5 a4xb5 Bg5xe3 Qe2xe3 Bd7xb
>5 Bc2-a4 Bb5xa4 Ra3xa4 Qc7-b7 Ng3-f5 Re8-d8
>01:10:56 72354865 (0) 15 1.20 Ra1-a3 g7-g6 Rc1-a1 Bf8-g7 a4xb5 Bd7xb5 Bc2-a4 Qc7
>-b7 Qe2-a2 Ra8-c8 Ba4xb5 a6xb5
>01:36:36 97926104 (0) 16 1.02 Ra1-a3 Bf8-e7 Rc1-a1 Qc7-b7 a4xb5 a6xb5 Ra3-a7 Ra8
>xa7 Ra1xa7 Qb7-c8 f2-f4 Be7-f6 Qe2-d2 e5xf4
>02:40:41 161738324 (0) 17 1.15 Ra1-a3 g7-g6 Rc1-a1 Bf8-g7 a4xb5 Bd7xb5 Bc2-a4 Qc
>7-b7 Qe2-c2
>04:53:08 294001588 (0) 18 0.88 Ra1-a3 Bf8-e7 Rc1-a1 Qc7-b7 a4xb5 a6xb5 Ra3-a7 Ra
>8xa7 Ra1xa7 Qb7-c8 Qe2-d2 Be7-g5 Be3xg5 Nh7xg5
>13:01:42 763686793 (0) 19 0.98 Ra1-a3 Bf8-e7 Rc1-a1 Qc7-b7 a4xb5 a6xb5 Ra3-a7 Ra
>8xa7 Ra1xa7 Qb7-c8 f2-f4 Be7-f6 Qe2-f3
>24:16:28 1427958548 (0) 20 0.86 Ra1-a3 Bf8-e7 Rc1-a1 Qc7-b7 a4xb5 a6xb5 Ra3-a7 R
>a8xa7 Ra1xa7 Qb7-c8 Bc2-d1 Be7-g5 Be3xg5
>
>If my line from the hashtable gets cut a lot then usual that's either a bug,
>or a transposition to a position that was stored with a bigger depth.
>
>>Thanks.
>>
>>Andrew
>>
>>PS  A good description for MTD(f) is http://www.cs.vu.nl/~aske/mtdf.html
>
>We all don't doubt that MTD is a fine algorithm. Regrettably it only
>works for programs using an evaluation which gives very little deviation;
>
>See the score differences the first few ply in DIEP's lines:
>
>0.87
>1.21
>0.63
>0.87
>1.29
>0.93
>0.94
>0.94
>1.00
>1.03
>0.77
>0.78
>0.82
>0.89
>1.03
>0.80
>0.81
>0.80
>0.86
>0.84
>1.03
>0.65
>0.97
>1.04
>1.20
>1.02
>1.15
>0.88
>0.98
>0.86
>
>And those deviations still considering it's a position where there is
>not too much tactics.
>
>Getting the big fail low at 14 ply caused a jump from 1.03 to 0.65
>which took 28.00M / 12.49 = 2.24 branching factor
>
>Just imagine the huge number of researches that MTD needs
>to get to 0.65!
>
>Because let's face it, what program *actually* use MTD currently:
>
>parallel version of fritz (?) :  evaluation of it under 200 clocks
>cilkchess                     :  evaluation also is very limited and
>                                 definitely doesn't have huge scores,
>                                 we all know that cilkchess evaluation is
>                                 always very close to the number of pawns that
>                                 it sees.
>SOS                           :  same comment valid as for cilkchess
>
>So the programs using MTD currently have hardly anything in their evaluation
>not many things causing big scores,
>so claiming that MTD is doing a good job is only true when taking into
>account this restriction, which a lot of programs do not wish to have.
>
>Greetings,
>Vincent



This page took 0 seconds to execute

Last modified: Thu, 15 Apr 21 08:11:13 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.