Knowledge Representation in The Many Faces of Go David Fotland 4863 Capistrano Ave San Jose Ca 95129 fotland@hpihoc.cup.hp.com February 27, 1993 Abstract: This paper describes the representations of Go knowledge in The Many Faces of GO, a strong computer Go program. Knowledge is encoded in the algorithms that recognize low level features, in the data structures that describe the current position, and in patterns that are used to suggest plausible moves. 1. Introduction The Many Faces of Go is one of the strongest Go programs commercially available. It won the United States Computer Go competitions in 1988, 1991, and 1992, and is ranked 13 kyu in the USA. It is based on traditional AI techniques, such as alpha-beta search, rule based expert systems, and pattern matching. The go playing algorithm is about 30K lines of 'C', plus a pattern database and a joseki database, and was written by one person, part time, over a 10 year period. As a commercial program, it has about another 20K lines of code in user interfaces for the IBM-PC, X windows, and PenPoint. Go is a much more difficult AI problem than Chess, and must be attacked with a knowledge intensive approach rather than brute force search. 2. Go is harder than Chess There are several reasons why Go is a more difficult problem than Chess. Strong chess programs depend on full width search 7 or more moves deep. This is not possible in Go since a Go position is much more difficult to evaluate than a chess position. An accurate evaluation of a Go position must do life and death analysis and assign a value for relative thickness and territory. Just Determining the location of secure territory is a difficult problem. A chess evaluation is dominated by the values of the pieces remaining on the board, which is easy to get right. If a go program misreads a life and death fight there would be a large error in the evaluation score. This leads to an evaluation function for a go program that is orders of magnitude slower than the chess evaluation function. Where a PC chess program can examine 100,000 positions each move, Many Faces examines less than 100 positions before deciding on a move. Second, Go has many more legal plays than Chess at each move. Even if the evaluation functions were the same speed, the go program could not look as many moves ahead. Third, people read deeper in Go than in Chess. A strong chess player might read 10 moves ahead, but a strong Go player routinely reads much deeper. This is because the board does not change as much after a move in go as it does in chess, so it is easier for a person to visualize the board many moves ahead. Even a beginner can read 60 moves deep in a ladder that crosses the board. 3. Knowledge in The Many Faces of Go Go knowledge is incorporated into Many Faces of Go in 5 major areas. First, there is low level go knowledge built into the evaluation, and hard coded in 'C' 'if' statements. This is knowledge used to determine connectivity, eyes, potential eyes, and territory, as well as the move generators and move sorters used by the tactician. The general philosophy here is to classify first, then analyze. This makes the code easier to debug. Second, there is the dynamic knowledge stored about the state of the current position. This data is stored in a global database, and is built up in successive passes, from low levels to high levels of abstraction. Third, there is a rule based expert system with about 200 rules that suggests plausible moves for full board evaluation. I try to only suggest reasonable moves for evaluation, to reduce the likelihood that errors in the evaluation function will cause the program to play terrible moves. Fourth, there is a Joseki database of standard corner patterns, currently consisting of over 36,000 moves, including all moves from most of the joseki books published by Ishi Press. Fifth, there is a pattern database of 8x8 patterns, each with a move tree attached, currently with over 700 patterns and over 4,000 moves. 4. Program Components The dynamic data stored about a position falls into 3 levels. First is incremental data, used for low level local data, such as point_empty_neighbors, or string_liberties. These data structures are modified incrementally and adjusted as each stone is added to or removed from the board. Second, there is data that is recalculated as needed. After a move or sequence of moves, the area of the board affected by the move(s) is recalculated, and areas that are not effected maintain their old values. This is used for connection strength, eyes, and string tactics. Third, there is data that is recalculated for the entire board after a move or sequence of moves. These include group strength and radiated influence. The dynamic data consists of: Point environment which string is this point part of (or None) lists of adjacent Black and White strings list of adjacent empty points number of adjacent Black, White, and empty points list of connections which eye is this point part of White and Black influence ... String data color list of points (stones) in string number of liberties list of liberty points of string list of adjacent enemy strings tactical status (captured, threatened, OK) list of connections which group is this string part of ... Connection data two strings lists of points in connection number of connections type of connection strength of connection Eye data list of points in eye list of vital points type of eye number of eyes Group data list of strings in group list of eyes in group number of eyes in group group strength list of potential eyes lists of running points list of adjacent enemy groups Territory Score Incremental data structures are modified as moves are made and taken back. Other data structures are maintained by the evaluation function. EVALUATION FUNCTION I have described the evaluation function elsewhere. Its major components are the tactical analyzer, which reads a single string with the twin goals of removing it from the board, or making 5 liberties or two eyes; the connection evaluator; the eye evaluator; the group strength evaluator; and the territory evaluator. It assigns a score to the position, using Chinese style counting, where each point on the board can have a value between +1 and -1, depending on how strongly it is controlled by white or black. Evaluation is a multiple pass process. STRATEGY Before each move, a strategy function looks at the dynamic data and attempts to focus attention on the important areas of the board. It decides what phase the game is in. Fuseki lasts as long as there are corners that still contain unplayed joseki moves. The game is in Endgame if more that 120 moves have been played and all groups are stable. Otherwise the game is in the Middle Game. It is possible for the phase of the game to go back and forth from endgame to middle game. The phase of the game is used as a qualifier for some of the move generation moves. For example the fill_dame rule will not fire unless the phase is the endgame. Strategy determines the relative score, and classifies it as "way ahead" (over 40 points), "ahead" (20-40 points), "about even", "behind" (over 10 points), and "way behind (over 20 points)". This is also used to qualify move generation rules. For example if the program is way ahead, it will play extra moves to be certain of big captures. If it is way behind it will try unsound invasions. The strategy function determines the value of taking sente. This declines from 7 points at the start of the game to 1 point at move 220 and above. At the end of a full board lookahead and quiescence search, this value is added to the side with sente, since presumably it can get that many points with a big move somewhere. Seven points is used at the start of the game since internally the program uses Chinese style counting, which increases the value of a move by one point relative to Japanese counting, and the value of the first move is known to be about 5 1/2 points with Japanese counting. It also finds friendly groups that urgently need defending. These are cutting groups and big groups. It finds enemy groups that urgently need capturing. These are big groups, cutting groups, and groups adjacent to groups that urgently need defending. Attack and defense of groups marked urgent, and moves marked urgent by the pattern matcher, are examined first, and if a reasonable urgent move is discovered, no other moves are considered. FULL BOARD LOOKAHEAD Sequences for full board lookahead are provided directly from the Joseki and Pattern databases. Joseki variations are laid out on the board and evaluated at the endpoints. This allows the program to pick joseki that it understands and that work well with adjacent corners. Patterns also suggest move sequences that are evaluated at the endpoints. Move generators examine the group types, eye potentials, and running points to generate move sequences to kill or save groups, fight semeai, and run out to the center. A rule based system generates other reasonable moves, such as extensions, moyo expansion, etc. QUIESCENCE SEARCH Since the evaluation function ultimately reduces the position to a single number, the score in 50ths of points, it is only accurate in a quiet position. It generates moves to save unsettled friendly groups or kill unfriendly enemy groups, and calls itself recursively until it finds a quiet position. For contact fights, a special set of "obvious local answer" patterns suggests moves that quiet the position. 5. Dynamic Data CONNECTIONS Each connection structure records all connectivity between a pair of strings. A connection point is a liberty of one string that sees a stone of another string along a straight line, either 1, 2, or 3 points away. This suffices to discover hane, one point jump, knight moves, 2 point jumps, large knight moves, and 3 points jumps. It does not see double kosumi or watari played on the 1st line from two stones on the second line. These are handled by special case patterns. A low level incremental data structure that records the distance to the nearest stone in each direction at each point makes it easy to incrementally maintain the basic connections. The structure looks like: string s1, s2; // two string numbers int num_d1; // number of distance one connections int num_d2; // number of distance 2 connections int num_d3; // number of distance 3 connections list_t d1points; // list of distance one connection points list_t d2points; // list of distance 2 connection points list_t d3points; // list of distance 3 connections int type; // type of connection: // hane // one point jump // half knight's move // knight's move // two point jump // half large knight's move // large knight's move // 3 point jump // multiple int strength; // strength of the connection // Already cut // Cuttable // Shared connection // Connected with aji // Connected solidly Type and strength are recalculated as needed. The others are incremental. Each point maintains a list of connection structures that it appears in, and each string maintains a list of connection structures that it appears in. The connection analysis code (representing low level go knowledge coded directly in 'C') is about 1500 lines. EYES Each eye structure records information about a single block of empty points completely or partially surrounded by stones of the same color, or a tactically captured string. list_t points; // empty points in the eye list_t vital; // vital points for the eye, destroy it or finish it int type; // type of the eye // single point // two point // line eye (closed, open one end, open both ends) // big eye // dead group eye int color; // color of the eye int min_eyes; // number of eyes if opponent moves twice int typ_eyes; // number of eyes if opponent moves first int max_eyes; // number of eyes if I move first The number of eyes is stored using the value 8 for one eye, 4 for 1/2 eye, etc. Each point can be part of only one eye, and which eye is recorded with the other data about a point. All parts of the eye structure are recalculated as needed. Eye analysis is about 2400 lines of 'C'. There are a lot more patterns to recognize for eyes than for connections, and nothing is incremental, so if I had to do it over again I would make it pattern based rather than coded in 'C'. POTENTIAL EYES Each group has a list of potential eye structures, and lists of running points. These are used to evaluate group strength and to generate attacking/defending moves. A potential eye contains a value, location, and type. Types are: Extend along the edge value is number of new points of eye space location is liberty to extend from Play vital point to make an eye value is number of new eyes location is vital point Connect to another group value is number of eyes location is connection number Capture tactically threatened string value is number of eyes location is string number Defend undercut territory on the edge value is number of new points for eye space location is liberty being undercut Running points are recorded in several lists, by type, depending on whether running this direction is toward friendly or enemy stones, etc. Potential eyes and running points are reevaluated on the whole board at each evaluation, consuming about 7% of the program's time. INFLUENCE FUNCTION An influence function is used that radiates from each stone with an initial value that is dependent on the group strength, and falls off as one over the distance. Radiated values are summed independently at each point for black and white. Influence does not radiate through a stone or a connection. The influence is used to calculate territory and thickness, find the best gradient for running moves, and help generate moyo building or reducing/invading moves. Influence is not used to determine group connectivity. A function that falls off as 1/distance will create a constant field inside any fully enclosed area, no matter how big it is, which is desirable for estimating territory. Dead stones radiate negative influence. 6. Rule Based System For Move Suggestion The move suggestion experts are: Fuseki Playing in empty corner Shimari and kakari Joseki moves Big moves on edge Towards enemy Invasions Between friendly stones Playing in the center (reducing moves and junction lines) Playing safe when ahead Respond when enemy adds stone to dead group Add extra stone to kill big group that is probably dead Squirming around when behind Make a bogus invasion Try to make a hopeless group live Pattern matching patterns for cutting and connecting patterns for surrounding and avoiding getting surrounded patterns for invasion and defending against invasion endgame patterns killing/saving groups patterns Shape moves Saving a weak group making eyes running fighting semeais Save threatened string Capture threatened string Killing a weak group surrounding taking eyes Cutting and connecting Contact fights Blocking extending for liberties hane Ko threats make a big atari Filling dame The move suggestion code is easily extensible by adding more patterns or firing rules based on other criteria. The program has text associated with each rule so it can "explain" its reasons for making moves. This makes it easier to debug. 7. Joseki Database The Joseki database is stored as a directed acyclic graph of moves, with the root representing an empty corner. Transpositions are built into the database manually as data is entered. An uncompressed representation is maintained in an ASCII file. Each uncompressed node contains: X and Y relative to corner (1-16 each) Sibling pointer First child pointer Type: Urgent, normal, complex, trick, bad, ignore, ... flags: color, symmetric, color reverse Urgent moves take priority over any other Complex and trick moves are avoided by the computer unless it is behind. Bad moves are never played by the computer, but are in the database so it can respond correctly if an opponent plays them. Ignore is used to delete an erroneous entry in the database. Color indicates whether the current move is the same color or opposite color as the first move in the corner. Symmetric indicates that this move makes the corner symmetric again. Color reverse is needed for some transpositions, for example certain 3-4 joseki are 5-3 joseki transposed with colors reversed. A compressed representation is used directly by the program. (x,y) are reduced to 6 bits via a lookup table. Values 0-62 index the lookup table of the 62 most common x,y pairs. Value 63 escapes to the next byte which contains the full x,y pair. Sibling and child pointers are replaced by two bits, has_sibling, and has_child. Data is stored in depth first order, except where lines converge due to a transposition, when a full 2 byte pointer is stored. Most entries are 1 byte long. The longest possible entry is 5 bytes. Across the entire database, the average move is stored in 1.2 bytes. 8. Pattern Database There is a pattern matcher with over 500 patterns in it. Each pattern is 8x8, where each point is specified as black, white, empty, don't care, white or empty, black or empty, or black or white. Each pattern has a set of attributes with it that must also match. For example, "the stone at (4,2) must be alive", or "the stone at (2,5) must have at least 2 liberties". Each pattern has a move tree attached that is used for full board lookahead. Patterns are also used for reading obvious local sequences based on shape. Internally a pattern is stored as three 8 byte arrays, one for black points, one for white, and one for empty. For example a black point in the pattern is indicated by setting the appropriate bit in the black array. Black or Empty is indicated by setting bits in both the black and empty arrays. Don't care is indicated by setting corresponding bits in all 3 arrays. Each pattern needs to be matched at each point on the board, in 8 orientations, and with colors reversed. Rather than rotate the patterns, I rotate the board before comparing. Color reversal is handled by reversing the black and white arrays. Once I have 3 arrays extracted from the board for a particular position, the pattern match is simple. Just bitwise AND the corresponding Black, white, and empty arrays; bitwise OR the three results, and if the result is all ones, then there is a match. After I find a matching pattern I check that the attributes specified by the pattern match. I plan to have at least 1000 patterns, so performance is an issue. 1000 patterns compared at 361 locations at 16 orientations is over 5 million comparisons. A full comparison requires 24 byte ANDS, 16 byte ORS, and 8 compares, or 48 primitive operations. That's almost 300 million operations to determine which patterns match at a single board position. I use an 8 bit hash function to reduce the number of patterns examined. Of course since there are don't cares in the patterns, a pattern may appear on more than one hash chain (current average is 3 chains). The hash reduces the number of patterns examined by about a factor of 20. I remember which patterns match from move to move and only rematch in the area near the last move. This reduces the number of points where patterns need to be matched from 361 to about 50. I do the bitwise operations 32 bits at a time, and most patterns miscompare on the first word, which reduces the number of logical operations about 6 on average. This reduces the number of operations to match all patterns down to about 350,000. This is still slow enough that I only match all the patterns once each time the computer has to make a move, to find sequences to read. A small subset of the patterns is used for obvious local lookahead during the quiescence search. The program currently spends about 1.5% of its time matching patterns. 9. Knowledge acquisition A graphical joseki editor allows me to enter about 400 new moves an hour, and compiles the database to the compressed binary form that the program uses. A graphical pattern editor allows easy modification of the patterns or move trees and can display 36 patterns at a time. The program can play through a professional game and compare its choices to the pro's. When it didn't even consider the pro's move, it cuts out the pattern from the pro's game and saves it. This turned out to be much less useful that I expected, since many of these moves involved difficult fights, where an 8x8 pattern was not big enough, or where the proper move was selected based on deep reading, not the local stone pattern. 10. Debugging Aids Many of the data structures are incremental. I can optionally include code that periodically recalculates the incremental data structures from scratch and verifies that they are correct. This code also walks all of the lists and finds any memory leaks. I'm confident that the program contains no bugs in incremental updates or memory leaks. Some data values are only recalculated as needed. Sometimes an eye or a tactical lookahead needs to be recalculated, and it doesn't get noticed. To detect bugs here I can include code that evaluates each position twice, before and after lookahead. A difference indicates that something wasn't reevaluated. There are many situations that can cause missed reevaluations. In test games they come up about once in 1000 moves. These are not critical bugs since they mimic similar oversights that people make, but I fix them as I find them. The debugging version of the program can dump all of the internal data structures in an easy to read form. When the program makes a bad move I can quickly determine the cause. I run two kinds of regression tests. First, I run about 100 self play games at different levels and handicaps with all the checking code included. Second, I have about 400 problems from Graded Go Problems For Beginners, and the program can automatically play thru them to produce a report of which problems got the wrong answers. I wrote an interface between Many Faces of Go and the Internet Go Server so Many Faces can play games there unattended. I collect some of these test games as samples that I can examine in detail to fix the problems that lead to bad moves. 11. Summary Playing the game of Go well is a difficult AI problem. Because of the large board and difficult evaluation, large searches are impractical, and a knowledge intensive approach is required. Many Faces encodes local, low level knowledge in C algorithms for speed, and higher level pattern knowledge in databases optimized for size.