Tic Tac Toe, 5x5

A quick game in 3D with min/max AI


Project Details


Delivered To Dr. Shengli Yuan
Date 12/16
Skills Unity, C#, UML, and Object Oriented design
Codebase GitHub.com

Project Description

Students tasked with developing a simple 5x5 Tic Tac Toe game. Each project needed to include: Player vs. Player, and Player vs. AI with three difficulty modes. All documentation related to the design, various presentations of the design, and the implementation were graded. Upon completion of the project, students performed a head to head matchup of their AI algorithms.

 

In this project, my team agreed to exceed the requirements by building the game in Unity. This allowed us to greatly expand the graphical components beyond what our peers could perform. Furthermore, I implemented a min/max AI on the 5x5 grid with optimizations to conform to time constraints. The entire project was done with portability in mind, so AI calculations are performed within the Unity framework instead using external non-portable code.

 

This project was the only project in 3D, and also the only project to include audio elements. Furthermore, the AI algorithm tied for first place with one win, one loss, and one draw.

Min/Max AI

With min/max, an AI attempts to find all possible combinations by recursively taking turns between itself, and an imaginary player. Each recursive turn, the AI then determines if the opponent or itself would win. It then tallies up each combination and assumes that any player would be rational and attempt to secure any victory.

 

This is very strong, but also very slow.

So Let’s Make it Better

In an unoptimized 5x5 grid, the first few turns would often take 5 or more minutes. However, upon inspection, I realized that there are combinations of spaces that will rarely result in a victory, and spaces that result in a victory only under certain conditions.

In the first turn, the AI will ignore all boarder spaces, and will always place itself either the optimal position (center) or secondary positions (top/bottom/left/right). Then, in the second turn, it determines any diagonal, vertical, and horizontal rows along any pieces on the board, and adds that to the innermost 9 squares for analysis. This results in a search tree that is orders of magnitude smaller than a full search. Additionally, the AI will search fewer turns into the future in the beginning of the game, and deeper towards the end to prevent stalemates.

Notice green is the AI, and orange is the opponent.

The result? These heuristics enable the AI to move quickly on the first turn, analyze only relevant squares in turns 2, and 3, and prioritize adding pieces that would secure its victory through ever increasing depth searches. These searches automatically become smaller as pieces are played therefore the time component stays relatively the same.

Is it scaleable?

During the design phase, I wanted to ensure the theory behind the AI playing the game was sound. I wanted to create a system where, given additional computing power, the game could be scaled to larger grids.

Heuristics per cell to use as a tie-breaker

So, the AI, the board, and the cells are all separate entities. Cells are configured such that adding another column or row is acceptable.

In fact, in the original implementation of the Unity scene, the board configured the cell linkings on its own. However, this dynamic linking resulted in performance losses at the start of a match so it was replaced by a static configuration. This same system, could be incorporated into a Unity Editor tool to allow another developer to create new rows or new columns and have the editor perform the linking by name. The victory condition of 5 in a row is already optimized, but it could be altered to search recursively by a specified depth. Lastly, every cell is given a heuristic value, the designer of the new board would need to modify the existing, and new cell values.

With those three changes any digital board size is feasible.

Like What You See?