Author: Pham Minh Tri
Date: 16:47:52 10/31/00
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
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.