Author: Ricardo Gibert
Date: 01:59:26 11/01/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 If you really interested in the theoretical side of computer chess programming, you may want to check out chapter 9 "An Analysis of Alpha-Beta Pruning" from D. Knuth's book called "Selected Papers on Analysis of Algorithms". You may find it a bit too dry for your tastes, but important insights can be derived with patience. I spotted this book at a Borders book store.
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.