RE: computer-go: Alpha-Beta Search

["Xu, Mousheng" <moushengxu@xxxxxxxxxxxxxxxx>]

As I recall the Knuth-Moore analysis assumes that all terminal
nodes are at the same depth. This is unrealistic.

* Why the assumption is unrealistic? I have the opposite: how could the
terminal nodes not be at the same depth? During an open game or a mid
game, most term nodes are at the same depth. Sure, in the case of
earlier termination such as capturing of a large enemy group, the term
nodes might not be at the same depth. But I don't know why that would
hurt the correctness of alpha-beta algorithm. I guess the analysis of
shrinking to branch factor to sqrt(bf) is based on the assumption that
all term nodes are at the same depth, but the algorithm still works as
far as the evaluation is dependable. Correct me if I am wrong.

* Thanks.

-- Mousheng