Author: Vincent Diepeveen
Date: 18:07:39 07/18/99
Go up one level in this thread
On July 18, 1999 at 16:09:54, Robert Hyatt wrote: >On July 18, 1999 at 14:10:16, Vincent Diepeveen wrote: > >>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. > >This is wrong. First move can be a check, so the move at ply=2 will >be searched to depth=14 also. And that can be a check as well which >can give _lots_ of moves searched that deep. Theoretical chance is actually very small, about (1/1000000)^8 Secondly the move *must* be extended. That's however theoretical BS. chance power gets turned off is bigger. >> >>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. > > >I'm not talking _probability_ here. I am talking _actual_ measured >results. IE I did the actual experiment in crafty, because my "stuff the >PV" code looks for the position and stores the PV move in it if it is already >there, otherwise it creates a 'bogus' position and stuffs the PV move there. >It is easy in this code to count the number of times it happens. And happen >it _definitely_ does... Right with 0.0006 chance it indeed happens now and then at depth==1. it happens nearly once every thousand times... >>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.