Finding Strategies to Solve a 4x4x3 3D Domineering Game [Thesis]
In December 2010, I successfully defended my thesis, Finding Strategies to Solve a 4x4x3 Domineering Game. To better understand what my thesis is about, I first need to introduce the game, Domineering.
Domineering is a two-player combinatorial game where two players play on a grid board (similar to a chessboard) of any size, placing domino pieces that cover two spaces on the board. One player can only place pieces vertically on the board; the other can only place pieces horizontally on the board. Each player take turns placing a piece on the board until one player is no longer able to place any more pieces, resulting in a loss for that player. For an example of how Domineering plays, you can download my C# Domineering prototype. This prototype allows you to play Domineering on a 8×8 board against another player or a computer opponent.
To solve a Domineering game, one must find a winning strategy for each turn order of a Domineering game. A winning strategy is one that a player can use that will guarantee victory regardless of how the opponent plays. The largest sized board that was solved is a 10×10 board by Nathan Bullock.
There is also 3D Domineering, a three-player variant of Domineering where three players play on a three-dimensional board (think Rubik’s cube). One player can only place pieces parallel to the board’s x-axis, the other player can place pieces parallel to the board’s y-axis, and the third player can only place pieces parallel to the board’s z-axis.
Solving a 3D Domineering game is more complicated than solving its 2D variant. In two-player games, either the first player or the second player can guarantee a victory (there are no ties in Domineering). In three-player games, it is possible that no player can guarantee a victory. This is because of the king-maker mechanic in multi-player games, where one player who cannot win can decide with his actions which of the other two players can win. Thus, to solve a 3D Domineering game, one must for each turn order:
- show which of the three players can guarantee a victory through a winning strategy, or
- demonstrate that no player has a winning strategy.
Alessandro Cincotti has solved 3D Domineering games where the sum of the board’s dimensions is less than ten (example, a 3x3x3 board; 3+3+3=9). However, solutions for games where the sum of the dimensions is greater than or equal to ten have not been published around the time I started my thesis work.
After a year of work, I was able to solve a 4x4x3 3D Domineering game. The strategies I found to accomplish this are as follows: two of the three players can form an alliance and collude to prevent the third player from winning. As long as the alliance follows a specific blocking strategy, there is nothing the third player can do to win. This creates a scenario where no player can guarantee a victory, regardless of turn order. This is because if the first and second players can prevent the third player from winning, then it also means that the first and third players can prevent the second player from winning, and the second and third players can prevent the first player from winning.
I started to prove my strategy in a 3x3x3 game, one that Alessandro Cincotti had already proved that no player had a winning strategy regardless of turn order. When a thorough analysis of my blocking strategy confirmed what Cincotti had already proved, I expanded the strategy to be applied to a 4x4x3 game. I wrote a proof to show that two players can prevent the third player from winning in a 4x4x3 game.
However, writing a proof was not possible for a 4x4x3 game flipped to its side (making a 4x3x4 game), as there were too many possible games to consider by hand. Therefore, I developed a C++ application that simulated a 4x3x4 game among three players. The simulation applied the blocking strategy I created for the two-player alliance and considered all possible moves that could be made by the third player. The output of my application showed that regardless of how the third player played, the other two players could always prevent the third player from winning as long as they followed the blocking strategy.
Thus, the 4x4x3 proof and the data from my application proved that the 4x4x3 game was solved to be one where no player had a winning strategy, regardless of turn order.
For a thorough examination of my strategy and proof, you can download my thesis [117 page PDF, including required signature pages].
To complement the Domineering simulation application, I developed a very bare-bones 3D Domineering game (written in C++ and DirectX) to test and verify the outcome of any 4x3x4 game. The application is available to download in this zip file. The zip file contains the dom_3d.exe application (Windows), a config text file that configures the board’s dimensions (you’re not restricted to playing on a 4x3x4 board), and a readme file with instructions on how to use the application.
The Resume & Contact Me page has my contact information if you want to ask me questions regarding my thesis or the application I developed to prove my thesis.