Why It's Hard to Create A Strong Go Software

For a long time it was a widely held opinion that computer Go posed a problem fundamentally different to computer chess insofar as it was believed that methods relying on fast global search compared to human experts combined to relatively little domain knowledge would not be effective for Go. Therefore, a large part of the computer Go development effort was during these times focused on ways of representing human-like expert knowledge and combining this with local search to answer questions of a tactical nature. The result of this were programs that handled many situations well but which had very pronounced weaknesses compared to their overall handling of the game. Also, these classical programs gained almost nothing from increases in available computing power per se and progress in the field was generally slow. Therefore, creating a strong Go-playing program was by many seen as something that could, if at all, be achieved only in the far future and possibly only with fundamental advances in general artificial intelligence technology. Even writing a program capable of automatically determining the winner of a finished game was seen as no trivial matter.


Computer vs. Human

The advent of programs based on Monte Carlo search starting in 2006 changed this situation in many ways, although the gap between strong human players and the strongest Go programs remains considerable.


Size of board

The large board (19x19, 361 intersections) is often noted as one of the primary reasons why a strong program is hard to create. The large board size is a problem to the extent that it prevents an alpha-beta searcher without significant search extensions or pruning heuristics from achieving deep look-ahead.

So far, the largest game of Go being completely solved has been played on a 5×5 board. It was achieved in 2002, with black winning by 25 points (the entire board), by a computer program called MIGOS (MIni GO Solver).

Most moves are possible

Continuing the comparison to chess, Go moves are not as limited by the rules of the game. For the first move in chess, the player has twenty choices. Go players begin with a choice of 55 distinct legal moves, accounting for symmetry. This number rises quickly as symmetry is broken and soon almost all of the 361 points of the board must be evaluated. Some are much more popular than others, some are almost never played, but all are possible.
[edit] Additive nature of the game

As a chess game progresses (as well as most other games such as checkers, draughts, and backgammon), pieces disappear from the board, simplifying the game. Each new Go move, on the contrary, adds new complexities and possibilities to the situation, at least until an area becomes developed to the point of being 'settled'.
[edit] Techniques in chess that cannot be applied to Go

The fact that computer Go programs are significantly weaker than computer chess programs has served to generate research into many new programming techniques. The techniques which proved to be the most effective in computer chess have generally shown to be mediocre at Go.

While a simple material counting evaluation is not sufficient for decent play in chess, it is often the backbone of a chess evaluation function, when combined with more subtle considerations like isolated pawns, rooks on open verticals, pawns in the center of the board and so on. These rules can be formalised easily, providing a reasonably good evaluation function that can run quickly.

These types of positional evaluation rules cannot efficiently be applied to Go. The value of a Go position depends on a complex analysis to determine whether or not the group is alive, which stones can be connected to one another, and heuristics around the extent to which a strong position has influence, or the extent to which a weak position can be attacked.


Evaluation function

Another problem comes from the difficulty of creating a good evaluation function for Go. More than one move can be regarded as the best depending on how you use that stone and what your strategy is. In order to choose a move, the computer must evaluate different possible outcomes and decide which is best. This is difficult due to the delicate trade-offs present in Go. For example, it may be possible to capture some enemy stones at the cost of strengthening the opponent's stones elsewhere. Whether this is a good trade or not can be a difficult decision, even for human players. The computational complexity also shows here as a move might not be immediately important, but after many moves could become highly important as other areas of the board take shape.

Combinatorial problems

Sometimes it is mentioned in this context that various difficult combinatorial problems (in fact, any NP-complete problem can be converted to Go-like problems on a sufficiently large board)[citation needed]; however, the same is true for other abstract board games, including chess and minesweeper, when suitably generalised to a board of arbitrary size. NP-complete problems do not tend in their general case to be easier for unaided humans than for suitably programmed computers: it is doubtful that unaided humans would be able to compete successfully against computers in solving, for example, instances of the subset sum problem. Hence, the idea that we can convert some NP-complete problems into Go problems does not help in explaining the present human superiority in Go.


