DRYing Up the Minmax Algorithm – the NegaMax Algorithm

The Minmax algorithm works great, especially with alpha-beta pruning. The only problem is that we have if and else branches in the algorithm that essentially negates each other.

As we know, in computer science, there is DRY code and WET code. DRY stands for Don't Repeat Yourself. WET stands for Write Everything Twice. When we write the same code twice, we double our chance of making a mistake while writing it. We also double our chances of each maintenance effort being executed in the future. Hence, it is better to reuse our code.

When implementing the Minmax algorithm, we always compute the utility of a node from the perspective of the AI player. This is why we have to have a utility-maximizing branch and a utility-minimizing branch in the implementations that are dual in nature. As we prefer clean code that describes the problem only once, we could get rid of this duality by changing the point of view of the evaluation.

Whenever the AI player's turn comes, nothing changes in the algorithm.

Whenever the opponent's turn comes, we negate the perspective. Minimizing the AI player's utility is equivalent to maximizing the opponent's utility.

This simplifies the Minmax algorithm:

def Negamax(state, depth, is_players_point_of_view):
    if depth == 0 or is_end_state(state):
        return utility(state, is_players_point_of_view)
    utility = 0
    for s in successors(state):
        score = Negamax(s,depth-1,not is_players_point_of_view)
    return score

There are necessary conditions for using the NegaMax algorithm; for instance, the evaluation of the board state has to be symmetric. If a game state is worth +20 from the first player's perspective, it is worth -20 from the second player's perspective. Therefore, we often normalize the scores around zero.

Using the EasyAI Library

We have already looked at the simpleai library, which helped us execute searches on pathfinding problems. Now, we will use the EasyAI library, which can easily handle an AI search on two-player games, reducing the implementation of the tic-tac-toe problem to writing a few functions on scoring the utility of a board and determining when the game ends.

To install EasyAI, type the following command in Jupyter Notebook:

!pip install easyAI

Note

You can read the documentation of the library on GitHub at https://github.com/Zulko/easyAI.

Activity 1.04: Connect Four

In this activity, we will practice using the EasyAI library and develop a heuristic. We will be using the game Connect Four for this. The game board is seven cells wide and seven cells high. When you make a move, you can only select the column in which you drop your token. Then, gravity pulls the token down to the lowest possible empty cell. Your objective is to connect four of your own tokens horizontally, vertically, or diagonally, before your opponent does, or you run out of empty spaces.

Note

The rules of the game can be found at https://en.wikipedia.org/wiki/Connect_Four.

1. Open a new Jupyter Notebook file.
2. Write the init method to generate all the possible winning combinations in the game and save them for future use.
3. Write a function to enumerate all the possible moves. Then, for each column, check whether there is an unoccupied field. If there is one, make the column a possible move.
4. Create a function to make a move (it will be similar to the possible move function), and then check the column of the move and find the first empty cell, starting from the bottom.
5. Reuse the lose function from the tic-tac-toe example.
6. Implement the show method that prints the board and try out the game.

   Note

   The solution for this activity can be found via this link.

The expected output is this:

Figure 1.29: Expected output for the game Connect Four