Tree Analysis Techniques in Tsumego

1. INTRODUCTION

We use a tree searching technique of perform­ ing a great deal of .analysis per node in order to choose superior lines for subsequent play. This idea is thought to be especially valuable for the chosen problem area, tsumego problems. Tsumego problems are restricted­ size situations in Go that determine a local, tactical result. The most interesting feature for game-playing is the peculiar shape of the game trees. The number of level 1 branches of the tree is approximately equal to the depth, and the branching factor declines fairly regularly with the search depth (n at level 1, n-1 at level 2, etc. where n is the ini­ tial number of possible plays). This implies that high-level pruning is especially effec­ tive. Doing considerable analysis per node, as shown by exercising the program on a prob­ lem set, provides enough information quickly enough to make good decisions on choosing the line of play.

2. THE GAME

2.1 Go.

The strategy and rules of Go have been con­ cisely and a.ccurately described by Iwamoto [4). Some aspects of programming the game have been treated by Benson (1) (2], Reitman & Wilcox (5) (6], Ryder [ 7], Thorp & Walden [9] (10], Zobrist (11], and others but the fundamental strategic and tactical heuristics used in human-quality play are still essen­ tially undiscovered.

2.2 Tsumego.

The main threat used in deterring intrusions into one's rightful territory is the threat to capture the invading stones. It is thus frequently necessary to evaluate small sec­ tions of the board to determine whether a group of stones will be safe from capture. This can be accomplished by connecting to another safe group or by gaining 'life' on one's own merit. Since the connection-to-a­ nother-group problem usually depends on glo­ bal game information concerning threats, book problems usually deal with local, tactically­ oriented life-or-death situations. These problems generally resolve themselves into two subclasses: first, a 'race-to- capture' where it is necessary to capture the oppo­ nent's stones before he succeeds in capturing your own stones. Second, sequences of play that attempt to form the two protected empty intersections (eyes) necessary to be safe from attack. Strategic concerns normally depend on the outcome of the tsumego battle but do not greatly influence its tactics. Thus we have an important but independent segment of the game which can be treated separately.

3. THE PROGRAM

3.1 The program's purpose

The tsumego program is designed to be one of several service routines callable by a dri­ ver. The functions of each of these subpro­ grams (tsumego, semeai, fuseki, chuban, yose) will be closely defined and specific. The driver program has the responsibility of developing and maintaining a coherent strategy for the various phases of the game (opening, midgame, endgame) and of calling the service routines, as necessary, for answers to the queries which it develops. For the tsumego routine, input consists of the board configuration containing the groups in question, a set of control information (who plays first, limits on computation resources, etc.) and a list of desired results i.e., the specified group shall live, die, connect out, or live in seki. Life-in-ko is not consid­ ered to be a distinct end-point condition. Output consists of a binary result (YES implies that a desired result can be achievea or NO, it cannot) and, if YES, the answer includes a forcing play-tree leading to the result. Other statistics are gathered to allow us to quantitatively measure the suita­ bility of heuristics for different classes of problems.

3.2 The program's method

The heart of the tsumego program is a heuristic algorithm which generates only the 'good' plays. These plays of course are the heuris­ tic's ideas of good plays and human players often take a different view.

Since constructing a 'live' group requires the formation of two simultaneously existing eyes that are both adjacent to the specified group, the program calculates all points which might become an eye. That is, it looks for unoccupied points that have all four of the adjacent points vacant or occupied by friendly stones and at least 3 of the 4 "shoulder" points vacant or occupied by friendly stones. The program then constructs a list of all pairs of these points which might form a pair of connected eyes. Note that if two possible eye points are adjacent then both points cannot simultaneously be eyes and thus would be excluded from the list of pairs of possible eyes. Construction of the list is basically derived from a transi­ tive closure algorithm with additional code meant to discard the inviable pairs. For all pairs which make the list, the program then calculates the plays necessary to complete and connect the two eyes. After a slight, artificial increase in the frequency counts of certain threatening and capturing plays, the program orders the resulting list by the frequency of occurrence of the potential plays. The list thus represents an ordered set of plays that may produce a live group. The plays at the front of the list and there­ fore those that are considered first by the recursive game player are those which appear more frequently in board configurations fea­ turing live groups. The list is constructed at each level in the game tree since the board configuration changes at each level as new plays are made.

If the program is on 'defense', its play gen­ eration task is done. If it is on 'offense', we rely on the well-knoWn Go heuristic: 'my opponent's best play is often my own best play.' This tactic leads to occasional wildly aggressive offense and often to a rather pas­ sive defense (typical beginner habits) but it is remarkably effective for several types of tsumego problems. It is remarkably ineffec­ tive for several other types.

Another module recognizes 'unconditional life' as proposed by Henson [1]. Uncondi­ tional life is a condition where an attacker is allowed an unlimited number of consecutive plays and is still unable to destroy the unconditionally alive group(s). This concept has been extended to also recognize 'unconditional death' where the defender is allowed an unlimited number of plays but is never able to produce a live group. The seki condition is also treated but this is not a static condition in the sense of the previous two ending conditions since a seki group might be sacrificed in return for a threat elsewhere. .Additionally, the seki condition (a sort of half-life, half-death) occurs much less frequently than the other two, uncondi­ tional, ending conditions.

