Author: Bo Persson
Date: 04:34:17 11/01/00
Go up one level in this thread
On November 01, 2000 at 00:17:29, Robert Hyatt wrote: >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. On the other hand Aske Plaat's thesis says that the practical node count(considering transposition tables and other stuff) could be even smaller: "The tree searched in Alpha-Beta's best case is usually considered to be equal to the minimal tree that has to be searched by any algorithm in order to find and prove the minimax value. We show that in practice this assumption is not valid. For non-uniform trees, the real minimal tree - or rather, graph - that proves the minimax value is shown to be significantly smaller than Alpha-Beta's best case. Thus, there is more room for improvement of full-width minimax search than is generally assumed. " http://www.cs.vu.nl/~aske/Papers/abstr-ks.html Bo Persson bop@malmo.mail.telia.com
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.