Learning AI with memes — MinMax Algorithm
The MinMax algorithm is a way of finding an optimal move in a two-player game. The goal of this algorithm is to find the next best optimal move. Breadth-First Search is not used as the MinMax algorithm searches down to a certain depth.
The story begins — Two people named MIN and MAX are playing a game. The game usually begins with MAX taking the first chance.
There are a few rules in the game. First, there will be a Game Tree with n number of nodes and having a depth d. In this tree, the root node will always be MAX as it starts the game. Then alternatively, turns will be assigned to MIN & MAX.
The MinMax algorithm uses back-tracking. Therefore, we will always start from the terminal/leaf node and move to the top/root node.
For every level, if it is MAX then it will try to maximize its utility. Therefore, MAX will select the child with a greater value. Whereas, MIN will try to minimize the utility of MAX. Hence it will select the node with a lesser value.
As we move up by each level and reach the root node, we have our optimal value.
Time Complexity Analysis:
Let the Graph tree contain b branches and a depth d. Since all nodes are traversed at least once before reaching the root node, the Time Complexity will be O(b^d).
Now, this might seem okay in the example above, but for games like Chess, this time complexity can reach around O(35¹⁰⁰). Hence, there exists an advanced version of the MinMax Algorithm called — Alpha-Beta Pruning.
Hello!
If I managed to retain your attention to this point, leave a comment describing how this learning AI with memes made a difference for you, and what other topics should I cover!
