Author: leonid
Date: 18:23:44 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: What is the "critical alpha-beta trees"? > 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: Probably "b" is average number of nodes per ply. It is really so? And after b "**" probably you want say "^". Don't be suprised about this formula numbers. When I looked into it I had the impression that it is truthful. I am more ready to see the "saying" of some best commercial programs as misleading. They tend (after what I could see) to present some excellent "selective search" as 100% brute force work. This make us wonder about our numbers. >- 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 :). You can put here, or send it to, me every concret position. Will say exactly all main data that you will indicate me as useful. I recently installed all major counter for this. For sure can say you exact number of total moves produced for given position when it make search 10 plys deep. In the same time I will say how many times all plys (of each ply) was accessed during this search. Also can say the number of moves used during the search. Leonid. >Pham
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.