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.