Connect Four 3D (aka Sogo, Connect Four advanced, or Score Four) is a two player strategy game. It is a three-dimensional version of the game Connect Four and is played on a three-dimensional 4x4x4 board. Both players alternate to place their stones in one of the columns unless it already contains four stones. The stone then falls to the bottom of the column. The player who manages first to position four stones in a straight line on any level or angle wins the game. Connect Four is very similar to 3D Tic Tac Toe (aka Qubic), with the difference that Qubic is without “gravity”, which means that stones can be placet at any free spot. While Patashnik proved that Qubic is a first player win already in 1980[8], Connect Four 3D is still unsolved.

The goal of this project is to progress towards solving Connect Four 3D. Particularly, the goal was to improve the solver developed in the thesis of Deutrich[3], who adapted many ideas presented in the excellent blog about solving Connect Four of Pascal Pons [5]. In the current project, I present two solvers: The first one is an implementation of the Minimax algorithm with improved heuristics that attempts to solve a position as fast as possible on a single CPU. The second solver distributes the search among many Minimax solvers of the first kind to achieve much better performance by using parallelism.

The solvers presented here are implemented using C++. For parallelism we use the OpenMP library[6]. The parallel solver runs on the CooLMUC-2 cluster which is part of the Linux cluster of the LRZ[7].

Connect Four 3D. The second player (black) needs to move. The first player won the game.

Minimax Solver

The minimax solver implements the recursive minimax algorithm to solve Connect Four 3D positions. In this chapter the bitboard, move order and transposition table are presented. Instead of using alpha-beta pruning, we make the additional assumption that connect four 3D is a first player win, and prune the search tree as follows: When the second player finds a draw, his other possible moves are pruned, since this is the best he can achive. If the search returns a first player win, then he can force a win from that position. In particular, there’s no distinction between a draw and a second player win. A similar technique was used for the checkers solver Chinook [9].
Next, we introduce some abbreviations for some important recurring patterns. If a player has three stones in a line, the empty fourth position is called a threat. If the player can play the thread and win the position, it is called an opening. If a player can move while having an opening that player wins the game. By anticipating bad moves, the number of explored nodes can be decreased. In particular, the following situations can be efficiently detected by using a bitboard implementation.

The player has an opening. The opponent has one opening. The opponent has two openings. the opponent has a threat above the opening of the current player. The second player has a stone in every line. The first player doesn’t win by placing the 63th stone. These positions yield either to a forced move or to a decisive move and do not require further exploration.

Bitboard

A bitboard is an encoding of a position into a bitmap. Representing the game board as bitboard allows us to manipulate it efficiently using bitwise operations. They are essential to increase the performance of the solver. The bitboard presented here is the same Deutrich[3] used, which in turn is based on a bitboard by Pons[5] for connect four. The idea is to map the stones of each player to a 64 bit integer. The following table shows how the positions of the game board are mapped to the 64 bit integer. The lowest bits 0 to 15 encode the first layer of the game board, the next 16 bits the second layer and so fort.

48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63

32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47

16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15</b>

For each player then a bit is set to 1 if the player has a stone at that position, otherwise the bit is set to 0. The number of stones placed in total and the locations of threats for each player are also saved in the bitboard so that they do not need to be computed each time. A different variant that stores the whole board in only 80 bits is used to store a position in the transposition table.

Move Order

The move order used for the minimax solver is based on a heuristic that assigns each move a score based on the other stones that are connected to the move. For each line that contains a stone of the other player no points are awarded. The point values can be seen in the following table. Notice how lines where stones of the opponent are placed give no points. Each player focuses on improving his own position and not on making the opponent worse off. Creating an opening gives a bigger score than a threat that has no direct consequences. Since each stone is part of at most 7 lines the scores of one level can never surpass the next higher ones. So if a move is the first stone in seven lines it gets a score of 7. It is considered worse than a move that is the second stone in one line and gets no points in all others, with a score of 10. The moves are ordered using insertionsort from best to worst.

The order in which the possible moves of a player are searched by the minmax solver has a big impact on the performance of the algorithm. For example, if all choices for the max player are wins, then the choice doesn’t matter. But if some moves lead to a loss, moves need to be explored until one winning move is found. If all moves are a loss then all need to be explored. It is therefore important to order moves such that the best moves are explored first. Despite putting in a lot of effort and testing, improving the move oreder turned out to be particularly hard. The current move ordering performs quite well for the middle- and endgame (>25 stones), but there is certainly room to improve when there are less stones. However, exhaustively testing different heuristics is almost impossible for positions with few stones.

Transposition Table

In Connect Four 3D, like in many other games like chess, one position can be reached by different lines of play. As a result the game tree contains many duplicate nodes or should be seen as a directed acyclic graph (DAG). Saving all visited nodes during search requires too much memory. The transposition table is a solution to this problem. It is a fixed size table that saves positions and their solutions. New positions can then be searched in the transposition table to check if they are already solved and the fixed size allows it to fit into memory. It is implemented as a fixed size hash table to allow for constant time insert and find operations. The following points need to be addressed when using a transposition table:

Symmetries of the same game board should be mapped to the same entries.

Minimizing the entry size to increase the number of stored positions.

Hash function, maps positions to table entries.

Replacement strategy, decides which positions to replace when the table is full.

Thread safety, to allow multiple threads to work on the same transposition table.

Thread safety is only required if multiple threads are sharing the transposition table, otherwise it will only be an overhead.

Symmetries

Connect Four 3D has 8 symmetries. All 8 different boards can be computed by flipping each layer horizontally, vertically or diagonally. When inserting or searching for a board, all 8 symmetric boards are computed. The one with the lowest numerical value is then chosen as the canonical key that represents all 8 boards. Here are the three flip functions that perform the left right (LR), up down (UD) and diagonal (DI) flips. They use masks to select a part of the board, move it with shifts and then recombine the moved parts. The function that computes the canonical key uses these three functions to compute the 8 symmetries of a position and then chooses the minimum.

Refrences

References [1] I.-C. Wu, H.-H. Lin, P.-H. Lin, D.-J. Sun, Y.-C. Chan, and B.-T. Chen. Job-level proofnumber search for connect6. In Proceedings of the 7th International Conference on Computers and Games, volume 6515, pages 11–22. Springer-Verlag, 2010.

[2] Breuker, Dennis M., Jos WHM Uiterwijk, and H. Jaap van den Herik. Replacement schemes for transposition tables. In ICGA Journal 17.4, pages 183-193, 1994.

[3] M. Deutrich. Determining the value of connect four 3d. Bachelor’s thesis, Technische Universität München, 2019.

[4] A. Kishimoto, M. H. M. Winands, M. Müller, and J.-T. Saito. Game-tree search using proof numbers: The first twenty years.International Computer Games Association Journal, 35(3):131–156, 2012.

[5] Solving Connect 4: How to build a perfect AI, Pascal Pons, https://blog.gamesolver.org/solving-connect-four/01-introduction/

[6] OpenMP, https://www.openmp.org/

[7] Leibniz-Rechenzentrum, https://www.lrz.de/

[8] Patashnik, Oren. “Qubic: 4× 4× 4 tic-tac-toe.” Mathematics Magazine 53.4 (1980): 202-216.