博客

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 8×8 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

8×8, 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 8×8 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.