Author: Robert Hyatt
Date: 21:17:29 10/31/00
Go up one level in this thread
On November 01, 2000 at 00:15:50, Robert Hyatt wrote: >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... 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.
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.