Computer Games Theory

Games are ideal domain for exploring the capabilities of computational intelligence. The rules are fixed, the scope of the problem is constrained, and the interactions of player are well defined.

Historically, games have been a popular choice for demonstrating new research ideas in artificial intelligence. Indeed, one of the early goals of AI was to build a program capable of defeating the human world chess champion in a match.

Computer-games research started in 1950 when Cloude Shannon, one of the luminaries in computing science history, published his seminal paper that laid out the framework for building high-performance game playing programs.

In the half century years since Shannon's papers, enormous progress has been made and chess isn't the only board-game researched. In the 1980s David Levy creates the Computer Olympiad: a multi-games event taking place every year in which computer programs compete against each other. The majority of the games are board games but other games such as Bridge take place as well. The Olympiad was originally held in either London or Maastricht, lately however, cities from around the world have hosted the Olympiad.

Here you will find informations, papers and source codes about these game:

• Amazons: papers, source, links, theory
• Checkers: papers, source, links, theory
• Chess: papers, source, links, theory
• Chinese Chess (Xiangqi): papers, source, links, theory
• Go: papers, source, links, theory
• Othello: papers, source, links, theory
• Shogi: papers, source, links, theory

Amazons

The Game of the Amazons (often called Amazons for short) is a two-player abstract strategy game invented in 1988 by Walter Zamkauskas of Argentina. It is a member of the territorial game family, a distant relative of Go. It is played on a 10x10 chessboard (or an international checkerboard). Although the game uses pieces with moves like a chess queen, it is in no sense a chess variant. The two players are White and Black; each player has four amazons, which start on the board in the configuration shown at right. A supply of markers (checkers, poker chips, etc.) is also required.

Rules

White moves first, and the players alternate moves thereafter. Each move consists of two parts: moving one of one's own amazons one or more empty squares in a straight line (orthogonally or diagonally), exactly as a queen moves in chess; it may not cross or enter a square occupied by an amazon of either color or an arrow. After moving, the amazon shoots an arrow from its landing square to another square, using another queenlike move. This arrow may travel in any orthogonal or diagonal direction (even backwards along the same path the amazon just traveled, into or across the starting square if desired). An arrow, like an amazon, cannot cross or enter a square where another arrow has landed or an amazon of either color stands. The square where the arrow lands is marked to show that it can no longer be used. The last player to be able to make a move wins. Draws are impossible.

Strategy

