Re: [computer-go] Search = Bad!

[Evan Daniel <evanbd@xxxxxxxxx>]

On Sun, 20 Feb 2005 01:51:46 -0600, Matt Gokey <mgokey@xxxxxxxxxxxxxxxxx> wrote:
> Evan Daniel wrote:
> 
> >
> >>Would you explain why you meant to joke?  Do you find the fractal
> >>equation go idea not worthy of serious discussion? If so, why?
> >
> > The idea that Go is a fractal doesn't seems useful to exactly the
> > extent that it provides useful techniques or analogies.  The most
> > obvious is the idea of the generating equation, but we already know
> > that -- it's the rules of the game.
> I don't understand, could you explain?

Sure.  The Mandelbrot fractal makes an infinitely detailed pretty
pattern when drawn in the right way, and is defined by only a couple
lines of equations.  The detail is an emergent property of some very
simple equations.  So if you want to draw the fractal, it's really
easy -- start evaluating the equations, and plotting points.  Voila,
fractal.

Go is the same way -- there's a simple set of equations (the rules)
which define a very complex highly detailed pattern (the entire game
tree, complete with ko fights, strategy, tactics, eyes, and lots of
other abstractions we humans like to talk about).  If you want to find
the winning way to play go, the answer is easy -- walk the game tree.

The only difference is in the quality of result we care about.  If you
decided that you wanted to find some feature of the mandelbrot set
that met a criteria to one part 10 ^ 250, and by the way you only get
two days of compute time, and that feature was in some way non trivial
to find, no one would take you seriously.  But getting, say,
professional dan strength from a program is the same level of task;
you're asking for a program that loses at most maybe one point per
move, out of tens of points possible, of the course of a couple
hundred moves of game play.

If you asked such a question about the Mandelbrot fractal, you would
probably get an answer that involved hill climbing, or simulated
annealing, or a genetic algorithm, or some combination of the above
that applied a bit of domain knowledge to avoid trouble spots.  And
you'd miss your 1in 10^250 target by many, many orders of magnitude. 
You ask the question about Go, and you get an answer involving alpha
beta search, a bit of pattern recognition, and some domain knowledge,
and guess what -- you miss your target by a mile.  That's hardly
surprising.  What is interesting is that we have a belief, created by
the existence of professional players, that a solution with that
degree of precision ought to be findable, and the motivation to pursue
that search with many, many man-years of effort.  However, that does
nothing to convince me that there is a trivial answer to the problem,
provided we just notice that this whole thing is merely a highly
detailed pattern created by simple rules.  If all you want is a
picture of the fractal to put on your desktop, fine, that shouldn't be
hard, but I really don't think the answer we're searching for is even
remotely in the same category.

I think the only difference is that I can easily name a property of
the Go tree that is hard to search for, but can't come up with one for
the Mandelbrot set with any ease.  Perhaps an easier analogy is
Conway's game of Life.  It's an emergent pattern defined by simple
rules, and there are plenty of hard questions about it -- gardens of
eden, maximal stable densities, minimal quadratic replicators, Turing
completeness, etc etc.  None of them are trivial, though some are
answered (it's Turing complete), and I don't think anyone seriously
studying it thinks that the answers will tend to fall out of the rules
in any simple way.

Evan Daniel
_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://www.computer-go.org/mailman/listinfo/computer-go/