[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: computer-go: perfect play : a new fractal algorithm
Matt Gokey wrote:
>
> Serge Boisse wrote:
>
> >>Since cute and intelligent algorithms for computer go tend to be very rare ;-),
> >>may I Propose you a new one ? You'll see that it is definitly completly
> >>different from anything else.
> >>...
> >>I call this algorithm "fractal go".
> >>...
>
> Well, I found your idea very interesting! As I have said multiple times, I believe
> go-representation - especially multiple level representation - and reasoning using
> higher level abstractions is the key to dealing with the complexity of Go. There
> have been several different approaches introduced on this list that differ greatly
> in the details, but have this common thread. Your idea is another one. I believe
> that despite the apparent problems with the Fractal-Go reduction approach losing too
> much information, that it may have some merit. The local searches for each reduced
> board give this search its potential. An advantage of this idea is that it is
> relatively simple. It would be interesting if someone were to implement this
> algorithm and see how well it might play. Of course, there is still the issues of
> searching locally even at the reduced branching factor, life and death analysis, and
> whole board evaluation, etc. If one of us with a full functioning go program added
> this Fractal Go "heuristic" to their search for selection/pruning I wonder what the
> results would be? Personally, I tend to think that the changes in the strategic
> nature of the game (as the board size shrinks to 11x11 and lower) due to the edges
> and corners and proximity of stones, not to mention shape changes, will skew the
> strategy on the larger boards, resulting in a lot of mistakes. However, it would be
> interesting to actually find out...
>
> Matt
Well, this might be a real weakness of my idea.
the problem comes from the importance of shape in go, and from the fact that any
reduction algorithm would necessarilly "distort" shapes : connecting stones that
were not, closing eyes, etc.
I think one idea to partially overcome this problem is a suggestion of Vlad
Dumitrescu to use feature trees (recently discussed in this list) to guide the
reduction process by maximimizing similarities btw the feature tress of both
boards. This can account for "life and death importance" distorsions, but not
for shape distorsions, since features trees don't care about shapes.
So far, the only solution i have for minimizing shape distorsions is to have
subboards with very little size difference. instead of a somewhat brutal
19x19->13x13->9x9->.. sheme, we could use more intermediate boards :
19x19->17x15->15x15...
The shape distorsion btw "adjacent" boards would be minimized.
Of course you have to pay for this : it increase computation time.
Again, there is a lot of possible tunig here.
Serge