MiniMax Client
The MiniMax is concept of game theory. It is used for games of perfect information where two players move one after the other. First of all, the algorithm builds a game tree with a certain depth. Every leaf of the tree represents a state of the game. The next step is to evaluate these leaves using a heuristic. To evaluate all the vertices of the tree, the algorithm minimizes the heuristic for the opposite player and maximizes the heuristic for the own player. This allows the own player to always choose the best move even if the opposite player moves perfectly.
To make this algorithm usable for spe_ed we had to make some adaptations. Spe_ed is indeed a game of perfect information, but it is played by up to six players who move simultaneously.
The number of leaves of a game tree grows exponentially with its depth. Therefore, it is very important to optimize the calculations. This can be done with alpha beta pruning and parallel processing.
We only take players in account if they are close enough. If we want to consider two other players, we build two separate game trees and combine them afterwards. Also, we process the backpropagation for every depth of the tree. This allows us to use the time until the deadline optimally.
MiniMax plays optimally if the depth of the calculated game tree reaches the end of the game. Therefore, it is a good strategy for the end game.
