Auteur: Serge Boisse
Date: Le 30/03/2023 à 16:03
Type: web/MOC
Tags: 
pub: oui
commentaires: ouiCopier

Discussion on fractal go in the computer-go mailing list (Oct 2000)

Vlad Dumitrescu wrote:

my first impression: interesting approach!

[Serge] thanks, vlad.

the big problem seems to be how to reduce the board size without losing
importnt information. If a reduced group becomes dead (because there isn't
enough space to make it alive), then the reduction fails...

yes, of course you will lose information. The key word is "important". My assumption is that you will not lose important information. This is highly dependant on the details of the reduction algorithm, which I did'nt want to dig trough. If a threat or atari on the smaller board is an (even less important) threat on the corresponding group on the larger board, important information is not lost.

one way to handle this might be using a method presented here for som months
ago - I'm not sure I remember correctly -- building a "feature tree" where a
string of stones or liberties becomes just a node... if the reduced board
position has the same feature tree, then it might be close enough to the
original one.

yes, i remember of that. But, alas, even the feature tree can not be exactly the same in both boards. Suppose a chain has a two distinct (not adjacent) liberties on the larger board, the corresponding chain on the smaller board may have only one (or even none). But the similarity btw both feature trees can be computed, and this number can give an evaluation of how "accurate" the reduction algo is, and may be used to select the "best" choice for local reductions and guiding the reduction process. Interesting idea.

A good working reduction algo may need to use a try and evaluate approach. One critera is the similarities btw both boards, another can be the similarities btw both feature trees.

Why do you say the branching factor is reduced from 361 to 4? it is so
directly at the 19x19 level, but you have to search the reduced boards too,
thus there are more moves to look into before being able to choose one of
the 4...

Of course you're right. I was a bit provocating when saying you have 361 to 4. However, since the searching process is an exponential one, and since the number of searches is a polynomial of degree number of subboards, the unknown beeing the (exponential) local searches, if you reduce the exponent, even thought you increase the number of searches, you end up with a dramatic net gain.

new approaches are always welcome! :-)
/Vlad

===============================

"Johan Roos (QCS)" wrote:

Interesting.

I suppose this algo would suggest a move in the center as a first move?

/Johan

NO !
suppose you play on a (level zero) 19x19 board, and the level 1 board is 13x13 :
then the best openings on a 13x13 are 2-3, 3-3 and 3-4 points, wich translates into 3-3, 3-4, 4-4 and 5-4 points when "uploaded" onto the larger board (simple linear coordinate transfo).
Then the fractal algo will open the game with one of these points, which are the bests ones on a 19x19 booard (at least, these are the most common)

"Johan Roos (QCS)" wrote:

My thought was,

As the center cross maps to the center cross of the board level above, and the center point is best on a 5x5
board it should

/Johan

You have a point, but not for the good reason ;-). The idea of the center cross shared by all board is just one way, among others, to reduce boards. But any reduction sheme wil manage to keep roughly the same proportion of white, black and empties in the center area. So you're right, since center (3-3) is the best opening on a 5x5 board it should translate all the way up...

But wait.

Suppose a 19x19 -> 13x13 -> 9x9 -> 7x7 -> 5x5 distribution of "fractal" boards. When uploding the 3-3 point from 5x5 to 7x7 board, it expands to an area of 3x3 intersections, located in the center of the 7x7 board, with best probablity of the center 4-4 point.

1 2 (3) 4 5 5x5 board, () best point
1 2 (3 4 5) 6 7 7x7 board , () area uploaded

but the local recursive search in the 7x7 board comes into play, looking further to decide which of these 9 points is the best. Then it may select 3-3 point instead of the 4-4, because 3-3 is a better opening than 4-4 on a 7x7 board.

then you expand from 7x7 to 9x9 as follows, ginving a 2x2 area (3-3 to 4-4) point :

1 2 (3) 4 5 6 7 7x7 board, () best point
1 2 (3 4) 5 6 7 8 9 9x9 board , () area uploaded
1 2 (3) 4 5 6 7 8 9 9x9 board, () point selected by search

the local search on the 9x9 board will gibe 3-3 point as the best opening.

Then you upload that (9x9)3-3 point to the 13x13 board, giving an area of size 3x3 located in the southwest : points 3-3 to 5-5

