Game Theory - PrincekinNicholas/PacMan-AI-Planning GitHub Wiki
Minimax theory
Minimax is a pessimistic algorithm, which assumes that each step of the opponent will introduce us to the direction of the smallest theoretical value from the current perspective. Even if the opponent has perfect decision-making ability, our strategy is still able to choose the best action in this circumstances.
Minimax does not find the theoretical optimal solution, because the theoretical optimal solution often depends on the strategy the other team choose. In Minimax, we fully grasp the initiative. If the decision of each other is perfect, then we can achieve the expected minimum loss pattern. If the other party does not make the perfect decision, then we may achieve a better ending than the most pessimistic situation expected. In short, we are going to choose the best in the worst case.
For the defender, Minimax strategy is used to design the mechanism to protect itself. Once the capsule in our side is eaten by the enemy, our defender is scared and lose the power to chase Pacman. In order to protect itself, our defender is encouraged to step into the opposite side to become a temporary attacker, until the scare time is about to end.
As for the attacker, when it founds out it is chasing by the ghost, it will play conservatively. If it can observe a ghost is 5 steps away, it will skip the food which is considered to be too dangerous to eat. And we also set a time limit for this situation, when the Pacman is chased by a ghost for a certain time, it will consider back to the portal. We assume that, once the enemy saw the Pacman, they will chase after it until it is dead or comes back home successfully.
Inspired by the Minimax strategy, we've designed the mechanism for the defender and attacker respectively. Even the enemy is considered to choose the best reaction in all situation, our agents are still available to make the decision which is the best reaction in this situation.