Optimizing Decision-making with the Minimax AI algorithm

Delivering efficient AI!

Let’s introduce you to the Minimax algorithm. I’ll explain some of its well known optimizations and some lesser known ones. This algorithm is useful in decision-making AI, which is used in popular game engines, like Stockfish for Chess. A major limitation of Minimax is that it is only used in two-player games.

Algorithm Basics

The Minimax algorithm can be thought of the computer playing against itself to find the best move! It follows the human thought process — if I do this move, what moves will my opponent have, then what moves can I play, and so on!

• A naive implementation would keep on building the possible-moves tree until each “path” concludes into a win/loss. This isn’t practically possible because the size of the tree increases exponentially with each increment in search depth.
• To solve this problem, a heuristic function is involved. An analogy to a heuristic function is a human’s evaluation of the board after thinking 5 moves ahead. A heuristic function (say h) returns a numerical value that predicts in whose favor the board is in. For example, if h is greater than zero that means player A is winning, and if it is negative then player B is winning.

The heuristic function is a way to inform the search about the direction to a goal. — artint.info/html/ArtInt_56.html