1 2 (3) 4 5 6 7 8 9 9x9 board
1 2(3 4 5)6 7 8 9 A B C D 13x13 board, () area aploaded
1 2(3)4 5 6 7 8 9 A B C D 13x13 board () 5-5 point selected.

again the local search runs, and my come with the 3-3 point as a result on the 13x13 board (and we know that 3-3 or 3-4 are the best opening on 13x13). Then you upload that (13x13)3-3 point to the 19x19 board, giving an area of size 3x3 located in the southwest : points 3-3 to 5-5

1 2 (3) 4 5 6 7 8 9 A B C D 13x13 board
1 2(3 4 5)6 7 8 9 A B C D E F G H I J 19x19 board

And so we come with the result that we expected : 3-3, 3-4, 4-4 and 4-5 (and perhaps 5-5 and 3-5) are the best first move on a 19X19 board.

So you see that the center opening on the 5x5 board does not "translate all the way up to 19x19.". Insted, because of local searches, it expands in the very familiar openings in the corner that we are used to.

==========================

Tapani Raiko wrote:

the big problem seems to be how to reduce the board size without losing
importnt information. If a reduced group becomes dead (because there isn't
enough space to make it alive), then the reduction fails...

This is a good point. The reduced shapes don't follow the same rules as
mere stones. Perhaps the reduction might work somewhat, if there were also
special stones to represent an eye and so on.

By the way: try to imagine a board with 31 distinct living groups
reduced to 5x5 board!!! What use is there from having solved 5x5 go?

But of course the weirdest ideas are usually the best way to good ideas...
:)

Of course the ultimate 5x5 board is useless for tactical needs. But for strategic ones ? The assumption I make in fractal go is that master 19x19 games, when "reduced", even to as little as 5x5, still have some meaning : first occupy one corner, then extend to a border, invade opponent groups, and so on... Also don't forget that the fractal go algorithm is not a one-step reduction from 19x19 to 5x5 : there are several intermediate sizes, and at each size you perform a "local "search" (with a small branching factor) to get the "best" move for this size.

=============================

Tristan Cazenave wrote:

Fractal Go reminds me of Bruno Bouzy's thesis, where
he says that what happen at the level of stones is
similar to what happens at the level of abstract groups.
He once wanted to show Go boards to B. Mandelbrojt, but
we never had the opportunity to do it (yet).

Tristan.

dommage !

=============================

Joan Pons Semelis wrote:

The idea looks workable for strategic decisions about important
areas to play, but tactically go is not scalable. Just take a 3-3
invasion: you still need 2 eyes to survive, even if they are small,
and only 1, even if it's as big as a rabbit 6, makes a dead shape.
Unless you change also L&D rules, using for example immortal stones,
a go variant pretty interesting.

Joan

That's right. This is why a local search is nessary at each subscale, to account for this tactical complexities. But the number of move to explore for these local seraches still can be reduced by the "genius advices" uploaded from the immediate subboard. So the search is tractable, and may be 15 or 20-ply, which is enough for most tactical needs.
So i don't think that your (good) remark is killing my idea.

Also the fractal stuff might be only a part of a whole programm, which might use both fractal "advices" and more classical ideas (patterns, neural net...) to select the bestmove at a given time.

=========================================

From: "Vlad Dumitrescu"

Of course the ultimate 5x5 board is useless for tactical needs. But for
strategic ones ?
The assumption I make in fractal go is that master 19x19 games, when "reduced",
even to as little as 5x5, still have some meaning : first occupy one corner,
then extend to a border, invade opponent groups, and so on...

Just a thought: at small board sizes, the special properties of the corner are much more important that at large board sizes... Also life and death is much more important on a 5x5 board... doesn't that somehow affect the results? Or maybe the play on the reduced boards should not be "real Go", but something else, tailored to give good moves on the larger ones - and the small boards become in fact "feature selectors" for the larger ones!

It would be interesting to really be able to test these ideas, because that is the ultimate proof that the algorithm works or not. There are so many so called "weird" ideas that prove to be the only solution...

regards, Vlad

===========================================

Matt Gokey wrote:

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->.. scheme, 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 tuning here.

Serge Boisse

Back to fractal go description.