Author: Robert Hyatt
Date: 10:13:09 11/01/00
Go up one level in this thread
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.
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.