Author: Robert Hyatt
Date: 21:15:50 10/31/00
Go up one level in this thread
On October 31, 2000 at 22:37:37, leonid 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. >> >>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. > >Thanks for explaining! I thought that D was average number of nodes in each ply. >If you could give some calculation, just as example, it will help to become sure >that this formula was understood correctly. > >Thanks, >Leonid. First, the _right_ formula: N = W^floor(D/2) + W^ceil(D/2) + 1 floor is D/2 rounded down to nearest int, ceil is rounded up to nearest int. D is the depth of search W is the width (or number of nodes at each position) Since for a modern program, D is dynamic, and for _all_ chess programs W is certainly not a constant, this can't be used for anything useful. The way to find optimal N is to do a search to depth=N, and save the best move at each ply where there is a best move, using the hash table (it must be big enough to not overwrite _anything_). During this search, you get your value for N. Then re-search, but always search the hash move first, to give optimal move ordering. Now you get optimal N. You can compare those...
This page took 0.01 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.