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

[OLE DAHL RASMUSSEN]

Dear Mr. Pogonyshev and others,

Thank you very much for very interesting and in-depth answers to my questions.

Earlier, I have been speaking with John McCarthy, professor emeritus from 
Stanford University, and he told me that go sometimes is characterized as 'the 
fruit fly of artificial intelligence’, thereby referring to the area of 
genetics where researches have used fruit flies as a research object. There aim 
here was obviously not to create the perfect fruit fly, but to contribute to 
the progress in the field of genetics. 

Since my article is for a popular science journal, I am hoping to make my 
readers relate to the go-subject by using some real world examples on where 
this kind of techniques could be applicable some time in the future. In the 
fruit fly-example from before, it is of course hard to determine the exact 
future usage, but it is not difficult to guess on using genetics for e.g. 
curing diseases, inventing medicine, developing crops etc. etc. 

If you should try to think about computer-go in the same way, what do you think 
could possibly be the usage of the techniques described?

Once again, thank you very much for your contributions so far!

Regards,
Ole

----- Original Message -----
From: Paul Pogonyshev <address@hidden>
Date: Friday, September 24, 2004 10:11 pm
Subject: Re: [gnugo-devel] address@hidden: Re: GNU go and Artificial 
Intelligence?]

> > > 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 
> evaluationfunction.  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, 
> whilea 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 
> programwould 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 
> searchalgorithm, 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 
> whichstones 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 
> wherestrategy 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 
> specificgoals.  First search answers the question ``if opponent 
> moves first locally,
> can she kill this dragon?''  If the answer is positive, then the 
> secondsearch is run aiming to solve another problem: ``if dragon's 
> owner moves
> first locally, can she save the dragon?''  Three possible outcomes 
> yieldthree 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 
> playercan 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 
> nearbyopponent'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 
> interactinglocal 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'sterritory, 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 
> possiblealternatives and only then use various ``cut-offs'' to 
> quickly abandon some
> (``bad'') of them.  Local searches, on the other hand, usually 
> specificallygenerate 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 
> evaluationfunction 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 
> tacticalreading.
> 
> Another way is based on patterns.  It is well-known that in some 
> commonpositions (``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 
> moveshas 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 
> searcheson 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
> 
>