Author: Robert Hyatt
Date: 21:12:12 10/31/00
Go up one level in this thread
On October 31, 2000 at 22:54:39, Pham Minh Tri wrote: >On October 31, 2000 at 22:01:05, Robert Hyatt wrote: > >>On October 31, 2000 at 19:47:52, Pham Minh Tri wrote: >> >>>Hi, >>> >>>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). His declare >>>makes me be curious how good my program is. Therefore, I tried to calculate the >>>number of nodes in critical trees. I found the simple formula in the >>>book "AI" of Patrick Henry Winston as the following: >>> >>> s = 2 * b ** (d/2) - 1 for d even. >>> >>>With the branching factor b = 30, the depth d = 10, I have the number of >>>node s > 48 million. And if I include the quiescent search nodes, it must be >>>over 60 million. This number makes me surprise, because it is twice as many >>>as the one of my program (around 25m in the beginning without opening book) >>>and tens times as many as the ones of some commercial programs (like Fritz >>>around 1 m). I was wondering: >>>- Am I doing something wrong: wrong formula, wrong constants, wrong calculation, >>>wrong understand about critical trees? >>>- 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. >>> >>>And could someone show me your number of search nodes at full depth of 10? I >>>want to compare my program with yours, but not commercial programs like Fritz, >>>they are too fast and make me feel sad about my work :). >>> >>>Pham >> >> >>Wrong calculation. D is constant. This means that _every_ path is searched to >>depth D only. No extensions. No pruning (null-move or etc). And no q-search >>at all. >> >>no way to calculate such a thing for a modern program. > >Yes, I agree that formula is for optimal trees, not for normal trees in model >chess programs. But I was wondering how to say "20%-30% more nodes on average >than the critical alpha-beta trees"? Is this comparison still meaningful? See my comment below. The value obtained (below) would represent the optimimal (minimal) tree. You can compare the normal search to this search to see how close they are... > >>You _can_ search an optimal tree with some work... to count the nodes. IE >>search it once and remember _every_ best move at every ply. Then search the >>tree again, using perfect ordering. That will give you a value to shoot >>for, node-wise.
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.