Re: [computer-go] Fractals, was Search = Bad!

[David G Doshay <ddoshay@xxxxxxx>]

On 24, Feb 2005, at 1:17 PM, wing@xxxxxxxxxxxxxxxxx wrote:

> Mandelbrot defined many fractal relationships
> that have inner and outer cutoffs. ...
>  All scales beyond these cutoffs
> are meaningless.
This is going to be far shorter than I intended because
I have an awful case of carpal tunnel and it hurts to type.

The first thing that must be considered is that while
Frank *said* Mandelbrot, he meant it as a metaphor,
not to be taken literally by those who know exactly
what "Mandelbrot Set" really means. His comments
about the complication in the colored regions makes
that clear.

The far better work to reference is that of Jim York,
Ed Ott and sometimes others. In that work the maps
of the plane are specifically those of fractal basins
of attraction. In those pictures each area is colored
specifically by where that point ends up as the result
of some specified dynamics that has more than one
attracting solution. In the Mandelbrot case the colors
are how many iterations it took to decide that it was
going to diverge to infinity.

So, the primary problem becomes choosing some
representation where the two end states, White wins
or Black wins, as a result of a move right now is spread
over the board. I have no idea how to do that, but I do
not doubt that such a representation is possible in the
same theoretical sense that one can claim that the entire
Go tree can be enumerated. In that theoretical world at
every move the board would have some points colored
White meaning that this point on the board leads to a
White win, and similarly for Black. This has got to be the
sense in which Frank says that Go is the same as OXO.

But as Bertrand Russell said "Somewhere there must be
a world that works just like in the textbooks."  ;^)

It is my belief that what makes the problem of Go worth
our time and trouble is that while we can say that in
theory this can be done, in fact it cannot. We quite simply
cannot enumerate the entire Go tree. So the first thing
that must be done is to scale back from "this is on the
winning path" to "this is probably on the winning path."
And that brings us back to where we are today in Go
programs, where we use a variety of heuristics to do the
best we can to find the moves that satisfy "our best guess
is that this move is probably on the winning path.".

But I must also say that just because we generally do
not use scaling relationships to choose our moves does
not mean that the idea does not have merit. I think it does,
but I have yet to figure out how to do it. But I am working
on exactly that  in my own round-about way.

SlugGo's algorithms are a first pass attempt to build a Go
program that pays attention to multiple length scales and
the relationships between those length scales. SlugGo
pays attention to the longest length scale possible and
lets GNU Go worry about the smaller scales. It is crude,
but it is a start. The only thing I feel sure of right now is
that I will need to bounce back and forth between Stat
Mech and Go programming many times before any
answers become clear. This is going to take a long time
and it is going to be hard.

So, all in all, I doubt that a program that "just jumps the
right way in the fractal space" will be written any time soon.
But some of the ideas close to that one are still interesting.


Cheers,
David


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