Author: Vincent Diepeveen
Date: 14:45:55 09/10/02
Go up one level in this thread
On September 10, 2002 at 17:36:49, martin fierz wrote: >On September 10, 2002 at 17:16:00, Vincent Diepeveen wrote: > >>On September 10, 2002 at 16:06:51, martin fierz wrote: >> >>I need to refer to extensive proof i wrote down at CCC >>which refuted that you overwrite the mainline. >> >>For a search of 20 ply with a loading factor which is pretty >>high, it is still true that with near sureness you have a >>19 ply line at least (assuming no extensions otherwise >>the line is longer). >> >>That's true for bounds too of course. >> >>The chance you overwrite a search depth of 1 ply left >>is considerably smaller than you overwrite something of >>0 ply left. >> >>In fact i do 8 probes. >> >>What loading factor do you talk about here, then fill in the >>chances. > >i'm talking about doing a search of ~10N nodes for a hashtable with N entries. First of all i don't know the level in checkers, but in international checkers it's about 60 moves in 1 hour. Or 90 seconds a move initially (of course exchanges are for free). I don't see how i get a loading factor of 10 there at all, which is a *huge* loading factor. With 12 bytes an entry at my dual k7 i have about 35 million entries. Well i don't get 350 million nodes in a search of 90 seconds at all. Anyway, to use your doom scenario But for 8 probes it means you have at 0 ply a chance it isn't overwritten. But how many nodes with depthleft of 1 ply do you have? right way less, we're not counting qsearch here obviously. how many nodes with depthleft 2 ply do you have? right even less than 1 ply. In fact about a bit more than your branching factor less about. Get the math idea? For a full written out chance see my writings elsewhere. >say again - why wouldn't i overwrite mainline nodes under these circumstances? > >aloha > martin > >>>On September 10, 2002 at 15:41:42, Vincent Diepeveen wrote: >>> >>>>On September 10, 2002 at 15:19:21, martin fierz wrote: >>>> >>>>>On September 10, 2002 at 14:45:27, Omid David wrote: >>>>> >>>>>>On September 10, 2002 at 14:30:56, martin fierz wrote: >>>>>> >>>>>>>On September 10, 2002 at 09:26:14, Eli Liang wrote: >>>>>>> >>>>>>>>A couple of chess programming questions: >>>>>>>hmm, i only wrote a checkers program, but here's my take: >>>>>>> >>>>>>>>(1) Are there any uses for ProbCut and/or Multi-ProbCut in chess positions where >>>>>>>>the variance of leaf-nodes is low? >>>>>>> >>>>>>>i've tried multi-probcut and it works well in checkers. i never tuned it as much >>>>>>>as my own pruning algorithm, and it doesn't perform quite as well - but it is BY >>>>>>>FAR better than no pruning. i'll be trying to tune it in the near future. for >>>>>>>games where the eval doesnt swing wildly, MPC is a fantastic algorithm. >>>>>>> >>>>>>>>(3) Reading Aske Plaat's search & re-search paper, it really seems like mtd(f) >>>>>>>>is something of a magic bullet. But I note it seems that more programs don't >>>>>>>>use it than do (for example Crafty). What is wrong with mtd(f) which Plaat >>>>>>>>doesn't say? >>>>>>> >>>>>>>i'm using MTD. i tried windowed search, PVS and MTD. in my tests, in long engine >>>>>>>matches, MTD performed marginally (no statistical significance...) better than >>>>>>>PVS. it typically searched a low 1-digit % less nodes for a given depth than >>>>>>>PVS. >>>>>>>i don't know how to get a PV out of MTD. in normal searches, a pv node is where >>>>>>>the value is > alpha but < beta. in MTD, you never get this condition. >>>>>>>retrieving a PV from the hashtable is possible, but in all probability, you will >>>>>>>not get the full PV. which is real bad for debugging if you want to know what >>>>>>>the program was thinking at the time... i once asked here how to get a pv from >>>>>>>MTD but got no answer - and if you can't get the pv, then that is a major >>>>>>>drawback. >>>>>> >>>>>>I haven't tried getting the PV out of MTD(f), but just a thought: why should >>>>>>there be any problem in getting the PV out of hash table? Play the first move, >>>>>>update the position, get the next best move from hash table, and so on... ?! >>>>> >>>>>there's no problem with that except that on any reasonably deep search, you will >>>>>not have been able to store all pv nodes in the hashtable. so you end up with a >>>>>search which says it was 23 ply deep and have e.g. 15 pv moves. if you just want >>>>>to display it for the user, that's fine. but if your program plays a bad move, >>>> >>>>but then your hashtable management sucks ass, sorry to say so. >>> >>>but you don't use MTD! which means you *know* when you have a pv node, because >>>"pvnode <=> alpha<value<beta". and then you can make sure it doesn't get >>>overwritten in the hashtable. if you use MTD, you don't have this information - >>>all your hashtable entries are either lower or upper bounds... so how do i know >>>which ones i have to keep? i'd really glad to learn how to do this :-) >>>so if you can tell me how to do it instead of saying i suck (well possible...), >>>i'd love to try! >>> >>>aloha >>> martin >>> >>> >>>>I get in Napoleon also only mainlines out of hashtable (with pvs) >>>>wasting system time in the search to update all kind of stupid >>>>arrays for it is a waste of time, and the next iteration you get >>>>true bounds, so you can't get the mainline in arrays anyway (mtd >>>>is different here). finding a win in 50 ply is no problem to display... >>>> >>>> >>>> >>>>>and you want to know what line it was considering as being best, e.g. because >>>>>you want to know if your static eval is bad in the final node of the pv, you >>>>>can't do it. IMO debugging your program and finding eval problems like this is >>>>>MUCH more important than something like 5% more speed. >>>>> >>>>>aloha >>>>> martin >>>>> >>>>> >>>>>> >>>>>>> >>>>>>>>(6) Has anyone found any real "practical" benefits to fractional-ply extensions? >>>>>>> >>>>>>>yes. i tried recapture extensions of different depth, and half a ply gave the >>>>>>>best result. don't ask me why, it's just an observation. >>>>>>> >>>>>>>aloha >>>>>>> martin
This page took 0.01 seconds to execute
Last modified: Thu, 07 Jul 11 08:48:38 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.