Author: Vincent Diepeveen
Date: 09:16:40 07/18/99
Go up one level in this thread
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).
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).
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.02 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.