Author: Robert Hyatt
Date: 06:40:01 09/21/99
Go up one level in this thread
On September 21, 1999 at 01:31:01, KarinsDad wrote: >On September 20, 1999 at 23:07:56, Robert Hyatt wrote: > >[snip] >> >> >>It also might not be a bug, but might be caused by poor move ordering, >>as that can blow up the search similar to what you are seeing.. > >I guess I do not understand how Alpha Beta works. I thought that it was >approximately the square root of the number of branches without any special move >ordering at all. If move ordering is applied, it should (theoretically) get >lower than the square root of the number of branches. Correct? > >If so (and since I am not using Alpha Beta, I remember next to no details on how >it works, so I could be way off here), then if you just used Alpha Beta and move >ordering and you consistently got a good deal higher than the square root of the >number of branches, then it would seem that you have a bug (either >implementation or design) in either your Alpha Beta code, or your Move Ordering >code. Or am I all wet here? > >KarinsDad :) 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.
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.