Author: KarinsDad
Date: 14:10:09 09/21/99
Go up one level in this thread
On September 21, 1999 at 13:19:25, Robert Hyatt wrote: >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. Now, wait a minute. This doesn't make sense. If perfect move ordering occurs, then for nodes where the order mattered, you would search one move and be finished. For "ALL" nodes, you have to search all 36 nodes. So, to get an average branching factor of 6 moves, you would need 6 one move nodes and 1 36 move node for a total of 7 nodes and 42 moves. So, it would seem that with perfect move ordering, move ordering would be meaningless for 1/7 of the total nodes and not 1/2 of the total nodes. Am I totally misunderstanding this again? > >I don't have the mental energy to check the 2d/3 value, although it might have >been mentioned in the Knuth/Moore paper... If the 2d/3 equation holds, then 36^2/3 = 10.9 is the random branching factor. If 10.9 is the random branching factor and 1/2 of the nodes are really "ALL" nodes, then (1/2y * 36 + 1/2y * x)/y = 10.9 or (x+36) * 1/2y = 10.9y or x+36=21.8 or x = -14.2 which does not make sense. In fact, with the lowest value of x being 1, (1/2y * 36 + 1/2y * 1)/y = yields a result of 18.5 which is way off 2d/3. y here is the number of overall nodes and x here is the average branching factor of nodes where move ordering matters in order to acquire an overall branching factor of 10.9. But, (1/7y * 36 + 6/7y * x)/y = 10.9 or (6x + 36) * 1/7y = 10.9y or (6x + 36) = 76.3 or x+6 = 12.7 or x=6.7 makes more sense for a random distribution. I do not know if the ratio is 6 to 1 (i.e. 6/7th) is correct, but that sounds better than a 1 to 1 ratio of "All" nodes to move order dependent nodes. KarinsDad :)
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.