Author: Peter McKenzie
Date: 13:16:23 08/29/00
Go up one level in this thread
On August 29, 2000 at 14:22:21, Robert Hyatt wrote: >On August 29, 2000 at 11:46:12, Vincent Diepeveen wrote: > >>On August 29, 2000 at 11:33:23, Robert Hyatt wrote: >> >>>On August 29, 2000 at 10:19:38, Vincent Diepeveen wrote: >>> >>>>On August 28, 2000 at 22:21:40, Robert Hyatt wrote: >>>> >>>>>On August 28, 2000 at 19:32:05, Larry Griffiths wrote: >>>>> >>>>>>I have been reading about the History Heuristic and have seen pro's and con's >>>>>>about it. >>>>>> >>>>>>I plan on implementing it to see what happens. This heuristic is related to >>>>>>killer moves and uses the from and to squares in a 64 x 64 array to maintain >>>>>>history information when moves are bestmoves or cutoffs. Each entry has 2 to >>>>>>the depth power added to it when a bestmove or cutoff is found. >>>>>> >>>>>>Would you recommend the History Heuristic, and has anything changed for the >>>>>>better with the method described above? >>>>>> >>>>>>Thanks in advance. >>>>>> >>>>>>Larry. >>>>> >>>>> >>>>>Works fine, but don't use 2^depth... for reasonable search depths, that will >>>>>overflow 32 bit counters almost immediately. I use depth^2 which is much >>>>>safer... >>>>> >>>>>Other than that it works fine. If you don't get a cutoff by the time you have >>>>>tried a few history-ordered moves, you probably should give up and just search >>>>>the rest of the moves in random order. >>>> >>>>Oh well is this bob speaking? >>>> >>>>searching things in random order is never a good idea actually. >>> >>> >>>On nodes where you have to search _all_ moves, the order in which you search >>>them is 100% immaterial. These are the so-called ALL nodes. also called FULL >>>in Knuth/Moore's paper. >> >>The tree below this node is sure having a lot of cut nodes. The way in >>which you search this all node is sure making a big difference for those >>nodes. > >It doesn't make _any_ difference at all, and this is both mathematically and >experimentally provable. Search a tree and save _everything_. Then re-search >the same tree, but on nodes where you searched everything and returned alpha, >use a different move order. Same sized tree. It _has_ to work that way, or >else alpha/beta is flawed. > > >> >>>So I don't follow. Once you are convinced that you can't find a fail-high move >> >>You never know this in advance. In crafty the chance is 5% that you get >>a fail high in DIEP it's 1%, still that's 1% chance to cheaply cutoff. > >I don't follow. I fail high 92% of the time on the first move. 98% of the >time on the first 2 moves. By the time I have looked at the hash table move, >the captures, two killers and 4 history moves, if I haven't failed high, I >am probably _not_ going to fail high. Certainly way below 1% of such positions >fail high, since 98% fail high on the first two moves or not at all. Perhaps it is worth doing the full 'sort' at nodes near the root of the tree. Or where remaining depth > X, where X is quite high (say 5 or 6). At these nodes, it might be worth it because you get quite a big saving from the (very) occasional cutoff. Just an idea, I think I might try it :-) > > > > > >> >>>using normal means, random is just as good as anything else, since "anything >>>else" hasn't worked so far. And since random (generated order) is cheaper than >>>anything else, why not? Works for me. And others, I might add... >> >>So random clearly isn't smart. > > >When it works? Smart is what works and produces the best result with the >lowest computational cost.
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.