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, an