Auteur: Serge Boisse
Date: Le 29/09/2000 à 17:03
Type: web/MOC
Tags: 
pub: oui
commentaires: ouiCopier

A fractal algorithm for computer Go

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.

It's an idea I had three years ago, but I lacked time to get a full working program for it (I only wrote parts, but not a complete program). I kept it a secret until now, in the hope I could one day win a lot of money with it, but now I realise that sharing ideas is better for everybody, including me !

I'm confident that some of you will find the idea interresting AND workable, and will write code for it. If you do so, let me know it !

This page is a bit long. I apologize for it. But I hope you will find it worth reading, and that you will pardon my poor english...

COPYRIGHT NOTICE : My idea, I call "fractal go", described below, will be public from now on ("now" meaning the date of this posting, September 29, 2000), so that you can use it freely without giving me any reward or money, with the only two following restrictions :

1. Should you use this idea in your code, please include the comment "this code uses the idea of fractal go by Serge Boisse" in your source code.
2. You are not allowed to ask for a patent for any algorithm based onto this idea. By the way, I will not ask for a patent, too. 

Introduction

Basically, you all know that current go playing programs suffer from two major handicaps :

• They lack a "sense" of global strategy that human apparently have, and

• They lack also good tactical search, for three reasons :

• Tactical and strategic play are deeply mixed in go, because of sente/gote and Ko fights.

• The famous enormous branching factor that precludes any deep global searching.

• Even in local searches, restraining the number of "possibles" moves is a hard task.

The idea of fractal go adresses both of theses handicaps, and I hope it could result in a dramatic improvement of the strongness of go programs. Strategic play in go can often be expressed by humans with sentences like "chase that group", "restrain influence of this group by building a wall here", "developp this corner", "keep sente", and so on.

Now suppose your program has somehow access to a genius go expert who is able to say "you should play in this area, then your opponent will likely play int that area", and so on, where the given "areas" are as small as a square of 2x2=4 intersections. No doubt that you could then explore a 30, or even 40 ply deep tree, using a stupid alpha-beta search, and have a super strong program as a result. Note that your program is not obliged to take what the genius says for granted : it might have its own list of "possible good moves", using only the genius advices to sort and restrain that list. You got the idea. What fractal go gives you is just that genius advice, with a little computation of course... and the warranty that, if you follow the advices, you will have a good strategic play as a result - it just cannot be bad !

Now the heart of the idea :

When playing onto a standard 19x19 goban/board, which i call "the board at level zero", consider simultaneously playing onto a smaller board, say 13x13, which I call the "reduced board at level 1". The reduced board is arranged in a manner that, also smaller, it looks strangely "like" the level zero board :
if for intance you have a big white group in a corner of the normal (zero) board, you will find a (slightly smaller) group of white stones in the same corner of the reduced board, with a "similar" (but slightly different) shape. You guess it, the reduced board is simply computed from the larger board, using an algorithm apparented to standard image reduction algorithms. I will developp this point later.

Now suppose that you somehow know the best possible move on the reduced board : it make sense then to "upload" that information into the larger board, translating the location of the good move into a small area of the larger board. You got your genius adviser ! Then the process is a 4-steps one :

1. First "reduce" the larger (level zero) board into a smaller, reduced, level 1 board.
2. then compute the bestmove for that smaller board, say 'white E5'
3. then "upload" or "expand" the location of that best move into a small area of the larger board where it would be good to play :say 'G7 or H7, or G8 or H8'.
4. and finaly select the best move to play onto the larger board, using an heuristic and/or a search which repeat the full procedure for the next moves, but the expansion branching factor is 4, not 361... you do not dream !

Why should the advice be good ? because on the reduced board, it is the best move and leads to the victory : if you threaten or kill a big opp group onto the reduced board, the expanded move will also threaten the corresponding group onto the larger board. yet an atari on the smaller board has a good chance to be a serious threatening on the corresponding larger group. In a sense, to compute strategic moves onto the larger board, you consider more tactical (but good) moves onto the smaller board. Another reason is, that uploaded moves (from the best move onto a reduced board) are very often sente. And you all know that, in a typical human expert game, the winner is the one who was able to stay sente most of the time.

