Author: Peter Kappler
Date: 13:39:17 08/29/00
Go up one level in this thread
On August 29, 2000 at 16:16:23, Peter McKenzie wrote: >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 :-) > I think it's a good idea. I added this about a month ago, and it seemed roughly break-even, but for deep searches, it turned into a small win. And this was with a very crude move scoring scheme. Lots of room for improvement... --Peter >> >> >> >> >> >>> >>>>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.