Intuition for Solving MiniMax Problems
In this post, I’ll be explaining the intuition and a generic approach to solve problems where you are given a game and you’ve to predict if a player can win or not. These problems are also categorized as MiniMax problems in programming community.
An example problem is https://leetcode.com/problems/nim-game/.
Let’s start.
A particular configuration of the game can be termed as a State. Each state is either losing or winning. If you land on winning state, you win. If you land on losing state, you lose.
Let’s say, you are on a state s. You can make n moves, each transforms the state of the game to p1,p2,p3…pn.
Now,
If any of the pi’s is a losing state, the current state becomes winning state.
Why?
Since you’ll always optimally and try to land your opponent in a losing state. And if you are able to do so, you can be assured that your current state is a winning state.
Similarly, if all of the pi’s are winning states, no matter what move you make, your opponent will land in a winning state. So your current state automatically becomes a losing state.
So, for solving any question, you need to identify:
1. What exactly is a state in current game
2. Which are all the states to which the current state can transition to.
So this way, we’ll able to build a tree of states.
And we compute the values bottom up. We know the state of the leaves, whether they are winning or losing. And using that, we compute the value of intermediate states.
That’s all the theory. Let’s jump into the example to make it more clear
Problem Statement:
You are playing the following Nim Game with your friend: There is a heap of stones on the table, each time one of you take turns to remove 1 to 3 stones. The one who removes the last stone will be the winner. You will take the first turn to remove the stones.
Both of you are very clever and have optimal strategies for the game. Write a function to determine whether you can win the game given the number of stones in the heap.
Solution:
Let’s do it step by step:
1. Identify the state.
State here is just the number itself. State(n) = n.
2. Identify transition to other states.
As a player can remove 1–3 stones, state n can transition to three states: n-1, n-2 and n-3.
State(n) -> State(n-1), State(n-2) and State(n-3).
This way, we’ll build the tree.
3. Let’s identify the base cases/leaves.
As we can clearly see,
State(1) is a winning state, as I can just pick 1 stone and end the game. Similary, State(2) and State(3) are also winning states.
Let’s talk about State(4) now.
State(4) can transition to State(3), State(2) and State(1). All of those are winning states, so as per our rule, State(4) becomes a losing state.
To make it more clear, let’s talk about State(5).
If there are 5 stones left, I can pick one and land the opponent in State(4), which is a losing state. So State(5) becomes a winning state.
This way, we can calculate upto State(n), the given input number.
Sample code that implements this approach:
public boolean canWin(int n) { boolean p1 = true, p2 = true, p3 = true; // these three booleans represent the states of last three numbers, as that's the only information we require to calculate the value of next state.
for (int i = 4; i <= n; i++) {
if (!p1 || !p2 || !p3) { // check if any of the pi's is a losing state
p1 = p2;
p2 = p3;
p3 = true; // if yes, the current state becomes winning state
} else {
p1 = p2;
p2 = p3;
p3 = false; // otherwise it's a losing state.
}
}
return p3;
}
I can discuss more questions like these in upcoming posts if required.
Feel free to comment/message me in case of any doubts.
Cheers.
