Re: computer-go: Mathematical Go

[William Harold Newman <william.newman@xxxxxxxxxxx>]

On Wed, Oct 10, 2001 at 03:42:16PM +0900, Darren Cook wrote:
> >I have heard that in Berlekamps book, Mathematical Go some new
> >counterintuitive results was found in the endgame. Could anyone that has
> >read this give an example and maybe som thoughts about the book.
> 
> If you're trying to write a strong go-playing program this book will not be
> any use. And for the part of the game it covers (very late endgame) brute
> force search is just as practical.

Brute force search scales differently, so that on a sufficiently large
board, it's not necessarily true that brute force search is just as
practical.

On a 4x4 board, it's probably impossible to construct a situation
where CGT analysis is worth doing. On a 100x100 board, I'd expect CGT
to win by a lot in typical board positions. My guess, from the numbers
I'll give below, is that a 19x19 board is also big enough that CGT can
win by a lot.

Many of the values in combinatorial game theory can be added and
compared efficiently, so that the problem becomes separable. If you
have situations A, B, and C on the board, in order to search one ply
deep in each, you need to consider
  move first on A, then on B, then on C
  move first on B, then on A, then on C
  move first on C, then on A, then on B
  move first on C, then on B, then on A
  move first on A, then on C, then on B
  move first on B, then on C, then on A
And in order to search 5 ply deep in all three situations, brute force
needs to search 15 ply, with all these which-do-I-do-first
permutations multiplying the number of choices on every decision. If
the situations are separable CGT situations, then the CGT algorithms
need to search 5 ply deep in each of them, and then the three results
from the three separate calculations can be combined reasonably
efficiently.

As far as I know, there's no published algorithm analogous to
alpha-beta for CGT search. (I asked Prof. Berlekamp about this at the
AGA Congress in Denver, and he said there isn't.) So the best known
algorithm for doing each local 5 ply CGT search is more expensive than
the corresponding local brute force search would be.

So, if you have a local branching factor of 20 in each separable
situation, in the hypothetical 3-separable-situation case, it seems to
me that you'd search on the order of sqrt(60^15) nodes for brute force
(where the sqrt is from the alpha-beta speedup) and 3*(20^5) nodes for
CGT. So CGT could have an advantage. And if we bump the 3 separable
situations up to 5 (a reasonably plausible value for a 19x19 board, I
think), then sqrt(100^25) vs. 5*(20^5) looks like a big win for CGT.

Note, though, that there are some extra costs to CGT that I ignored:
  * In order to do your CGT analysis, you presumably have to do some
    initial work to notice that the situations are separable. That's
    not counted in the cost above. There's no corresponding ignored
    term in brute force: you just start crunching.
  * Each step is cheaper in brute force, since minimaxing
    an integer is cheaper than simplifying a CGT score.
  * After you've done your CGT search in the N separated situations,
    you have N CGT values of depth D that you need to combine or
    compare. There are some NP-complete problems lurking in here
    for (I think) both large N and large D. (There are errors in
    the proofs of this in _Mathematical Go_, but David Wolfe later
    published a new proof which seems to've nailed this down.)
    The average-case complexity of this problem is still probably
    OK, especially for anything close to a 19x19 board, but the
    worst-case complexity for arbitrarily large values is bad.
  * The CGT program is substantially more complicated than the 
    brute force alpha-beta program, so much so that AFAIK no one
    has a program which does all this automatically.
I also ignored some other complications:
  * Hash tables can reduce the size of the calculation significantly.
    I suspect that in the limit of huge calculations they're more
    helpful for CGT than for brute force (partly because the brute
    force hash tables become impractically huge much faster than
    the CGT ones do), but I'm not sure.
  * Kos make things harder both for CGT and for brute force.

Does anyone have any empirical or theoretical results on how many
independent subgames tend to exist in real 19x19 endgames, or on how
many points remain to be settled at the time that subgames become
independent, or on the average-case complexity of combining the CGT
results from the independent subgames?

-- 
William Harold Newman <william.newman@xxxxxxxxxxxxxxxxx>
"Those who study history are doomed to watch others repeat it."
    - Susan E. Cohen
PGP key fingerprint 85 CE 1C BA 79 8D 51 8C  B9 25 FB EE E0 C3 E5 7C