Author: Ernst A. Heinz
Date: 10:25:23 11/01/00
Go up one level in this thread
Hi Pham, >In the book "Scalable Search in Computer Chess", Dr. Ernst A. Heinz >said, "The best chess programs generate search trees with only 20%-30% more >nodes on average than the critical alpha-beta trees" (pp 22). I am always amazed how much people like to quote statements out of context, thus making them look weird and fishy. If you had cared to mention that the quote originates from a subsection of the book called "Move Ordering", the 20% to 30% overhead should have been easy to understand. It simply quantifies the effectiveness of move-ordering schemes used by state-of-the-art chess programs in their PVS searches in comparison with the best-first move ordering of critical trees. Of course, you must do fixed-depth searches with uniform path lengths (i.e., without any forward pruning or extensions) in order to measure this overhead. Now, if you add forward pruning and large transposition tables leading to frequent cutoffs, the effective trees searched by modern chess programs actually shrink to less than half the corresponding critical trees of a standard alpha-beta search. >- I guess that Dr. Ernst A. Heinz does not concern some techniques like >hash table, null move, rasoring and so on, which make the real trees could be >much smaller than critical trees. Yes, see above -- the 20% to 30% overhead solely relate to move-ordering issues. They are meant to show how well good schemes for move ordering (such as the one given in my book) work with PVS searches in computer-chess practice. =Ernst=
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.