On Tue, 14 Sep 2010, Brian Sheppard wrote:
This explanation looks inexact.
The move matching will always be better than 1/branching factor.
I think you missed the point of the explanation.
If you ponder taking the opponent's point of view, and you have
a match on his move, then you will have a tree for *your* move that
is 1/BF of the size of a full tree. So your gain from pondering
is a factor of 1 + 1/BF. But that only applies when you have a
match, which happens 50% of the time, so the net gain is 1 + 1/2*BF.
You're mixing the two pondering strategy. In this strategy, you always
have a match, so you really get 1 + 1/BF.
(Note: BF here is the effective branching factor == growth rate
of the search process, not the nominal branching factor, which equals
the growth rate of the search space. So in chess, BF ~2.5, not 36.)
If you speculatively ponder, and you have a match, then you gain
a factor of 2. This is scaled back to a factor of 1.5 because you
match about 50% of the time.
It is clear that speculative pondering is much better.
How is the former explanation different from go, or invalidating my
argument ?
Your first formula is 1 + 1/BF.
Your second formula yields 1 + P[match].
I say P[match] >= 1/BF if the two opponents play the same game. Hence
the second strategy should always be better.
The problem is likely to be that the right mean is NOT the arithmetic
mean.
There could also be interactions with different thinking times for
different moves, or different branching factors at different depths,
etc.
Jonas
_______________________________________________
Computer-go mailing list
[email protected]
http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