4. TESTING AND RESULTS

The tsumego problems used in testing our pro­ gram were taken randomly from a collection ot such problems by Davies [3]. The reasons for choosing this set of problems was simple: they come fro~ published material and repre­ sent problems that humans solve. They were not composed especially for computer solu­ tion; their difficulty is easily rated; and we thought them to be within the capability of a specialized heuristic. Tne problems were modified slightly to restrict their size for economic reasons but we were careful to main­ tain all possibilities of attack, defense and counter-attack. As soon as the next module, a semeai-player, is incorporated into the program, these modifications can be removed since the program will be self-limiting.

The following two figures simple way the type of Go treating and the program's tree. illustrate in a problem we are resulting search

In Figure 2, note the decrease in branching factor as depth increases in the tree search for the sample problem. This could be expected since stones do not move, captures are infrequent and so each play reduces the number of possible continuations. If the pruning is heavy enough and early enough we are able to dispense with immense amounts of lookahead because of the top-heavy nature of the fW.l results tested. aaua tree. T~~le 1 for the c.cuplete set gives taoul-.r of problems

TABLE 1

Notes:

0: heuristic failed... ~ave wrong binary result. We are counting this as a wron~ answer. Both wrong answers were the result of a bug in the seki reco~nition routine.

1: program returned a message saying the problem was unsuitable for the eye-stealing heuristic. Ye are not counting this result as a wrong answer since another local expert routine will presumably eventually be availa­ ble to take over.

• 2: vro~ram was makin~ progress but exceeded allotted resources. This indicates that the

REH;RENCES

• [1) Benson,D., 'Life in the Game of Go', Information Sciences, 10:1 (1976) 17-29.

[2) Benson,U.; Evers,P.; Miller,J.; Tackett,M.; Starkey,D.; 'Computerizing the Game of Go',

In Proc. Northwest 76: ACH Pacific Regional Symposium, ACH, New York, 1976.

[3] Davies, J. Life and Death, Tokyo: Isni Press, 1975.

[4] Iwamoto, K. Go for Beginners, Tokyo: Ishi Press, 1973.

[5] Reitman, W.; Wilcox, B.; Nado, R., 'Goals and Plans in a Pro~ram for Playing Go.' In

Proc. of the ACH Annual Conf., ACH, New York, 1974, pps 123-127.

[6] Reitman, w.; Wilcox, B. 'Perception and Revresentation of Spatial Relations in a Program for Playing Go.' In Proc. of the ACH Annual Conf. ACH, New York, 1975, pps 37-41.

[7) Ryder,J. 'Heuristic Analysis of Large Trees as ·Generated in the Game of Go.' PhD thesis, Comvuter Science Dept., Stanford University, 1971.

• [8) Slate, D.; Atkin, L. 'Chess 4.5: The Northwestern University Chess Program.' In Chess Skill in Man and Machine, P.Frey,ed., Springer-Verlag, New York, 1977.

[9) Thorp, E.; Walden, w. 'A Computer Assisted Study of Go on ~~N Boards', Information Sci­ ences, 4:1 (1972), 1-33.

[10) Thorp, E.; Walden, W. 'A Partial Analysis of Go', Computer Journal, 7:3 (1964), vps 203-207.

[11) Zobrist, A. 'A Model of Visual Organisation for the Game of Go', PhD thesis, Computer Science Dept., University of Wisconsin, 1973.

single heuristic is not suitable for this class of problem. . Additional local-expert subroutines will have to be included to extend the range of the program's capabili­ ties.

5. CONCLUSIONS

Bushy, top-heavy game trees where the number of future plays is inversely proportional to the tree depth suggest the need ·for heavy, early pruning. The strategy of performing a full-width search to a pre-set depth (Slate & Atkin [8)) would in fact search a considera­ ble portion of the game tree. In addition, the complexity and diversity of patterns in Go make the dcv~~upment of effective evalua­ tion functions difficult. Chess-type strate­ gies which rely on a slow build-up of infor­ mation are inappropriate for tsumego.

As an alternative, we provide enough heuris­ tic analysis at hi~h tree levels to provide information necessary for effective play ord­ ering and then let a branch-and-bound techni­ que severely prune the tree. This procedure has worked well for our tsumego program (9 correct vs. 2 incorrect). There is consider­ able vruning as evidenced by realized branch­ ing factors (<2 at upper levels) in the tested problems.

To date the program includes an eye-form­ ing/eye-stealing heuristic as the play gener­ ator. The heuristic is effective for solving tsumego problems of the type found in the first five chapters of Davies [3). The pro­ gram is handicapped when solving other classes of problems, particularly problems involving race-to-capture (semeai) and play­ under-the-stones (ishi-no-shida). Its profi­ ciency for tsumego problems might generously be rated as the same as a human player in the 20-25 kyu range. Any increased capability of the pro~ram will be measured objectively by attempts to solve published problems.