Re: computer-go: Programs learning to play Go

[Joan Pons i Semelis <joan@xxxxxxxxxxxxxxxx>]

Heikki Levanto wrote:
> 
> On Tue, Aug 21, 2001 at 02:59:02AM +0200, Joan Pons i Semelis wrote:
> > In a board of any size, which % of the total number of positions
> > do you estimate you need to have outputed to be usefull ?
> > Try in 2x2, 2x3, 3x3, 3x4 and 4x4 boards. Estimate at 7x7 which number
> > is it?
> 
> I don't think this is a relevant question to my model, as I never ever feed
> the board position to the net! I only feed it key numbers, like the count of
> living/strong/unknown/weak/dead groups, etc. Such figures can not be
> meaningfully computed from a 3x4 position!
 
Then may be they are not meaningful :-)
Seriously: in a 3x3 board you have a very good first move that's playing
in the center because it builds the stronger group possible, after that
you
can turn the rest of the game in a life & dead struggle, and still,
unless your
net decides that it is so and turns the problems to the life&dead
modules,
there's still room for good and bad shape that is what makes groups ( or
put it differently: arrangements of stones also taking into account the
sides and corners ) weak or strong.

May be to see if your key-numbers are really meaningfull a simple
application could work:

grab as many games as possible, find all the games close enough to a
given set
of numbers ( or even exactly equal ? ) at move 25, check which key
numbers they
have at #50, keep the more numerous subset with similar keys, add new
games of 
similar keys, and so on. Finally compare the results of the games
(win/lose)
 
That should give statistical information about what's important; for
example, you
should find that most profesional games have a balance between number of
black
and white groups, and that inbalance usually means that the player with
more
groups loses. But this stops beeing really meaningfull once small yose
is
reached, and 3-3 invasions do not qualify as groups to be counted ...
sometimes.  

> > How to learn how to punish the most obvious mistakes, then?
> Note that this is not meant to be the whole program, only a component that
> evaluates the whole-board position. GnuGo is already pretty good at
> punishing tactical mistakes. I hope my net would learn to notice strategic
> blunders... Maybe I need to feed it many games with known mistakes too (any
> sources of suitably commented games?)

The Go Teaching Ladder, but are commented for human readers.
 
> > This is good to find flaws in the evaluation function: if it thinks the
> > position becames unbalanced on a pro game that ends with someone winning
> > by less than 5 there's probably an error.
> 
> No, in the end one player has won by 100% probability, and the other by 0%.
> Even if the score is tight, this still applies.

100% only exists when the game is over. A 3.5 win is almost a sure win
for any
pro 100 moves before the end of the game, and that with japanese rules
that still
shorten the end by maybe 15 dame points, don't count if you have to
actually
kill dead groups.
A typical european 10 kyu (that's 13K* in IGS more or less) loses about
30 points
during those 100 moves. If he's playing another player of equal strength
those 30
points are more or less taken back, but a 3 point difference before
means it's
a pretty much undecided game still. 
The probability of winning depends on the players.

> > > Maybe, in a few years when computers get really fast, it
> > > might make sense to try and evaluate most of legal moves, or to even to do
> > > simple limited read-ahead.
> >
> > That's not a few years, I'm afraid. Better strive for a good way to
> > prune the tree from the beginning.
> 
> True, and I have another way in my mind. Instead of trying hundreds of
> moves out, you could quite quickly try ideas, directly on the net, without
> ever playing them out. For example, an idea would be to connect those two
> groups. That would reduce the number of one-eyed groups by two and increas
> the number of two-eyed groups by one (and make even bigger difference in the
> number of stones and empty points affected). Now the net should tell us that
> this will increase our chances by a small number. Likewise we could imagine
> an invasion, adding one weak group to worry about, and neutralizing lots of
> territory. Again the net should come up with a value for this idea. This
> would enable us to test out many high-level ideas, and at a later stage, try
> to find moves to implement them. Once played on the board (a temporary board
> inside teh engine), we could recalculate all inputs and verify that the
> strategic value holds, and that it does not have too many side effects.

This looks promising: you look for the best strategy, then try to
implement it,
if it's not possible (best would be to kill that big weak group floating
in
the center) try next one till one is feasible. Goal oriented is how
human 
play, and it works pretty well. But still, when deciding how to try to
implement the strategy and if it works at all, we are very good at
looking
only at a very few moves, the main difference between weak and strong
players
is which moves they look at ("this is not a move" or "this move does not
exist"
are usual comments of strong players), even more deciding than the
strategy 
choosen when it involves weak groups or the timing to make the first
really big
yose move.


> Still, all of this is empty speculation, until I get enough time (read:
> priority) to do anything about it.
> 
> -H
> 
> --
> Heikki Levanto  LSD - Levanto Software Development   <heikki@xxxxxxxxxxxxxxxxx>