On the other side, the corresponding group onto the larger board will be bigger and will have more liberties, thus it might be harder to capture and this might take more steps. This is because ther is a subtle phenomenon at play here, i call time dilatation.

On the larger board, there are 19x19=361 moves, and the whole game will last a sgnificant part of that, say 250 moves. However, if the reduced board is 13x13 (169 intersections), a normal game will last about 120 moves. So a move onto the smaller board is roughly equivalent to two moves onto the larger board. That is,

• take the larger board in a state S1 and reduce it, giving a smaller board in a state s1,
• then play a move onto S1, giving state S2, and reduce it, giving s2 :
  sometimes, with a 1/2 chance in fact, will will get s2=s1 dispite that S1 != S2 : this is why it is harder to kill a larger group.

You sure have noticed that I did not say how I got the best move onto the reduced board at step 2) of the above procedure. Well, it is where the "fractal" term comes into play :

To get the best move onto the smaller (level 1) board, just add an even smaller (say 9x9) "level 2" board, and repeat the procedure. And to get the best move on that level 2 board... yes, you got it. Just re-iterate until you have a 5x5 board, onto which a perfect play can be precomputed and stored on disk.

tricky tricks

lists of move

Instead of finding only one "best" move onto to the smaller board, consider the easier-looking task of finding a small list of "good" moves. Then when uploaded onto the larger board, this moves will result in a list of small areas, possibly intersecting. the branching factor will be higher, but the task of finding good moves is easier. There are a lot of possible variations and possible tunings here.

time dilatation

I described this curious phenomenon above. But there is another consequence : when you "upload" a move from the reduced board, it might be valid for more than one move onto the larger board. So the area that you get from uploading is in fact a list of small areas resulting from the last two or three uploadings...

center managment

If you play go, you know that center control is the big thing that 19x19 adds over 13x13 game. So just why should we get a good strategic advice from a (reduced) board which does not care for center control ? well, just because center exists on the smaller board, even if it has far less importance than onto the larger one. But this "far less" is just the reduction factor.

You should consider several scales of succesives reductions, like :

• "standard" : 19x19 -> 13x13 -> 9x9 -> 7x7 -> 5x5
• "faster" : 19x19 -> 9x9 -> 5x5
• "slower" : 19x19 -> 19x13 (yes !) -> 13x13-> 13x9 (!) -> 9x9 -> 7x7->5x5

The "standard" scheme will partially take the center control into account. It is a compromise, with all advantages and unconveniences of a compromise.

The "faster" will take lass time, but the reduction is a bit brutal and you should notice that any move onto a 9X9 will translate into a 4x4 = 16 intersections area when uploaded, thus increasing the subsequent branch factor and finally gaining nothing.

The "slower" scheme is a bit curious, because it uses non-square boards. But why not, after all ? next-level board will look more closer to the original level board, and uploaded areas will only have 2 intersections. Just by precaution however, I prefer to reduce a square board BOTH into a horizontal AND a vertical rectangle. Eventually from those two rectangular boards i will get two different best moves, but why not ? The computing time will be higher, but not too much (4x in the above scheme), but the quality of the representation is greatly improved.

Again, make your own choice.

Illegal positions onto the smaller board.

When reducing the board, you can use a variety of algorithms (discussed below) .Of course, nothing prevents you to end up with an illegal position onto the reduced board : a stone or chain with no liberties.

I think this is mainly a false problem, and the reduction algorithm can be arranged so that this situation is avoided or corrected by, for instance, adding a liberty or removing a stone from the chain, wichever looks most "like" the configuration onto the original larger board.

The reverse is also true : when "uploading" a move from the smaller board, you must check its legacy.

