A Model of Strategy for the Game of Go Using Abstraction Mechanisms

1 Introduction

1.1 A brief presentation of the game of Go

Go is an ancient game of strategy which originated in China and which has been played by Occidentals since the sixties. The game is played on a 19 x 19 board on which two players in turn place a stone of their colour. Starting with an empty board, each stone is placed on one of the vacant points of intersection of any two lines. The players can remove the opposing stones from the board by completely enclosing them. The object of the game is to have a greater number of stones on the board than the opponent at the end of the game. These basic rules differ from one country to the next, but all of them can be interpreted according to the above presentation Playing Go is not essential to understand the issues which are dealt with in this paper.

· We can distinguish several levels in the understanding of a move in Go There is a tactical level which enables one to recognize the basic forms. In addition this level is concerned with the structure and the tactical interactions of sets of adjacent pieces. There is also a strategic level which enables one to interpret the meaning of these forms in the particular context of a particular Go match. The polysemous characteristic of the entities at the tactical level in the interpretation of the strategic level makes us think that there may be some similarities between a) the cognitive mechanisms which are operated to understand a move or a position in Go, and b) the understanding of a sentence or a text in a natural language (with a very short semantic context for Go).

In short, the specific characteristics of Go cset this game at the frontier of the realm of reality and the formal domain. Indeed, the domain is not only formal with respect to its representation which allows no ambiguity -concerning its description at the lowest level- but also real with regard to the nature and complexity of the knowledge, as well as the concepts and the mechanisms which are put to work.

1.3 The significance of an abstract approach to the game of Go

Resolving the problems of Go through a standard combinatorial approach would be useless. Therefore, we have tried to change the problem by using a player's strategic approach. «It is natural to simplify an intricate problem ~f its resolution can then he guided by the resolution l?( the simple problem. Abstraction itself consists in creating an easier proh/em that can be solved first, so that tis solution can be used as the starting point for resofloing the real problem» [Pitrat, 90). We believe that the possibility of using part of the strategic human reflection onto the framework of an abstraction is a natural approach. Consequently, thanks to our strategic knowledge of Go, we have created a domain which is parallel with this game but which has a smaller space search. We shall name this parallel domain the Abstract-Go. ·

Unlike the applications usually tested within the context of abstraction, [Giunchiglia 92], there is neither solution nor theorem to be found in Go but a possibly profitable position as it is the case in most of the games where the space search is large. A system using abstraction is generally made up of at least two levels : a real level and an abstract level . They respectively correspond to the initial domain and the simplified one Each level has its own description of the states of the. problem, a mechanism of exploration and generation of new states, and a mechanism of translation into the other representation

2 General presentation of the system

The GOBELIN system is made up of four modules which can be thematically divided into the two following manners : Real/Abstract & Description/Analysis. There are two modules for the handling of real and abstract descriptions I}] and 0 and two modules of analysis -one for the research of plans m and the other for the tactical veritlcation of the latter [!]. The arrows ):>- signals the transitions between the different modules during the working cycle. The modules of reflection also takes into consideration the modules of description to create new states (in their respective level).

Module OJ Handling of the real representation This module deals with the evolution of the real representation of the different game states. It can generate a subsequent position from a current position. It governs the rules of the game at the lowest level , that is to say the placing of a new stone, the capture, and the detection of illegal moves. It is the generator of <;tates that is used in most computer game programs.

Module 0 Calculation of the abstract representation

