Basic Minimax Tic-Tac-Toe

basic minimax 1Making a computer play any type of game is difficult. You need to make it consider every element, every possible situation that could arise. Because of this, some games are considerably more complicated to program for than others. Chess, with its 8×8 board, dozens of individual pieces, and millions of possible moves, is more complex than Tic-Tac-Toe, which only has a 3×3 board, one type of action, and limited possible moves. For ease of programming, we will begin with Tic-Tac-Toe.

Like the game, our goal is simple; make a program that will play against a human player. We will design the program to try to win the game. However, if it can’t win, it will try to tie the game. To begin our planning, let’s look at a simple example.

basic minimax 2That wasn’t very complicated, but it’s good to start with simple cases. Let’s try another board.

basic minimax 3From these two examples, we now have two rules for how our program should behave:

  • If there is a move that will make you win, play there.

And if there is no winning move:

  • If there is a move that will block the other player from winning, play there.

Both of these rules have something in common. They require the program to analyze the board. Playing in the winning spot is impossible if you don’t know where that spot is. Let’s go back to the previous example. The image above only showed one of the possible actions we could have taken. It skips an important step; choosing the correct action. We have one arrow leading to one board, but what if we showed every possible move the computer could have made?

basic minimax 4This branching map demonstrates exactly what we want our program to do. When given a board, it should simulate every possible move that the computer could make, and give a score value to each option based on what the outcome of each branch is. We can use this same algorithm at any point on the board. Let’s continue this example tree.

basic minimax 5.pngDo you see what’s happened here? Using this simple system, we can break a winning Tic-Tac-Toe strategy down into a few basic steps.

  1. Simulate playing in each open space.
  2. Rank each of those possibilities based off of who wins. one for a program victory. zero for a tie or there still being open moves. Negative one for human victory.
  3. Choose the highest number available.

A program that follows these steps will be able to win many Tic-Tac-Toe games. However, there is still one big problem. Strategy. Our program blocks the opponent if they are about to win. But, it doesn’t plan ahead to stop unwinnable situations. Additionally, It doesn’t maximize winning. There is no method of making a board that will increase the likelihood of winning. All it does is stop itself from losing.

This version of our program isn’t completely non-functional, though. It acts like a human child playing the game. It stops itself from immediately losing, wins if it can, but has no plans for the future.

Click here to read about how to add strategy to this algorithm.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s