A common complaint in video games is that AI opponents make bad decisions. That's why in some cases they directly cheat, but sometimes the opposite happens, and they present very effective strategies in games we can consider "simple". One of the reasons is the application of the Minimax theorem, an algorithm whose goal is to minimize the maximum expected loss in two-player games with perfect information for both sides.
Many games hide information from participants as part of their mechanics. Think of the "fog of war" in classic games (StarCraft and Civilization come to mind). That resource allows AI to conjure up 20 or 30 units by magic without you knowing (among other things), and its elimination is an essential step, either by sending units to explore, or developing technologies that cancel its effect (like Satellites in Civ).
But what happens when information is perfect? How does an AI behave when there is nothing to hide, and all elements of the game are known from the start? One of the many possibilities for the developer is implementing the Minimax theorem. The official description tells us about a "decision method to minimize the maximum expected loss", which may seem simple on the surface, but deserves a deeper exploration.
Minimax Theorem: Optimal Solutions for Zero-Sum Games
The BitBoss channel does an excellent job summarizing the Minimax algorithm, and the best part is that it takes less than four minutes. Basically, Minimax works in zero-sum games, meaning our gain or advantage becomes a loss for the opponent. Chess is a classic example of a zero-sum game with perfect information, but the video takes a simpler route, using tic-tac-toe as a reference.
Each phase of the game can be defined with a number, positive for one player, and negative for the other. The strategy of the Minimax algorithm seeks to select the best available move, fully assuming that the opponent will also select the best move against it. If a Minimax AI reaches victory with a positive number, its decisions will try to follow the path that favors that number.
The graph shows the last six possible moves of an AI in a tic-tac-toe game. Four of them express a victory for the AI (yellow) with a condition of 1, and the other two for the human player (blue), with -1. The moves are analyzed from bottom to top, or from back to front: Since the AI only has one move left, the values for each one move to the previous step. Following the same logic, the human player has two moves that guarantee a -1, and a third that forces them to choose 1. Therefore, the AI ensures victory by placing pressure on that path, which begins with a cross in the center.
Obviously, this is a very simple example, possible only thanks to the natural limits of tic-tac-toe. If we apply the Minimax method to high-complexity games like chess or go, the number of states to check grows exponentially, and the application of Minimax becomes unfeasible. A possible solution is to limit the depth of exploration, and in general terms, it's more than enough to give a beating to n00bs.
