The Art of Overthinking : Intuitive approach to Minimax algorithm

I played a lot tic-tac-toe in my school days, no matter it is lunch time or some free time in-between the lectures. The interesting part of that game was to think the next move which can beat the best possible move of the opponent at the current state of the game.

tic-tac-toe game-board

The Minimax algorithm is similar to this tic-tac-toe game. There are two players, one is minimizer and other is maximizer. Minimizer wants the minimum possible target-value where as maximizer wants the maximum possible target-value.

Let’s understand it with the following simple treasure-hunt game. there are four layers in the game( from layer 0 to layer 3). you are at a entry door at layer 0, every higher layer(>layer 0) have double number of doors, that of the previous layer. each door of the non-final layer (the 3rd layer) opens toward any two distinct door of the next layer. According to this structure there are 8 doors at layer 3, behind each there is a treasure box of different quantities of diamonds. In one traversal you can get only one treasure box, of course you will choose the maximum possible quantity of the diamond. But here is the twist, there is a person who is your opponent wants that you get the minimum possible diamonds, and at even number of the layer you can choose the direction for the next layer, but at the odd number of layer that opponent person will decide your path to the next layer. It is well visualized as follows:

Now, what maximum quantity you can get, if you and your opponent both play optimally and both of you already know the quanitity of diamonds in each treasure box, kept at layer-3.

Here the minimax algorithm can help you.

The code for the minimax algorithm is as follows:

# as the array of size n of the leaf node value is given.
# find out the depth of the recursion tree,
# here I am considering there are only two options to choose at each layer
# target_depth = \(\log _{2}\left(n\right)\)
# maximizer turn -> True (boolean Value)
# minimizer turn -> False (boolean Value)

def minimax(curr_depth, idx, target_depth, bool_max, arr):
    if(depth == target_depth):
        return (arr[idx]
    if (bool_max == True):
        left = minimax(curr_depth+1, idx*2, target_depth, bool_max = False, arr)
        right = minimax(curr_depth+1, idx*2+1, target_depth, boolmax = False, arr)
        return max(left, right)
    else:
        left = minimax(curr_depth+1, idx*2, target_depth, bool_max = True, arr)
        right = minimax(curr_depth+1, idx*2+1, target_depth, boolmax = True, arr)
        return max(left, right)

Now let’s understand, how this code will solve the given treasure-hunt problem:

Lets traverse the recursive tree in bottom up approach

When you be stand at layer-2, and its your (the maximizer) turn. here you will be at one of following four pair:

Pair 1: 20 and 90 , obviously you will choose 90.

Pair 2: 100 and 50, obviously you will choose 100.

Pair 3: 45 and 56, obviously you will choose 56.

Pair 4: 80 and 70, obviously you will choose 70.

as according to code line return max(left, right), [90,100,56,70] be returned to the layer-1 in the two pair form, where there is minimizer’s(your opponent) turn.

Pair 1: 90 and 100, obviously opponent will choose 90

Pair 2: 56 and 70, obviously oppnent will choose 56.

and return min (left, right)[90, 56] to the layer-0, where there is maximizer (your) turn.

Obiously you will choose 90 which is the final answer.

The visualization is as follows:

This algorithm implemented on binary choice concept, you can also implement it on n-choice at each layer as follows.

#choice at each layer = n
def minimax(curr_depth, idx, target_depth, bool_max, arr, n):
    if(depth == target_depth):
        return (arr[idx]
    if (bool_max == True):
        max_val = -inf
        for i in range n:
            ans= minimax(curr_depth+1, idx*2+i, target_depth, bool_max = False , arr, n)
            max_val = max(ans, max_val)
        return max_val
    else:
        min_val = inf
        for i in range n:
            ans= minimax(curr_depth+1, idx*2+i, target_depth, bool_max = True , arr, n)
            min_val = min(ans, min_val)
        return min_val

Thanks for reading, don’t forget to clap, drop your comment, positive and negative both feedback are welcome.