Author: J. Wesley Cleveland
Date: 10:40:19 11/01/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... Another idea is to add iterative counters to keep track of the number of nodes in optimal move ordering. At each depth, the optimal number of nodes is either the total number of subnodes or the number of subnodes for the move that causes a cutoff. As I write this, I realize that to find the true optimal tree, you need to do the full minimax search, not just alpha-beta, i.e. for nodes where there are multiple moves that cause cutoff, you need to find the one with the smallest subtree.
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.