From the real representation of the board position, this module builds an abstract representation of that position where the real objects are piled up and where the strategic relations are clarified in order to create new objects which are strategically more relevant . The system also detem1ines the implicit objects which corresponds to strat(;!gically profitable moves. Thus, we are provided with a new representation of the board position as a network of object relations of a higher level than the real representation Blocks, Chains, Groups and same colour stones are connected by a relation of proximity and of natural extension.

Module [[I Abstract reflection

Followi~he abstract description which is created by the module ~, the mechanism of strategic reflection evaluates the position and seeks a profitable plan of action for the colour to be played. It also takes into consideration th~ various emergencies, postponable actions and possible threats. A move is comparable to a series of abstract operators (possibly a tree) representing operations which can be implemented by several elementary actions -for instance, splitting two groups, removing the heart of a colour group, defending a group which undergoes attacks, extending a group by natural extension, etc.)

Module [I) Real verification

When a strategic move is chosen by module [I], the «tactical operator» [I) verifies the feasibility of the series of operators in the real representation. It does so by developing a reduced arborescence for each operator in order to validate or invalidate the initial move. In case of failure in the tactical feasibility of the strategic plan, a return to the abstract level [I] is operated (transition II]r::>{IJ) so as to allow the strategic plan to search for a new move with the new indications (notably on the impossibility of realizing the operators which are tactically unfeasible) which were provided by the tactical evaluation. Finally, when the tactical module delivers a positive verdict on the feasibility of a strategic move, the systems actualizes the first real move of the first operator of the plan

4 An example

In this section we shall illustrate the methods that are used in GOBELIN with a relatively simple example of a beginning of a match with a handicap of five stones. In order not to cumbersome the expose, we have not mentioned a vast number of details which, though useful, could not be accounted for in this paper. For further information see [Ricaud, 95; Ricaud, 96].

In this example, Black has begun the game with five stones already on the board (the five stones denoted 0 ), which gives it some lead over White. As White tries to build territories and areas, it tries to neutralize the potential territories and the areas which are under the control of Black.

We shall illustrate the various methods which are implemented in GO BELIN by studying the reactions of the system with respect to the position following the move @ that has just been played by White. Theretore, in our example, GOBELIN makes the decisions for Black. In this instance, the strategic search is focused on the group of stones e ' ® ' © and 0 in the south-west comer because they have particular characteristics which make them vulnerable. The two areas that are controlled by the Black family e are invadable through gliding, moreover this group has only one escape extension towards the center of the board.

5 Validity of the abstract solution

The solution we found with respect to the Abstract-Go is not always valid in the Real-Go, and a stage of verification of the validity and feasibility of the abstract sequence is necessary (see above). The abstract description entails a loss of information which results in a loss of accuracy in the evaluation of game positions which are generated at the abstract level. Consequently, the longer the abstract solution is (in terms number of operators), the less accurate it is and the less probable it is that it shall be converted into a real solution. The tactical validation can be non-existent for some moves which are itemized as always valid. This is the case for sliding in certain situation. In the opposite case, a geographically limited tree, which is guided by a goal, is run on the real representation so as to test the possibility or impossibility of fulfilling the goal with respect to the particular context of the position.

5.1 The limits of the Approach with regard to the domain

The abstraction which is implemented to model the strategy operated in the game of Go is not a faithful representation of human players' reasonings. Indeed, players often use tactical sequences in the midst of their strategic reflections to immediately verify the feasibility of their reasoning and modify it in case of impossibility or major obstacles. GOBELIN should be able to tactically zoom in in its strategic research when a tactical opportunity occurs or when it is not sure of its strategic sequence.

Similarly, because the opponent has to respond to tactical threats by an easily predictable sequence of moves, giving a particular advantage to the player, every simple tactical threat has to be taken into consideration at the strategic level. In the game of Go, the Shibori (wringing out) is a classical example of such a situation. As we know, players can shift to a tactical exploration during the phase of strategic reflection. This fact allows them to develop an adaptable game which fails Go programs nowadays.

6 Conclusion

Strategic modules of present Go programs yields bad results, which strongly penalizes the general level of the game. The strategic dimension of Go is not at all mastered in these modules, and yet it is an essential part in the human player's reflection. We have used an applied abstraction to model the fundamental strategic mechanisms of the game of Go. Contrary to most of the domains which are dealt with on publications about abstraction, our abstraction deals with a non-logical domain. The mechanisms that make up abstraction ( a) the translation of a real description into an abstract description, b) the research of an abstract solution, c) the translation of the abstraction solution into a real solution) are implemented in the GOBELIN system.

GO BELIN is the end-result of a thesis which was carried out within the Metaknowledge team and under the direction of Jacques Pitrat at the Pierre et Marie Curie University (Paris 6). GOBELIN has been evaluated upon a basis of tests carried out at the beginning of a match. It yields responses the quality of which is assessed at about 9th kyu. Considering the modest, encouraging results of our approach, we hope to be able to improve our modelling by creating a new one which would take into account the interaction between strategy and tactics that is used by human players.

It is clear that human strategy is made up of more than the operators and knowledge that were introduced in our modelling, but we think that the strategic reactions we have obtained are encouraging. In addition, the concepts that were outlined are comparable to the concepts of elementa1y strategy that are used by the average player in game commentaries.