RE: computer-go: Mathematical Go

["Mark Boon" <tesuji@xxxxxxxxx>]

"The poison is in the tail", a popular Dutch expression. Pure brute-force is
not affected by ko of course, but CGT is completely destroyed by it since it
cancels any possible locality.

> -----Original Message-----
> From: owner-computer-go@xxxxxxxxxxxxxxxxx
> [mailto:owner-computer-go@xxxxxxxxxxxxxxxxx]On Behalf Of William Harold
> Newman
> Sent: Wednesday, October 10, 2001 4:27 PM
> To: computer-go@xxxxxxxxxxxxxxxxx
> Subject: Re: computer-go: Mathematical Go
>
>
> 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
>