Computer Go Musings

    Keywords: Software

Computer chess works very simply. The computer looks at all of the (typically <40 per ply) moves, and gives them a numerical rating. When the calculation time is done the move with the highest numerical rating gets played.

Too often people who are trying to program a computer Go game fall into this trap. They want the computer to be able to look at move 1 and move 2 and rate one move as better than the other.

What you need to do is have a main loop like this:

int main () {

  if (move = CanConnect ()) play_move (move);
  else if (move = CanCut ()) play_move (move);
  else if (move = CanLive ()) play_move (move);
  else if (move = CanKill ()) play_move (move);
  else if (move = CanInvade ()) play_move (move);
  else if (move = CanBlockInvasion ()) play_move (move);
  else if (move = CanShoulderHit ()) play_move (move);
  else if (move = CanEstablishTerritory ()) play_move (move);
  else if (move = CanPress ()) play_move (move);
  else if (move = CanFillDame ()) play_move (move);
  else play_move ("Pass");

}

This way the computer knows its priorities. First priority is to CONNECT and STAY CONNECTED. If it can't connect then it must try to CUT THE OPPONENT. If it can't connect up and can't cut then it better TRY TO LIVE. Etc.

Then you have the main loop established and you work on the subroutines. How does a computer know if it can connect? Where will it need to try to connect most? Is trying to connect just a waste of time?

Then you test it. You've got to assume that the computer will be weak so you give it four stones. Then you start to play joseki against it. The computer should be able to work out, on its own, the joseki. If it can't or openly blunders, you know that there's a problem in the subroutine that led it to that move.

[Diagram]
Simple Example  

3. Connection threatened - extending
5. Invasion threatened - blocking
7. Invasion threatened - blocking

Does that make sense?


Not to me (Sandy Harris).

3 is a standard move, but only one of several choices. It appears your program would not even consider attaching above stone 2. That is a viable alternative in this position and the best choice in some related ones.

5 is a reasonable move but unnecessary. The player should at least evaluate the possibility of tenuki instead. With the rigid ordering of priorities in your subroutine, the program does not even consider it.

I think 7 is a bad move, moving toward white's strength when there are lots of alternatives. I'd be interested in hearing strong players' opinions on this.


[Diagram]
Where Go Computers Go Wrong  

It should be obvious to everyone that this shape is dead. Yet too many computers will say, "Oh, I've got more than three liberties, I must live." Even a group with 5 liberties can die (see Killable Eyeshapes Introductory).


exswoo: Umm...I don't think it'll be quite that simple. For one thing, the AI (Artificial Intelligence) has to know how to connect, if the connection is necessary, and how to connect the best way, keeping sente, fighting ko, and so on. A series of if-else statements is very poorly suited to AIs in general I think, because you need to be able to "think" non-linearly.

Sean: Details for how to connect and what is connected can be fleshed out in the subroutine. See GorobeisGoProgram/Introduction for discussion of how much GnuGo work is put into the tweaking the main loop vs. tweaking the subroutines? As far as I'm concerned it should all go into the subroutines.


jsha: You have an interesting classification of problems. I see it the other way around: I think that the really hard problem is joseki. If you could write a program that figured out joseki from first principles, you would probably become a very rich man. You might even discover some bizarre new joseki! As I understand it most Go programs have some sort of pattern-lookup for the opening game.

Conversely, any Go program that can't figure out that the above square shape is dead probably isn't worthy of the name. All it requires is a little bit of (not very deep) search. In fact, even if a program doesn't search it should assume (bad idea) the group is dead because it does not have two eyes and is trapped.

I like your classification of types of move, though: I've often thought about a similar arrangment. There is no strict hierarchy, though; rather you should have a set of move generators which generate moves to cut, connect, steal eyespace, extend, etc. The moves generated by each generator would have to be considered in terms of the local situation, but they give you a starting point. It also allows some small amount of provision for moves with multiple uses. Moves can be considered with more weight if two move generators agree on them.

