Win Gomoku with Threat Space Search

1. Introduction

Gomoku, also known as Connect 5, is a 2-player game where the goal is to place 5 consecutive markers on the board in a horizontal, vertical, or diagonal line. The first player to achieve such a line wins.

Many AI approaches have been developed to play various board games. Recent deep learning approaches have had success across many complex games. However, such approaches are complex, and classic AI approaches can also be worthwhile.

In this tutorial we introduce and describe the heuristic search algorithm of Threat Space Search (TSS), which was first proposed in this paper. We show how threats are formulated and continue to show how searching for a series of threats is a powerful heuristic to reduce the size of an otherwise large search-space.

2. Alpha-Beta Search

A traditional approach to many two-player games is – search. This is often combined with some form of pruning. Otherwise, the search space would be too large to explore fully.

In this turn-based setup, a tree of moves and counter moves is created up to a specified depth or stopping criteria. Once the depth is reached, each position is evaluated. The players then seek to Maximize their scores and minimize their opponents’ scores. This is a high-level introduction to the mini-max algorithm and – search.

The – search algorithm is a full, depth-first search of the game tree. This is an exponential algorithm with a large branching factor. So searching the whole tree is not going to be the solution. Instead, we must introduce some heuristics. Human Gomoku players tend to look for threat sequences, which they explore further. So that is what we will do.

3. Threats

In Gomoku, certain combinations of tiles are more threatening than others. Some threats need to be dealt with immediately and force the opponent to play a specific set of limited options. A winning strategy consists of a series of threats leading to a forced win. First, we introduce the threats to develop an intuition and to help us understand the concept of threat space search more intuitively. After presenting the threats, we introduce concepts for analyzing them.

Finally, we show how these concepts allow us to develop a heuristic search function.

We show the various threat structures in the accompanying figure and describe them below:

Let’s discuss it now:

• The four is a line of 5 squares, of which 4 are occupied by the attacker, and the 5th square is empty
• The straight four is a line of 6 squares of which the attacker occupies the center 4, and the remaining squares are empty
• The three consists of a line of seven squares of which the center 3 are occupied with the remaining 4 squares empty
• A second option for the three is a line of 6 squares with any 3 of the center 4 squares occupied by the attacker
• The broken three is a line of 6 squares of which the attacker has occupied 3 non-consecutive squares of the center 4 with the remaining squares remaining empty

Threats like these are an immediate danger because if a 4 exists, the players’ next move will win, and a 3 should be countered because otherwise, it becomes a straight 4, which is an immediate win. Using the threats we have outlined, we will now describe threat space search and show how TSS allows us to combine a series of threats to create a winning move sequence.

4. Threat Space Search

In TSS, we focus only on attacking play and ignore defensive moves. If more than one defensive move is possible, then we treat each move as if it had been played simultaneously. Once a suitable threat sequence is discovered, we can then further investigate it in order to evaluate whether it is winning. That is, we investigate whether the sequence will survive any combination of defensive moves.

TSS is designed to more closely mimic human play. In this way, humans can evaluate and quickly discard threats that don’t lead to further threats and a winning sequence. The TSS algorithm seeks to replicate this by identifying threat sequences that are likely to lead to victory and then further verifying them.

4.1. TSS Concepts

In order to build our threat search tree, we first need to define some concepts:

• The gain square is the square played by the attacker
• The cost squares are the squares played by the defender in response to the threat; this is a list of all possible direct responses
• The rest squares are the remaining squares which, together with the gain square, constitute a threat

With these concepts, we can now define some macro concepts for the tree structure:

• A threat is dependent on threat is a rest square of is a gain square of
• The dependency tree of threat is the tree with root and consists only of dependent nodes. That is, the children of each node are the threats that are dependent on
• Two dependency trees, and , are in conflict if within the dependency tree a threat exists and within the dependency tree, a threat exists, such that the gain square of is a cost square of or the gain square of is a cost square of or a cost square in is a cost square in .

5. TSS Example

The example on the second board sets up a number of threats. If we run TSS we will identify a number of threat trees:

Many will not lead to forced win positions, so we can ignore those trees and focus only on trees where a potential forced win has been found. We show the trees in the table below:

The corner set of tiles produces 4 threat trees of depth 1. Since none of the trees results in a straight four or a five we can discard those trees as non-winning sequences. We can also see how some moves result in conflicting threat trees because the gain square is the cost square in another tree. For example, the first two rows in the table show this.

We also see a winning sequence discovered in the tree of depth 3 and how one branch leads to a winning sequence, but the other branch at depth two doesn’t. This example shows how we can quickly discard threat trees and also shows that we don’t need to consider exact opponent responses to our moves. This allows the algorithm to reduce the search space and speed up evaluation.

6. Conclusion

Threat Space Search is a heuristic search function designed to reduce the size of the search space to a more manageable size while identifying the winning moves. TSS is not guaranteed to find a winning threat sequence. However, the general speed-up in search can make up for this fact. TSS can also be combined with other heuristic search algorithms to compensate for this issue.

Further, a full agent will combine TSS with other heuristics in order to build a fully functioning agent.