Implementing Minimax Tree Search

Game playing is one way to learn machine learning strategies. A most game playing bots involve some searching mechanism. It’s how the bot can “see” which move can result in a favorable outcome down the line.

Lets learn about minimax, a useful technique to build an AI to compete on simple games.

Single Player Tree Searching

Lets play a little game. The object of the game is to end up with the highest number.

For a single turn, one player game the choice is simple.

You go right, end of with a score of 10! That’s the highest possible score in our little game.

Lets make it a little more complicated. Our game now has two turns, what do you choose?

On your first turn, if you make the same decision (pick 10), that will leave you with bad options on your second turn (2 or 3).

To achieve the highest score, you need to pick 1 on your first turn in order to be able to pick 20 on your second turn.

One way to model this, is to start at the bottom and choose the max at each node. If we do that across our entire tree, we determine our max score (20) and which decisions to make (left, left).

Two Player Tree Searching (Minimax)

What if we introduced another player into this game? Now two players are competing to against each other. With a small tweak in the rules.

• Player 1 wins if a positive number is chosen.
• Player 2 wins if a negative number is chosen.
• A tie occurs if 0 is chosen.
• Players alternate turns with Player 1 going first.

Lets take the following game.

Player 1 (P1) makes the first choice, then Player 2 (P2) has a turn, and finally Player 1 makes the final pick.

Player 1 wants positive numbers, so they’re looking to maximize their score.

Player 2 wants negative numbers, so they’re looking to minimize their score.

That’s where the term minimax comes from, from players wanting to either minimize or maximize their score.

How could this game play out? If each player choose the best available option to them at the time, the optimal game outcome is 7, which means Player 1 wins!

Lets model this game as well.

Again, Player 1 attempts to maximize their score, Player 2 attempts to minimize their score.

Player 1 goes left, Player 2 goes left, and finally Player 1 goes right landing on a score of 7.

Programming Minimax

Lets implement a minimax search in python!

We first need a data structure to hold our values.

We create a Node class, it can hold a single value and links to a left and right Node.

Then we’ll create a Choice class that represents the players choice.

Next we’ll initialize a tree with the values from the two player game we modeled above.

You’ll notice on line 41, I’m printing the tree. Which outputs the following:

The print_tree function is available on the github repo.

We’ll solve this by coding a recursive depth first search algorithm. The main concerns we want to keep in mind are:

1. We need to keep track of which players turn it is, I’m using the is_max to track that.
2. We need to know when to stop our search, in recursion that means we need some base cases.
3. We want to explore our whole tree. We need some comparison logic to determine which sub tree we will choose to explore.

Our base case will be when our node no longer has any children, we just return the value of the node.

In order to explore our whole tree, we’ll call minimax on each sub tree in our node.

Making sure to reverse is_max because the players alternate turns.

Finally, we compare the results. If we’re maximizing we take the max results, then if we’re minimizing we take the minimum results.

Lets create a little simulator to play our game for us.

Running this outputs the following:

• Moving left to node with value -2
• Moving left to node with value 3
• Moving right to node with value 7
• Game ends with a score of 7

Congrats! We’ve correctly demonstrated how to use minimax to optimally solve a simple two player game.

Parting Thoughts

This game is about as simple as it gets. But searching is an integral part to most automated game playing bots. It’s how bots can “see” into the future.

For a challenge, see if you can use minimax to build a tic tac toe playing bot.

As you can imagine, with complicated games (Chess and Go) searching has its limitations due time and memory constraints. Further strategies such as alpha-beta prune and Monte Carlo simulation can help in those cases.

You might have noticed that my base case will only work with nodes that have two or 0 child nodes. The minimax in the git repo will contain code to handle that condition.

Originally published at thesharperdev.com.