Re: [computer-go] Search = Bad!

[John Tromp <John.Tromp@xxxxxx>]

Matt Gokey wrote:
> John Tromp wrote:
>
> > Right; as is probably easy to tell from browsing my home page:)
> Yeah.
>
> > The 7 moves can be nicely used to subdivide a circle into 7 smaller ones:
> >
> >   2 3
> >  1 4 7
> >   5 6
>  >
> John, perhaps you would take the time to explain this representation and 
> what its significance is to playing the game?  Furthermore, do you think 
> this is the same as the concept Frank has introduced?
I have computed the game theoretical results of all positions in the game
of connect-4 as played on a 7x6 board, with up to 4 stones. The way I map
this depth-4 game tree into 2 dimensions is to start with a big circle for
the root, and then draw the 7 1-ply positions as subcircles of that one,
and the 7x7=49 2-ply positions as subsubcircles etc. Each circle is colored
in one of 3 shades, represting a loss, draw, or win (but then partly obscured
by the smaller circles drawn on top of it).

It could be used as a very small opening book:)

I was simply reminded of my cover when Frank mentioned fractals, because
that's how always talked about it to people: "look at this graphical
representation of early connect-4 positions; isn't it fractal like?"
But I'm afraid the shortest formula to describe this fractal would be
the brute force game tree search:(
For go, a shortcut formula is even less likely, since its PSPACE completeness
implies that any fast (subexponential) algorithm for go would translate to
a fast algorithm for *any* problem whatsoever solvable in polynomial space.

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