MiniMax using Divide and conquer approach

MiniMax Using Divide & Conquer

Idea

MiniMax is a decision-making algorithm used in adversarial search (like games).
Using divide and conquer, we recursively split the game tree into two subproblems:

• Left subtree → Maximizer’s choice

• Right subtree → Minimizer’s choice

At each level:

• Max level: choose max(left, right)

• Min level: choose min(left, right)

The game tree is divided into two equal halves until we hit leaf nodes.

Procedure

int minimax(int arr[], int l, int r, bool isMax) {
    // Base case: when only 1 or 2 elements left
    if (r - l + 1 <= 2) {
        if (isMax) return max(arr[l], arr[r]);
        else return min(arr[l], arr[r]);
    }

    int mid = (l + r) / 2;

    // Divide into two equal problems
    int left  = minimax(arr, l, mid, isMax == false);
    int right = minimax(arr, mid + 1, r, isMax == false);

    // Combine result depending on Max or Min level
    if (isMax) return max(left, right);
    else return min(left, right);
}

Divide & Conquer Recurrence

Given:

This simplifies to:

Time Complexity

Taking :

• $n=2^k$

• $k={\log }_{2}n$

• $n/2^k=1$

The inside term is a geometric progression:

This is GP with:

• first term $a=1$

• common ratio $r=2$

• number of terms $k$

GP Sum Formula

For $r=2$

Asymptotically:

Final Time Complexity

✔ $O(n)$
✔ You process all leaf nodes once
✔ Divide & Conquer halves the problem but doubles calls → linear overall