Project Abstract

I have always been interested in developing various AI solutions for video games. This project is my first timid attempt at such a task, using traditional algorithms like MCTS and Minimax to solve a board game. In the modern day, despite Machine Learning models taking the front pages of AI development, I believe there is still good room for determenistic algorithms, especially in the environments where the quality of a decision is secondary to speed and flexibility of said decision, like mobile gaming that constitutes a huge portion of todays video game market. As such, I have implemented a game called Ultimate Tic Tac Toe, simple rules but notoriously complicated for AIs to solve due to unintuitive move coupling quality. I have implemented and tested my own optimised implementations of Alpha Beta Pruning and Monte Carlo Tree Search with handwritten heuristics, as well as an interactable demo for the game, allowing human player to face off against one of these algorithms. As for analysing efficiency of these algorithms in solving the game, I have run hundreds of simulations where I faced these algorithms off against each other as well as against a random AI opponent to assess the win rates, memory requirements on run-time, time and processing needs to compete with each other. While I have successfully achieved these goals, I cannot call my project a success due to my general failure to optimise MCTS to the level I wanted to be able to compete with Alpha Beta Pruning. Additionally, I failed to implement my version of reinforcement learning agent in time to compete against my algorithms, which could have provided additional reference point to the efficiency of my algorithms and their ability to train the learning agent. All in all, I believe I still managed to produce one of the best AI algorithms to solve the particular game of Ultimate Tic Tac Toe.

Keywords: Artificial Intelligence, Monte Carlo Tree Search, Minimax

 Conference Details

Session: Poster Session B at Poster Stand 22

Location: Sir Stanley Clarke Auditorium at Wednesday 8th 09:00 – 12:30

Markers: Ulrich Berger, Thomas Reitmaier

Course: BSc Software Engineering FA, 3rd Year

Future Plans: I’m looking for work