Dieter: I don't think the main problem is to find subroutines that decide whether a group is alive or a position can be cut. The main questions are: is it worthwhile to live? or am I cutting weak or strong groups? and on top of that who leads in territory? or who is thicker?. Then comes a selection of moves that are candidates to serve the goal set. This selection is mostly done by intuition coming from experience. A computer can probably find good candidates by database searching. Only at the next step its tactical ability comes to surface, exploring a tree deep and broad but then it's faced with the first problem again: am I thicker than before?, have I more territory?, how did this sequence affect the rest of the board?.

As for A.I.: I will be truly convinced of artificial intelligence not the day a program beats a 9 pro, but the day the computer program adapts to a new board size faster than the 9 pro.

Karl Knechtel: You raise interesting points there, Dieter. Actually, has there ever been a pro tournament using Unusual Gobans? Anyway, the "questions" you suggest all seem very high level for the current state of computer Go - if we really had any idea how to answer that stuff I'm sure we would have strong computer Go programs by now :) I can imagine heuristics for counting unsettled regions (i.e. "who leads in territory?"), but decisions like "is it worthwhile to live?" strike me as fantasticly difficult to make with computational logic.

My own contribution to the topic: CGT Life Points Values. This occurred to me when I saw (on various SL pages) that CGT is being applied not just to point values, but also to eyespace values, connection values and even liberty values. I think it is possible to combine various CGT techniques into a super-analysis which may give a computer program some concept of Whole Board Thinking.

Stefan: Another question to the original poster of this model: why is there a hierarchy in the subroutines? Why not have them all generate their favourite move and look for moves suggested multiple times? By definition these would be dual or multi-purpose moves, a good thing in Go. Then, if you didn't find any, you could always revert to prioritising moves via the subroutine pecking order in the end.

Sean: I am the page creator, but don't know how to put my name on. I am not an expert Go player by any stretch of the imagination, yet I manage to solidly defeat every Go program I've played. I can beat TurboGo with 7 stones. I never count territory. I don't know joseki. I only do one thing - connect everything. I always win against a computer program by doing that. That's why I put that as the first thing. See GamesAgainstComputers1 where the computer initially seems to be doing great. However, its groups quickly get cut and it makes no effort to keep them connected.

exswoo:To be fair, Turbo Go is a pretty weak opponent, even as far as Computer Go is concerned. The biggest flaw in the hierarchy scheme of course, at least in the way that the way you have it set up, is that the AI will ALWAYS connect and won't even go to the other sub-routines, since there is no position in Go where a connection isn't possible somewhere on the board. I personally don't see how it would be possible to write a decent AI that didn't didn't have a move generating function...

I'm also not convinced that checking for dual purpose moves by itself is very useful. There are many, many dual-triple-quadruple purpose moves that are usually not played because of the moves either being slow or being redundant. Perhaps such a check would be useful if the AI first managed to narrow the candidates for the best move down to a handful of choices and had to choose from there?

[Diagram]
How Many Computers Will Figure Out They're Dead?  

I'm betting not many.

Confused: When asked about the status of the above Black group, Many Faces of Go replies with: This group is probably dead, but may be able to live with some difficult sequence.

This seems a pretty good judgement of the situation here. Black can still live, if he can play two stones in a row, perhaps due to a Ko fight somewhere else.

Sean: Somewhere in here I saw someone say that for chess the goal is not to look ahead a move or even two moves or a certain set number of moves, but to have a realizable plan. A Go master countered that in Go you shouldn't have any plan because having a predetermined plan will ruin your flexibility in dealing with your opponent. I consider it differently. The goal, in Go, is to have two plans, either one of which can be implemented. This is the essence of miai.

[Diagram]
All Stones Connected  


I would consider that a computer subroutine should look at this situation and conclude that all stones were connected. After 2, however, the computer should worry that a later move at 4 would effectively isolate the stone. Accordingly the computer should feel reluctant to play tenuki and instead work on maintaining the connection between the two marked stones.


Computer Go Musings last edited by 131.111.8.102 on May 28, 2008 - 15:30
RecentChanges · StartingPoints · About
Edit page ·Search · Related · Page info · Latest diff
[Welcome to Sensei's Library!]
RecentChanges
StartingPoints
About
RandomPage
Search position
Page history
Latest page diff
Partner sites:
Go Teaching Ladder
Goproblems.com
Login / Prefs
Tools
Sensei's Library