Author: Vincent Diepeveen
Date: 11:10:16 07/18/99
Go up one level in this thread
On July 18, 1999 at 13:00:24, Robert Hyatt wrote: >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... No way. Let's calculate a bit Say our line at 14 ply is build up out of a search based upon 14 ply then 13 ply 12 .. 0 ply (where 0 = qsearch) Now first we must take into account 2 things a) diep searches at 15k nodes a second at a PII450, crafty more like 220k nodes a second b) diep uses 8 probe, and last thing i remember was crafty using 2 probes. Now i store in diep depth based, so we can easily calculate After say 180 seconds of search my DIEP has searched about 180 x 15k = 2700k = 2.7M nodes My hashtable size is about 60mb, which gives around 2.5M tuples. Now first move is for sure stored as there is no other search of 14 ply stored. Now we have this loading factor alfa is more or less 1, so this means we only have overwritten qsearch nodes. I'm not sure what is the objective best calculation. An important thing to realize is that it's *very* unlikely that we get by making moves the same hashkey, so we store this depth at a different index in the hashtable, so it's very unlikelythat it overwrites. Chance we have overwritten a tuple at depth = 1, you can calculate it yourselve, is quite small, as an 8 probe is performed. Suppose out of that 2.7M nodes about 60% is qsearch. Now that gives us left: 1.08M nodes with depth >= 1 left Now all these 1.08m nodes *might* overwrite the 1 ply search *only* if all 8 probes lead to nothing. So we have then roughly a chance of 1 / 2.5 = 0.40, *if we have bad luck* that chaining happens. However, in DIEP i'm not storing tuples after each other in hashtable. I store them at different locations in the hashtable, so i'm hardly suffering from chaining nowadays. Chance that all 8 tuples get overwritten by a tuple: a single slot has chance 1/2.5 = 0.40 to get overwritten. So 8 slots have chance 0.40*0.40*0.40*0.40*0.40*0.40*0.40*0.40 = 0.40^8 = 0.0006 So total chance that a tuple gets overwritten is with a loading factor 1 my let's estimate that at 0.0006 Chance is way less for tuples at bigger depths, that's quite obvious. It's simply a summation for every depth. Personally i don't care if in 0.0006% of the chances tuples of depth=1 left gets overwritten. That means my PV is 13 ply instead of 14 ply. And if a few qsearch moves falls out of that, who cares? We're talking here about a loading factor near 1. For my DIEP that's near to impossible to achieve. I think some smart dudes might even be able to calculate for a loading factor = n, what the length of the line is i can get out of hashtable very likely. >>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... cuz otherwise my lines get way too long at analysis depth, where they don't give much better insight in what's happpening in this position. At icc this is quite annoying as one has already a loaded hashtable. In the endgame i get lines from 60 ply or something out of hashtable then which are completely insane. I'll take a look at it to turn it back on :) >> >>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.