Course:CPSC312-2024/Ultimate-Tic-Tac-Toe

Authors: Jerry, Tony, Junming

Ultimate tic-tac-toe is a variant of the traditional tic-tac-toe board game. It adds complexity to the gameplay while maintaining the same principle mechanisms. This variant of the game consists of a $3\times 3$ board, with each square of this outer board containing a traditional tic-tac-toe board, adding up to a total of $(3\times 3)^{2}=81$ playable squares.

The first player may begin by playing in any of the squares, while all subsequent turns must be played, if possible, on the small board whose location on the outer board matches the previous play's location relative to the small board it's on (i.e., if the previous player placed an X in the bottom-right square of centre small board, the current player may place an O in any square of the bottom-right small board). If a placement requires the subsequent player to play on an already claimed board, this player must choose any other unclaimed small board to play on. A player may claim a small board by winning the traditional tic-tac-toe game on that board. Once a player claims three small boards that form a horizontal, vertical, or diagonal line on the outer board, the player immediately wins the overall game.

What is the problem?

We intend this project to be an implementation of the ultimate tic-tac-toe game in Haskell. As such, the project poses a number of interesting challenges: the core mechanism, the graphical representation of states, the handling of user inputs, and the computer program that acts as the opponent of the user in-game. The mechanism of the game itself is not so difficult to grasp, but translating that conceptual understanding to function definitions in Haskell is where the challenge resides. On the other hand, we believe that there are important design choices to be made on how the boards are displayed to the user, and how the user interacts with the boards. Lastly, the computer-based opponent (which we cover in the next section) may be considered the most challenging part of our goals, as it involves the use of Haskell programming and problem-solving techniques that extend mostly beyond the scope of this course.

What is the something extra?

In the first place, we will be including some form of computer-based opponent in our game implementation for the user to play against. It has been known that, unlike the traditional version, the ultimate tic-tac-toe cannot be easily solved with any brute-force algorithms. In fact, even minimax-based computer opponents of this game end up consistently losing to human players. Therefore, we decide to implement a number of algorithms and strategies, including minimax, and compare their performance as computer-based opponents in ultimate tic-tac-toe.

What did we learn from doing this?

We find that Haskell is very suitable for implementing the game mechanism itself. For a game like ultimate tic-tac-toe, which has very clear rules and win-lose conditions, the functional nature of Haskell allows very straightforward definitions for such rules, which made the process rather smooth and painless. In fact, it took less than a day for us to implement the game, with only minor adjustments needed afterwards.

However, it quickly became a huge challenge, as we proceeded to implement our first machine player using the minimax strategy. Since minimax requires an evaluation function that essentially quantifies the advantage of a game position for a player, we had to create our own interpretation of what makes a state favourable to a player, which we found to be very difficult. By design, sometimes a move giving one player an advantage on a small board ends up giving the other player even more advantage towards winning the whole game; while a less advantageous move may force your opponent into giving you a bigger advantage when it is your turn again. We realized that exploring all possible states and associate them in a graph was nearly impossible (even outside the scope of this project), so we had to rely on a subjective approach, where, for any given state, we perform a very limited search for possible future outcomes, identify/assign weights to select characteristics, apply biases to the predicted outcomes, and, finally, use the minimax strategy to choose the move with the adjusted outcome that is most likely to win the game.

Having spent more than a week tweaking the evaluation function, we believe it is now capable of resisting enough to play interesting and engaging games, not to mention that states in this game are also very difficult for an average human player to evaluate. Though, we do recognize that the algorithm can still be improved to produce better results, as, at the moment, it plays very defensively and lacks ambition to conclude a game when in obvious advantages (both we have attempted to solve but have not reached any satisfactory outcomes).

It is also worth noting that we understood, midway through the project, that it was no longer viable for us to implement multiple strategies for the computer-based opponent and do comparisons, which we had planned to do when we proposed this project; however, we consider our algorithm a combination of multiple strategies and methods, including minimax, depth-first graph traversal, randomization, and basic arithmetic, among others.

In general, we successfully chose a task that clearly benefited from Haskell's functional principles while being challenging at the same time. We implemented the game itself without much trouble, and, despite the recursive format of the game, we were able to design a satisfactory program to play against the user using the minimax strategy. We believe that further attempts can be made to create more intelligent computer programs for finding the best move for a given position, perhaps using alternative approaches. We also encourage a smarter implementation of the game mechanism to be explored, where, for example, draws are detected when no possible wins can be achieved, without the players having to play in all playable squares without any of them winning. This was not considered in this project because of its low probability and of the typical rules only defining draws as having no possible moves overall.

Links to code etc.

https://github.students.cs.ubc.ca/tchen66/cpsc312-project1