Author: Robert Hyatt
Date: 19:15:16 09/04/99
Go up one level in this thread
On September 04, 1999 at 19:44:22, Ralf Elvsén wrote: >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 The measurement I do inside crafty is to count the number of positions where I get a fail-high, and then count the number of positions where I get a fail high on the _first_ move I search. I am generally seeing this average about 94%, which means 94% of the times when I fail high, I fail high on the first move, which is pretty good. if you want to compare, count the same things I count, and look at the fh:94% output in the statistics...
This page took 0.03 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.