Game playing has been a fixture in the development of artificial intelligence ever since it emerged as an academic discipline in the 1950s.
In fact, the first working AI programs were written in 1951 at the University of Manchester to play the board games checkers and chess.
The latter remains a benchmark for AI research today, with researchers at DeepMind making headlines in 2018 when their AlphaZero chess AI defeated the world's reigning best chess player, an AI called Stockfish.
Games like chess make appealing settings for AI development, with perfect information and no element of randomness.
Far less attention has been given to developing AI for contemporary strategy board games such as Settlers of Catan, Ticket to Ride, or Race for the Galaxy, despite their ever-increasing popularity.
Yet the relative messiness of these games (multiple players, plenty of chance and uncertainty) makes them an intriguing, and potentially productive, testbed for modern AI algorithms.
Fortunately, this opportunity has not been wholly ignored by the AI research community.
In this comps project you will explore this literature and conduct your own experiments applying AI algorithms to a modern board game.
In this project you will explore applications of game-playing artificial intelligence to a contemporary board/card game. In particular, you will
Study the existing literature on AI and board games.
In addition, you will do background reading on major types of game-playing AI.
Select a particular type of game-playing AI algorithm to focus on, and a board or card game to apply it to.
Develop a simulator for your chosen game, starting with a simplified subset or varient.
Alternatively, you can use an existing, publically available simulator if one exists for your chosen game.
A few examples of existing simulators are listed below.
Implement your chosen type of game-playing AI.
Evaluate the performance of your algorithm.
In this project, you'll be working AI algorithms. You don't need to have previous experience with this kind of work, but you should know it tends to involve significant amounts of both theory and implementation. Some courses that may be useful but are not required are Algorithms, Advanced Algorithms, Artificial Intelligence, Data Mining, Computational Models of Cognition, Data Science, Probability, or Linear Algebra.
Some existing simulators for developing board game AI:
de Mesentier Silva, F., Lee, S., Togelius, J., & Nealen, A. (2017). AI-based playtesting of contemporary board games. In Proceedings of the 12th International Conference on the Foundations of Digital Games (pp. 1-10). [pdf]
Eger, M., & Martens, C. (2019, October). A Study of AI Agent Commitment in One Night Ultimate Werewolf with Human Players. In Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment (Vol. 15, No. 1, pp. 139-145). [pdf]
Szita, I., Chaslot, G., & Spronck, P. (2009, May). Monte-carlo tree search in settlers of catan. In Advances in Computer Games (pp. 21-32). Springer, Berlin, Heidelberg. [pdf]
Woolford, M., & Watson, I. (2017, June). SCOUT: a case-based reasoning agent for playing race for the galaxy. In International Conference on Case-Based Reasoning (pp. 390-402). Springer, Cham. [link]