Author: Pham Minh Tri
Date: 19:54:39 10/31/00
Go up one level in this thread
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. Yes, I agree that formula is for optimal trees, not for normal trees in model chess programs. But I was wondering how to say "20%-30% more nodes on average than the critical alpha-beta trees"? Is this comparison still meaningful? >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 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.