Title : A Solution of Go on 4x4 Board by Game Tree Search Program Authors : Shinichi Sei Toshiaki Kawashima Affiliation: Fujitsu Social Science Laboratory Ltd. Abstract We had made a search program to find a solution of Go on small boards (4x4 or smaller) based on Japanese Go rules. This paper describes the solutions and the method of our program. We found that the solution were a draw on the 4x4 board, victory for black on the 3x3 board, and a draw on the 2x2 board. 1. Introduction There are some games which perfect play has been found using a game tree search program, such as 6x6 Othello and Gomoku. However, there is no report finding perfect play in the game of Go. The main reason is that the search space of Go is very large. Another reason is that there are vague areas in the Japanese Go rules. There is a report that a professional Go player solved Go on small board by hand[Cho 1993]. According to the report, black wins on 3x3 board, draw on 4x4 board and black wins on 5x5 board (Komi is assumed to be 0). However, because not all candidate moves were examined, it cannot be asserted that the solution in the report is correct. So, we did the experiment to find perfect play for Go on a small board using a game tree search program. In this paper, we first explain the vague parts in Japanese Go rule. Then we describe how to formalize them for computer implementation. Finally, we describe the specification of our search programs and give the experimental results. 2. Problems with Go game rules There are various rule sets for the game of go: Japanese rules, Chinese rules, Ing rules, etc. However, because differences are small and the essence of the rules are the same (players take turns, player with the most territory wins, stones with no liberties are removed, etc.). In this paper we use Japanese rules. The Japanese rules were provided by Nihon Kiin and Kansai Kiin in 1989 [Nihonkiin 1989]. Naturally this is a rule set designed for humans, not computers, and there are some problems in trying to apply this ruleset to computer go [Nakamura 1996]. We explain these various problems, then describe how we adapted Japanese rules to computer go. 2.1. Judgment of life and death Life and death is described in Article 7 of the Japanese rules as follows. Article 7. Life and death 1. Stones are said to be "alive" if they cannot be captured by the opponent, or if capturing them would enable a new stone to be played that the opponent could not capture. Stones which are not alive are said to be "dead." 2. In the confirmation of life and death after the game stops in Article 9, recapturing in the same ko is prohibited. A player whose stone has been captured in a ko may, however, capture in that ko again after passing once for that particular ko capture. In human play considering, "Does this group have two eyes or not?" is the usual method to determine life and death. However it is complex and there are exceptions. For instance, a large eyeless group of black stones count as alive if, after they are captured by white, black can make a living group in the resulting open space. Thus, we adopted the following method: (1) Computer continues playing as long as there is a legal move. (2) Life and death is judged by examining whether the stone remained on the board at the end of the game. Because, the stone's remaining at the game end corresponds to stones "cannot be captured by the opponent" in Article 7 clause 1 of the rules. This method is suitable for the computer because, though it increases the number of moves until the game end, it is easy to judge life and death. 2.2 Definition of end The end is described in Article 9 of the Japanese rules as follows. Article 9. End of the game 1. When a player passes his move and his opponent passes in succession, the game stops. 2. After stopping, the game ends through confirmation and agreement by the two players about the life and death of stones and territory. This is called "the end of the game." 3. If a player requests resumption of a stopped game, his opponent must oblige and has the right to play first. "The play ends by agreement" in Article 9 clause 2 is impossible for current computers. Therefore, in the computer go championships, the game ends after both players pass, then both programs must display the territory and the life and death status of stones. If the two programs agree, the game ends. If the programs disagree, the program operators (the developers) judge territory and the life and death of stones. If they do not agree, the umpire decides. Because one program plays the role of both players when the search program solves the game of Go, "agreement" is unnecessary. Therefore, when both players pass, the game ends. However, if there is a ko after both players pass, the game must not end. 2.3 No result The "no result" is described in Article 12 of the Japanese rule as follows. Article 12. No result When the same whole-board position is repeated during a game, if the players agree, the game ends without result. The definition of whole-board position is not written in the Japanese rule. Does "whole-board position" means the arrangement of stones? Or does it include turn and Agehama (captured stones)? So, it is necessary to define "whole-board position" more precisely.. The phrase "if the players agree, the game ends" is there because it is difficult for human players to remember the arrangement of stones. Therefore, we can ignore this phrase. When the "whole-board position" repeats, the game ends without result. However to solve Go by the search program, it is necessary to give the comparable evaluation values to all nodes and so we must assign a comparable evaluation value to a "whole-board position is repeated" node. We re-arranged the rule about Article 12 of Japanese rule as follows. (1) "Whole-board position" means that following five items are all the same: arrangement of stones, player to move, position of Ko, whether the move immediately before is pass or not and the difference in number of prisoners. (2) When the same whole-board position is repeated during a game, the game ends and the score is a draw. 3. Outline of program This chapter describes the outline of the program which we made. We made programs to solve Go on 2x2 board, 3x3 board and 4x4 board. Each is slightly different for performance reasons. 3.1. Common specification (1) No komi. (2) The evaluation value is one of three values( win/defeat/draw ). This program does not examine the differences in points. (3) Program ends when a win for black is found. (4) Symmetric situations are considered to be the same. (5) If four things (the arrangement of stones, player to move, position of Ko, and whether the move immediately before is pass or not) are all the same as a previous position, the evaluation value of win/defeat/draw is given by the difference in number of prisoners. If number of captured stones is the same, the evaluation value is "draw" because all five items are the same (see definition of "whole-board position" above). If the difference in prisoners is smaller than an earlier, the evaluation value is "defeat". If Agehama is bigger, the evaluation value is "win". This is because the difference in prisoners will continue to grow as search depth increases. And, some time, even if all points on the board are opponent territory, it can be exceeded by the difference in number of prisoners. (6) Transposition table are used. When the transposition tables are compared with board situation, the superiority relation of the board situation is considered. For example, we assume that the four items described in (5) are the same. When "white's prisoner count is smaller than black's by 3 points" and "white win" is written in the transposition table, then if white's prisoners is smaller than black's stone by 4 points in the current board situation, white wins. 3.2. Specification of program for 2x2 board We made the depth first search program which used the minimax method. All candidate moves are ordered by following heuristics. (1) When all sides are enclosed with my stone, the candidate move's priority is low. (2) Capture moves are high priority. (3) If the opponent passes, our pass move is high priority. Otherwise pass move is low priority. 3.3. Specification of program for 3x3 board We made the depth first search program which used the minimax method. All candidate moves are ordered by following heuristics. (1) When all sides are enclosed with my stone, the candidate move's priority is low. In addition, the priority level is adjusted by four diagonal points' situation (my stone/opponent stone/empty). (2) The center move's priority is higher than an edge move. An edge move's priority is higher than a corner move. In short, coordinate (2,2) > (1,2),(2,1),(2,3),(3,2) > (1,1),(1,3),(3,1),(3,3) (3) Capture moves are high priority. (4) If the opponent passes, our pass move is high priority. Otherwise pass move is low priority. 3.4. Specification of program for 4x4 board We made the program using alpha-beta pruning. All candidate moves are ordered by following heuristics. (1) When all sides are enclosed with my stone, the candidate move's priority is low. In addition, the priority level is adjusted by four diagonal points' situation (my stone/opponent stone/empty). (2) Avoid filling empty triangles. The priority of move in the following figure is low. Figure * * * : black * x x : black's candidate move (3) When an opponent stone is adjacent, the candidate move's priority is raised. (4) The closer the move is to the center, the higher it's priority. (5) Capture moves are high priority. (6) If there is Ko, the priority of pass is low. If there isn't Ko and the opponent move immediately before was a pass, the priority of a pass move is high. (7) When it is possible to win even if keeping passing, the pass move is given priority. If we have enough prisoners that we can still win even if the opponent captures all our stones on the board, then pass is a winning move. 4. Experimental results The computer which we used is Ultra SparcII360MHz, with 2GB memory. The program language is C. 4.1. Result ( 2x2 board ) Because of symmetry there are only two candidate moves for the first move: (1,1) and passing. When black put a stone on (1,1), the game was a draw. Even if black passed the result is still a draw, because nothing changed except the player to move. We show the resulting game tree in appendix 1. 4.2. Result ( 3x3 board ) If black played (2,2) as the first move, black won; wherever white responded, black was able to capture white. We show the resulting game game tree in appendix 1. The number of nodes was about 500. 4.3. Result ( 4x4 board ) When black played (2,2) as the first move, the game became a draw. When black put a stone at another coordinate as the first move, black could not win. We show some parts of the game tree in the following figure. The number of nodes was about 14,000,000. In the experiment, we could decrease the number of nodes by refining ordering of candidate moves. To the contrary, if ordering is rough, the number of nodes easily exceeded 100,000,000. Figure ( omission, refer to original paper ) In our method, because game continue as long as there is a legal move, we guess that almost every possible combination of stone arrangements appears as a node. In the case of the 4x4 board, there are 3^16=43,046,721 possible stone arrangements, because there are three possible states, empty/black/white, in 16 places on 4x4 board. If we don't count symmetry and illegal stone arrangement, there are 3,047,783 of actually possible combinations. However, the number of nodes visited in the search actually exceeded this, because the difference in number of prisoners, turn, position of Ko and whether the move immediately before is pass or not, all make two identical stone arrangements count as different nodes. 5. Conclusion We solved Go on 2x2 board, 3x3 board, and 4x4 boards by using a game tree search program. We would like to solve Go on larger board and try using other Go rulesets. Reference [Cho 1993] CHO, Chikun. CHO CHIKUN NO SMALL WORLD. Go Weekly, 1993.9-1994.4 (in Japanese) [Nihonkiin 1989] Nihonkiin. NIHON IGO KIYAKU. 1989 (in Japanese) http://www.cs.cmu.edu/~wjh/go/rules/Japanese.html ( in English ) [Nakamura 1996] NAKAMURA, Teigo. COMPUTER IGO NO TAMENO RULE TUKURI NI MUKETE. Magazine "Game of go", December 1996, pp.80-81 (in Japanese)