Implementing Minimax Tree Search
Tags: python, machinelearning
Published: 2020-04-26 00:54:48

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.
![Single Turn Game](https://dev-to-uploads.s3.amazonaws.com/i/g4y4xsoxfwwqveztatfo.png)
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?
![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/bzcb2mdvx3wcbvjxs50y.png)
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).
![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/nzmcon4xr805jtj9uk8h.png)
## 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.
![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/x3n9p8liibugdjp3b5wh.png)
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.

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/kb27tpmqo5c681mveomq.png)

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.
{% gist https://gist.github.com/morgankenyon/b3c7bf0200053d750c9ea36662fdf2b4 %}

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.
{% gist https://gist.github.com/morgankenyon/0e7d1a24533376e5bfec33aeeeffce82 %}
Next we’ll initialize a tree with the values from the two player game we modeled above.

{% gist https://gist.github.com/morgankenyon/6db980f6091eb31d72a47ef998a8e86d %}
You’ll notice on line 41, I’m printing the tree. Which outputs the following:
![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/sy65snhc3yrhjjmw4exk.png)
*The `print_tree` function is available on the [github repo](https://github.com/morgankenyon/RandomML/blob/master/src/minimax.py#L15).*

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.
1. We need to know when to stop our search, in recursion that means we need some base cases.
1. 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.

{% gist https://gist.github.com/morgankenyon/a9b17aab0836f9401342dd900cbeefec %}

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

{% gist https://gist.github.com/morgankenyon/aed7be3d69ee78aba838114b6eed950b %}

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.

{% gist https://gist.github.com/morgankenyon/e77f491d0a6a07088d47c749d7e215f1 %}

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

{% gist https://gist.github.com/morgankenyon/b86e611fc6db5666327f3370c2c78831 %}

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](https://github.com/morgankenyon/RandomML/blob/master/src/minimax.py) will contain code to handle that condition.

*Originally published at [thesharperdev.com](https://thesharperdev.com/implementing-minimax-tree-search/).*