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