| Summary | In this assignment students extend a Tic Tac Toe program to Ultimate Tic Tac Toe and implement a different search strategy than the example code. |
| Topics | Search algorithms, adversarial search, Monte Carlo algorithms |
| Audience | This assignment is intended for an Introduction to AI course, when adversarial search algorithms are discussed. |
| Difficulty | Most junior/senior undergrad and graduate students can complete this in a week. Depending on the assignment objectives, studens could be asked to extend a normal tic-tac-toe implementation and include AI, or start from a ultimate-tic-tac-toe program and add AI. |
| Strengths | The Ultimate Tic Tac Toe game is a simple extension to the widely-known Tic Tac Toe game. Ultimate Tic Tac Toe is not known to many US students yet is easy to understand, with non-trivial game strategy. In-class example code can be used and extended for the game, making implementation easier and allowing more time to concentrate on different search algorithms. Students with a deep programming background can explore more complex algorithms if they choose. No extra Python modules are necessary. |
| Weaknesses | Students must be comfortable with Python. The UI for the game is text-based, but usable and usable on any Python system. |
| Dependencies | Students must understand 2-ply game playing search algorithms. The current example files and solution are in Python and run in Python 2.X or 3.X. |
| Variants | Other search algorithms could be included for student implementation. The speed in which a move is found could be tracked and points could be given appropriately. A student tournament system could be used which pits different student implementations against each other, with the number of wins and total time tracked. This is possible if students start from the ultimate-tick.py file and are asked to modify the getAIMove function. If students have time, they could implement multiple search strategies and analyze their performance. |
During the discussion of 2-ply game AI agents, various search algorithms are discussed in class. A motivating and simple game is tic-tac-toe. The tick.py game is built in class with student assistance as a demonstration of a simple game and AI. Students are then asked to take what was done in class and extend it to implement Ultimate Tic Tac Toe and modify it to implement another search strategies. Students could be provided with ultimate-tick.py which implements the game and its rules, with a task of implementing some AI strategy.