flinn@seismo.UUCP (E. A. Flinn) (12/29/83)
I propose to post articles on computer Go as I run across them in the American Go Journal. Here is the first installment. Ryder's Program - An Introduction by Bruce Wilcox (copyright 1979) (the first part of one of a series of articles on computer Go, begun in AGJ vol. 13; this one is from vol. 14, no. 1, pp. 23-28.) In the last issue I discussed the Go program written by Albert Zobrist; it was the first complete program to be published. The next contribution to the development of computer Go was made by Jon Ryder; his Ph.D. thesis at Stanford, "Heuristic Analysis of Large Trees as Generated in the Game of Go," written in 1971. Ryder continued the spirit underlying Zobrist's program (choosing a move by summed feature evaluation as discussed below) in a vastly different implementation. He expanded the uses of influence, created notions of attack and defense of weak groups, and added a reasonable tactician. Ryder's program has recently taken on new value. The invention of home computers has made it a prototype for small Go programs. Therefore I will try to give you a thorough understanding of it. First I will discuss the overall "flow" of the program (in Go terms). Then I will dip into the basic entities being used in this process and how they are computed. Finally I will surface for an overview of the results of his work. How the Program Selected Its Move After the opponent's move was read in, the first thing the program did was update all of the basic data. This included determining which strings could be captured, which groups were weak and who controlled which areas of the board. Then a two-part feature evaluation was used to select the program's respnse. The first part, called DEVELOPMENTAL ANALYSIS, checked each legal move for the presence of simple features. Whenever a feature was detected, a number was added to the cumulative value of that move. The second part then checked for more complex features using only the 15 best-scoring moves from the first part. The new feature values were added to a move's preliminary total, and finally the highest scoring move was chosen. Ryder's and Zobrist's programs both chose the move with the highest summed feature value, but there were three crucial differences: (1). Zobrist's fatures emphasized expanding and securing influence. lacking adequate safety considerations, his program collapsed against strong players. Ryder's program emphasized attacking and defending weak groups. It would not have collapsed gainst strong players, but it was completely outplayed by a human beginner in the endgame, where attack and defense were no longer a dominant theme. (This could be corrected by changing the fature values during different stages of the game.) (2). Zobrist's program could check for facts CURRENTLY available in the BASIC DATA only. Ryder's program also tested for thigns not in the basic data, such as determining FUTURE effects of a move. Determining future effects gives feature recognition much more power. Not only could the program ask what the current influence was, for example, it could also ask what it would be if a move were played. (3). All of Zobrist's features were examined for every legal move. In Ryder's program, moves weeded out during the first phase could not be examined in the second. This gained efficiency, while introducing a risk of discarding the best move before all the facts were in. The FIRST PASS - Ryder's first part checked only 18 distinct features, but they were tested from both players' points of view and had values depending upon which side(s) had the feature. In addition, up to 3 values were added to the move's value when a feature was detected, depending upon the presence of weak groups. The normal vlaue was always added, but if the move was near an endangered enemy group, then a second value was also added, and if the move was near an endangered program group then still another value was added. To hel in understanding "developmental analysis," I have listed the features used from the program's viewpoint and their normal values. These features are only crudely approximated in Ryder's implementation. Interchanging the terms "program" and "enemy" in the features below will supply the enemy features (but you won't know their values). Remember that a move is checked from both points of view (implementing the Go proverb that 'the opponent's key play is my own'). 1. (10000) splits or hinders connection of enemy groups. 2. (8000) saves program stones. 3. (3000) makes program eye. 4. (2000) ataris enemy string. 5. (1500) makes program territory. 6. (1500) combines program groups. 7. (1500) threatens to make program eye. 8. (1000) reduces enemy string to two dame. 9. (1000) securely connected to program group. 10. (750) hinders expansion of enemy group. 11. (500) near endangered program group. 12. (250) expands program group(s). 13. (-300) within enemy influence. 14. (-1250) leaves behind a cutting point in program position. 15. (-1500) on enemy group point or next to enemy stone. 16. (-1800) reduces own program string to 2 dame. 17. (-2000) within enemy territory. 18. (-12000) could be killed if played by program. For a quick example of how the feature values changed near weak groups, consider feature #3, "makes program eye." Its normal value of 3000 near a weak program group would add 10000 more, which translates as "make eyes fast!" The normal value of the feature "makes enemy eye" (flipping viewpoints) is -2500. Thus the program has no reason to stop enemy eye formation. Such a move would be avoided unless it were near an enemy weak group, in which case a value of 7500 would also be added. The program would then leap to the attack. THE SECOND PASS - The 15 highest-scoring moves from developmental analysis were then run through more thorough tactical and strategic analysis. The tactical analysis determined if the proposed move "unexpectedly" altered the tactical safety status of any string. Various bonuses were given, depending upon how many of whose stones changed status in what way. Strategic analysis determined changes in the composition, number, and overall influence of armies, walls, and groups, and gave bonuses accoridngly. These evaluations were added to the developmental score to obtain the final value. The highest-valued move was the program's response. COMMENTS - The task as Ryder saw it was "to develop a function which on the whole (and in the absence of many of the complications of actual positions) produces good scores for moves a Go player might recommend." The utility o f his kind of move selection process lies in the ease of its implementation and the ready insertion of new features. The process creates a good "orge" to make a useful, multi-purpose move each turn. The weakness of the process is exactly that it does not easily handle the complications of actual positions. It does not provide the precision used by skilled players in selecting moves, nor does it allow long-range planning and execution. Basic Data Now that you know vaguely how Ryder's program chose its move, you may want to understand just what basic Go structures it used and what their limitations were. If you don't, skip down to the RESULTS section. As I mentioned in the last installment, strong players "see" many more things on a board than do weak players. ryder created a more sophisticated representation than Zobrist. Below are the entities Ryder programmed. (1) STRINGS. Strings have liberties, adjacent enemy strings, etc. Strings were basically the same as used by Zobrist. Being such a basic Go phenomenon, all programs have them. (2) INFLUENCE. Ryder's implementation + + + + + + + + of influence was faster and easier to + + + 1 + + + + understand than Zobrist's. Each stone + 1 2 5 2 1 + + played added fixed amounts of influence to + 1 6 13 6 1 + + nearby locations. Diagram 1 shows the 1 5 13 60 13 5 1 + influence exerted by a single isolated + 1 6 13 6 1 + + stone played at 60 upon nearby points. + 1 2 5 2 1 + + The total influence of a point is the sum + + + 1 + + + + of all stones' influences on that point. + + + + + + + + Once again, Black added positive numbers; White added negatives ones. Diagram 1 (3) ARMIES. These were areas of contiguous influence of the same sign (the same as Zobrist's segments). (4) WALLS. Not content with the information available from armies, Ryder attempted to reflect the Go concept of walls. Areas of strong influence (contiguous points with an absolute influence value of 10 or more) were recognized separately. Walls were not used as a focus for planning, as a human would use them. they were merely entities to be counted for strategic bonuses. (5) CONNECTED. Ryder created two independent concepts, "connected" and "stongly related," to handle the connection and barrier effects of linkages. Discovering that influece did not do a good job describing the connectivity of stones, Ryder created "connectedness" to recognize stones that would be considered joined (even though it might be possible for the opponent to break the connection). A point was "connected" to Black if it was occupied by a non-dead Black stone or was empty and adjacent to it was at least one Black stone and not adjacent to any White stones. A point was "half-connected" to Black if it was empty, adjacent to at least 2 Black stones, and adjacent to at least one White stone. Similar tests were used for White "connectedness." Half-connected points loosely reflected threatened connections. "Connectedness" did not recognize the large knight's move (ogeima), nor a threatened double skip (niken-tobi). (6) STRONGLY RELATED. This concept covered the "barrier" effects of a linkage, and was used to recognize territory boundaries. A point was "strongly related" b`to Blackif it was occupied by or adjacent to a Black stone, or was diagonal from a Black stone with an empty point between (kosumi), or was a single skip away from a Black stone with an empty point between (ikken-tobi). Points could be "strongly related" to both sides simultaneously. (7) GROUPS. A group was a set of ontiguous "connected" or "half-connected" points of one color. (A single isolated stone created a five-point group.) Each group had a security value, summed from rewards for the number of: actual and potential eyes, points in the group, territory points, connecting moves to other groups, and extensions. Security values above a fixed number meant that the group was safe; below a fixed value meant that the group should be abandoned. In neither case would moves be rewarded for attacking or defending the group. (8) TERRITORY. Territory was the set of empty points contianed by edge points and points "strongly related" for one side, but not "strongly related" for the other side. Not wanting the program to depend upon weakly held territory, it was further required that 4/7 of the points in a territory be "strongly related" ones (else the territory was ignored). The definition of "strongly related" recognized linkage-enclosed area (including niken and ogeima relations), but it had a flaw. The program would perceive double-diagonal jumps (hazama-tobi), triple skips (sangen-tobi) and other weak formations as sealed boundaries, whereas skilled players think of them as gaping holes. (9) TACTICS. Tactical results were important features. Each string was examined by the tactician to see if the string could be captured or saved. No connection or eye searches were performed. Much of Ryder's total effort was spent on improved string tactics. As Ryder said, "Since tactics are so difficult to do well, perhaps it is better to call the program's present degree of tactical proficiency 'blunder avoidance.'" Results ryder's program represents a second stage of Go programming: he developed much more Go-specific information. While he claimed in his thesis that his program played well enough to beat human beginners, I regret that the only game presented was lost to someone who had just learned the rules and had been told some general strategy. This is not the result to expect of a program superior to Zobrist's. What happened is something that occurs with any large and complex program. It suffered from both errors and oversights in the program. Ryder later improved his program, but no other games were reported. (to be continued)