Minimax with Alpha-Beta Pruning in Python
Introduction
Way back in the late 1920s John Von Neumann established the main problem in game theory that has remained relevant still today:
Players s1, s2, …, sn are playing a given game G. Which moves should player sm play to achieve the best possible outcome?
Shortly after, problems of this kind grew into a challenge of great significance for development of one of today’s most popular fields in computer science – artificial intelligence. Some of the greatest accomplishments in artificial intelligence are achieved on the subject of strategic games – world champions in various strategic games have already been beaten by computers, e.g. in Chess, Checkers, Backgammon, and most recently (2016) even Go.
Although these programs are very successful, their way of making decisions is a lot different than that of humans. The majority of these programs are based on efficient searching algorithms, and since recently on machine learning as well.
The Minimax algorithm is a relatively simple algorithm used for optimal decision-making in game theory and artificial intelligence. Again, since these algorithms heavily rely on being efficient, the vanilla algorithm’s performance can be heavily improved