Re: computer-go: Neural networks

[heikki@xxxxxx]

On Wed, May 16, 2001 at 01:17:22PM +0100, Julian Churchill wrote:
> The actual idea is to use a neural network trained on some professional
> games, as a sort of ultra fast pattern matcher, but it would also pick up
> trends and general techniques to apply to playing Go as it was trained,
> that's one of the features of neural networks. I am thinking of using this
> to suggest plausible moves given the current board state and then these
> could be fed into a minimax search, this could be taken further where the
> network suggests moves for each level in the minimax tree, keeping it
> focused. If the network was good enough at suggesting appropriate moves then
> only a few at each level need be considered, say a branching factor of 6. I
> hope this will be a useful improvement to the minimax search, especially
> combined with pruning techniques, allowing a much deeper search.

Personally I remain rather sceptical about this ever working, but wish you
good luck anyway.

The problem - or at least one of them - is that to appreciate the value of a
move, you need to know a lot of the context, far more than just a pattern of
black and white stones.  For example, it is relatively easy to make up
patterns that detect the possibility of cutting a one-point jump, but it is
much harder to see how much could be gained at making that cut, and at what
cost. Cutting a group in two halves that both have enough space for two eyes
is useless, compared to cutting off a large lump that can only make one eye.
Cutting off a few stones in the opening may be worth a lot, unless your
opponent can sacrifice those stones and build thickness that dominates the
rest of the board. Yet, later in the game, making one of those "bad" cuts may 
be a good move, if it forces the opponent to fill in just a few stones into
what would have been his own territory...

I have not yet found any decent way of structuring a neural network that
could take this sort of things into consideration. The mere board image is
far too simple to be of much use - sometimes a cut depends on a ladder that
goes on for 50 moves, and changes the move from a game-winner to a
game-looser.

Yet another problem is how do you evaluate the endpoints of your search? It
is allwell to pick up 6 (or 60) possible moves in any position, and play out
the sequences, but if you can not distinguish a winning position from a
loosing one, there is no way to make a qualified decision between them...
For example, if you read out that you can split a 4-eyed group into two
2-eyed halves, or into a 1-eyed part and a 3-eyed part, it is clear that you
choose the later. But if your code can not decide how many eyes a group has,
you are lost. You can have some heuristics to do that, but in the end you
will need some tactical reading to get reliable results - I know GnuGo
improved a lot when just such a reading module was added to an already
pretty advanced static eye reading code (look for the "owl" code in the docs
or in the source)

One of my dreams has been to use a neural network for evaluating positions.
Not based on a board image at all, but on a great number of carefully
prepared key numbers. Unfortunately Ihave never had the time to dig deeper
into it. If there is interest, I can try to explain my ideas here, if only
to get them shot down...


Best of luck to your project, and keep us posted. I would love to hear that
my scepticism was unfounded!

- Heikki





-- 
Heikki Levanto  LSD - Levanto Software Development   <heikki@xxxxxxxxxxxxxxxxx>