When AI plays Tic Tac Toe

I remember the first time that I was playing Tic Tac Toe with a non-human, I really had no idea how it works or how it knows what moves to make to prevent me from winning the game.

My answers to this question were hilarious at the time; but then, after some time, I found that this is just a simple algorithm which never led me beat it.

The algorithm is called MiniMax.

MiniMax

MiniMax isn’t just for Tic Tac Toe game, in fact it’s a very cool algorithm which we can use in any match where there is an opponent in front of you and is acting against you.

The theory behind the MiniMax algorithm is to predict the opponent moves or thoughts, which are obviously beneficial for her/him and then choosing the best move based on your prediction.

The best move should be both to your advantage and to your rival’s disadvantage.

Tic Tac Toe

The first step of the process is to predict all possible actions after a player makes any moves.

We continue this process till the game overs. You’ll see it makes a recursive function.

To understand this picture better, at first we should specify a score for each position of the game board.

-1: O wins
0: No one wins
+1: X wins

And then, please consider player O and player X as min player and max player.

1. Min player: Chooses the minimum score
2. Max player: Chooses the maximum score

For instance if we have 3 possible options on the board which the scores are [0,-1,-1] X player will choose 0 and O player will choose one of the -1 options.

Now, that we know the final score of each action on the board (by continue filling it out) we can easily choose between the scores based on which player is acting as AI player.

If you’re interested in this algorithm and Tic Tac Toe game, you can take a look at This GitHub Repo which I covered MiniMax algorithm in an interesting Tic Tac Toe game, in both JavaScript and Python languages.

原文链接：When AI plays Tic Tac Toe