Take the 2-minute tour ×
Board & Card Games Stack Exchange is a question and answer site for people who like playing board games, designing board games or modifying the rules of existing board games. It's 100% free, no registration required.

I am a relative newcomer to Go and more interested in the programming aspects of designing a Go Engine.

Do Go engines use a systematic list of Endgame positions with known wins, the way chess engines do? And do professional-level Go players memorize a list of endgame positions as part of their training?

Some online digging turned up this Wikipedia article and computer science paper suggesting that Solving Go Endgames by computer is really hard problem, guaranteed to take up plenty of time. Perhaps that's the reason why Go endgame tablebases don't exist / aren't widely used?

share|improve this question
    
On topic at game development? –  DJClayworth Nov 9 '11 at 22:14
    
As there is two question in one I migrated the second here –  Xavier Combelle Dec 13 '11 at 17:24

2 Answers 2

up vote 14 down vote accepted

I know much more about Go than chess, so I don't know how accurate my guesses about chess endgames will be, but... I think chess tends to be at its simplest in the endgame (like Go), and there is little information in the endgame about how the rest of the game progressed (unlike Go). And, there are algorithms for winning (in some cases) that generalize to a large number of positions. E.g., if white has a Queen and a King, and black only has a King, unless the Q is about to be captured white will win, regardless of position.

In Go, the endgame is also the simplest part of the game, in that it is the only part of the game in which the score and the value of each move can be calculated very precisely, however position is everything, and you will never see two games end with the same board position. In chess, you can generalize many positions to what pieces remain, but in Go the only generalization is the score count and the number of points still remaining to be taken.

It would be utterly impractical to rely on whole-board level tables in Go, however many small areas of the board will fit common patterns, which are memorized by Go players and programmed into computers alike. A medium-level example would be bent four in the corner is dead, but you'll see that this relatively common position is not at all obvious to a beginner and comes with several caveats (no un-removable ko-threats, surrounding group must be alive with 2 eyes), and while relatively common, it is somewhat of a special case.

Something like knowing where to play to kill (or save!) bulky five (and many many other shapes) should be automatic for a human or computer.

Programming a computer to play good yose is a very hard problem, but is one of the few aspects of Go at which computers can beat professional Go players, as it is all calculation and, while difficult, the theory is well-understood. To do it effectively the program must be able to estimate the current score, identify the moves left on the board that are worth points, and sort them in order of worth---not trivial. This article might be a good place to start.

Summary: There is a place for systematic lists of positions in Go programs, but they won't be useful for whole-board positions. The program needs to be able to evaluate the life/death status of every group on the board, and it is in these one or two group positions that lists will be most useful---and they'll be valuable throughout the game. In trying to attack opponent's groups, your program's goal won't be just to recognize shapes from the list, but rather to force the opponent into shapes that it knows are dead, while maintaining live shapes itself. See also Common Corner Shapes.

In writing a Go program, I would give you the same advice as I would a person learning Go: start on a small board, even as small as 5x5 until you have the rules down. Move up to 7x7, and then stay with 9x9 for a long time before you even think of trying 13x13.

Good luck!

share|improve this answer
    
And, after writing this answer last night, I woke up to this article in my inbox: [usgo.org/resources/downloads/Supercomputer%20Go.pdf] –  Gregor Oct 31 '11 at 17:33
    
Clearly, the Go god was listening. –  Ganesh Nov 1 '11 at 0:07
2  
Good answer, another page on SL that might be useful (the closest thing I know of to the endgame table asked about) is the miai values of common endgame positions page - senseis.xmp.net/?MiaiValuesList –  Mef Dec 4 '11 at 13:41

There are no whole-board endgame databases because there are too many possible permutations in the end. Such an approach could not be handled with state-of-the-art computer systems.

The good news is that endgame databases for confined, local situations do make sense and can be applied really well, the further the endgame has progressed. After you have analyzed, what's the result of each confined, local situation, you can calculate the best way to deal with them by finding the right order of moves. Of course it is not that easy to find a perfect solution, because you have to time "free" sente moves that do destroy your own ko-threats and so on, but AI endgame in Go is pretty good compared to midgame.

To understand the concept of the endgame, common patterns, the importance of sente/gote and so on, I can recommend the book The Endgame, if you are interested in them.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.