Author: Robert Hyatt
Date: 11:22:05 09/21/98
Go up one level in this thread
On September 21, 1998 at 13:25:12, John Coffey wrote: > >>So, roughly, alpha/beta reduces the branching factor from W to sqrt(W). >>To drive it below that, requires unsafe tricks. IE null-move is one big >>winner here, because some nodes are searched less deeply than others, which >>can reduce the effective branching factor from sqrt(W) to something even >>less, approximately 2.5-3.0, roughly, in Crafty... >> >> > >Let us assume that squrt(W) is in the 5 to 6 range, then in order to get >the numbers down to 2.5 to 3 that we would have be eliminating half of >all the moves on every branch of the tree. Seems to me that null-move >won't even get you close to that, so it occurs to me that most of your >speed up must be coming from hash-tables being used at every branch to >get near perfect move ordering, thus improving the efficiency of the >alpha-beta algorithm. Is this not so? > No... you are ignoring the exponent, completely. When you do a null-move search, you search two plies less deeply. If *this* causes a cutoff, you just reduced the total nodes by a factor of *25*. If this happens often enough, reducing the branching factor from 5 to 2.5 is not just easy, it becomes trivial... >By "near perfect move ordering" I mean that the best move is usually >tried first. I am guessing that all the other moves would be close >to random order. generally accepted terminology says that if, when you get a fail-high, it happens on the first move at least 90% of the time, you have what is called a "strongly-ordered game tree with near-perfect ordering." Crafty is sitting at around 92-94% on this statistic... > >john coffey
This page took 0.02 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.