minimax algorithm
https://www.geeksforgeeks.org/minimax-algorithm-in-game-theory-set-1-introduction/
In Networks class, we went over game theory, where multiple individuals contested with one another to optimize their own values. In most of the examples we did, we looked at a game where two players each chose one move, and then received a value based on which pair of moves they chose. But what about games like chess or tic-tac-toe where the players must make multiple moves or take turns? Games where there can only be a single winner?
One way to model and reason about such a game is the minimax algorithm. In this game, the two players are the minimizer and the maximizer. The maximizer wants to increase the value as much as possible, while the minimizer wants the value to be as small as possible. In every case, there is a board state. If the board state is positive, the maximizer has the upper hand. If the board state is negative, the minimizer has the upper hand. If the score is 0, players are even. A graph tree can be constructed, where each node represents a board state (with the top node representing a graph at the beginning of the match, and each edge from the node represents a possible move the player can make. The players take turns; after the maximizer makes his move, the minimizer will make his move, and vice versa. In each of the maximizer’s turns, he will choose the choice that increases the board value the most, while the minimizer will choose the option that reduces the board value the most.
Besides describing the minimax algorithm, the website also provides code in several different languages that performs the minimax algorithm, given the game tree.
The link also contains links to additional topics involving minimax. One, for instance, is alpha-beta pruning. Lets say that we need to evaluate the tree. As each player can make multiple moves, the tree will grow exponentially, which could be a problem if there are many available moves each turn, and if there is no definite limit to the game. In alpha-beta pruning, the searching is optimized, by removing branches for which we know there already exists a better alternative. This can reduce computation time by a large factor, while also allowing deeper levels to be searched.
Another variant is where moves are determined randomly; once the player moves, there are a set of values, each with their own chance of being picked. With chance involved, the players must determine which move will lead to the overall highest value for them. A further complication can be outliers, where there is an outcome with an enormous value, but very low chance of getting it. In this case, it may be smarter to go to another path with less earnings but a better chance of getting them.
The minimax algorithm is often used to model games like tic-tac-toe, backgammon, chess, or go. In machine learning especially, the game tree is constructed and searched in order to find the move and/or strategy that will lead to the optimal value.