Go
Go is a two player board game in which chance plays no part. It is an Oriental game which originated between 2500 and 4000 years ago and enjoys a similar status in Japan, China, Taiwan and Korea as Chess does in Western countries. Go is played on a board which consists of a grid made by the intersection of horizontal and vertical lines. The size of the board is generally 19 x 19, however, 9 x 9 and 13 x 13 sized boards are also used for playing quicker games. Intersection points are connected along the horizontal and vertical lines such that the neighbours of any given point are the intersection points that are horizontally and vertically adjacent to it.
Rules
Two players alternate in placing black and white stones on the intersection points of the board (including edges and corners of the board) with the black player moving first. A stone or a group of stones is captured and removed if it is tightly surrounded by stones of the opposing color. The objective is to control a larger territory than the opponent’s by placing one’s stones tactically, so that as few stones as possible could be captured by one’s opponent. The game ends and the score is counted when both players consecutively pass on a turn, indicating that neither side can increase its territory or reduce its opponent’s.
Liberties and Capture
Empty points that neighbour a stone are called its liberties (white and black dots marked in figure).
Any stone which has no liberties is captured and removed from the board. This is the only instance in which stones, once placed, are moved.
Suicide
A player cannot commit suicide by placing a stone in a position which leads to its immediate capture.
Repetition of Board Positions – Ko
To stop endless cycles occurring, a player cannot play a stone which causes a previous board position to be repeated. In general, the only situation in which a cycle can arise is called a ko. A ko situation can lead to a ko fight in which the player which loses a stone in the ko threatens an opponent stone elsewhere and then recaptures the opponent stone in the ko after the opponent responds to the threat.
Winning the Game
A player may pass at any time and the game is over when both players pass consecutively. A determination of territory begins by removing the stones in black strings and white strings which are dead. Each player then adds the number of opponent stones they have captured and the number of empty intersection points which are surrounded by their stones i.e. points that cannot trace a path to an opponent’s stone along the horizontal and vertical grid lines. The player with the largest territory wins.
Strategy
Opening
The whole board opening is called Fuseki. An important principle to follow in early play is “corner, side, center.” In other words, the corners are the easiest places to take territory, because two sides of the board can be used as boundaries. Once the corner are occupied, the next most valuable points are along the side, aiming to use the edge as a territorial boundary. Capturing territory in the middle, where it must be surrounded on all four sides, is extremely difficult. The first moves are usually played on or near the 4-4 star points in the corners, because in those places it is easiest to make territory. (In order to be totally secure alone, a corner stone must be placed on the 3-3 point. However, if a stone is placed at a 4-4 point and the opponent invades, the first player can build a surrounding wall as the second (invader) is forming a live group, thus exerting strong influence on a large area.) After that, standard sequences (Joseki) are used to divide corners, and extensions along the side are made. Usually, the center area is kept empty the longest. Plays are usually on the third or fourth line—the second makes too little territory, while the fifth is too easily undermined by a play on the third. A play on the fourth line is directed more towards influence to the center, a play on the third line more towards making territory along the side.
Connection and separation
A fundamental Go strategy involves keeping stones connected. Connecting individual stones into a single group results in an increase of liberties; connecting a group with one eye to another one-eyed group make them live together. For instance, a single stone played in the center of the board has four liberties, while two adjacent stones in the center of the board form a unit with six. To capture the unit, an opponent would have to play stones on all of its liberties. Thus connected stones are stronger because they share their liberties. Since connecting stones keeps them secure, an important offensive tactic is to prevent the opponent from connecting his stones, while at the same time keeping one’s own stones connected. This act of dividing the opponent’s stones into separate groups is called cutting. While one should generally try to keep one’s own stones connected, situations exist where doing so would be a wasted move. Stones are considered tactically connected if no move by the opposing player could prevent them from being connected. In a handicap game, Black starts with two or more handicap stones played before White’s first move. If played in the traditional places on the “start points”, these stones will be useful for the purpose of connection and separation of stones played closer to the edge (“lower”), as well as in many other ways. The White player’s stones are threatened immediately with separation, while Black has many potential connections to begin with. An example of inefficiency or poor coordination of stones in the context of connection is the empty triangle, where the stones are arranged so that they share fewer liberties than if they were deployed in a straight line.
Strings
Stones of the same colour can be joined into strings by being horizontally or vertically connected to each other. Single stones can also be described as strings which we will refer to as unitary strings. Instead of the stones in a string having individual liberties, the liberties of the constituent stones of the string become the liberties of the string. To be captured, a string must be surrounded by opponent stones such that no stone in the string has any liberties. When a player fills the penultimate liberty of a stone or string, it is courtesy to declare “Atari!” which alerts the owner of the stone or string of its impending capture.
Eyes
Eyes are formed when a string surrounds one or more empty intersection points. Strings which contain a single eye can be captured by first being surrounded and then the eye being filled. Filling the eye does not violate the suicide rule since the opponents captured stones are first removed, creating liberties for the last stone played. A string that has two eyes is safe from capture since there is no way for an opponent to capture such a string. The reason for the inability to capture a string with two eyes is that the stone played in the first eye will be subject to the suicide rule.
Groups
A group is composed of strings of one colour that are in close proximity to each other. Being in close proximity means that they can be securely linked by a links (other than nobi of course). Groups are the main perceptual units concerning the player throughout the game. The most important attributes of a group is whether it is alive, and whether it can create two eyes or connect to a group with two eyes to ensure survival.
Links
The only links between stones which is recognized in the rules of Go is between horizontally and vertically adjacent stones (called nobi). In practice however, there are several links which are recognized by experienced Go players. The ikken tobi link can be physically connected as long as black plays next. The kosumi link can be made as long as black plays next or each of the connecting points are empty if white plays first. Of the other links, physical connection depends on the context of the surrounding stones. If two strings are denied a physical connection they are said to be cut.
Dead or Alive
A key concept in the tactics of Go, though not part of the rules, is the classification of groups of stones into alive, dead or unsettled. At the end of the game, groups that cannot avoid being captured during normal play are removed as captures. These stones are dead. Groups can reach this state much earlier during play; a group of stones can quickly run out of options so that further play to save them is fruitless, or even detrimental. Similarly, further play to kill such a group is often of no benefit (except when securing liberties for an adjacent group), since if it remains on the board at the end of the game it is captured anyway. Thus groups can be considered “dead as they stand”, or just dead, by both sides during the course of the game. Groups enclosing an area completely can be harder to kill. Normally, when a play causes an area completely enclosed by the opponent to become filled, the group filling the area is captured since it has no remaining liberties (see “suicide”). Only if the last play inside the area would kill the enclosing group, thus freeing one or more liberties for the group that filled the space, can the play be considered. This can only be achieved if the liberties on the outside of the enclosing group have been covered first. Thus, enclosing an area of one or more liberties (called an eye) can make the group harder to kill, since the opponent must cover all of its external liberties before covering the final, internal liberty. From this, it is possible to create groups that cannot be killed at all. If a group encloses two or more separate areas (two or more eyes), the opponent cannot simultaneously fill both of them with a single play, and thus can never play on the last liberty of the group. Such a group, or a group that cannot be prevented from forming such an enclosure, is called alive. Groups which are not definitely alive nor definitely dead are sometimes called unsettled groups. Much of the tactical fighting in Go focuses on making one’s own groups live, by ensuring they can make two eyes, and on making the opponent’s groups die, by denying them two eyes.
Seki
When adjacent groups of black and white are neither alive nor able to capture each other, the situation is called Seki.
Ladders
Ladders are a capturing race between a group that is almost enclosed, and a surrounding group.
Armies
An army is a loose federation of groups of one colour that are in close proximity to each other. Being in close proximity means that there are no intervening enemy stings between the groups. Although armies cover a large territory, they are not as secure for defending territory as groups. Thus it is important for a players to convert armies into groups whilst stopping their opponents from doing the same. Converting an army into groups implies playing stones in between strings of separate groups such that they can be linked together as described above.
Sente and Gote
Skilful players can engineer the game so that they gain the initiative for a number of moves and dictate the response of their opponent. In such a case, a player is said to have sente and the opponent to have gote.
‘Sente’ and ‘gote’ are complementary terms. Sente loosely corresponds to taking the initiative, and gote loosely corresponds to the responsibility of defense. If a move forces the other player to respond, that player “has gote”; if not, he/she can play elsewhere, “taking sente.” The player who holds sente more often in effect controls the flow of the game. ‘Taking gote unnecessarily’ would mean that one had defended for oneself a smaller area of the board than one could have threatened to take from the opponent, elsewhere. Very few plays in a game are really forcing — the opponent may well ignore you. If your play was ‘really’ sente, you expect to gain by following it up, as soon as possible. The act of playing elsewhere (in other words, breaking off from a local exchange of plays in one area of the board) is called tenuki. It may indicate either a natural pause in the sequence, or a disagreement as to the importance of an area of the board. Between strong players tenuki may be used as a kind of gambit. Because the Go board is so spacious, the balance between attack and defense, and amongst different areas, holds great importance for strategy.
Middlegame
A large part of the middle game of a game of Go is usually spent by one player attacking the other player’s weak group(s). What is important to remember is that in most cases the goal of an attack is not to kill the attacked group, but to gain territory or influence. The attack is more or less used to restrict the opponent’s options and make it impossible for him to make territory or influence himself.
Endgame
In the endgame, if the game is close, moves that are small are still worth some points, some more than others. One must choose which of these moves is more urgent to play based not only on the points it may gain, but on whether that move is sente. Yose refers to a specific kind of play during the endgame, which yields a reduction for one’s opponent. Generally, in the endgame, all the territory is staked out—there is no more to be gained. However, there are still points to be made, as well as possible ways of reducing small amounts of your opponents territory. A simple example would be a move that is dame (neutral point for you), but when filled in, it is sente, requiring white to fill a stone in his territory to answer. It would be thus said this is ‘a one point reduction, with sente.’
The Go Handicap and Ranking Systems
Go has a sophisticated handicap and ranking system. Players are ranked according to their ability with a complete novice being ranked at 30 kyu (pronounced “cue”). After playing between 10 and 15 games, a player’s rank would likely be around 20 kyu. After reaching 1 kyu, further improvement would result in a rank of 1 dan or first-degree master. Amateur ranks continue up to 6 dan. Professional ranks start at what would be 7 dan amateur and extend from 1 dan to 9 dan. The amount of effort required to increase to the next best rank becomes harder as a player moves up in ranks. For instance, to rise from 20 kyu to 10 kyu would require playing 1 or 2 games a week for around a year and possibly reading a few books on Go tactics and strategy. [The differentiation between professional ranks is also smaller than between amateur ranks. The difference between a 1 dan professional and a 9 dan professional is approximately equivalent to the relative difference of 2 amateur ranks, say 4 dan to 6 dan.] Many years of full-time play is required to reach professional ranking. To provide balance for both weak and strong players, the weak player is given handicap stones at the start of the game. In the Chinese rules, the handicap stones are placed at the weaker player’s discretion whereas in the Japanese rules, the handicap stones are placed on set points called hoshi points. The weaker player is given as many handicap stones as the difference between the players rankings. For instance, a 10 kyu player would give 5 handicap stones to a 15 kyu player. Ranks are usually determined in one of two ways. The first is by finding the number ofhandicap stones a player needs to win about half the games played against a stronger player on a 19×19 board. The other is by giving 1 handicap stone for each 10 stones that a player is beaten by. The relative value of handicap stones diminish as the board size increases. One handicap stone on a 9×9 board is worth two on a 13×13 board and four on a 19×19 board. Playing first without handicap is equivalent to a 5 point advantage. It is customary for the weaker player to play first using black stones. If both players are ranked equally, the White player is given a 5 point bonus or komi (pronounced “ko-mee”). In tournaments the komi is usually 5 1/2 points so as to avoid ties.
Computer Go
Compared to the Chess programming field, the Go programming field is not well developed. A strong commitment to research on programming Chess in the 1960′s and 70′s has not been replicated in the Go field. There are fundamental differences between Chess and Go which have contributed to making Chess a more attractive research domain so far. However, even allowing for the smaller amount of work done on programming Go, the performance of Go programs have not kept pace with the performance of Chess programs. There are several reasons for this disparity, which is in part due to the complexity of Go and also the unsuitability of the programming techniques used in Chess as described below.
A Comparison of Chess and Go
1. There are fewer types of pieces in Go than chess (in chess there are 6 types of pieces, whereas in Go each player has only one type, called a stone). However, the board size is much greater in Go (8×8 squares in chess vs 19×19 grid in Go).
2. The size of the board, and the relative freedom in the placement of stones mean that there are also many more moves made in a typical Go game (about 80 moves in chess vs. about 300 moves300 moves in Go).
3. Stones can be placed anywhere on the board, making for a very large branching factor in the selection of each move (estimated at ~200), whereas pieces in chess are constrained to a much smaller set of legal moves (branch factor of ~ 40). The diversity of chess pieces is exploited to reduce the branching factor in chess programs in a way that is not possible in Go (see discussion of evaluation functions in 7. below). The branching factor also plays a role in the different stages of both games (beginning, middle and end). In the opening stage of chess, there are many well-known openings, and these are often followed for up to 10 moves. In Go, the number of sensible openings is much larger, and set openings are rarely followed for more than about 3 moves. However, there are sequences of moves in local skirmishes, known as joseki, that reflect optimal play (for both sides) in tactical battles in the corners. Skill in the use of joseki libraries lies in selecting the right joseki to optimise interactions with stones outside the region of interest or diverge from the known sequence to serve other interests.
4. Both games can be won by resignation of the opponent, or by an outright win – check-mate in chess, or surrounding more territory and taking more prisoners in Go. In chess, the end of a game is easy to determine: checkmate is simply defined in terms of the position and threats to the King. In Go, a game is finished when both players pass, but it is frequently difficult for beginners to know when the end of a game has been reached. Beginners typically prolong play beyond the point where experts would stop, and their difficulties are echoed by Go programs, which also have difficulty estimating when to end a game. The natural end of the game occurs when playing additional stones reduces the player’s score, either by filling in their own territory, or giving unnecessary prisoners to the opponent. Go programs are often inefficient in both these ways. There are several different rule systems for scoring in Go: they are all similar, based on calculating the sum of territory surrounded plus prisoners taken during the game for each player, and taking the difference between these scores (a typical margin in a professional game would be less than five points).
5. In both chess and Go, pieces can have long range effects. In chess the effect is directly a result of some pieces’ ability to move many squares (e.g, queens, rooks, bishops). In Go, a stone once placed on a grid point does not move (although it can be captured and removed from the board). However, a group (or pattern of stones) does have long range effects in that it can play a role in a capturing race, or can affect the life and death struggle of another group. For example, a stone played in the path of a ladder (a group of stones involved in a certain type of capturing race) can change the potential to link two stones later in the game – even though the stones are on the other side of the board.
6. The state of the board changes rapidly in chess, as pieces move positions. In Go, the board is only gradually changing, as stones are added to the existing configurations. This gradual change compensates significantly for the greater memory load imposed by the larger board. It also allows accurate “read-out” of board positions later in the game – even beginners can read out ladders up to 60 moves ahead (a deep but narrow search). The only time the physical state of the board changes significantly is when a group is captured, and the stones are removed from the board. Groups worth as much as 30 points are often won or lost in a game as trade-offs for other groups, even though the final difference in scores may be just 2 points.
7. Evaluation of board positions (in expert human play) typically reflects both tactical and strategic factors in both chess and Go. However, in chess, there is a good correlation between the likelihood of winning (from any stage of the game) and the number and quality of pieces on each side. Thus in computer chess programs, strategic factors have not been essential in evaluating board position. In Go, there is no strong correlation between winning a tactical struggle over a group, and winning the game, as each tactical struggle over a group requires moves that are not contributing to another group. Early in the game, players strive to achieve influence on the board, rather than directly taking territory. In fact, taking territory at the start of the game can indicate an over-concentrated position, that will not be effective in containing the opponent’s territorial moves much later in the game. Algorithmic approaches to measuring the influence of a position are a standard part of most Go programs but there are no methods to confirm their efficacy, except for the strength of the program itself which is usually very weak.
8. For all the reasons discussed above, programming approaches to chess are amenable to tree searches, with good evaluation criteria. Such approaches have not succeeded in Go, because the branching factor is too large for brute force search techniques, and pruning is not a viable option without good evaluation measures.
9. Human lookahead in chess and Go is very different. Beginners of both games might start by only looking ahead a few moves, but in Go, patterns such as ladders can be read out with very little effort, and beginners are soon able to trace the path of a ladder across the board (which can require up to 60 moves). However, in these read-out sequences, there is only one sensible move at each stage, i.e, a series of forcing moves, so there are no alternative paths to follow (see the horizon effect below). In a typical chess game, expert players may search alternative possible moves many steps ahead (although typically about 10), but for each move there are several alternatives. In Go, there are too many alternatives that are reasonable to search far ahead in most moves, although for any move, there are likely to be some sequences that can be very deep (e.g., ladders). This combination of factors is not captured well by either breadth-first or depth-first search techniques.
10. The horizon effect in chess is where a search to a specific depth (such as 12 moves ahead) elicits an evaluation that would be radically altered if a few more moves had been studied. This effect is often seen in sacrifice moves. The horizon effect begins to be a problem at the Grandmaster level in chess. In Go, the horizon effect is seen in assessment of even beginner level play (e.g., ladders).
11. Chess was used in the early 1970s to study human grouping processes, and Chase and Simon (1973) showed that expert chess players view the board in terms of hierarchical groups of stones. In trying to replicate the results with Go players, Reitman (1976) found a completely different structure, in which stones are seen as part of many intersecting groups. Identifying the eventual group to which stones belong is critical in determining their safety, however, from Reitman’s research, it appears that no clean assignments can be made until the end stage of the game. Such results indicate sources of potential problems for computer go programs that assign stones into hierarchical groups in order to estimate features such as influence.
12. One major difference in the actual playing of chess and Go lies in the standards of the opponents. In chess, a similar standard is required for an even game. In Go, there is a very effective handicap system, in which a weaker player starts with a predefined number of stones (usually 2-9) placed at influential points on the board. Thus the greater skill of one player is offset by the material advantage of the weaker one. In such contests (and most Go games are of this type) neither player can assume an infallible opponent, for the weaker player tries to simplify the game, and play safely, whereas the stronger player must take more risks, and exploit the weakness of the other player. Although the final score of a Go game is often used as an indication of the relative strengths of the players, the important factor is winning, by however small a margin, rather than taking chances that may increase the margin, but are not as safe. Thus, estimating the other player’s level of skill is a critical aspect of many Go games. It is also the case that a Go player needs to be skilled at all facets of the game, rather than having great strength in just one area. This requirement is because players exploit the weaknesses of their opponents. It is common to rank the strength of computer Go programs according to their first game against a human of a given level. In subsequent games, the same human player will often overwhelm the same program that had won previously, because the human will learn the program’s weaknesses, but the program does not change.
The Complexity of Go
An algorithm which can be solved in polynomial time can be practically implemented to solve “real-world” problems. Algorithms which cannot be solved in polynomial time are described as exponential-time algorithms. Except for very small problem spaces, these algorithms are impractical. Problems that can be solved by a computer with a polynomial amount of memory space are said to be solvable in P-space.
It has been shown that, given an arbitrary Go position on an n x n board, determining the winner is P-space hard (Lichtenstein and Sipser, 1980). This result used together with situations arising from ko positions have been used to show that for an arbitrary Go position on an n x n board, deciding whether Black can force a win or deciding on Black’s best move is exponential-time complete (Robson, 1983). These results indicate that the use of approximation algorithms which return near-optimal solutions are necessary to solve some aspects of Go and that brute-force search methods will quickly run into difficulties.
A comparison of the complexity of Go to the complexity of other games is provided in Allis et al. (1991). They defined the terms cracked and solved, and illustrated the difference between search-space complexity and decision complexity. A game is said to be cracked if a program is capable of achieving the best possible theoretical results regardless of its opposition. To be solved, the best move must be explicable in human terms. The difference between search-space complexity and decision complexity is illustrated by a variant of Go. The variant consists of players alternatively placing stones on unoccupied points of the board or passing. The first player to place 181 stones wins. This variant has the same search-space complexity as Go, however, since if the player moving first does not pass is bound to win, the decision complexity is trivial.
Allis et al. graphed log log search-space complexity versus log decision complexity, dividing the graph into solvable and unsolvable space for 16 games. Go was shown to be the most complex in both log log search-space complexity and log decision complexity and to be in the unsolvable area. A comparison of Go and Chess shows that 9×9 Go is around about the same complexity as Chess (35 versus 50 in 10 log search space) and that 19×19 Go is a vastly more complex game than Chess and may well be unsolvable as defined above (Allis et al. (1991).
Why Go Cannot be Programmed Like Chess
Chess programs typically use a heuristic search and evaluation technique. Search trees of board positions are generated to a fixed depth and are heuristically pruned according to an evaluation of the merit of the board positions. This approach works well in Chess because the board size is sufficiently small and the nature of Chess is more tactical than strategic.
Evaluation of a board position in Go presents problems not encountered in Chess. Go is a much more strategic game in comparison to Chess. Unlike Chess, Go does not focus around the capture of a single piece. Positional advantages are slowly built up in achieving the long term goal of acquiring more territory than the opponent. There are many direct and indirect ways to achieve this goal such as making territory, building influence, attacking weak enemy groups, securing friendly groups, destroying enemy territory etc. Due to the large size of the board, a Go game is comprised of many small local skirmishes. If a game of Chess were described as a battle, a game of Go could be described as a war. Many good tactical moves at the local level must all compete for selection in the context of strategic global considerations. Thus a player must balance resources to achieve local goals at many locations whilst trying to pursue an overall global objective.
Due to the problems associated with evaluation, the brute force methods employed in AI to program Chess will not work for Go. As a domain, Go is rich for research in AI and cognitive science. Hans Berliner, a former Correspondence Chess World Champion, a top-ranked U.S. over-the-board player and a well-known Chess programmer referring to Go as saying “… this game may have to replace Chess as the `task par excellence’ for AI” (Berliner, 1978).
Description of some Go engines
The Many Faces of Go
The Many Faces of Go (MFG) is one of the best commercial Go programs currently available. David Fotland has been writing Go programs on a part time basis since 1981 and released MFG in 1990. Fotland has continued to enhance MFG since then and has contributed regularly to discussions on the computer-go mailing list concerning computer go programming in general and MFG in particular. MFG evolved from two other significant programs: G2 and Cosmos.
G2
Fotland’s first Go program determined territory by radiating influence. Unfortunately, it could be beaten by a simple liberty filling algorithm so he discarded it and wrote G2. The internal structure of G2 was described by Fotland in terms of its data structures, its tactical analyser, and its move selector (Fotland, 1986). G2 used full board reading and evaluated all legal moves with an emphasis on strategic moves. After the full board evaluation of all moves, the move that received the highest score was played.
The Data Structures
Most of G2′s code was devoted to updating the data structures. Stones occupied points (referred to as squares) and were organized into strings (referred to as groups) and then into groups (referred to as armies). Data was associated with each point on the board and included the distance to the nearest and second nearest edge, a list of adjacent and diagonal neighbours, string number of the stone occupying the point, the number and a list of liberties, colour of stones on neighbouring points (white, black, or mixed), an influence function, and the nearest occupied point in each direction. Horizontally or vertically adjacent points containing like-coloured stones were organised into strings. String data included colour, number and list of liberties, a list of its connections, a list of neighbouring enemy strings, the army it was part of, and an aliveness value (described below). The types of connections recognized by G2 included one and two point jumps, diagonal connection and knight’s move. Connection data included the strings it joined, its type, the points involved, and its status. Groups were comprised of strings which were connected by unbreakable connections or were both adjacent to a dead enemy string. Group data included a list of its constituent strings and dead enemy strings used as connections, the number of stones and liberties, the number of eyes, and an aliveness value.
The Tactical Analyser
The tactical analyser was used to evaluate board positions so that a move could be selected. Each group was assigned an aliveness value which was also inherited by its constituent strings. The strength of G2 was primarily determined by the tactical analyser and consumed the largest portion of Fotland’s effort (Fotland 1986). Since most of the program’s time was spent in the tactical analyser, it had to be both fast and efficient in its pruning of search trees. Aliveness values resulted from a multi-stage process: strings which could be captured were identified as dead; eyes were found by the eye evaluator; unbreakable connection were identified; connected strings were identified as groups; territory was determined by the territory evaluator; and the life and death evaluator assigned an aliveness value to each group which was then assigned to its constituent strings. The tactical analyser examined every string with less than five liberties to determine whether it was dead i.e., whether it could be captured; strings which could obtain at least five liberties were assumed to avoid capture. Interesting moves were suggested during lookahead to determine the status of a string. Interesting attacking moves included geta moves for groups with two liberties, liberty filling moves, moves adjacent to an enemy string’s liberties, and liberty gaining moves for friendly strings. Interesting defensive moves included diagonal moves into unoccupied territory, one point jumps, extensions, connections, and liberty filling moves (for adjacent enemy strings). The interesting moves were heuristically evaluated and the best were selected for further analysis. The best of these moves was hypothetically played and the resulting situation analysed from the opponents point of view. Once again, the best moves were chosen and the best one was hypothetically played. Normal backtracking was used at each stage as well as alpha-beta pruning. Thus, a depth-first tree was generated until the string being examined was captured or gained sufficient liberties to live. The search tree was generated to a maximum of 80 moves which still enabled ladders to be accurately read. The number of “best moves” considered (between 1 and 3) depended on the depth of the current move in the search tree: more moves were considered near the root and less near the leaves. Since the value of the terminal node had only two values (i.e., captured or escaped), alpha-beta pruning was very efficient (Fotland, 1996). An eye evaluator was used to maintain information about eyes, half eyes (eyes made in gote) and quarter eyes (eyes needing two moves to be made) by evaluating small enclosed eyespace. G2 recognised some basic dead shapes and various types of eyes including three in a row, four in a square, bulky five, pyramid, and cross. Groups were determined by finding strings that were connected by unbreakable connections. The tactical analyser tried to cut connections to test their strength. Dead opponent strings could also be used as connections between live friendly strings. Territory was determined by the territory evaluator. As well as completely enclosed territory, G2 also evaluated territory near the board edge which did not need to be completely enclosed. Territory could be made near the edge by being between a stone and the edge or a connection and the edge. However, such territory could be challenged by a stone within four lines along the edge, and closer to the edge (undercutting the edge). The life and death evaluator analysed every group. An aliveness value was assigned to each group by considering the number of liberties it had, its eyespace, the amount of territory it controlled, whether it could extend along the edge, its size, whether it was in contact with an enemy string, and whether it was completely surrounded. The aliveness value rating itself had 20 different values including “has two eyes”, “has enough space to make two eyes”, “unsettled”, “not enough eyespace”, and “can’t possibly make two eyes”.
The Move Selector
A rule-based strategic evaluator with 65 rules was used to select moves by choosing the highest scoring move using a two step process. In the first step, strategic moves were evaluated and in the second step, all legal moves were evaluated. Information from the data structures and the tactical analyser was used to evaluate board positions resulting from moves in both step one and two. Fotland felt that this was the weakest component of G2 due to the weakness of the data structures (Fotland, 1986). The rules suggested strategic moves to evaluate such as playing in an empty corner, make shimari or kakari, a move from the joseki dictionary, extending along an edge, invasions, contact fights, blocking, cutting, connecting, blocking an invasion on a wall, or making a ko threat. In the first step, all the suggested strategic moves were evaluated. A particular strategic move was hypothetically played and the resulting board position was evaluated. The evaluation process consisted of assigning values to the board points and then summing them together to return an overall score. The value for a given board point was determined by the aliveness value of the string that controlled it. If the board position resulting from a strategic move did not satisfy the strategic goals associated with the rule that suggested it, the evaluation of the move was ignored. In the second step, all legal moves (including the strategic moves considered in the first step) were evaluated. The value assigned to a board position resulting from hypothetically playing a move was based on the aliveness, size, and amount of territory controlled by each string on the board. The values that resulted for each move from step two were summed with the value they obtained if they were considered in step one. The move with the overall highest score was then chosen as G2′s next move.
Size, Performance and Timeline
Between 1981 and 1988, Fotland spent around four years part time writing G2. He stopped work on G2 for several years because the available computers were not fast enough for the development of strong Go programs (Fotland, 1996). G2 was around 11000 lines of C code and used around 700k for the code and data. During that time, Fotland’s Go skill advanced from 15 kyu to 1 dan. G2 played at about the 25 – 20 kyu level and could beat beginners without much trouble (Fotland, 1986). Fotland had some success at computer Go competitions with G2 coming 4th in the world computer Go competition in Taiwan and 1st in the US computer Go championship in 1987.
Cosmos
Fotland converted G2 into Cosmos in 1988. The main difference between Cosmos and G2 was that instead of evaluating all legal moves, only suggested moves were evaluated. This transition was achieved by increasing the number of move suggestors to over 250. Quiescent search was added and the connection, eye, and territory evaluations were made more accurate (Fotland, 1996).
Data Structures
The data structures used in Comos were basically the same as those used in G2. The eye information included the number of eyes achievable in gote, the number of eyes achievable in sente, the number of eyes achievable if the opponent moved twice, a list of vital points, and eye type. The information contained in the data structures was updated either incrementally (e.g., lists of liberties) or after every move (e.g., influence).
Tactician
Essentially, Cosmos had the same tactician as G2 but better move generation and sorting. In Cosmos, the tactician was only used to determine dead and threatened strings by trying to capture them. Its parameters were maximum liberty count, maximum, depth, and maximum search size. The maximum liberty count was 4, and therefore as for G2, strings with more than 4 liberties were assumed to avoid capture.The maximum depth allowed was 100. The search size determined the playing level (Stoutamire, 1991) and since forcing moves were not counted, ladders could be accurately read even at low playing levels.
Influence Function
Territory was determined by radiating positive influence from alive groups and negative influence from dead groups. Radiated influence did not pass through stones or connections and was inversely proportional to distance.
Board Evaluation
Life and death of groups was the primary concern dealt with by the evaluation process. Board positions were evaluated by a similar process to that used in G2 with the addition of quiescent search. The tactician was used to determine dead and threatened strings (those that could be captured if they moved second) and whether the stones at the diagonal of eyes could be captured. This information was useful in identifying unbreakable connections and forming strings into groups. Eyes were analysed to determine their potential and then allocated to groups. False eyes were identified by checking the diagonals of eyes and some dead shapes were also known by Cosmos. Any group with enough eyespace to make two eyes was considered to be alive. Potential eye space could be gained by extensions along the edge, possible connections, being adjacent to a threatened enemy group, and by controlling territory which was not already considered to be an eye. There were 25 values that described a groups strength in terms of its life and death status. The values were divided into five main categories which included very alive, alive, unsettled, weak and dead. Determining the strength of a group included considering potential connections, potential eyes, and potential extensions along the edge. Positive influence was radiated from alive groups and negative influence was radiated from dead groups with black and white influence being maintained separately. Weak groups which were contacted by the influence from friendly alive groups were considered not to be surrounded. Weak groups were further divided into those that could run and fight and those which would almost certainly die. In general, board points were scored according to the radiated influence values. However, occupied board points, board points adjacent to a stone and board points between a stone and an edge were scored differently. Unsettled groups were scored according to who as to play next.
Move Selection
Cosmos had over 250 rules that suggested moves which included fuseki moves (including shimari, kakari and joseki moves), edge moves, playing in the centre, playing safe when ahead of opponent, “squirming” around when behind opponent, pattern matching, saving weak friendly groups (including making eyes, running, or fighting semeais), killing weak enemy groups, cutting, connecting, contact fights, ko threats, and filling dame. Cosmos had a joseki library which contained around 5000 suggested joseki moves and a pattern database which had 60 patterns which were 5 x 5 in size. Whenever a match was made, the rule (code) associated with the pattern was applied (executed) and would then suggest a move. The addition of extra moves to be suggested could easily be accomplished by the addition of new move suggestor rules or the addition of patterns. The rules would supply a guess value (probable evaluation of the move), bonus value, minimum aliveness value, and would indicate which groups were being attacked or defended if any. The moves were sorted by their guess values and, depending on playing level, a certain number were “played”. Moves could be rejected before being evaluated if they did not “apply”. A move applied if it accomplished what it was intended to do: if a move was intended to defend a group and the group ended up weaker than it started the move was rejected. Surviving moves were awarded a sente bonus if they achieved sente. The position resulting from the move was then evaluated. The evaluation score, the sente bonus and the rule bonus were summed together and the highest scoring move was selected as the next move.
Size, Performance and Timeline
It took Fotland nine months to compress G2 down to 512 k and add a new user interface. In 1988 Cosmos was released by Ishi Press for IBM-PC as Cosmos, The Computer Go Partner and was released a second time in 1989. Due to the amount of time spent on the user interface, Fotland was unable to devote sufficient time to improving Cosmos’ playing level and its performance in various world computer Go championships was modest coming 8th in 1988 and 7th in 1989 (Fotland, 1996).
Many Faces of Go
After a rewrite of the user interface and addition of professional graphics and new features, Cosmos was released as The Many Faces of Go in 1990. Additions to MFG included a limited full board lookahead capability, consideration of the value of sente, and a strategy function which is used to focus attention on the important areas of the board and to identify urgent moves. The number of patterns in both the joseki and pattern databases were increased. The pattern database was also improved by increasing the pattern size from 5×5 to 8×8, by storing many suggested moves for each pattern in a move tree (rather than just one per pattern as for Cosmos), and by a complete rewrite which encompassed algorithms, code, and data structures and lead to an increase in speed (Fotland, 1996).
Data Structures
The dynamic data describing a board position is stored in three classes of data structures: incremental, locally recalculated, and globally recalculated. The data in the incremental data structures is updated upon addition or removal of a stone and includes low level information such as lists of empty points, number of liberties etc. Locally recalculated data is updated as it is needed i.e., it is only updated for regions of the board which have been affected by a particular move or move sequence, and includes connection strength, and eyes. Globally recalculated data is updated for the whole board and includes group strength and influence. The locally and globally recalculated data structures are maintained by the evaluation function. The dynamic data is stored globally and is generated progressively in several passes of increasing abstraction. The dynamic data used in MFG includes point environment, string data, connection data, eye data, potential eye data, group data, territory, and score. An instance of the connection data structure stores information pertaining to connectivity between two strings. Each connection has a list connection points i.e., a liberty of one string which is no more than three points away from the other string. Thus, the connection recognised by MFG include hane, one point jump (ikken tobi), knights move (kogeima), two point jump (nikken tobi), large knights move (ogeima), three point jump, and bent three point. Other special connections near the board edge are handled through the pattern database. The data stored in the connection data structure includes the strings involved in the connection(s), the number of and lists of one, two and three point connections (i.e., as measured from the connection points), the type of each connection, and the strength of each connection (e.g., already cut, cuttable, shared connection, connected with aji, connected solidly). Other than the type and strength data which is stored in a locally recalculated data structure, the connection data is stored in an incremental data structure. The eye data structure records information pertaining to either a block of empty point or dead enemy strings which are partially or completely enclosed by friendly stones. Data stored in the eye data structure includes colour, a list of the points in the eye, vital points, and eye type (e.g., one point, two point, line eye, big eye, and dead group eye). The number of eyes (to a resolution of 1/8 of an eye) achievable under various conditions were recorded including the number of eyes if opponent moves twice, number of eyes if opponent moves next, and number of eyes if program moves next. A board point can only be recorded as belonging to one eye. The eye data structure is a locally recalculated data structure since eye data does not lend itself to incremental update. In hindsight, Fotland says that a pattern based approach to recognizing eyes would be preferable (Fotland, 1993). The evaluation of group strength and the generation of attacking and defending moves involves identifying potential eye space and running points. The potential eye data structure contains type, value and location data for potential eyes. An examples of data stored in the potential eye data structure is “extend along edge” (type), value is number of new points of eye space, and location is the liberty to extend from. Running points are stored by type (e.g., running towards friendly/unfriendly stones) in several different lists. Potential eyes and running points are stored in a globally recalculated data structure.
Tactician
Every string with three or less liberties and many strings with four liberties are read by the tactician. Each string is read twice, once with White moving first and once with Black moving first. The tactician determines whether a string is captured (i.e., can not live even if it moves first), threatened (i.e., it lives if it moves first and dies if it moves second), or stable (i.e., lives regardless of who moves next). The tactician relies on simple heuristics concerned with the number of liberties and connectivity; pattern matching is not used in the tactician. The tactician has two separate move generators; one to generate attacking moves and one to generate defensive moves. The moves suggested by the move generators are sorted according to criteria which include second order liberties, cut points, and simple eye shapes. Once sorted, an alpha-beta depth-first search is employed with the performance of the search depending on the quality of the move sorting (Fotland, cgm1 5 Mar. 1993). Tactical searches are goal directed and are limited to a maximum number of nodes. For string captures this is around 100, however, when only one move is suggested, it is not counted towards the node limit. In this way, ladders can be read without problems (Fotland, cgm1 14 Oct. 1993). The number of nodes for a search are allocated to the branches according to the value given to the moves by the first ply move generator and thus different branches may end at different depths. The branching factor at each successive ply is progressively constrained by the tactician. The branching factor falls from five at the first ply to one or two by the fifth ply. Since the data structures in MFG are separated into incremental, locally recalculated and globally recalculated, low level local tactical searches can be executed quickly by only updating the incremental data structures. However, the possible goals of such a search are limited since the high level data structures are not recalculated. It is not possible, for example, for MFG to search for x liberties and two eyes (Fotland, cgm1 3 Nov. 1993). The tactician is used to read connections and eyes. A cutting stone can be examined by the tactician to determine whether or not it will be captured. Stones on the diagonal of eyes can be examined to determine whether they can be captured. These types of search do not exceed around 12 ply since the program actually plays worse if more plies are considered (Fotland, 1996). MFG uses caching to reduce the amount of time spent reading. Since strings are read twice, tactical results related to eyes, capture or threat, and cuts are cached rather than re-evaluated. Life and death analysis are cached as trees since they are smaller than the trees which would result from tactical searches (Fotland, cgm4 16 Aug. 1994).
Influence Function
The influence function radiates influence which is inversely proportional to distance. Influence is radiated to a fixed maximum distance of nine although when lower playing levels are chosen, the distance is smaller. Stones and connection impede the radiation of influence. Black and White influence are radiated separately (i.e, they are not summed together to give a single value for each board point) so that their relative values can be compared. Dead stones radiate negative influence and thus, since Black and White influence is maintained separately, dead stones reduce their own influence rather than increase their opponents influence. The initial influence value radiated from a stone depends on its strength. Influence is not used to determine group connectivity. The use of influence in MFG includes determining thickness and territory, identifying surrounded groups, and generating moyo building or reducing moves. Another way in which influence is used is to determine a group’s running ability. A group’s ability to run towards a liberty depends on the relative values of friendly and unfriendly influence nearby. The sum of a group’s ability to run toward each of its liberties determines its running ability whilst the gradient of the influence determines the direction in which it should run.
Evaluation
Board positions are evaluated in a multiple pass process. The evaluation function consists of many components which include the tactical analyser and evaluators for connections, eyes, group strength, and territory. A score for the position being evaluated is achieved by assigning a value between -50 and +50 to each board point to indicate the level of Black or White control exerted on them. The overall score for the board position is the sum of these values for each board point. In order to try and overcome the difficulties associated with the horizon effect, Fotland chose to use quiescent search rather than modify the evaluation function. In quiescent search, positions are evaluated when they become quiet rather than when they are in a state of flux (e.g., such as in the middle of a piece exchange in chess). Positions which are not quiet are characterised by oscillations in the evaluation values returned for successive moves which makes it difficult to make good decisions based on the evaluations. MFG uses quiescent search as part of the evaluation function for full board evaluation to overcome this problem by either calling itself recursively (i.e., generating further moves) until a position becomes quiet or by using patterns suggested as obvious local answers to make the position quiet. MFG will generate up to six plies of moves in a quiescent search which improves its performance by up to four stones (Fotland, cgm1 30 Sep. 1993).
Move Suggestion
Moves are suggested by a rule-based expert system and include fuseki (e.g. shimari, kakari, and joseki moves), moves on the edge (e.g., invasions and extensions), playing in the centre, conservative play when ahead, risky play when behind, pattern matching (e.g., cutting and connecting, surrounding and escaping, invasion and defence, endgame, killing and saving groups, and shape-based moves), group defensive moves (e.g., making eyes, running, and fighting semeais), contact fights (e.g., blocking, extending for liberties, and hane), ko threats, and dame. A limited form of full board lookahead is achieved by storing move sequences in the pattern and joseki databases. Move sequences attached to patterns in the pattern and joseki databases are played onto the board and evaluated at their endpoints. Thus if a particular joseki is suggested as appropriate, the stones in that sequence are played and the resulting board position is evaluated. This enables MFG to “play” to the end of a lookahead sequence and minimax the score returned by the evaluation function for the resulting board position.
Pattern Database
Each pattern in the pattern database has a a move tree associated with it. The pattern database contains around 1200 patterns of size 8×8 and around 6900 suggested moves with the average number of moves stored for each pattern being about 5. Each point in a pattern is marked as black, white, empty, white or empty, black or empty, black or white, or anything (i.e., do not care). Patterns are categorised according to whether they are in the middle of the board or whether they contain edges and/or corners. A successful match of a pattern depends on both matching the stones in the pattern with those on the board and matching any attributes associated with the pattern. Each pattern has as many as 10 attributes which pertain to stones and include whether they were dead or alive, minimum number of liberties, and connectivity between stones. To match over a 1000 patterns on a 19×19 board in 16 different orientations requires around 3 million primitive operations. Since performance is a big issue, the patterns are compiled into a bit array which facilitates fast bit-parallel comparisons. By using an 8-bit hash function and bit-wise operations, the number of primitive operations is reduced to around 350000. This number of operations still takes enough time to make it too expensive to match all patterns more than once per move. Patterns from the pattern database are evaluated after being played on the board in their entirety i.e., they are evaluated at the endpoints of their move trees. A small subset of patterns are used to read local sequences based on shape. Fotland has recently begun evaluating the strength of one point jump connection using patterns (Fotland, 1996). A fast pattern matcher is necessary for a strong Go program according to Fotland. Pattern matching can be used to suggest and sort moves, and to classify connections and eyes. Reading is employed to determine whether eyes are false. Pattern matching on its own is not adequate for life and death and group strength determination (Fotland, cgm1 8 Apr. 1993). The eye and connection patterns are hand coded decision trees. One method that Fotland tried to increase the number of patterns in the pattern database was to take them from professional games.When replaying a professional game, if MFG didn’t consider the move played by a professional or the move played was low on the suggestion list, Fotland would manually cut-and-paste an 8×8 section from the game into the pattern database using a self-written graphics pattern database editor. Fotland discontinued this method since most of the missed moves were tactical (i.e., based on read-out not shape) or depended on a larger context than the 8×8 section that was placed in the pattern database. Fotland found that the cut-and-paste approach to patterns was more profitable from even games played on the IGS (Fotland, cgm1 13 Jan. 1994).
Joseki Database
The joseki database contains around 45000 moves. Joseki sequences are stored as directed acyclic graphs (i.e., they contain no loops) having empty corners at their roots. Moves in a joseki sequence can be one of several types including urgent, complex, trick, and bad. The urgent move have priority whilst the complex and trick moves are only played if MFG is behind. The bad moves are not for the program to play, rather they are used by the program to know how to respond to bad moves played by its opponent. Joseki patterns are evaluated by being played on the board in their entirety and evaluating the resulting board position. MFG selects joseki sequences that are appropriate given the status of the other corners (Fotland, 1993).
Strategy
A strategy function is used to focus attention on important areas of the board before each move (Fotland, 1993). The dynamic data is examined to determine what phase the game is in, the relative score, the value of taking sente, and whether there are any urgent offensive or defensive moves that need to be made. Urgent offensive and defensive moves are examined initially and if sufficiently urgent are played without any further considerations. Urgent moves can be suggested by the pattern matcher or by examination of groups which are determined to need urgent attention. Friendly groups which need urgent defence include big groups and cutting groups. Opposition groups which need urgent attack include big groups, cutting groups, and groups adjacent to friendly groups needing urgent defence. Move suggestion is affected by the phase that the game is in. Certain rules will only fire in certain phases of the game. The fuseki phase lasts until joseki sequences have been pursued in all the corners. The middle game lasts until at least move 120 and MFG enters the end game when there are no unsettled groups on the board. Transition between middle game and end game phases may occur many times during a game. The types of moves suggested are also affected by the relative score. MFG plays more conservatively when it is far ahead of its opponent and makes unsound invasions when it is far behind its opponent. The relative score is classified into many states including “way ahead” (over 40 points), “ahead (20 – 40 points), “about even”, “behind” (over 10 points), and “way behind” (over 20 points).
Move Selection
Since the evaluation function is very slow (Fotland, cgm4 16 Aug. 1994), a limit is placed on the number of full board evaluations which can be performed each move depending on the playing level. MFG can only look at 5 to 10 moves in detail (depending on playing level) before selecting the move it finally plays. A safeguard against errors in the evaluation function is that only reasonable moves are suggested for full board evaluation (Fotland, 1993). By employing the strategy function, the move suggestion expert system, and the joseki and pattern databases, MFG fully examines a small number of moves, playing the one which receives the highest score from the evaluation function. The score returned from a full board evaluation is also modified by the addition of sente if applicable. Thus if MFG plays a sente move, the value of sente is added to the evaluation for the resulting position. The value of sente varies from 7 points during the fuseki to 1 or 2 points in the endgame and is determined by the strategy function.
Size, Performance and Timeline
With some help from Ishi Press and a professional artist, Fotland rewrote Cosmos’ user interface and released it as MFG in 1990. Until the present time (July 1996), MFG has had 3 releases with various improvements. MFG contains around 40000 lines of C code with around another 20000 lines of user interface code. MFG has performed well in various world computer Go championships including 4th in 1993, 2nd in 1994, and 3rd in 1995. According to Fotland, MFG gains about one stone in strength each year (Fotland, 1996). MFG plays on both the IGS and the NNGS as ManyFaces. MFG participates in the NNGS rating scheme and was rated 9 kyu (as at July 1996). It was also awarded an 8 kyu diploma from the Nihon Ki-in in Japan based on its performance against a 1 dan amateur at 9 stones and a sample play against a professional in September 1995 (Fotland, 1996).
Go4++
Micheal Reiss started writing Go programs in 1983 and his current program, Go4++, has evolved from various predecessors over that time. Reiss has met with some success in computer Go competitions and Go4++ came 2nd in both the 1st and 2nd FOST cups. Reiss’ programming philosophy is to use simple algorithms on a large amount of data rather than complex algorithms on a small amount of data. Go4++ calculates everything from first principles; complex concepts are calculated from simpler concepts which are in turn functions of even simpler concepts. Thus, Go4++ does not have an elaborate rule-based expert system at its core. A positive consequence of this approach is that Reiss’ relatively weak ranking (2 kyu) compared to other top Go programmers is not a deficit. It also means that Go4++ usually responds well to the strange moves (by human standards) that are quite often played by computer Go programs and which are difficult to foresee when designing a rule-based system. The major drawback of this approach is that it is computation intensive and requires a powerful computer. At the foundation of Go4++ is a massive amount of connectivity data from which almost everything else is eventually derived. Go4++ selects a move by first generating about 50 candidate moves that are analyzed by an evaluation function which estimates territory. The move scoring the highest evaluation is played as the next move. Thus, Go4++ uses 1 ply global lookahead although tactical lookahead and search is used in evaluating each move.
Candidate Move Generation
Candidate moves are generated by a process of pattern matching to determine the best 50 moves to examine in depth. Go4++ has around 15 high level patterns which include terms for the probability of an eye, safety, and territorial value. Whenever a match is made, the board point(s) suggested as good places to play have an appropriate value added to them. The 50 highest scoring board points are then examined by the evaluation function. The board point which receives the highest score from the evaluation function is played as the next move. In some circumstances, Go4++ effectively evaluates more than 50 candidate moves per turn. Pattern matching is not applied to regions of the board where the stone safety and territory do not differ from those of the previous move. Thus after evaluating the 50 highest scoring board points after pattern matching, the next move is selected from the combined set of evaluation scores of the 50 board points just considered and the evaluation scores of any board points in the undisturbed regions which were considered during the selection of the previous move.
Evaluation Function
The evaluation function is a six step process: 1. a connectivity probability map is generated, 2. groups are determined, 3. eye space is determined from which individual eyes are identified, 4. the safety of each stone is determined, 5. a radiation function combines the stone safety data and connectivity probability map to radiate safety to empty points, and 6. territory is determined. Reiss describes the evaluation function as pessimistic since whenever it is applicable, the evaluation function considers that the opponent is the next to move.
Connectivity Probability Map
Each time a hypothetical move is played on the board, a connectivity probability map for all friendly and opponent stones (including the hypothetical stone) is generated and stored. The connectivity probability map for a stone contains the probability of connecting to nearby friendly stones already on the board or to an empty point if it was occupied by a friendly stone. Stones and empty points which can be reached directly (nobi), by a diagonal move (kosumi link), a one point jump (ikken-tobi link), a two point jump (nikken-tobi link), a small knight’s move (kogeima link), or a large knight’s move (ogeima link) are examined (total of 32 possible points). The probability of connecting two stones is calculated empirically by playing out the sequences of moves needed to determine whether the stones can be connected or whether the opponent can cut them. This process requires the use of lookahead, particularly when ladders are generated by cutting moves (e.g., cutting a kogeima link generates two ladders, one for each cutting point). If all possible cutting stones are captured, then the probability of connection is 100%. However, if the cutting stones can not be captured, a hand-tuned algorithm estimates the connection probability. A massive amount of data is generated in calculating the probability map for each stone on the board for every hypothetical stone being evaluated. The process is very computationally expensive and requires a powerful computer (Go4++ currently runs on a Pentium-Pro 200).
Group Determination
Stones and strings are catalogued into groups: any stones which are 100% connected are considered groups. A tactical search on all strings with less than 4 liberties is used to determine which strings are definitely dead. Dead strings are not included as part of any group.
Eye Identification
Identifying eyes is achieved in a two step process: 1. eye space is determined, and 2. individual eyes are identified from the eye space. A floodfill type algorithm is used to identify contiguous regions in which opponent connectivity probability is low. Points in those regions whose 8 neighbouring points are mostly clear of opponent connectivity probability are considered to be eye space. Individual eyes within a groups eye space are identified by shape. There are several grades of eyes with the grade being a function of the opponent’s connectivity map. Eyes with a grade above a certain level (see Stone Safety below) are considered to be true eyes.
Stone Safety
The safety of each group is determined by the number of true eyes it has. The safety process is repeated 5 times; each successive pass is more pessimistic about which points will eventually become true eyes (i.e., the threshold is raised for selecting which grade of eyes will eventually become true eyes). The final safety value for a group is the average of its safety scores on each of the 5 passes.
Radiation Function
The safety value for each stone is radiated to the nearby empty points in proportion to the connectivity probability map for that stone. The inverse of a stones safety (100% – safety) is radiated in the same manner and contributes to the opponents radiated value i.e., dead stones radiated full opponent safety. Black and white radiation (including inverse radiation) is summed at each empty point.
Territory
Black and white territory is estimated from the radiation values of the empty points. The difference between black and white territory is returned as the evaluation of the hypothetical move for which it was generated.
Performance and Timeline
Reiss’ Go skill has progressed from 10kyu in 1987 to 4 kyu in 1992 to 2 kyu in 1996. Reiss has programmed full-time on Go4++ for about the last year (1996) and also programmed full-time for one and a half years around 1986. Other than for these two periods since starting Go programming in 1983, Reiss has programmed part-time with the most effort usually expended in the two months leading up to a competition. There have been many commercial releases of Reiss’ programs by Oxford Softworks with another soon to follow. Notable releases have been Go Player Professional and an updated windows version, Go Professional II, released in Japan. Reiss characterized Go4++ as the weakest of the current strong programs at tactical situations requiring life and death analysis although it is good at creating moyos and gaining territory in the middle and endgame. Since Go4++ tends to play well in the centre of the board, Prof. Chen played 200 games against Go4++ in an attempt to test modifications to Handtalk which were designed at playing better in the centre. According to Reiss, other weaknesses are the absence of global lookahead, lack of a concept of “shape”, and the reluctance of Go4++ to invade. Since the evaluation function pessimistically considers that the opponent moves next during tactical searches, Go4++ does not usually evaluate the likelihood of invading stones forming eyes as being favourable. To compensate for not invading well, Go4++ always plays it first move at the 3,3 point and also tries to live in as many places as possible to stop its opponent creating moyos early. Reiss uses many empirically hand-tuned algorithms within Go4++ although no learning algorithms are used. Carefully crafted changes to these algorithms can improve the strength of Go4++ e.g., by making the connection algorithm more accurate, eye and territory evaluation also become more accurate, resulting in an increase in playing strength. Before the 2nd FOST Cup in 1996, Reiss tuned the performance of Go4++ by playing 700 test games against Handtalk, resulting in Handtalk’s only defeat during that competition.
Handtalk
Handtalk has been one of the strongest programs in recent years and is written by Zhixing Chen, a Chinese professor from the University of Guangzhou. Although Handtalk becomes stronger each year and was awarded a 4 kyu diploma by the Nihon Kiin in 1996, Prof. Chen does not believe that Go programs will reach shodan by 2000 if shodan is taken at its international level (2 – 3 dan Japanese). Details of the architecture and algorithms used by Prof. Chen are not abundantly available. Some of the details which have emerged from discussions that various people have had with Prof.Chen at various competitions are provided below. Handtalk is written completely in IBM-PC assembly language and is very small (around 250k) and very fast. Only a very small number (around 4) candidate moves are evaluated using a static evaluation function which seems to be accurate and stable. Handtalk also uses an influence function whose influence decreases as 1/2^distance. Handtalk does not use very much global search. Pattern matching is used to some extent although it is unclear whether the patterns are contained in a database or if the pattern matching is rule-based. Handtalk does not use joseki much and has only about 10% as many josekis as MFG. According to Prof. Chen, Handtalk’s strong points are its fighting, group safety estimation, ability to recognize life and death, the end game, and board evaluation. Other people have also commented on its strength at estimating a group’s running ability, sense of shape, the middle game, and winning semeais. Prof. Chen characterizes its weaknesses as surrounding, ko, and attacking territory. Recent changes include fighting less often than in previous versions and an improvement in gaining territory in the centre which was achieved by testing alterations in around 200 games played against Go4++.
New approach: Monte-Carlo method
One major alternative to using hand-coded knowledge and searches is the use of Monte-Carlo methods. This is done by generating a list of potential moves, and for each move playing out thousands of games at random on the resulting board. The move which leads to the best set of random games for the current player is chosen as the best move. The advantage of this technique is that it requires very little domain knowledge or expert input, the tradeoff being increased memory and processor requirements. However, because the moves used for evaluation are generated at random it is possible that a move which would be excellent except for one specific opponent response would be mistakenly evaluated as a good move. The result of this are programs which are strong in an overall strategic sense, but are weak tactically. This problem can be mitigated by adding some domain knowledge in the move generation and a greater level of search depth on top of the random evolution. Some programs which use Monte-Carlo techniques are MoGo, CrazyStone, Olga and Gobble. In 2006, a new search technique, upper confidence bounds applied to trees (UCT), was developed and applied to many 9×9 Monte-Carlo Go programs with excellent results. UCT uses the results of the play outs collected so far to guide the search along the more successful lines of play, while still allowing alternative lines to be explored. The UCT technique along with many other optimizations for playing on the larger 19×19 board has led MoGo to become one of the strongest research programs. Successful applications of UCT methods to 19×19 go include MoGo, CrazyStone and Mango, which achieve respectively a rating of 4th kyu and 6th kyu on the KGS server. Since October 2006, MoGo itself has won every monthly KGS Computer Tournament, including the 19×19 event in March 2007 and the 2007 Computer Olympiad. Mogo has an estimated 3-4 dan strength in 9×9 games. In 2007, Rémi Coulom developed a new method of generating candidate moves for the UCT algorithm based upon machine analysis of ELO scores/past games. As a result of these changes, CrazyStone has shown an improvement of roughly 600 ELO points on the CGOS server.
[from Wikipedia.org; GoBase.org; "An Introduction to the Computer Go Field and Associated Internet Resources" by Jay Burmeister and Janet Wiles; ]