Ko

Ko may differ onto the larger and the smaller board. A move that is forbidden by Ko rule onto the smaller board might be legal on the larger, but, anyway, this does not change dramatically the situation. More important, Ko threats on both board will likely correspond, and that is what is important.

Reduction algorithm

Several reduction algorithms are possible, depending from the reduction factor. For reducing a 19x19 to a 9x9, you can proced locally, as follows, since 19 = 9+1+9 and 9 is 4+1+4 :

   A B C D E F G H J K L M N P Q R S 
19 . . . . . . . | . . . . . . . . .
18 . NW sector   | . NE sector . . .
17 . . . . . . . | . . . . . . . . .
16 . . . . . . . | . . . . . . . . .         A B C D E F G H J
15 . . . . . . . | . . . . . . . . .       9 . red.. | .red. .
14 . . . . . . . | . . . . . . . . .       8 . NW. . C .NE . .
13 . . . . . . . | . . . . . . . . .       7 . sect. O .sect .
12 . . . . . . . C . . . . . . . . .       6 . . . . M . . . .
11 . . . . . . . O . . . . . . . . .  ===> 5 -----COMMON------
10 . . . . . . . M . . . . . . . . .       4 . . . . O . . . .
 9 COMMON-----COMMON----COMMON-----        3 . red . N . red .
 8 . . . . . . . O . . . . . . . . .       2 . SW. . | . SE. .
 7 . . . . . . . N . . . . . . . . .       1 . sect. | . sect.
 6 . . . . . . . | . . . . . . . . .
 5 . . . . . . . | . . . . . . . . .
 4 . . . . . . . | . . . . . . . . .
 3 . . . . . . . | . . . . . . . . .
 2 . SW sector   | . SE sector . . .
 1 . . . . . . . | . . . . . . . . .
Copier

The two board will share the center cross. The problem is now to reduce a 8x8 square into a 4x4 one.

• You can use a 2x2 to 1x1 majority algoritm for instance, with a "look next" to solve equalities.
• Or you can use directly such a majority scheme on the larger board, but since 19 is prime, you have to handle special cases at the center or the borders. But this works well for reducing a 9x9 board into, say a 6x6 one : you consider nine 3x3 a areas, that you will reduce in 2x2. On a 3x3 area, there are only 3^9 possibilities = 19683, that can be precomputed and stored in memory, saving real time computations.
• Or alternatively you can use a standard image reduction algorithm, considering each intersection as a pixel of one of three colors. it is best that black and white stones have equal contrasts on the original image, say red and blue, while empty may correspond to green. Image reduction algorithms are designed so that the human eye sees roughly the same "patterns" in the original and the reduced image, which is exactly what we are needing.

Uploading algorithm

simply consider a linar coordinate transformations, and look the place in the larger board that is closest to the transformed coordinate, then the next one, etc. so that you get an ordered list. This is quite simple.

conclusion

It is interesting to notice that the fractal reduction/uploading scheme seems to work because of the very "spatial" nature of the game of go. Unlike chess, for instance, in go shape and spatial relationships have a tremendous importance.

The fractal algorithm I discovered is an effective way to reduce the branching factor, from 361 to 4 !

It has the second major advantage of providing the program with a somewhat magical sense of strategy that current programs currently lack.

A funny extension of it is that the algo has the possibility of managing very large boards : 27x27,  37x37, 1001x1001 or even larger ones. I think that perfect or even "good" playing onto these large boards is above the limit of human intelligence. At the limit, an "almost" infinite board is, perhaps, what God is playing (against himself) at to build the universe. One fascinating feature of th go game is that both players are indeed building structures together : the physical universe might be a gigantic go game... And the fractal algorithm is the only way of handling such gigantic boards. I would be very interested if one reader of this page would think about and come with a theory of go game onto gigantic or even infinite boards.

Well, gentlemen, what do you thing about this idea ?
A discussion on this topic in computer-go mailing list