The strategy of the game is based on using arrows (as well as one's four amazons) to block the movement of the opponent's amazons and gradually wall off territory, trying to trap the opponents in smaller regions and gain larger areas for oneself. Each move reduces the available playing area, and eventually each amazon finds itself in a territory blocked off from all other amazons. The amazon can then move about its territory firing arrows until it no longer has any room to move. Since it would be tedious to actually play out all these moves, in practice the game usually ends when all of the amazons are in separate territories. The player with the largest amount of territory will be able to win, as the opponent will have to fill in her own territory more quickly. Scores are sometimes used for tie-breaking purposes in Amazons tournaments. When scoring, it is important to note that although the number of moves remaining to a player is usually equal to the number of empty squares in the territories occupied by that player's amazons, it is nonetheless possible to have defective territories in which there are fewer moves left than there are empty squares. The simplest such territory is three squares of the same colour, not in a straight line, with the amazon in the middle (for example, a1+b2+c1 with the amazon at b2).

Computer Amazons

The large branching factor of Amazons in the opening and middle game strongly limits the search depth of full-width search programs. There are over 2000 possible starting moves on the 10x10 board, and although this number decreases quickly in the opening, there are several hundred legal moves during most of the game. Experiments have shown that as in most other games, search depth is strongly correlated to playing strength. Amazons seems to be a very suitable game for experimenting with selective search methods.

[from Wikipedia.org; "A gamut of games" by Jonathan Schaeffer; "Experiments in Computer Amazons" by Martin Muller and Theodore Tegos]

top

Checkers / Draughts

Checkers (American English, sometimes spelled chequers in British English) or Draughts (British English) is a group of abstract strategy board games between two players which involve diagonal moves of uniform pieces and mandatory captures by jumping over the enemy's pieces.

The most popular forms are international draughts, played on a 10×10 board, followed by English draughts, also called American checkers that is played on an 8×8 board, but there are many other variants:

• International draughts (also called Polish draughts) - The board size is 10×10 with 20 pieces on each side and has flying kings. Unlike in chess the playing fields are numbered just by the numbers from 1 to 50. If there are many sequences to capture, one has to capture the sequence that has the most pieces. If a man touches the kings row from a jump and it can continue to jump backwards, it has to jump backwards, but it is not kinged. It is mainly played in the Netherlands, France, some eastern European countries, some parts of Africa, some parts of the former USSR, and other European countries.
• English draughts - Also called American checkers or "straight checkers". It is played on an 8×8 board with 12 pieces on each side. Black (the darker color) moves first. Men (the uncrowned pieces) can only move and capture forward. When there is more than one way for a player to jump, one may choose which sequence to make, not necessarily the sequence that will result in the greatest number of captures. However, one must make all the captures in that sequence.
• Brazilian checkers - Exactly the same rules as international draughts, but it is played on an 8×8 board. It is mainly played in Brazil.
• Canadian checkers - Exactly the same rules as international draughts, but it is played on a 12×12 board with 30 pieces on each side. It is mainly played in Canada.
• Pool checkers - Exactly the same rules as Brazilian checkers but when there is more than one way for a player to jump, one may choose which sequence to make, not necessarily the sequence that will result in the greatest number of captures. However, one must make all the captures in that sequence. Another different rule between Brazilian checkers is in which black moves first, instead of white. It is mainly played in the South-Eastern states in the United States.
• Spanish checkers - Also called Spanish pool checkers. Men cannot jump backwards. Exactly the same rules as Brazilian checkers, but if there are many sequences to capture, one has to capture the sequence that has the most pieces. If there are still more sequences, one has to capture the sequence that has the most kings. The board is mirrored (the left side is flipped to the right side and vice versa). It is mainly played in some parts in South America and some Northern African countries.
• Russian checkers - Also called shashki or Russian shashki checkers. Exactly the same rules as Brazilian checkers, but if a man touches the kings row from a jump and it can continue to jump backwards, it has to jump backwards as kings, not men. It is mainly played in some parts in Russia, some parts of the former USSR, and Israel. In many games at the end one adversary has three kings while the other one has just one king. In such a case the first adversary normally wins if (s)he occupies the main diagonal first and then builds the so-called Petrov's triangle.
• Italian checkers - Men cannot jump kings and men cannot jump backwards. If there are many sequences to capture, one has to capture the sequence that has the most pieces. If there are still more sequences, one has to capture with a king instead of a man. If there are still more sequences, one has to capture the sequence that has the most kings. If there are still more sequences, one has to capture the sequence that has a king first. The board is mirrored (the left side is flipped to the right side and vice versa). It is mainly played in Italy, and some Northern African countries.
• In Turkish draughts (a common form of checkers in the Middle-East, known as Dama), played on an 8×8 board, pieces move straight forward or sideways, and capture by jumping over an enemy piece. If there are many sequences to capture, one has to capture the sequence that has the most pieces. When a piece reaches the last row it promotes to a flying king (Dama) which moves like the rook in chess. Each player starts with 16 pieces on the second and third rows. It is played in Turkey, Kuwait, Israel, Lebanon, Syria, Jordan and several other locations of the Middle-East, as well as the same locations as Russian checkers.

Rules

Draughts is played by two people, on opposite sides of a playing board, alternating moves. One player has dark pieces, and the other has light pieces. The player with the dark pieces makes the first move unless stated otherwise. Pieces move diagonally and pieces of the opponent are captured by jumping over them. The playable surface consists only of the dark squares. A piece may only move into an unoccupied square. Capturing is mandatory in most rules. A piece that is captured is removed from the board. In all variants, the player who has no pieces left or cannot move anymore has lost the game unless otherwise stated.

Uncrowned pieces ("men") move one step diagonally forwards and capture other pieces by making two steps in the same direction, jumping over the opponent's piece on the intermediate square. Men can jump side to side. Multiple opposing pieces may be captured in a single turn provided this is done by successive jumps made by a single piece. In English draughts men can only capture forwards, but in international draughts they may also capture (diagonally) backwards.

When men reach the crownhead or kings row (the farthest row forward), they become kings, marked by placing an additional piece on top of the first, and acquire additional powers including the ability to move backwards (and capture backwards, in variants in which they cannot already do so).[2]

In international draughts, kings can move as far as they want in diagonals like a bishop in chess. However, they cannot capture like a bishop, but jump over the captured piece, moving over as many empty fields as the player wants but jumping over only a single, opposing piece in each jump. (As with men, a king may make successive jumps in a single turn provided that each is a capture.) This rule, known as flying kings, is not used in English draughts, in which a king's only advantage over a man is the ability to move and capture backwards as well as forwards. Notice that captured pieces are removed from the board only after capturing is finished. Thus sometimes the captured but not yet removed piece obliges a king to stop after capturing at a given field where he in turn will be captured by the adversary.

Computer Checkers

The structure of a checkers engine is similar to that of a typical chess program: search, knowledge, database of opening moves and endgame databases. Chinook (the strongest program available and a research effort at The University of Alberta) uses alpha-beta search with a myriad of enhancements including iterative deeping, transposition table, move ordering, search extensions and search reductions. Chinook is the first program to win a human world championship for any game.

In 2007 Jonathan Schaeffer (Chinook team's leader) announces that checkers has been solved: perfect play leads to a draw.

[from Wikipedia.org; "A gamut of games" by Jonathan Schaeffer]

top

Chinese Chess (Xiangqi)

Xiangqi, is a two-player Chinese board game in the same family as Western chess, chaturanga, shogi and janggi. The present-day form of Xiangqi originated in China and is therefore commonly called Chinese chess in English. Xiangqi has a long history. Though its precise origins have not yet been confirmed, the earliest literary reference comes from the 9th century.

Xiangqi is one of the most popular board games in the world. Distinctive features of Xiangqi include the unique movement of the pao ("cannon") piece, a rule prohibiting the generals (similar to chess kings) from facing each other directly, and the river and palace board features, which restrict the movement of some pieces.

Rules

Board setup

Xiangqi is played on a board that is 9 lines wide by 10 lines long. In a manner similar to the game Go, the pieces are played on the intersections, which are known as points. The vertical lines are known as files, while the horizontal lines are known as ranks. With a few awkward substitutions, it is possible to play this game using a standard chess set.

Centered at the first through third ranks of the board is a square zone also mirrored in the opponent's territory. The three point by three point zone is demarcated by two diagonal lines connecting opposite corners and intersecting at the center point. This area is known as the palace or fortress.

Dividing the two opposing sides (between the fifth and sixth ranks) is the river. The river is often marked with the phrases "Chu River", and "Han border", a reference to the Chu-Han War. Although the river provides a visual division between the two sides, only a few pieces are affected by its presence: soldiers are promoted after crossing, and elephants cannot cross the river.

The starting points of the soldiers and cannons are typically marked with small crosses, but not all boards have these marks.

The Pieces

The pieces are small discs of wood, plastic, or some other material. Pieces are identified by Chinese ideograms in the team colours, typically black (sometimes another dark colour) and red. The names of some of the pieces differ on the two sides. The character on the red elephant, for example, actually means minister or augur. However, discussions of the game in English invariably assign the same names to the pieces on both sides. There is also some variation in the form of the characters, especially in older sets.

General. The general starts the game at the midpoint of the back edge (within the castle). One point in any non-diagonal direction. Cannot move outside the castle. In addition, the general has the theoretical power of moving like a rook along a file from his own castle to the enemy castle, to capture the opposing general. Therefore it is illegal to make any move that leaves your own general on an open file opposite the opposing general, because to do so would be to move into check.

Mandarin (also known as guard, advisor or minister, and less commonly as assistant or warrior). The mandarins start to the sides of the general. One point in any diagonal direction. Cannot move outside the castle.

Elephant. They are located next to the mandarins. Two points in any diagonal direction. It must move two points, and cannot leap another piece of either colour. Cannot cross the river. An elephant can thus reach only seven points on the board.

Horse. They begin the game next to the elephants. One point in any non-diagonal direction, followed by one point in a diagonal direction, so that it ends two points away from where it started. This is similar to the knight’s move in Western chess, except that the move is blocked by any piece occupying the point at the "elbow" of the move. Hence it is important to remember that the non-diagonal part of the move comes first.

Chariot. The chariots begin the game on the points at the corners of the board. Any number of points in any non-diagonal direction. Cannot leap. This is just like the rook’s move in Western chess.

Cannon. The cannons start on the row behind the soldiers, two points in front of the horses. When not capturing, moves just like the chariot. When capturing, must leap a single piece of either colour before proceeding to the point occupied by the target piece. This intervening piece is called a screen.

Soldier. Soldiers are placed on alternating points, one row back from the edge of the river. One point straight forward. After it reaches the opposite river bank, can move one point forward or directly sideways. Never moves diagonally or backward. No further promotion is gained when a soldier reaches the farthest rank of the board

Player take alternate turns. In each turn, a player must make a single move with a single piece. If a piece ends its move on a point occupied by an enemy piece, that piece is captured and permanently removed from play. The object of the game is to capture the enemy general. The game is won as soon as one player can make no move that prevents capture of his general. This is checkmate. Stalemate, where one player has no legal move but is not in check, is a win for the last player to move. It is illegal to make any move that exposes your general to immediate capture. This is called moving into check. It is illegal to avoid defeat or attempt to force a draw by repeating the same series of moves over and over. In particular, perpetual check is not allowed, and the onus is on the attacker to vary his move.

Strategy

Xiangqi is a fast game for several reasons. First, the barrier of pawns is reduced dramatically. Second, the cannons jump to capture, making them a long-range threat early in the game. In addition, since the general is confined to only moving within the palace, it can be checkmated more easily unless it is protected by other pieces. Because of the size of the board and the relative low number of long-range pieces, it may take time to move one's army of pieces from place to place on the board, and there is a tendency for the battle to focus on a particular area of the board. Common strategies used in Western chess such as forking with horse and pinning with chariot (sometimes the cannon and general can also pin) are also applicable in xiangqi. Usually, the soldiers do not support each other unless the player has no better move. This is because from the initial position, it takes a minimum of 5 moves of a soldier to allow twin soldiers to protect each other. Defensively, a common configuration is to leave the general at his or her starting position, deploy one advisor and one elephant on the two points directly in front of the general, and to leave the other advisor and the other elephant in their starting positions, to the side of the general. In this setup, the paired-up advisors and elephants support each other, and the general is immune from attacks by cannons. However, with the loss of a single advisor or elephant, the general becomes vulnerable to cannons, and this setup may need to be abandoned. The defender may move advisors or elephants away from the general, or even sacrifice them intentionally, to ward off attack by a cannon. The two chariots are not normally lined up together as they are the most powerful piece and in doing so, a player risks the chances of losing at least one chariot to an inferior piece of the enemy. Depending on the situation, it may be advantageous to position a chariot at one of the corners of the enemy's side of the board, where it is very difficult to dislodge, and threatens the enemy general. It is common to use the cannons independently to control particular ranks and files. Using a cannon to control the middle file is often considered vital strategy, because it helps to lock certain pieces such as the advisors and elephants in certain positions to prevent a check. The two files adjacent to the middle rank are also considered important and knights and chariots can be used to push for mate here. In addition, the cannons can also be used one in front of one another in the centre line, therefore checkmating the general/marshall in almost all scenarios, as the front cannon ensures that nothing can block, and the rear ensuring that if the front cannon is taken, the general/marshall is still check, and therefore resulting in checkmate. Unfortunately, there are ways to block this tactic, but there is less chance that the opponent can block this manoeuvre in time.

Opening

Since the left and right flank of the starting setup are symmetrical and therefore equivalent, it is customary to always make the first move from the right flank. Starting on the left flank is considered to be needlessly confusing.

The most common opening is to move the cannon to the central column, the most common reply is to advance the horse on the same flank. This is usually followed by the most common second move, in which the first player moves a chariot forward one space, usually the right one (moving the left one loses the horse, but you can reply by trapping the cannon with your chariots). The most common reply is to move the right advisor diagonally. This is to prevent a series of events that leads to the first player quickly checkmating the second.

Less common first moves include:

• moving an elephant to the central column
• advancing the soldier on the third or seventh file
• moving a horse forward
• moving either cannon behind the 2nd pawn from the left or right

General advice for the opening includes rapid development of at least one chariot, because it is the most powerful piece and the only long-range piece besides the cannon. It may not be a bad move to develop one horse to the edge of the board, for example, to avoid being blocked by one of one's own pawns that cannot advance. Usually, at least one horse should be moved to the middle.

Beginners often succumb to an early checkmate with two cannons. This checkmate may be executed in four moves from the beginning of the game. However, it is easily countered by the horse reply. A double cannon technique involves 2 cannons of the same side lining up with the enemy general with no other pieces in between. This results in a check as the rear cannon uses the front cannon as cannon platform. The opponent cannot get away by placing a piece in front of the general to block the rear cannon because the front cannon will use that newly-moved piece as cannon platform to capture the general. The solution is either to move the general up before the check or to nullify the 2nd cannon either by taking it out or placing a piece between the two cannons.

Computer Xiangqi

Compared to other games such as Checkers, Othello, and Go, the complexity of Chinese chess can be said to be similar to that of Western chess, although it seems to lead to longer tactical exchanges. On average slightly more capturing moves are possible, the board is slightly larger, and a draw by repetition of forcing moves is not allowed. Despite that, the tactical exchange and long-term planning ideas from chess carry across. Thus most computer methods developed for chess apply equally well in Chinese Chess.

Chinese-chess programs are like Western-chess programs in that they can be divided into two types: knowledge-based and brute-force programs. A knowledge-based program emphasises the evaluation of positions. A brute-force program uses the ability to compute quickly and to explore the game tree deeply, so as to discover better moves. Even in Western-chess, the better approach has not been identified yet. Chinese chess has more different pieces and a larger board than chess, so knowledge-based programs are considered to have more potential.

A game of Chinese chess can usually be divided into three stages – the opening, the middle game, and the endgame. In the opening, Chinese-chess programs currently use an opening database to support computation. An opening database is enlarged by Chinese-chess game records from tournaments on the Internet and by the results of Chinese-chess tournaments. According to the results of the competition between human and computer, the best program with an adequate opening database is currently above 7-dan and the program that implements adequate searches in the middle game can exceed 6-dan. These ratings may be improved as hardware advances. The endgame is the weakest part of the present Chinese-chess programs. A massive memory is necessary to combine endgame database and the search system. The development of hardware may overcome this difficulty.

[from Wikipedia.org; "An Introduction to Chinese Chess" by Peter Donnelly; "A gamut of games" by Jonathan Schaeffer; "Searching for solutions in games and artificial intelligence" L. V. Allis; "Computer Chinese Chess" Yen, Chen, Yang Hsu]

top

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 19x19 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 9x9 board is worth two on a 13x13 board and four on a 19x19 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 (8x8 squares in chess vs 19x19 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 9x9 Go is around about the same complexity as Chess (35 versus 50 in 10 log search space) and that 19x19 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 5x5 to 8x8, 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 8x8 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 19x19 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 8x8 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 8x8 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 9x9 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 19x19 board has led MoGo to become one of the strongest research programs. Successful applications of UCT methods to 19x19 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 19x19 event in March 2007 and the 2007 Computer Olympiad. Mogo has an estimated 3-4 dan strength in 9x9 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; ]

top

Othello

Othello was invented by Goro Hasegawa in 1971. The name is a reference to the Shakespearean play Othello, the Moor of Venice, referencing the conflict between the Moor Othello and Iago, who describes himself as "two faced" (or more controversially, to the marriage between Othello, who is black, and Desdemona, who is white, recalling the coloring of the game pieces). It is an abstract strategy board game which involves play by two parties on an eight-by-eight square grid with pieces that have two distinct sides. Pieces typically appear coin-like, but with a light and a dark face, each side representing one player. The object of the game is to make your pieces constitute a majority of the pieces on the board at the end of the game, by turning over as many of your opponent's pieces as possible.

Rules

Each of the two sides corresponds to one player; they are referred to here as light and dark after the sides of Othello pieces, but "heads" and "tails" would identify them equally as well, so long as each marker has sufficiently distinctive sides.

Originally, Reversi did not have a defined starting position. Later it adopted Othello's rules, which state that the game begins with four markers placed in a square in the middle of the grid, two facing light-up, two pieces with the dark side up. The dark player makes the first move.

Dark must place a piece with the dark side up on the board, in such a position that there exists at least one straight (horizontal, vertical, or diagonal) line between the new piece and another dark piece, with one or more contiguous light pieces between them. Players take alternate turns. If one player cannot make a valid move, play passes back to the other player. When neither player can move, the game ends. This occurs when the grid has filled up, or when one player has no more pieces on the board, or when neither player can legally place a piece in any of the remaining squares. The player with more pieces on the board at the end wins.

Strategy

A beginner often looks for the move that will reverse the greatest possible number of pieces, trying for immediate numerical advantage. For unsophisticated players, this strategy works quite well and will win a majority of games as long as the player thinks at least a few turns in advance. As the experience of the opponent increases, this strategy becomes ineffectual. Instead of numerical advantage, the key elements of successful Othello strategy are corners, mobility, edge play, parity, endgame play, and looking ahead.

Corners

Corner positions, once played, remain immune to flipping for the rest of the game (because there is no other opposite color behind them to create a flip): thus a player can use a piece in a corner of the board to anchor groups of pieces (starting with the adjacent edges) permanently. So capturing a corner often proves an effective strategy when the opportunity arises. More generally, a piece is stable when, along all four axes (horizontal, vertical, and each diagonal), it is on a boundary, in a filled row, or next to a stable piece of the same color. Grabbing a corner too soon can be a mistake, however, if it leaves "holes" in the edge that the opponent can make use of.

Mobility

An opponent playing with reasonable strategy will not so easily relinquish the corner or any other good moves. So to achieve these good moves, you must force your opponent to play moves which relinquish those good moves. The best way to achieve this involves reducing the number of moves available to your opponent. If you consistently restrict the number of legal moves your opponent can make, then sooner or later they will have to make an undesirable move. An ideal position involves having all your pieces in the center surrounded by your opponent's pieces. In such situations you can dictate what moves your opponent can make. When moves seem equal with respect to what moves you will leave yourself and your opponent, playing a minimum piece strategy will tend to give you an advantage, because minimizing your discs will tend to leave fewer discs for your opponent to flip in subsequent moves of the game. One should not play the minimum disc strategy to an extreme, however, as this also can quickly lead to a lack of mobility.

Edges

While playing pieces to edges of the board may seem sound (because they cannot be flipped easily), this strategy can often prove detrimental. Edge pieces can anchor flips that influence moves to all regions of the board. This can poison later moves by causing players to flip too many pieces and open up many moves for the opponent. However, playing on edges where an opponent cannot easily respond drastically reduces possible moves for that opponent. The square immediately diagonally adjacent to the corner (called the X-square), when played in the early or middle game, typically guarantees the loss of that corner. Nevertheless, such a corner sacrifice is sometimes played for some strategic purpose (like retaining mobility). Playing to the edge squares adjacent to the corner (called the C-squares) can also be dangerous if it gives the opponent powerful forcing moves. In general, edge play in the early and middle game is to be avoided, unless players can gain larger concessions in terms of mobility or a mass of unflippable pieces. A good rule of thumb is to keep pieces grouped together in the middle of the board and minimize tangents formed by a player's own pieces. This strategy leads to the greatest mobility.

Parity

Parity is one of the most important parts of the strategy. In short, the concept of parity is about getting the last move in every empty region in the end-game, and thereby increasing the number of stable discs. The concept of parity led to a change in the perception of the game, as it led to distinct strategies for playing black and white. It forced black to play more aggressive moves and gave white the opportunity to stay calm and focus on keeping the parity. As a result the opening books and mid-game were focused on black being the "attacker" and white being the "defender". Another side effect of parity is that black should try to complicate the game whereas white should seek to simplify it. It is easier to maintain parity in a simple position. The concept of parity also controls how edge positions are played and how edges interact. Today it is essential to have an understanding of parity to get the maximum experience out of the game.

Look-ahead

As in any good strategy for chess or for checkers, a player should not consider only the current situation on the board. For each move you consider, you must consider possible responses from your opponent, then the subsequent responses you will make to those moves and so on. The aspects of the current position may not remain relevant a few moves hence. So when optimizing your mobility, gaining corners or anything else, you should consider how best to do this for the long term rather than just for the next move.

Endgame

For the endgame (the last 20 or so moves of the game) the strategies will typically change. Special techniques such as sweeping, gaining access, and the details of move-order can have a large impact on the outcome of the game. At these late stages of the game no hard-set rules exist. The experienced player will try to look ahead and get a feel for what will lead to the best final outcome.

Computer Othello

Today, machines play the Japanese board game Othello very well. In fact, the 6-0 defeat of the then human World-champion Takeshi Murakami by Logistello in 1997 strongly indicates that machines have surpassed human playing strength.

A typical Othello programs consists of an alpha-beta searcher with a static evaluation function, some forward pruning method, iterative deeping, opening book, endgame database and patterns database. The most important positional feature in Othello are disc stability, mobility and parity. Most methods of search extensions and reducitions that work in other domain do not work in Othello: null moves don't work in othello because it is often preferable to pass in a given position. Fortunately, there are methods whic do work: Probcut and Multi-level Probcut, for example.

[from Wikipedia.org; "The evolution of strong othello programs" by M. Buro; "Keyano unplugged - the construction of an othello program " by M. Brockington; "A gamut of games" by Jonathan Schaeffer;]

top

Shogi

Shogi is a Japanese traditional Chess-like game that is played with a 9 by 9 board and 40 pieces that are classified in eight kinds: king, rook, bishop, gold general, silver general, knight, lance, pawn. The goal of Shogi is checkmating the opponent King. Each player plays a move alternately. The first player is Black and the second player is White. The pieces in the lower side of the board are Black’s pieces and other pieces in the upper side of the board are White’s pieces even if except for the kings, opposing pieces are differentiated only by orientation, not by marking or color. We use coordinates files as numbers (1 to 9 from right side of the board to left) and ranks as alphabets (a to i from top of the board to bottom). The squares in rank g to i are Black’s area and the squares in rank a to c is White’s area.

Rules

Board setup

Each player places his pieces in the positions shown below, facing the opponent.

In the rank nearest the player:

• The king is placed in the center file.
• The two gold generals are placed in the adjacent files to the king.
• The two silver generals are placed adjacent to each gold general.
• The two knights are placed adjacent to each silver general.
• The two lances are placed in the corners, adjacent to each knight.

That is, the first rank is |L|N|S|G|K|G|S|N|L|.

In the second rank, each player places:

• The bishop in the same file as the left knight.
• The rook in the same file as the right knight.

In the third rank, the nine pawns are placed one to each file.

Traditionally, even the order of placing the pieces on the board is determined. There are two recognized orders, ohashi and ito. The Japanese-language page Shogi Pineapple indicates the two orders; ohashi is depicted on the left and ito on the right.

Gameplay

The players alternate taking turns, with Black (the side containing the Jeweled General) playing first. The terms "Black" and "White" are used to differentiate the two sides, but there is no actual difference in the color of the pieces. For each turn a player may either move a piece which is already on the board and potentially promote it, capture an opposing piece, or both; or to "drop" a piece that has already been captured onto an empty square of the board. Professional games are timed as in International Chess, but professionals are never expected to keep time in their games. Instead a timekeeper is assigned, typically an apprentice professional. Time limits are much longer than in International Chess (9 hours a side plus extra time in the prestigious Meijin title match), and in addition byoyomi (literally "second counting") is employed. This means that when the ordinary time has run out, the player will from that point on have a certain amount of time to complete every move (a byoyomi period), typically upwards of one minute. The final ten seconds are counted down, and if the time expires the player to move loses the game immediately. Amateurs often play with electronic clocks that beep out the final ten seconds of a byoyomi period, with a prolonged beep for the last five.

Movement and capture

If an opposing piece occupies a legal destination for a friendly piece (that is, a piece belonging to the player whose turn it is to move), it may be captured by removing it from the board and replacing it with the friendly piece. It is not possible to move to or through a square occupied by another friendly piece, or to move through a square occupied by an opposing piece. It is common to keep captured pieces on a wooden stand (or komadai) which is traditionally placed so that its bottom left corner aligns with the bottom right corner of the board from the perspective of each player. It is not permissible to hide pieces from full view. This is because captured pieces, which are said to be in hand, have a crucial impact on the course of the game. The knight jumps, that is, it passes over any intervening piece, whether friend or foe, without an effect on either. It is the only piece to do this. The lance, bishop, and rook are ranging pieces: They can potentially move any number of squares along a straight line limited by the edge of the board. If an opposing piece intervenes, it may be captured by removing it from the board and replacing it with the moving piece. If a friendly piece intervenes, one is limited to a distance that stops short of that square; if the friendly piece is adjacent, one may not move in that direction at all. All pieces but the knight move either orthogonally (that is, forward, backward, or to the side, in the direction of one of the arms of a plus sign, +), or diagonally (in the direction of one of the arms of a multiplication sign, ×).

• King: King can move to the neighboring squares. The movement is the same as King of Chess.
• Rook: Rook can move along the rank and file for any number of squares, but cannot jump over any pieces. This movement is the same as Rook of Chess.
• Bishop: Bishop can move along diagonal squares for any number of squares, but cannot jump over any pieces. The movement is the same as Bishop of Chess.
• Gold: Gold can move one square forward, backward, sideways or diagonally forward.
• Silver: Silver can move one square forward, diagonally forward or diagonally backward.
• Knight: Knight can move one square straightforward and then one square diagonally forward, to the right or left. It is the only piece that can jump over other pieces. The movement is not the same with Knight of Chess. The Knight of Chess can move eight directions, but the Knight of Shogi can move only two forward directions.
• Lance: Lance can move straightforward for any number of squares, but cannot jump over any pieces and never go back.
• Pawn: Pawn can move one square forward. The movement and capturing are different from the Pawn of Chess.

Promotion

In Chess, pawns can be promoted. In Shogi, all pieces except the king and the gold general can be promoted. Promotion can happen at the end of any move in which the piece enters, exits, or moves within the three-row promotion zone. Pawn and lance must be promoted when reaching the 9th row. Knight must be promoted when reaching the 8th or 9th row.

The promoted pawn, promoted lance, promoted knight, and promoted silver general all have the moves of the gold general.

The promoted rook becomes Dragon King (not to be confused with the king). It has the moves of the rook and the king.

The promoted bishop becomes Dragon Horse (not to be confused with the knight). It has the moves of the bishop and the king.

Drops

Captured pieces are truly captured in shogi. They are retained "in hand", and can be brought back into play under the capturing player's control. On any turn, instead of moving a piece on the board, a player may take a piece that had been previously captured and place it, unpromoted side up, on any empty square, facing the opposing side. The piece is now part of the forces controlled by that player. This is termed dropping the piece, or just a drop.A drop cannot capture a piece, nor does dropping within the promotion zone result in immediate promotion. However, either capture or promotion may occur normally on subsequent moves by the piece.A pawn, knight, or lance may not be dropped on the far rank, since it would have no legal move on subsequent turns. Similarly, a knight may not be dropped on the penultimate rank.

There are two other restrictions when dropping pawns:

• A pawn cannot be dropped onto the same file (column) as another unpromoted pawn controlled by the same player. (A tokin does not count as a pawn.) A player who has an unpromoted pawn on every file is therefore unable to drop a pawn anywhere. For this reason it is common to sacrifice a pawn in order to gain flexibility for drops.
• A pawn cannot be dropped to give an immediate checkmate. However, other pieces may be dropped to give immediate checkmate, a pawn that is already on the board may be advanced to give checkmate, and a pawn may be dropped so that either it or another piece can give checkmate on a subsequent turn.

It is common for players to swap bishops, which face each other across the board. This leaves each player with a bishop "in hand" to be dropped later, and gives an advantage to the player with the stronger defensive position.

Check and mate

When a player makes a move such that the opposing king could be captured on the following turn, the move is said to give check to the king; the king is said to be in check. If a player's king is in check and no legal move by that player will get the king out of check, the checking move is also checkmate (tsumi) and effectively wins the game. To give the warning "check!" in Japanese, one says "ote!". However, this is an influence of international chess and is not required, even as a courtesy. A player is not allowed to give perpetual check.

Winning the game

When a player cannot do any legal moves, that player must resign and the player loses. For example, the one's king is in checkmate. In professional and serious amateur games, a player who makes an illegal move loses immediately. There are two other possible, if uncommon, ways for a game to end: repetition (sennichite) and impasse (jishogi). If the same game position occurs four (formerly three) times with the same player to play, the game is declared no contest. For two positions to be considered the same, the pieces in hand must be the same as well as the positions on the board. However, if this occurs with one player giving perpetual check, then that player loses. The game reaches an impasse if both kings have advanced into their respective promotion zones and neither player can hope to mate the other or to gain any further material. If this happens, the winner is decided as follows: Each rook or bishop scores 5 points for the owning player, and all other pieces except kings score 1 point each. (Promotions are ignored for the purposes of scoring.) A player scoring less than 24 points loses. Jishogi is considered an outcome in its own right rather than no contest, but there is no practical difference. In professional tournaments the rules typically require drawn games to be replayed with colours (sides) reversed, possibly with reduced time limits. This is rare compared to chess and xiangqi, occurring at a rate of 1-2% even in amateur games. The 1982 Meijin title match between Nakahara Makoto and Kato Hifumi was unusual in this regard, with jishogi in the first game (only the fifth draw in the then 40-year history of the tournament), a game which lasted for an unusual 223 moves (not counting in pairs of moves), with an astounding 114 minutes spent pondering a single move, and sennichite in the sixth and eighth games. Thus this best-of-seven match lasted ten games and took over three months to finish; Black did not lose a single game and the eventual victor was Kato at 4-3.

Strategy

Drops are the most serious departure from International Chess. They entail a different strategy, with a strong defensive position being much more important. A quick offense will leave a player's home territory open to drop attacks as soon as pieces are exchanged. Because pawns attack head on, and cannot defend each other, they tend to be lost early in the game, providing ammunition for such attacks. Dropping a pawn behind enemy lines, promoting it to a "tokin" (gold general), and dropping a second pawn immediately behind the "tokin" so that they protect each other makes a strong attack; it threatens the opponent's entire defense, but provides little value if the attack fails and the pieces are captured. Players raised on International Chess often make poor use of drops, but dropping is half the game. If a player has more than a couple of captured pieces in hand, it is likely that dropping attacks are being overlooked. However, it is wise to keep a pawn in hand, and often to exchange pieces if necessary to get one. Compared to International Chess, Shogi players are more likely to sacrifice pieces (even valuable ones), if the resulting capture can be dropped back into play for a specific purpose. There are two openings typically used in Shogi. Players can both move the rook pawn forward, or more commonly, advance the pawn above and to the right of the bishop. The former is known as a rook opening while the latter is a bishop opening. When doing a bishop opening, it's common to exchange pieces by having one bishop attack the other. This allows each player to return their newly capture bishop into play anywhere on the board. However, it is not always advantageous to exchange bishops, depending on what they intend to do next. Attacking pieces can easily become trapped behind enemy lines, as the opponent can often drop a pawn on a protected square to cut off the line of retreat. For this reason, rooks, which can retreat in only one direction, are commonly kept at a safe distance in the early parts of the game, and used to support attacks by weaker pieces. However, once the game has opened up, a promoted rook is an especially deadly piece behind enemy lines. Kings can also be easily trapped by their own pieces, so a good last-ditch defensive effort is to open a back door through the pawn line to allow kings to escape. Kings are more difficult to checkmate in the open, especially if the opponent does not have many ranged pieces in play. Many common opening attacks involve advancing a silver, and ideally a pawn, along a file protected by the rook. This is the climbing silver attack. Because silvers have more possibilities for retreat, while golds better defend their sides, silvers are generally considered superior as attacking pieces, and golds superior as defensive pieces. It is common practice to defend the king with three generals, two golds and a silver. There are various furibisha or "ranging rook" openings where the rook moves to the center or left of the board to support an attack there, typically with the idea of allowing the opponent to attack while arranging a better defence and aiming for a counterattack. However, as the most powerful piece on the board, the rook invites attack, and in most cases, especially for weaker players, it is a good idea to keep the king well away from the rook. Leaving a king on its original square (igyoku or a "sitting king") is a particularly dangerous position. Advancing a lance pawn can open up the side of the board for attack. Therefore, when a player first advances a lance pawn, it is usual for the opponent to answer by advancing the opposing pawn, in order to avoid complications later in the game. It also allows the king to escape if attacked from the side. Because defense is so important, and because shogi pieces are relatively slow movers, the opening game tends to be much longer in shogi than in International Chess, commonly with a dozen or more moves to shore up defenses before the initial attack is made. There are several strong defensive fortifications known as castles.

The Yagura castle

The Yagura castle is considered by many to be the strongest defensive position in shogi. It has a strongly protected king; a well fortified line of pawns; and the bishop, rook, and a pawn all support a later attack by the rook's silver or knight. It is notoriously difficult to break down with a frontal assault, though it is weaker from the side. It is typically used against ibisha or "static rook" openings, which involve advancing the rook's pawn. However, one's opponent may just as easily adopt this defense, giving neither side an advantage. Instead of the rook's pawn being advanced two squares as shown in the diagram, the adjacent silver's pawn is often advanced one square, allowing both the rook's silver and knight to move forward. These offensive moves are not properly part of the castle, but the two-square pawn advance must be carried out early if there is to be room for it, and so it is often done while still castling. There is a good deal of flexibility in the order of moves when building the Yagura defense, and the possibilities will not be listed here. The only point to keep in mind is that the generals should move diagonally, not directly forward. However, there is a strong intermediate position called the kani ("crab"). It has the three pawns on the left side advanced to their final Yagura positions, and on the second rank all four generals are lined up next to the bishop, which is still in its starting position: |B|G|S|G|S| bishop-gold-silver-gold-silver. The king is moved one square to the left, behind the middle silver. A common attack against the Yagura defense is to advance the rook's knight directly forward, with a pawn in hand, to attack the fortifications on either side of the castled king. If the defender has answered a lance's pawn advance on that side, a pawn may be dropped where the edge pawn had been. If the defending silver has moved or is not yet in position, a pawn may be dropped there.

The Mino-Gakoi castle

A defensive position that is considered easier for beginners, but still popular with professionals, is the Mino-Gakoi castle. The King is placed in a safe position, while the three generals work well to back each other up. This is sometimes used when a player chooses a bishop opening rather than the rook-pawn opening.

The Mino-Gakoi takes six moves to complete, not necessarily in this order:

1. Move the rook to the left side of the board, preferably the fourth rank. This move must be first.
2. Move the king to where the rook started, 3 moves.
3. Move the silver general next to the king up one space.
4. Move the left-side gold general diagonally up and right so that it is protected by the other gold general, which hasn't moved yet.

Computer Shogi

A typical shogi programs consists of an alpha-beta searcher with a static evaluation function, some forward pruning method, iterative deeping and a tsume shogi solver to look ahead for mating; tsume shogi ia a shogi problem position where the king has to be mated by giving check with each move. The idea is to mate before the opponent has a chance to counterattack, since check is a forcing move. The rule differences between chess and shogi lead to differences in various aspects of game programming:

1. Chess is a converging game, while Shogi id diverging (in the endgame the number of possible moves increases). This is mainly caused by the possibility of drops. However, since chess is slowly converging, the use of endgame databases is non so important as it is for example for mankala games and go-moku. In shogi, no endgame database is of any use, even though a special Tsume Shogi solver is part of almost every shogi computer program.
2. There is a considerable difference in game tree complexity due to the dropping possibility, the extra promotion possibilities and the virtual impossibility of draws. Shogi has an average branching factor of about 80. In chess this is estimated at 35.
3. On Average, a gmae of shogi takes about 115 ply. The maximum game length (in actual games) is more than 500 ply. In chess, the average is about 80 ply, while the record game length is currently 382 ply.
4. Many pieces in shogi have limited movement. This lead to a slow build-up and influences the average game length. It also influences the opening database that is so important in chess. There is a large number of books written on opening theory in shogi, but in general only patterns instead of strict move orders are being discussed. Also, new and interesting opening patterns are being developed until this day. Therefore, building a good opening dtabase is more difficult in shogi

Tsume shogi

One of the most successful results in Computer Shogi is mating search for checkmate problems called Tsume Shogi in Japanese. Tsume Shogi is a kind of puzzles for which the goal is mating the defender’s King by successive checks. There are some problems that are solved over 100 plies of moves because both players can drop captured pieces in Shogi. It is hard to solve such problems by searching with typical depth-first algorithms. Therefore, best-first search algorithms are used to solve those problems. After the depthfirst algorithms that behave like as best-first algorithms were invented, the famous problem entitled “Microcosmos” with the longest solution sequence of 1525 plies were solved in 1997. Nowadays, these algorithms are used not only in computer Shogi but also in other domains and obtain good results. In the field of Tsume Shogi, a computer has the ability for solving problems much better than the human champion. The playing strength of top computer Shogi is regarded as amateur 5th dan on the whole. On the other hand, there are lots of problems to improve in computer Shogi. Especially, the playing strength in the opening game is regarded only as 1st kyu. This weakness of opening play often causes some mistakes in the opening game, and it is hard to compensate such mistakes in the endgame. Therefore, the improvement of opening play becomes one of the biggest assignments for computer Shogi.

Realization-probability search

Realization-probability search was proposed by Tsuruoka et al. and used in their computer Shogi Gekisashi. Gekisashi is one of the strongest computer Shogi programs and won the 12th CSA World Computer Shogi Championship. After their first winning, the realization-probability search has been paid much attention and used in some other Shogi programs including Tacos.

Here a short sketch of the algorithm.

• Classifying moves into some categories. For example, moves are categorized into check moves, profitable capturing moves, attacking two pieces at the same times, and so on.
• From many master games, compute the statistics of the following two frequencies in each position. The one is the number of how many times masters play the moves classified in each category. Another one is the number of how many times the moves classified in a category exist as a legal move. In case where there are some such moves classified in the same category, it is counted as only one.
• Calculating transition probability for each category as follows: Tp =Np/Ne ; where
  • Tp: Transition (move-category) probability.
  • Np: The number of times moves of a category are played.
  • Ne: The number of times moves of a category exist as legal moves.
• In every node visited during a search, realization probability of each node is calculated as follows: RP(n+1) = RP(n) * Tp ; where
  • RPn: realization probability of a node in the depth n.The realization probability of the root node of a game tree is 1:0 because that position is already realized.
• Search stops when realization probability of a node becomes lower than a threshold probability.

This algorithm can be applied with less expensive costs to any game program that uses the minmax-based search. A computer simply needs to decide whether or not it continues searching based not on the depth but on the realization probability in a position considered. With this algorithm, search extensions and selective search are systematically carried out with some good results. It is also possible to incorporate domain knowledge into this search framework.

[from Wikipedia.org; "Towards master-level play of Shogi" by Jun Nagashima; "A gamut of games" by Jonathan Schaeffer; "Chess, Shogi, Go, natural developments in game research" by Hitoshi Matsubara, Hiroyuki Iida, Reijer Grimbergen]

top

Home | About Mizar | Theory | Papers | Columns | CChesspedia | Download | Source Code | Links | Site Map

Copyright (c) 2007,2008 by Nicola Rizzuti - All rights reserved - e-m@il