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.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.