Have you ever wondered how AIs for two player games like chess, checkers, tic tac toe, and even 2048 work? Well, it turns out that they all use pretty much the same method! In this article, we introduce the Minimax algorithm, a method for programming AIs that can play a huge variety of two-player games, including all of the games mentioned above, and more!
Let’s start off with an example. Say you are playing a game where you take cookies from a cookie jar, and you want to get the most number of cookies possible. Now say that you are at a point where you can make one of two moves: take 5 cookies, which then your opponent has the option to take 3, 6, or 9 cookies; or take 10 cookies, which then your opponent has the option to take 1, 10 or 100 cookies.
In this case, knowing nothing else, you would probably take the latter choice. Why? Because we can simplify the situation by assuming what the opponent will do: by maxing the latter choices, we can simplify the situation to: if take 5 cookies, then the opponent will take 9; if we take 10, then the opponent will take 100. Then, we simply take the best of the two choices (the choice that minimizes their cookies minus our cookies, hence the name minimax).
That is the intuition behind the Minimax algorithm. By expanding upon this idea, it is possible to create extremely sophisticated and powerful AIs. For example, the famous chess playing robot Deep Blue was programmed using these techniques!
That’s all for this week. See you guys later!
— John Ma