Author: leonid
Date: 05:24:51 11/02/00
Go up one level in this thread
On November 01, 2000 at 13:20:41, Robert Hyatt wrote: >On November 01, 2000 at 13:13:09, Robert Hyatt wrote: > >>On November 01, 2000 at 12:22:31, Ernst A. Heinz wrote: >> >>>> On November 01, 2000 at 00:17:29, Robert Hyatt wrote: >>>> >>>>I should add that the quoted within 30% of optimal seems wrong. I recall >>>>Hans Berliner doing a test like this and I believe he quoted 100%. IE the >>>>searched tree was about twice as big as the optimal tree, which is _still_ >>>>very good since we can't possibly have perfect move ordering. >>> >>>I am sorry to say so, Bob, but you are _dead wrong_ here. >>> >>>Ebeling and Berliner always mentioned 40% overhead for HITECH >>>as compared to the critical tree in their publications. See >>>page 102 in "Computers, Chess, and Cognition" for example. >>> >>>Tony Marsland provides a nice comparison of the various search >>>and move-ordering enhancements with respect to the critical >>>tree in Figure 8 of "Computer Chess and Search" published in >>>the "Encyclopedia of AI (2nd ed.)". There we see 20% to 30% >>>overhead at depths of 2 to 6 plies for the combination of all >>>those enhancements (including PVS, best hashed move, and >>>history heuristic). >>> >>>Last but not least, Rainer Feldmann mentions the 20% to 30% >>>overhead in his Ph.D. thesis about the sequential version of >>>ZUGZWANG. >>> >>>I am really surprised that you do not seem to remember these >>>numbers because I am sure that you know the publications I >>>refer to above. >>> >>>=Ernst= >> >> >>Sorry... You are correct and my memory did fail. I think the 2x came from >>an older paper by Tony where he defined "strongly ordered game tree" as a >>tree where the best move is searched first 90% of the time or more. If >>you do the math, that is a factor of 2 in nodes. My percentage seems to hover >>around 92% or higher, which would pull it down a bit. And I think it also >>matters a great deal whether we talk about a game, or a _position_. A position >>is harder. In a game, hash information carries across searches to assist in >>move ordering. In a position, you start off blind. >> >>I believe the 2x figure came from positions, but I don't have time to dig up >>the paper to check it. > >I also forgot to add, that I think the 'simpler' the program, the better it >will do. I change my mind at the root at _least_ 20% of the time. Which means >that for those cases, I search at _least_ 2x the nodes I would normally search. >If I change my mind twice, that is 3x. And actually is more as this only counts >the root sub-trees that are done. > >I am going to run this experiment myself one of these days, just to get a hard >number for myself. 20-30% seems too low, IMHO, unless the test positions are >tactical and easy, like WAC. If you find the right move quickly, then of course Please, whatever you will find on the subject, come here to say your result. I am, at least, one person that watch discussion on this subject with great interest. Leonid. >you search the optimal tree (or nearly so). The right test is a series of >consecutive positions from a game, without a clearly "right" move.
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.