Endgame

Given that the endgame contains fewer possible moves than the opening or middle game, one could suppose that it was easier to play, and thus that computers should be easily able to tackle it. In chess, computer programs perform worse in endgames because the ideas are long-term, unless the number of pieces is reduced to an extent that allows taking advantage of solved endgame tablebases.

The application of surreal numbers to the endgame in Go, a general game analysis pioneered by John H. Conway, has been further developed by Elwyn R. Berlekamp and David Wolfe and outlined in their book, Mathematical Go (ISBN 1-56881-032-6). While not of general utility in most playing circumstances, it greatly aids the analysis of certain classes of positions.

Nonetheless, although elaborate study has been conducted, Go endgames have been proven to be PSPACE-hard. There are many reasons why they are so hard:

* Even if a computer can play each local endgame area flawlessly, we cannot conclude that its plays would be flawless in regards to the entire board. Additional areas of consideration in endgames include Sente and Gote relationships, prioritisation of different local endgames, territory counting & estimation, and so on.
* The endgame may involve many other aspects of Go, including 'life and death', which are also known to be NP-hard.[17][18]

* Each of the local endgame areas may affect one another. In other words, they are dynamic in nature although visually isolated. This makes it much more difficult for computers to deal with. This nature leads to some very complex situations like Triple Ko, Quadruple Ko, Molasses Ko and Moonshine Life.

Thus, it is very unlikely that it will be possible to program a reasonably fast algorithm for playing the Go endgame flawlessly, let alone the whole Go game.


Speculations on why humans are better at Go

Go has features that might be easier for humans than computers.[20] The pieces never move about (as they do in Chess), nor change state (as they do in Reversi). Some speculated that these features make it easy for humans to "read" (definition needed) long sequences of moves, while being irrelevant to a computer program, while no rigorous cognitive neuroscience evidence indicating so.

In those rare Go positions known as "ishi-no-shita", in which stones are repeatedly captured and re-played on the same points, humans have reading problems[citation needed], while they are easy for computers.

Order of play

Current, Monte-Carlo-based, go engines can have difficulties in solving problems when the order of moves is important.

Tactical search

One of the main concerns for a Go player is which groups of stones can be kept alive and which can be captured. This general class of problems is known as life and death. The most direct strategy for calculating life and death is to perform a tree search on the moves which potentially affect the stones in question, and then to record the status of the stones at the end of the main line of play.

However, within time and memory constraints, it is not generally possible to determine with complete accuracy which moves could affect the 'life' of a group of stones. This implies that some heuristic must be applied to select which moves to consider. The net effect is that for any given program, there is a trade-off between playing speed and life and death reading abilities.

State representation

An issue that all Go programs must tackle is how to represent the current state of the game. For programs that use extensive searching techniques, this representation needs to be copied and/or modified for each new hypothetical move considered. This need places the additional constraint that the representation should either be small enough to be copied quickly or flexible enough that a move can be made and undone easily.

The most direct way of representing a board is as a 1 or 2-dimensional array, where elements in the array represent points on the board, and can take on a value corresponding to a white stone, a black stone, or an empty intersection. Additional data is needed to store how many stones have been captured, whose turn it is, and which intersections are illegal due to the Ko rule.

Most programs, however, use more than just the raw board information to evaluate positions. Data such as which stones are connected in strings, which strings are associated with each other, which groups of stones are in risk of capture and which groups of stones are effectively dead is necessary to make an accurate evaluation of the position. While this information can be extracted from just the stone positions, much of it can be computed more quickly if it is updated in an incremental, per-move basis. This incremental updating requires more information to be stored as the state of the board, which in turn can make copying the board take longer. This kind of trade-off is indicative of the problems involved in making fast computer Go programs.

An alternative method is to have a single board and make and takeback moves so as to minimise the demands on computer memory and have the results of the evaluation of the board stored. This avoids having to copy the information over and over again.

Source: Wikipedia