Author: Robert Hyatt
Date: 19:01:05 10/31/00
Go up one level in this thread
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.
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.