Tic Tac Toe - Creating Unbeatable AI

Introduction to Minimax Algorithm

In today’s article, I am going to show you how to create an unbeatable AI agent that plays the classic Tic Tac Toe game. You will learn the concept of the Minimax algorithm that is widely and successfully used across the fields like Artificial Intelligence, Economics, Game Theory, Statistics or even Philosophy.

AI X vs Human O

Table of Contents

• About Tic Tac Toe
• Minimax algorithm
• Unbeatable Tic Tac Toe AI
• Bonus
• What’s next?

Before we go into the AI part, let’s make sure that we understand the game.

About Tic Tac Toe

Tic-tac-toe (also known as noughts and crosses or Xs and Os) is a paper-and-pencil game for two players, X and O, who take turns marking the spaces in a 3×3 grid. The player who succeeds in placing three of their marks in a horizontal, vertical, or diagonal row wins the game.

I recommend you to play the game yourself, feel free to check out my iOS Tic Tac Toe app.

‎Beat me XO

In order to solve Tic Tac Toe, we need to go deeper than just to think about it as a game where two players place X’s and O’s on the board. Formally speaking, Tic Tac Toe is a zero-sum and perfect information game. It means that each participant’s gain is equal to the other participants’ losses and we know everything about the current game state.

In a two-player (A vs B) game, if player A scores x points (utility units), player B loses x points. Total gains/losses always sum up to 0.

With that in mind, let’s proceed to the Minimax algorithm that’s suited for such cases.