Re: [gnugo-devel] address@hidden: Re: GNU go and Artificial Intelligence?]

[Paul Pogonyshev]

> > My name is Ole Dahl Rasmussen, I am a freelance journalist and I am
> > writing an article on Go and Artificial Intelligence for the
> > Scandinavian popular science journal Illustreret Videnskab. I called the
> > Free Software Foundation today, Thursday, and they gave me your email.
> >
> > In connection to this article, I have some questions that I hope you
> > would be able to answer, or that you could eventually direct me to
> > someone who could.

Dear Mr. Rasmussen,

As Daniel Bump wrote, he redirected your message to the GNU Go mailing list,
which is certainly the place where you questions can be best answered.  Here
is my shot at the first two.  Feel free to ask more questions of for
clarifications on the following text.  Please reply to the list---this way
more people can help you.

> > The questions are the following:
> >
> > I have heard that computerprograms are not very good at go. Why is it so
> > difficult for computers to play go?

Game-playing computer programs generally use a technique called ``search.''
Essentially a searching program analyzes all positions than can emerge after
N moves and then selects the move that leads to the best result.

Searching can be subdivided into two parts: search algorithm and evaluation
function.  Search algorithm determines in what order the future positions
should be analyzed.  It also usually skips some alternatives, either because
they are proven to be ``worse'' in the process or because they ``seem likely
to be worse'' (heuristical approach.)  Search algorithms are needed because
the number of possible positions grows extremely fast as N grows.  If on
each move you have M alternatives, then the number of positions after N moves
is roughly M ^ N (M in Nth power.)  Search algorithm allow to greatly reduce
this number and thus make searching much faster (often some orders faster.)

Evaluation function determines which positions are considered ``good'' and
which are ``bad.''  In other words, it gives a preference order over the set
of all possible positions.  When our depth N is reached (i.e. when N moves
are ``played'' in the process of searching), evaluation function is called.

Search algorithms are game-independent save for minor game-specific
optimizations.  Their goal is to reduce average ``branching factor''---the
number of alternatives considered on each moves---of the search tree.  The
smaller the branching factor, the faster the program is.

Evaluation functions, on the other hand, greatly change from game to game.
Indeed, to know how good a position is, you have to know the game rules and
goal.  Evaluation function directly influences program's strength, while
a good search algorithm does this indirectly, by making the program faster.

Now, finally, we can answer why Go is difficult for computers.

First of all, Go has large branching factor.  In the beginning of the game
each player has over 300 legal alternatives on each moves.  It can be
considered that branching factor of Go is 150--250 on average.  Of course,
advanced search algorithms can reduce this a lot, but it will still be way
higher than for games like chess (where average game branching factor is
about 30.)  Of course, we can still use search no matter how high the
branching factor is, but this means smaller search depth, N, and hence
much weaker program.  Recall that branching factor is to be rised in power N
to estimate the number of calls to evaluation function.  So, a Go program
would be able to search *much* shallower than a chess program in the same
time.

That's not all, however.  Another very important problem lies in evaluation.
For chess evaluation function can be made efficient and fast.  For instance,
simply adding material points with a few other terms like mobility will give
you a modest evaluation function which, complemented with a good search
algorithm, will play sane chess games.  (Though you will not be able to get
to the top program's level with this, of course: their evaluation is well-
tuned and much more complicated.)  But in Go evaluating a position is not a
simple task on its own.  For instance, you absolutely have to know which
stones are alive and which are dead.  But you cannot tell this just by
looking at the board, you have to analyze life-and-death problems.  In other
words, to evaluate a position you have to at least run smaller-scale searches
for each group of stones on the board!  A good evaluation function for Go
would be perhaps thousands times slower than for chess.

So, computers are weak at Go because they cannot get to even mediocre result
with simple search: branching factor is high and good evaluation is very
slow.  Another, quite often mentioned reason, is that Go is a game where
strategy is very important, while chess is mostly tactical.  This is not so
clear and quite speculative, though.

> > How are you trying to learn them? What techniques do you know of to
> > learn computers to play go, and what are the special features in GNU go?

The technique described above is known as ``global search,'' because it
considers the whole board position at once.  For the reasons mentioned,
global search is nearly hopeless for Go (at least if not mixed with other
techniques.)  However, GNU Go *is* a searching program, but it uses several
different local searches instead of one global.  They are often called
``reading'' instead of ``search'' to follow Go therminology.

Go is a game where you can divide the board into ``local games'' on
different levels.  Of course this different local games do not exist on
their own, they influent each other, but it is possible to achive good
results by analyzing them separately.

