An algorithm for solving complex problems in theory – minimax

Minimax is a method that helps to determine the optimal choice in a disadvantageous situation.

Today you will find an algorithm for solving complex problems in game theory – from theory to practice.

During the study of game theory in our last article, it was found out:

• Game theory is a key foundation, without which further steps become more difficult.
• Game theory is an arsenal of tools for making rational, thoughtful, and accurate decisions, as well as for understanding data.
• The game we are analyzing necessarily involves at least two participants. Each of them has their own interests and options for action.
• The decision is made from information about the actions of other participants.
• There are generally accepted rules that are available to everyone.

Most everyday situations can be considered from the point of view of game theory. Even casual conversations about a salary or a vacation spot are influenced by game theory.

Therefore, there is an algorithm that allows finding optimal solutions even in difficult situations. This algorithm is called the minimax rule.

Minimax: strategy

In game theory, the task of each player is to find a strategy that maximizes his profit.

Game theory can be divided into zero-sum and non-zero-sum games. A zero-sum game means that a win for one will be a loss for all the other players. Many classic games and life situations are zero-sum games. This means that each player seeks to improve his position by worsening the position of other players.

If a player understands that the actions of others can affect his position, he needs a strategy that reduces this influence and minimizes losses. For this, the minimax rule is used.

Minimax rule

To understand how the minimax rule works, you need to understand the logic of the players:

1. In some games, defeat is expressed by a number, such as a monetary loss after a game. In other cases, defeat simply indicates who won and who lost.
2. Every other player makes decisions that can increase your maximum loss. For example, due to its action, you can lose 10 or 500 points. The maximum possible loss in this case is 500 points.
3. The goal is to make decisions at every step that reduce this loss. In other words, even if the loss occurs, then not 500, but 10 – the minimum of the possible options.

The minimax rule defines a strategy that minimizes the maximum possible loss. The hallmark of such a strategy is as follows:

This is the best minimax strategy because the worst possible variant in it is much better than the worst possible variant in other strategies.

Algorithm in action

Consider the minimax algorithm using the example of a game of tic-tac-toe. To win, you need to make a line horizontally, vertically, or diagonally. Given this, we will create an algorithm for the second player walking:

1. The first player places a cross in any cell of the field. There are 9 cells in total, one is occupied, and 8 are left.
2. We sequentially consider all possible cells where a zero can be placed, and evaluate the situation – whether we win or lose. If it is not clear, we switch to a new situation and perform the same algorithm.
3. This process continues until all the cells are filled – we get a lot of possible options and branches.
4. For successful options, we add a certain number of points for each of our moves in a particular cell, and for losing options, we subtract the same amount.
5. After such calculations, we get an estimate for each of the 8 free cells.
6. Finally, select the cell with the highest scores for the next move and place the zero there.

So, we recursively consider all possible moves (or to a certain depth of nesting, if there are not enough resources), and evaluate the results for each cell. Thus, we choose the cell that best suits our strategy.

For those who want to create their own game, we invite you to programming courses from the GoMother IT school. Depending on the age of the child and the desired result, we will select the optimal programming language.

Minimax: How this principle works in real life

Imagine that there are three different grocery stores in a small town, and each of them seeks to maximize their profits. The goal is to get customers to choose his store. One logical solution might be to lower the prices of key products to attract customers. Customers who come for bread and milk can purchase other goods.

However, the seller is aware that competitors may do the same or offer other promotions and price cuts on other products. This means that the seller will have to react to maintain their leading position and retain the majority of customers. Consequently, competitors will also make their moves.

If the seller has sales data, relevant indicators, and figures, he can calculate several options for the development of the event.
ty with a certain depth, for example, 2-4 moves ahead, taking into account competitors. Then he analyzes the most common solutions and chooses those that bring the most results. This is the best step in the fight for customers.

This strategy is called the maximin algorithm. The point is to maximize the minimum possible gain.

Application in information technology

The minimax algorithm finds application in a wide range of games where the computer must make decisions that are optimal for it from the uncertain actions of the player. These can be both classic games, such as checkers or arcades, and applied cases: choosing the best deal, determining a behavioral model for successfully passing the selection, or acting in situations that cannot be foreseen in advance.

In the next section, we will test the minimax rule in practice – we will create a game of “tic-tac-toe” and teach the computer to choose the optimal moves. Follow the updates on our website and subscribe to our Instagram!