Course:CPSC312-2018-Ultimate-Tic-Tac-Toe
Ultimate Tic Tac Toe
Authors:
Guilherme Lameira de Almeida, Prayansh Srivastava, Mingyu Gao
What is the problem?
Ultimate Tic Tac Toe is a variation of Tic Tac Toe which is more challenging than regular Tic Tac Toe for a computer. The board consists of 9 small 3-by-3 boards, which together compose a large 3-by-3 board. So you technically play on 10 boards at a time. Players take alternating turns, and a player wins a small board just like regular Tic Tac Toe, by placing three of his symbols in a row. When a player wins a small board, they put their symbol in its position in the large board. The game ends when one of the players gets three symbols in a row in the large board, or in a tie if all squares have been exhausted. To make gameplay more interesting, a player must place their symbol in the small board that corresponds to the position in the small board of the previous move. More info can be found here.
What is the something extra?
Since the game deals with 10 boards simultaneously, it is no longer a simple problem that can be solved via a simple minimax algorithm, so we will be experimenting and creating an AI with different implementations and see which ones tend to win the most games.
What did we learn from doing this?
Haskell as a functional language, enabled us to test our game logic implementation and AI logic implementation seperately. It also allowed us to test our game starting from a pre-defined state and simulate a partially complete game, which we think would be a chore to do in other languages. We also learnt that making a completely pure application is a very tough thing to do!! And threading new features into our code requires a lot of refactoring, because functional programming does not preserve state, making the initial part of a project easy to design but tough to improve on in the future.
Haskell is a great language for abstracting out games. Our initial goal was to make a working implementation of the game for a human vs simple bot, and at first we didn't think that we were going to be able to create an interface for a bot vs bot game, or a human vs human game. But once that was achieved, it was clear that this was indeed possible through more abstraction, and our focus shifted onto creating Players that can play the game autonomously. You will see that we created multiple autonomous players that can simulate playing the game, or a tournament if you want.
We ended up creating multiple AI implementations (atleast one per group member), and we found that the Out-of-the-box Minimax algorithm is WAY TOO SLOW! The minimax tree was way too big for us to compute, so after some deliberation, we decided that a depth limited minimax algorithm with some heuristic is the best way to proceed. Our best bots ended up being `smart_player`, `my_mm_player` and `gui_player`.
In conclusion, we did realize that Ultimate Tic Tac Toe unlike its predecessor is not a very simple game to play, and requires a series of complex logical actions. And the best way to learn more about a game is by making an AI representation of a player (it does make you think of how the game works). As a final note, I would like to invite you all to write a Player, to pit against our AI implementations.