Author: Robert Hyatt
Date: 10:19:25 09/21/99
Go up one level in this thread
On September 21, 1999 at 12:02:25, Dave Gomboc wrote: >On September 21, 1999 at 09:40:01, Robert Hyatt wrote: > >>First the precise formula: >> >>nodes=w^(floor D/2) + w^(ceil D/2) >> >>floor=round down, ceil=round up. For d even, this turns into >> >>nodes=2 * w ^ (d/2) >> >>for simplicity we generally drop the 2 and just say nodes=sqrt(w^d) >> >>With that out of the way, that is based on perfect move ordering. As move >>ordering gets worse, nodes approaches w^d (pure minimax) which is why we spend >>so much time on hash moves, killer moves, history moves, ordering the captures >>in order of expected gain, etc. The more accurate the move ordering, the >>closer we get to the true alpha/beta node count. As ordering becomes less >>accurate, we drift toward the minimax node count. > >It may also be interesting to note that using completely random move ordering >will visit w^(2d/3) nodes (IIRC!) > >Dave something in that range... the reason is that for about 1/2 the total nodes, move ordering is meaningless, because _all_ moves have to be searched at so- called ALL nodes anyway. I don't have the mental energy to check the 2d/3 value, although it might have been mentioned in the Knuth/Moore paper...
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.