The X-0-0 Heuristic in Game Tree Analysis

1. Introduction.

Current programs for complex two person games such as chess or Go rely heavily on minimax­ based lookahead to evaluate board positions and to select moves. In chess programs this is usu­ ally an analysis performed over good moves throughout the whole board, while in most Go situations lookahead must be restricted to lo­ cal battles. In order to increase the number of nodes that can be analyzed with the comput­ ing resources available, alpha-beta tree prun­ ing is invariably utilized, usually in conjunc­ tion with the killer heuristic [1,4].

In this paper we will introduce a new heuristic named the x-o-0 heuristic. The purpose of this heuristic is to anticipate and protect against the opponent's strong moves, both offensive and defensive. In section 2 we will informally describe the heuristic, and will give examples of it in use in chess and Go. We will then de­ fine the algorithm for the heuristic precisely in section 3. We will assume that the reader knows the basic rules of chess and Go.

2. The !~-Q heuristic.

There is a Go proverb "The enemy's play is my own key play" [3) · A simple example of this is shown in Figure 1.

If it were black's move, he would play in the corner, guaranteeing the safety of his group. If it is white's move he uses the proverb to play in the corner. In its simplest form, the X-0-0 heuristic is similar to the proverb in that it attempts to recognize the opponent's strongest move, and to take it away from him.

A chess example is shown in Figure 2.

It is White's move. In this situation current chess programs will perform extensive lookahead analysis attempting to find a mating sequence. In t he same position, even a poor human player wil l quickly recognize the R-R8 threat, and wil l decide that the only way to block that move is R-RS, and so the block move is forced. No l ookahead is necessary to make the move. The t hought process that has occurred is:

" If it were black's move instead of mine, does he have any obvious st~ong moves? Yes, he would move his rook to R8 and check me. Would I then be able to do. any­ thing about that? No, it would be check­ mate. How can I stop that move? I must e ither capture the rook, block its path, de lay him by putting him in check, guard Rl, or block the path between Rl and my king. The only one of these that I can do is to block the path of the rook with R­ RS, and so this is a forced move."

Figure 3 shows a similar board position.

Here the threat is the same as before, u~ack plays R-R8, white needs two block the threat; either P-R3 or P-R4 by K-R3. The x-o-o heuristic compels play either P-R3 or P-R4 at this move. but if moves to followed white to

Figure 4 shows a Go position called the nose tesuji. It is black's turn to play, and he wants to capture the two white stones on the right. A tesuji pattern matching program de­ cides that the probable best play is the stone marked with an X, on top of the white "nose". Black must now confirm that the white pieces cannot escape. Tackett [2,5] analyzed this po­ sition, and decided that its solution would take nearly a month on an IBM 360/67, using standard lookahead techniques. Using the X-0-o heuristic the analysis is very inexpensive. White can only escape in two directions, to the left or right. Consider an escape to the right: if it were black's move he would immediately play to the right of the two white stones, blocking all possibility of escape. Therefore the x-o-o heuristic compels white to block that move by playing there. A simple template pat­ tern match should now show that white is trapp.ed. A .similar analysis on the left shows that white cannot escape that way either, and so black's nose tesuji is confirmed.

3. The !-Q-Q algorithm.

We are now ready to give the formal algorithm for the heuristic. Assume that the two players are X and 0, and that it is O's turn to play.

The algorithm can then be written:

Find all very strong X moves, X1, ··· , Xn.

For each Xi

(a) If there is an 0 move which nullifies the effect of Xi then Xi can be ignored.

{b) If Xi must be blocked now, add blocking

• 0 moves to the forced move list for Xi. (c) If two 0 moves are needed to nullify the effect of Xi, say 0' and 0'', then add 0' to the forced move list for Xi.
• If there are no forced move lists, then use alpha-beta lookahead as usual.

If there are forced move lists, then play a move which is in the intersection of all of the forced move lists.

4. Summary

The success of the heuristic in any given game will depend on the care with which the good X moves are selected. The list of moves should be kept as small as possible, and n should usu­ ally be much smaller than the branching factor of the minimax game ~~e. We are currently ex­ perimenting using the game of Go-Moku in order to obtain a good estimate of the improvements

which can be expected using x-o-o.