a*****g
发帖数: 19398 | 1 (转载)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
Posted by Biondy at 1:39 PM
Labels: Go Software |
|
