Author: Ralf Elvsén
Date: 16:44:22 09/04/99
I was thinking of the number of positions one has to search in the alpha-beta algoritm. With perfect moveordering the number is roughly n^(d/2) , where n = number of moves in a position and d = search depth. I know this is a simplification of the actual formula but it catches the "essence" of it. With the worst possible moveordering it goes like n^d (same as mini-max). We can summarize this qualitatively as number of positions = n^(s*d) , where s = 1 for the worst case and s = 0.5 for the best case. Is there anyone out there who has a feel for the actual value of s in the programs used today? This would be a measure of the quality of the moveordering. I realize that most programs have a more complicated search structure with null moves, hash tables etc, but it would be interesting to see some educated guesses. Thanks in advance, Ralf
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.