# Minimax Algorithm

## Game Trees

The Minimax algorithm is often used for making AI's for turn-based games. It relies on the use of a type of **game tree,** which maps out all of the possible moves that players can make.

In the tree, there are two types of nodes: **maximizing nodes** and **minimizing nodes.** The max-nodes represent **you**- you want to make your position as advantageous as possible (maximizing your score). The min-nodes represent **your opponent-** they want to make you do as poorly as possible (minimizing your score).

The scores themselves are generated using a **heuristic function** that assesses the current game state and returns a number based on which player has an advantage, and to what extent. **This heuristic is totally up to you to figure out and has very few constraints.** There are a couple rules, however:

* Heuristic functions must return **positive values** if you're doing better than your opponent, and **negative values** if your opponent is doing better.
* Heuristic functions must return the **maximum value** for a state in which you won, and the **minimum value** for a state in which your opponent won.

In most games, you and your opponent will take turns, so each layer will alternate node type, like this:

![](https://628945320-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M6l_SlXhV46y96GQwmG%2F-M79jH3BVJv9U2RCyP3T%2F-M79p11PSo3eIuRMU3Dy%2Fimage.png?alt=media\&token=a0267fa8-a739-42ac-b8c7-8116eb8a42ba)

In most games, this tree will spiral out of control because there are far too many nodes to possibly analyze (maybe even an infinite number)! Therefore, we need to set a **depth** to stop searching and compute a heuristic. For example, if the depth is **3**, it'll look something like this:

![](https://628945320-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M6l_SlXhV46y96GQwmG%2F-M79jH3BVJv9U2RCyP3T%2F-M79s-AJjWGIzVkqU1T3%2Fimage.png?alt=media\&token=dbffdce9-d3ec-4aeb-83fe-86dae1c05328)

Now that the tree has bottomed out at the heuristic layer, we can start going back up to figure out which move we should make! The rules are simple: **min-nodes take the smallest of the values** while **max-nodes take the largest of the values.** Here's the first layer, for example:

![](https://628945320-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M6l_SlXhV46y96GQwmG%2F-M79jH3BVJv9U2RCyP3T%2F-M79sHNTqGD7ZE0i-8ZR%2Fimage.png?alt=media\&token=96cadd5d-a3fb-42fd-8ef7-8e3ce27f6028)

Here's the entire tree filled out:

![](https://628945320-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M6l_SlXhV46y96GQwmG%2F-M79jH3BVJv9U2RCyP3T%2F-M79te9yiYvp5gxDXnvQ%2Fimage.png?alt=media\&token=d8c00d42-7498-4963-bc00-d3755fc3053f)

And here's the minimax algorithm in pseudocode format:

```python
def minimax_value(s: MinimaxNode):
    if is_terminal(s):
        return s.value
    elif s.player == Maximizing:
        return max(minimax_value(c) for c in s.children)
    elif s.player == Minimizing:
        return min(minimax_value(c) for c in s.children)
```

## **Alpha-Beta Pruning** 

We can make our tree **even more efficient** by simply ignoring all of the branches that will lead to results that will **never be chosen.** Here, we'll assume that **both players play optimally** (choose the best move for their particular node).

In the example above, we can see that the 7 on the right will **never need to be visited** because we **already know that 5 will be chosen.** 

In order to do this, we'll introduce two additional parameters, **alpha** and **beta.** Here are the rules:

* **Alpha** starts out as **negative infinity** and is set by **max nodes** to their current value.
* **Beta** starts out as **positive infinity** and is set by **min nodes** to their current value.
* A node **passes its alpha and beta values** onto its children.
* If **alpha is greater than beta (**$$\alpha \ge \beta$$**),** the branch will be **pruned** (no longer visited).

Here are the step-by-step instructions on how to process a node:

1. Copy the alpha and beta values from the parent node. (If no parent node exists, then initialize alpha to negative infinity and beta to positive infinity.
2. For every branch:
   1. Recursively process the branch.
   2. Update the current alpha/beta value depending on the value of the branch after processing. (MaxNodes can only update alpha, and MinNodes can only update beta.)
   3. If $$\alpha \ge \beta$$**,** then prune the rest of the branches (stop this loop).
3. Set the value of this node to the biggest (MaxNode) or smallest (MinNode) value seen.

The pseudocode for alpha-beta pruning is as follows:

```python
```

This is a pretty tough concept to grasp, and that's why I've illustrated how it works below. Read on!

## A Story of Minimax Nodes: An Intuitive Understanding

Minimax is quite difficult to understand just by studying its rules. In order to really know what's going on, we need to know why we have all of these rules and what everything represents. Here's how I think about it:

![](https://628945320-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M6l_SlXhV46y96GQwmG%2F-M6wpsYq7BUWTxSFoQYx%2F-M6wqZqsa4tGj4bK0N5h%2Fimage.png?alt=media\&token=3474cb97-2803-43e0-80e2-78623ca99aa8)

![](https://628945320-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M6l_SlXhV46y96GQwmG%2F-M6wpsYq7BUWTxSFoQYx%2F-M6wqeI2aXNVuu67FuwY%2Fimage.png?alt=media\&token=87078482-925f-4be8-b3a3-58cd9522656a)

![](https://628945320-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M6l_SlXhV46y96GQwmG%2F-M6wpsYq7BUWTxSFoQYx%2F-M6wqq_VUdo3nh5CaeM9%2Fimage.png?alt=media\&token=1caa680f-9bbc-4e58-9809-0723366ed4b9)

![](https://628945320-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M6l_SlXhV46y96GQwmG%2F-M6wpsYq7BUWTxSFoQYx%2F-M6wqu3BSCIJRKOBfEci%2Fimage.png?alt=media\&token=f16ce373-e8d7-4d41-82f7-b15074873467)

![](https://628945320-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M6l_SlXhV46y96GQwmG%2F-M6wpsYq7BUWTxSFoQYx%2F-M6wr4Rfp2oExSESFN9H%2Fimage.png?alt=media\&token=cf7b4ec8-4d16-4e3a-8236-f4ce42e5928c)

![](https://628945320-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M6l_SlXhV46y96GQwmG%2F-M6wpsYq7BUWTxSFoQYx%2F-M6wr7jZhJym0mvXqecm%2Fimage.png?alt=media\&token=72e46c1b-257a-4013-b4d7-8dbe107265e5)

![](https://628945320-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M6l_SlXhV46y96GQwmG%2F-M6wpsYq7BUWTxSFoQYx%2F-M6wrB2UdqjGVHAXv7WV%2Fimage.png?alt=media\&token=fdd24f89-ddb5-4e11-b396-b017852231fb)

![](https://628945320-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M6l_SlXhV46y96GQwmG%2F-M6wpsYq7BUWTxSFoQYx%2F-M6wrIFtxIDJJbhlWjNh%2Fimage.png?alt=media\&token=82c74ff1-14ac-429d-afc7-b8e11571c7be)

*NOTE: The 5's in the above image should all be 7's. This will be corrected soon (tm).*

## Practice Problems

{% tabs %}
{% tab title="Question 1" %}
Here's a tree. Figure out:

* What values each of the nodes report
* Which branches are pruned
* The alpha and beta values at each visited node

![](https://628945320-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M6l_SlXhV46y96GQwmG%2F-M6ztweNtGH2bXL1PzJX%2F-M6zxhI6kxXw8ZMG0OHx%2Fimage.png?alt=media\&token=24139cad-d559-4449-b3c0-98384350659e)
{% endtab %}

{% tab title="Q1 Answer" %}
Here's my answer! The green arrows denote the order in which the nodes are visited. Note that the branches are pruned every time **alpha is greater than beta.** 

![](https://628945320-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M6l_SlXhV46y96GQwmG%2F-M6ztweNtGH2bXL1PzJX%2F-M6zxusxAxi9_uU53Vyr%2Fimage.png?alt=media\&token=30a40cfd-376c-4b95-b6c6-33f1c7eee881)
{% endtab %}
{% endtabs %}

This was just an ordinary problem and **might not be enough to ensure that you fully understand minimax trees**! Here are some checks you can do to ensure that your understanding is strong:

* Figure out what the tree returns and prunes intuitively *without* finding any alpha or beta values.
* Make your own minimax tree problem like the one above and solve it. Are you confident in your answer (since no answer key exists)?
* Make a minimax tree that's missing some values, and try to find all possible values that fit in there such that the branch will become pruned.
* Implement the minimax algorithm in Java.


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://cs61b.bencuan.me/algorithms/minimax.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.