In this lesson, you'll learn how to use the minimax algorithm with complicated games like Connect Four.

Advanced Minimax

Great work! We've now edited our `minimax()` function to work with games that are more complicated than Tic Tac Toe. The core of the algorithm is identical, but we've added two major improvements:
* We wrote an evaluation function specific to our understanding of the game (in this case, Connect Four). This evaluation function allows us to stop the recursion before reaching the leaves of the game tree.
* We implemented alpha-beta pruning. By cleverly detecting useless sections of the game tree, we're able to ignore those sections and therefore look farther down the tree.

Now's our chance to put it all together. We've written most of the function `two_ai_game()` which sets up a game of Connect Four played by two AIs. For each player, you need to call fill in the third parameter of their `minimax()` call.

Remember, right now our evaluation function is using a pretty bad strategy. An AI using the evaluation function we wrote will prioritize making sure its pieces are the top pieces of each column.

Do you think you could write an evaluation function that uses a better strategy? In the project for this course, you can try to write an evaluation function that can beat our AI!


Review

By adding the `depth` parameter to our function, we've prevented it from spending days trying to reach the end of the tree. But we still have a problem: our evaluation function doesn't know what to do if we're not at a leaf. Right now, we're returning positive infinity if Player 1 has won,  negative infinity if Player 2 has won, and `0` otherwise. Unfortunately, since we're not making it to the leaves of the board, neither player has won and we're *always* returning `0`. We need to rewrite our evaluation function.

Writing an evaluation function takes knowledge about the game you're playing. It is the part of the code where a programmer can infuse their creativity into their AI. If you're playing Chess, your evaluation function could count the difference between the number of pieces each player owns. For example, if white had 15 pieces, and black had 10 pieces, the evaluation function would return `5`. This evaluation function would make an AI that prioritizes capturing pieces above all else. 

You could go even further &mdash; some pieces might be more valuable than others. Your evaluation function could keep track of the value of each piece to see who is ahead. This evaluation function would create an AI that might really try to protect their queen. You could even start finding more abstract ways to value a game state. Maybe the position of each piece on a Chess board tells you something about who is winning.

It's up to you to define what you value in a game. These evaluation functions could be incredibly complex. If the maximizing player is winning (by your definition of what it means to be winning), then the evaluation function should return something greater than 0. If the minimizing player is winning, then the evaluation function should return something less than 0.

Evaluation Function

By writing an evaluation function that works on non-leaf game states, we can stop the recursion early. But in a perfect world, we'd still want to reach the leaves of the tree. In order to traverse farther down the tree without dramatically increasing the runtime, we can implement a technique called alpha-beta pruning.

The core idea behind alpha-beta pruning is to ignore parts of the tree that we know will be dead ends. For example, consider the gif on this page. When determining the "value" of the node labeled E, we can stop looking at possible moves as soon as it discovers the `8` node. 

We know that B will only consider values less than or equal to `5`, and E will only consider values greater than or equal to `8`. We know that node B will never care about E's value and we can stop looking through E's moves.

<img src = "https://content.codecademy.com/courses/learn-knn/number_line.svg" alt = "A number line showing B will only consider numbers lower than 5 and E would only consider numbers greater than 8.">

Similarly, we can prune a large section from the right half of the tree. There comes a point where node A will only consider values greater than or equal to `5` and node C will only consider values `3` and below. We can stop looking at all of the C's children because we know they will never be relevant.

In the next lesson, we'll implement alpha-beta pruning, but for now, take the time to study the gif on this page to understand how alpha-beta pruning works conceptually.

Alpha-Beta Pruning

Alpha-beta pruning is accomplished by keeping track of two variables for each node &mdash; `alpha` and `beta`. `alpha` keeps track of the minimum score the maximizing player can possibly get. It starts at negative infinity and gets updated as that minimum score increases.

On the other hand, `beta` represents the maximum score the minimizing player can possibly get. It starts at positive infinity and will decrease as that maximum possible score decreases.

For any node, if `alpha` is greater than or equal to `beta`, that means that we can stop looking through that node's children.

To implement this in our code, we'll have to include two new parameters in our function &mdash; `alpha` and `beta`. When we first call `minimax()` we'll set `alpha` to negative infinity and `beta` to positive infinity.

We also want to make sure we pass `alpha` and `beta` into our recursive calls. We're passing these two values down the tree.

Next, we want to check to see if we should reset `alpha` and `beta`. In the maximizing case, we want to reset `alpha` if the newly found `best_value` is greater than `alpha`. In the minimizing case, we want to reset `beta` if `best_value` is less than `beta`.

Finally, after resetting `alpha` and `beta`, we want to check to see if we can prune. If `alpha` is greater than or equal to `beta`, we can `break` and stop looking through the other potential moves.

Implement Alpha-Beta Pruning

The first strategy we'll use to handle these enormous trees is stopping the recursion early. There's no need to go all the way to the leaves! We'll just look a few moves ahead.

Being able to stop before reaching the leaves is critically important for the efficiency of this algorithm. It could take literal days to reach the leaves of a game of chess. Stopping after only a few levels limits the algorithm's understanding of the game, but it makes the runtime realistic.

In order to implement this, we'll add another parameter to our function called `depth`. Every time we make a recursive call, we'll decrease depth by `1` like so:

```py
def minimax(input_board, minimizing_player, depth):
  # Base Case
  if game_is over(input_bopard):
    return ...
  else:
    # …
    # Recursive Call
    hypothetical_value = minimax(new_board, True, depth - 1)[0]


```

We'll also have to edit our base case condition. We now want to stop if the game is over (we've hit a leaf), or if `depth` is `0`.


Depth and Base Case

In our first lesson on the minimax algorithm, we wrote a program that could play the perfect game of Tic-Tac-Toe. Our AI looked at all possible future moves and chose the one that would be most beneficial. This was a viable strategy because Tic Tac Toe is a small enough game that it wouldn't take *too* long to reach the leaves of the game tree. 

However, there are games, like Chess, that have much larger trees. There are 20 different options for the first move in Chess, compared to 9 in Tic-Tac-Toe. On top of that, the number of possible moves often increases as a chess game progresses. Traversing to the leaves of a Chess tree simply takes too much computational power.

In this lesson, we'll investigate two techniques to solve this problem. The first technique puts a hard limit on how far down the tree you allow the algorithm to go. The second technique uses a clever trick called pruning to avoid exploring parts of the tree that we know will be useless.

Before we dive in, let's look at the tree of a more complicated game &mdash; Connect Four!

If you've never played Connect Four before, the goal is to get a streak of four of your pieces in any direction &mdash; horizontally, vertically, or diagonally. You can place a piece by picking a column. The piece will fall to the lowest available row in that column.