GNU Go has two general levels of local games: tactical and life-and-death.
On the first (lower) level individual groups of connected stones are
considered.  They are called ``strings'' in GNU Go, or sometimes
``blocks'' elsewhere.  Life-and-death (higher) level is concerned with
larger groups, called ``dragons'' (or sometimes just ``groups'' elsewhere.)
This is the level where ``two eyes live, one eye dies'' rule works.  While
strings that are found unattackable can easily end up dead, dragons should
not.  If a dragon is found alive and is later killed, then either GNU Go
has sacrificed it for a larger gain elsewhere, or it misread the position.
And one of the important goals is to reduce the likelihood of the second
scenario.

For each dragon on the board GNU Go runs one or two searches with specific
goals.  First search answers the question ``if opponent moves first locally,
can she kill this dragon?''  If the answer is positive, then the second
search is run aiming to solve another problem: ``if dragon's owner moves
first locally, can she save the dragon?''  Three possible outcomes yield
three major statuses for dragons: ``alive'', ``critical'' and ``dead.''
The fate of critical dragons ultimately depends on who moves first locally.

Apart from described life-and-death reading, GNU Go has a number of other
local searches.  Obviously this includes reading of whether a string can be
attacked and/or defended.  This is simply called ``tactical reading.''
Very important is connection reading that tries to determine if a player
can connect two his strings or disconnect two opponent's strings.  These
two searches are regularly called from life-and-death search, which
illustrates the point that evaluation function in Go has to include search
in turn.

Semeai reading is concerned with two hostile dragons at once.  While
life-and-death reading considers only one dragon and assumes that nearby
opponent's dragons don't change their status (alive or dead) in process,
semeai reading can analyze positions where life of one dragon depends on
whether it can kill an opponent dragon, and similar.  Semeai reading is
not a particularly advanced part of GNU Go: it involves heavily interacting
local games and those are always difficult.

Break-in reading tries to invade opponent's territory and block off
opponent's attempts to do the same.  Interestingly, it is closely related to
connection reading, though this relation is not obvious for a human player.
Roughly speaking, it tries to ``connect'' one of its strings to opponent's
territory, or, when blocking off, to ``disconnect'' all opponents string
from own territory.

Finally, there are two different combinational readers.  Their goal is
either ``capture at least one of these strings'' or ``defend all these
strings.''  One of them runs for the whole board and is thus not
particularly fast.  The other runs only for two strings and has about the
same level as the tactical reader.

Apart from being local, these searches has another aspect that differs them
from global search.  In global search it is common to consider all possible
alternatives and only then use various ``cut-offs'' to quickly abandon some
(``bad'') of them.  Local searches, on the other hand, usually specifically
generate alternatives to consider, instead of using all legal ones.  This is
mainly due to the nature of the problem, which is to answer ``yes'' or
``no'' to some question.  For various reasons, searching all alternatives in
this case is very inefficient.  So, in effect, in local searches evaluation
function is trivial (``yes'' or ``no'') but there is a third part: move
candidates generator (alternatives generator.)

GNU Go uses two major ways of generating ``interesting'' alternatives:
algorithmical and pattern-based.  Algorithmical generation involves hand-
coded Go knowledge.  It often uses smaller-scale searches.  For instance,
when trying to kill a dragon, it might help to capture a large (or, even
better, ``important'' in some sense) part of it.  This means using tactical
reading.

Another way is based on patterns.  It is well-known that in some common
positions (``patterns'') certain moves are almost always the best (locally.)
For instance proverb ``when attached---extend'' suggests this pattern to
use (in GNU Go): ``when you see an opponent stone directly next to your own
and there are no more stones nearby---extend you stone into a group of
two.''  Of course, patterns are not written in such way, rather they
resemble small pieces of the board with some stones on them and the
suggested move.

Patterns are not used blindly.  Some patterns have a ``constraint'' which
is actually a function that complements simple pattern-matching mechanism.
This constraint function often calls tactical or connection reading.
Pattern matcher can determine that ``the board here looks just like this
pattern.''  The constraint then can check, for instance, if certain stones
are alive etc.

Patterns are also used as part of move valuation.  Move valuation is a
module that actually does the work of evaluation function.  However, since
GNU Go doesn't use global search, move valuation is performed only once:
for that very position a move is being generated for.  Valuation combines
data from life-and-death, break-in and other readers, pattern matching,
territorial and influence analyzer and a few other GNU Go modules.  It
finally determines the best move which GNU Go reports.  If several moves
has very close values, GNU Go choses one of them randomly.  This is more
important than it sounds, because it makes GNU Go moves less predictable.

To summarize: main techniques used in GNU Go are various local searches
on different problem levels, heavily interacting with each other, and
pattern-matching.  GNU Go also uses a great amount of hand-coded Go
knowledge.

Hope this helps.

Paul Pogonyshev, GNU Go team