Tic-Tac-Toe AI

December 31, 2011


This came up as a way to test my programming knowledge, and as a proof-of-concept that I could build an unbeatable AI. One limitation I imposed to make this more challenging was that the program could not simply go through all of the relevant game possibilities and pick the best one (ie look some number of moves ahead), but rather use a formulaic method based on the current state of the board to pick its best move. It would create a probability matrix, with each unoccupied place on the board having a probability assigned based on a certain formula, which would involve for instance the number of own and opponent pieces in the same row/column/diagonal, and how many of those are next to each other.

The original AI was made in MATLAB and truly has no look-ahead; however certain patterns are pre-programmed, specifically first and second moves. The second AI, which was made in C++ and has a graphical interface, looks ahead one turn in certain cases, but other than that has no patterns pre-programmed. I believe both are unbeatable, with the second one being more aggressive than the first in winning the game if the human player makes a mistake. The second one will in fact attempt to set up a trap if it is possible (as a side effect of the AI logic and not specifically programmed in, which is pretty cool).

Second Version AI (C++)

Download binary zip file here, extract and run tictactoe.exe; instructions included. Download code files here.

First Version AI (MATLAB)

Download MATLAB function file here; run t() to use.