Kavalan wins Connect6 tournament

Abstract

The computer Connect6 tournament was held as part of the Computer Olympiad 2018, which took place in Taipei, Taiwan, from July 7^th to 13^th, 2018. A total of six teams participated in the tournament. The participating teams and the final standings are listed in Table 1. All six teams’ programs were executed on Windows-based PCs. They obtained points of 9, 6, 5, 4, 3 and 3.

The game Connect6, a kind of six-in-a-row game, was first introduced by Wu and Huang (2005) and then described in more detail by Wu et al. (2006). The rules of Connect6 are very simple. Connect6 is a game for two players (Black and White). Black and White take turns placing stones on a $19 \times 19$ board. Except for the first move, which is limited to placing just one stone, in subsequent moves each player is allowed to place two stones simultaneously. Normally, Black moves first. Because the rules do not allow players to pass, the game states change in a stable manner. Since stones cannot be killed, a cell’s1

The intersections to place stones on the board is referred to as cells in this report.

state remains constant following stone placement, and thus the game state never repeats during a single game. The player who first obtains six consecutive stones (horizontally, vertically or diagonally) wins the game. When all cells on the board are occupied with neither side successfully connecting six, the game is a draw. In the tournament, the games were played according to a round-robin system in which one program played twice against all other programs. In each game, every program had to complete all of its moves in 30 minutes. For each game, the winner scored 1 point and the loser scored nothing. For a draw, both scored 0.5.

Table 1

The participants and final standings

Ranking	Program	Author	Country	Points
1	Kavalan	Jung-Kuei Yang, Shi-Jim Yen	Taiwan	9
2	Neptune	Yiwei Chen, Xiaobin Wang	China	6
3	Sixgo	Weihe Yin, Junkai Lu	China	5
4	Connection	Zhang Song	Japan	4
5	Explorer	Zhang Yunpeng, Li Yaguang, Liang Tailin, Zhou Ke	China	3
5	Clouds	Jing Ge, Yu-xiang An, Lin-nan Wang	China	3

Kavalan won the gold medal of the Computer Olympiad 2018 Connect6 tournament by winning 9 of 10 games except for a single loss to Clouds. Neptune and Sixgo won the silver and the bronze medals respectively, with 6 points and 5 points. The cross table is listed in Table 2. For the six programs, Kavalan was developed based on Monte-Carlo tree search (MCTS) with deep neural networks, while other programs were based on alpha-beta search. Kavalan uses pre-trained deep neural networks to perform predictions of promising moves from MCTS leaf nodes instead of using the Monte Carlo random game (or playout) for the prediction. The results show that MCTS with deep neural networks can enhance the correctness of choosing a leaf node to develop the search tree.

Table 2

The cross table

Program	Kavalan	Neptune	Sixgo	Connection	Explorer	Clouds	Total score
Kavalan	–	2	2	2	2	1	9
Neptune	0	–	2	1	1	2	6
Sixgo	0	0	–	1	2	2	5
Connection	0	1	1	–	1	1	4
Explorer	0	1	0	1	–	1	3
Clouds	1	0	0	1	1	0	3

This report provides commentary on three games, Kavalan (gold) versus Neptune (silver), Sixgo (bronze) and Clouds. The first game, Kavalan (white) vs. Neptune (black), shown in Fig. 1 (below), is the only game in this tournament in which Kavalan was defeated by Clouds, which occurred during move 8 for Kavalan. In Fig. 1, when Clouds generated a double-threat move in move 7, Kavalan played the wrong blocking move to defend against the double-threat in move 8. Consequently, Clouds found the winning position in move 9, as shown in Fig. 1. A close match between Kavalan and Neptune is shown in Fig. 2. In this first game between the two programs, both programs successfully blocked each other’s attacks at the beginning of the game. Kavalan did not find a winning position until move 61 (double-threat move). Typically, in the mid-game, there tends to be a large number of search positions for threat-moves (double- or single-threat moves). For this reason, finding the winning position in a limited amount of time tends to be one of the biggest challenges for Connect6 programs. Figure 3 shows the first game between Kavalan and Sixgo. As in the match between Kavalan and Neptune, the first move for Kavalan was not played on the central location (J, J) of the board. Since most games start with (J, J), many programs tend to only consider that as the first move. It is therefore relatively easy to break this opening pattern and play somewhere else, as is the case here for Kavalan, where it is designed to play the first move not only on the cell_{(J, J)}, but also consider the 8 surrounding cells as well. In this game, Kavalan found the winning position in move 7, as shown in Fig. 3.

Fig. 1.

Black: Clouds, White: Kavalan, Moves 1–9.

Fig. 2.

Black: Kavalan, White: Neptune, Moves 1–61.

Fig. 3.

Black: Kavalan, White: Sixgo, Moves 1–7.

F.l.t.r. .

Shun-Chin Hsu, Junkai Lu (Sixgo, operator), Jung-Kuei Yang (Kavalan, author), Xiaobin Wang (Neptune, author), Jen-Chun Chang.

References

Wu, I.-C. & Huang, D.-Y. (2005). A new family of k-in-a-row games. In The 11th Advances in Computer Games (ACG11) Conference, Taipei, Taiwan.

Wu, I.-C., Huang, D.-Y. & Chang, H.-C. (2006). Connect6. ICGA Journal, 28(4), 234–242.

Yen, S.-J. & Yang, J.-K. (2011). Two-stage Monte Carlo tree search for Connect6. IEEE Transactions on Computational Intelligence and AI in Games, 3.

Yen, S.-J., Yang, J.-K., Kao, K.-Y. & Yang, T.-N. (2012). Bitboard knowledge base system and elegant search architectures for Connect6. Knowledge-Based Systems, 34, 43–54. ISSN: 0950-7051.