By: Jennifer Devitt on December 14th, 2016

# A Brief Introduction to Game Theory: The MiniMax Algorithm

**Artificial Intelligence**

**A Brief Introduction to Game Theory: The MiniMax Algorithm**

**Breaking Down Non co-operative Game Theory**

By definition, game theory is "the study of mathematical models of conflict and cooperation between intelligent rational decision-maker"^{1}. Where a rational decision-maker is someone who is trying to maximize their rewards. Non co-operative game theory implies that players work independently and are not assuming what the other player is doing^{2}.

**What is the MiniMax Algorithm**

The MiniMax algorithm is one approach to computing the best possible outcome by recursively generating all possible final states of a game(which can be represented as a tree, where the final states are the leaf nodes) while simultaneously keeping track of the current optimal node and comparing that to all other siblings of that node. Before exploring my example below we will need to make a few assumptions.

1.) Each level of the tree alternates between each players turn.

**Figure 1: **Visual representation of each players turn

2.)

- 1 = player 1 wins
- 0 = tie
- -1 = player 2 wins

3.) We are running the algorithm as the optimal strategy for player one. Therefore, If it is player 1's turn, they will choose the next state with the highest return. Alternatively, if it is player 2's turn, we will assume that they will always pick the next state with the lowest return. This is because we are running the algorithm for player 1 and the state with the lowest return is equal to the state with the highest return for the other player.

**Figure 2: **Path leads to tie

**Figure 3: **Path leads to loss

**Figure 4: **Player 2 chooses the lowest number

**Figure 5: **Path leads to a win

**Figure 6: **Path leads to a tie

**Figure 7: **Player 2 picks the state with the lowest number

**Figure 8: **Tie game: Player 1 picks the state with the highest number

Following the example images above if player 1 and player 2 both follow the optimal strategy, he/she can only tie at best. In other words this is considered a zero sum game. Of course, this result will only occur if both players are using the optimal strategy.

**Pseudocode **

function miniMax(board, player) {

if (player1) {

highestReturn = -2

for each possible move on the board {

board = makeMove(board)

result = miniMax (board, player2)

highestReturn = max(highestReturn, result)

}

return highestReturn

else { // player2

lowestReturn = 2

for each possible move on the board {

board = makeMove(board)

result = miniMax (board, player1)

lowestReturn = min(highestReturn, result)

}

return lowestReturn

**A Brief High Level Analysis of the Algorithm**

We can quickly analysis the pseudocode above by breaking it down. Although we did not define the min(), max(), and makeMove() functions we can assume that these functions have a constant runtime, or O(1). Therefore, they will not have an affect on the overall runtime of our miniMax algorithm. To analysis the runtime of this algorithm, we will take a look at the binary tree.There are two factors that will affect the big-oh notation of our runtime, the number of possible moves at each node and the depth of our binary tree. In this case at each node a player has 2 possible options and our tree has a depth of 3. This makes our runtime O(2^{3}-1). We can simplify this to O(2^{3}). Finally we can say for any game, the runtime of our miniMax algorithm is O(n^{m}), where n is equal to the number of moves per node and m is equal to the number of levels in our tree. As you can probably tell, this algorithm grows very quickly

**Wrapping Up**

Although, the miniMax algorithms computes the optimal strategy it is important to note that it has an extremely large big-oh bound. This wouldn't necessarily be an issue for games with relatively few possible states such as tic tac toe, but it certainly becomes an issue with games that have numerous possible states. For games with many possible states, like chess, it is important to optimize this algorithm by either adding a heuristic or stopping the recursive calls after a certain number of moves. This is often done by using a technique called alpha-beta pruning.

**References**

1.) Myerson, Roger B. (1991). Game Theory: Analysis of Conflict, Harvard University Press, p. 1. Chapter-preview links, pp. viiâ€“xi.

2.) Department of Computer Science and Engineering, IIT Delhi. N.p., n.d. Web. 07 Dec. 2016, https://www.cse.iitd.ernet.in/~rahul/cs905/lecture1.html.