Stone Game 2

Rhythm Jain
Last Updated: May 13, 2022

Introduction

Stone Game 2 is a very famous problem based on Dynamic Programming and Game theory.

We have 2 players, A and B, playing a game. Several piles are arranged in a row, with each pile containing a positive integer number of stone piles[i]. The goal is to have the most stones at the end of the game.

This Problem is a classic example of the Minimax Algorithm in Game Theory.

In the Minimax Algorithm, the two players are called maximizer and minimizer, respectively. The maximizer tries to maximize the score and get the highest score possible, while the minimizer attempts to do the opposite and get the lowest score possible.

Let’s proceed deeper into the Problem and its solution approach.

Problem Statement

The problem statement is described as two players A and B playing a stone game. There are N piles, each of which contains some positive number of stones. The game will always begin with Player A. A and B are supposed to pick all the stones in the first X piles where 1<= X <= 2M (Initially M = 1) one by one, and then set M = max(X, M ) until there are no more piles left. The goal is for Player A to have the most stones at the end of the game. Find the maximum number of stones that Player A can collect such that both the players play optimally.

Example:

Assume we have the following combinations of piles-

INPUT:

[2,7,9,4,4]

OUTPUT: 

10

Explanation:

If A takes one pile at the beginning, B takes two piles. Then A takes 2 piles again. A can get 2 + 4 + 4 = 10 stones in total. If A takes two piles at the beginning, then B can take all three piles left. In this case, A get 2 + 7 = 9 stones in total. So we return 10 since it is the maximum number of stones that A can get.

Approach 1: Recursion

This Problem is a famous example of a minimax algorithm. The key of the minimax algorithm is that A will always choose the maximum among all his choices (the same as B), and then B will always leave the minimum of the rest choices to A when it switches back to A (the same as A leaves to B).

Regardless of who the player is, we want the function call only to return A’s score. So, we will keep a turn variable turn to keep track of whose turn it is. So if we are A, we will return the maximum of the set: (stones picked this turn + recurse on the turn of B starting at the next index from what we picked). If we are B, we will return the minimum of (recurse on the turn of A starting at the next index from what we picked). The size of these sets will be 2M (less than the size of the array) since one can try grabbing 2M stones at a turn.

Code

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

int rec(int idx, int M, vector<int> &piles, int turn){
    
    //if Reached end of the array, return
    if(idx >= piles.size()) return 0;
    
    //if it is the urn of B
    if(turn){
        int aStones = INT_MAX;
        
        // if a person can take all the remaining stones then, he/she must take them all to get better score
        for(int i = 0; i < 2 * M && idx + i < piles.size(); i++){
            aStones = min(aStones, rec(idx + i + 1, max(M, i + 1), piles, !turn));
        }
        return aStones;
    }
    //else if it is the turn of A
    else
    {
        int aStones = 0, temp = 0;
        
        // if a person can take all the remaining stones then, he/she must take them all to get a better score
        for(int i = 0; i < 2 * M && idx + i < piles.size(); i++){
            temp += piles[idx + i];
            aStones = max(aStones, temp + rec(idx + i + 1, max(M, i + 1), piles, !turn));
        }
        return aStones;
    }
}
    
int stoneGameII(vector<int>& piles) {
    return rec(01, piles, 0);        
}

int main()
{
    vector<int> test={2,7,9,4,4};
    int ans=stoneGameII(test);
    cout<<ans<<endl;
    return 0;
}

 

Complexity Analysis

Time Complexity: O(NN)

Space Complexity: O(NN) (Recursion Stack)

Approach 2: Recursion with Memoisation

From the above recursive method, we can clearly observe that the recursion only depends on three states that vary with each function call: the value of M, current index idx, and current turn.

We can use either dp or memorization to reduce redundant calculations. The goal is the same: we only need to calculate once for a single case.

So the above recursive solution can be easily converted to “recursion with memoization” with a 3D memoization table since we have only three varying states.

Let the memoisation table memo of size N x N x 2.

Code

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

int rec(int idx, int M, vector<int> &piles, int turn,vector<vector<vector<int>>> dp){
    
    //if Reached end of the array, return
    if(idx >= piles.size()) return 0;
    
    //check of we already have solution for the current state
    if(dp[idx][M][turn] != -1){
        return dp[idx][M][turn];
    }
    
    //if it is the turn of B
    if(turn){
        int aStones = INT_MAX;
        
        // if a person can take all the remaining stones then, they must take them all to get a better score
        for(int i = 0; i < 2 * M && idx + i < piles.size(); i++){
            aStones = min(aStones, rec(idx + i + 1, max(M, i + 1), piles, !turn,dp));
        }
        return aStones;
    }
    //else if it is the turn of A
    else
    {
        int aStones = 0, temp = 0;
        
        // if a person can take all the remaining stones then, they must take them all to get better score
        for(int i = 0; i < 2 * M && idx + i < piles.size(); i++){
            temp += piles[idx + i];
            aStones = max(aStones, temp + rec(idx + i + 1, max(M, i + 1), piles, !turn,dp));
        }
        return dp[idx][M][turn]=aStones;
    }
}
    
int stoneGameII(vector<int>& piles) {
    int n= piles.size();
    vector<vector<vector<int> > > dp(n, vector<vector<int> > (n, vector<int> (2-1)));
    
    return rec(01, piles, 0,dp);        
}

int main()

    vector<int> test={2,7,9,4,4};
    int ans=stoneGameII(test);
    cout<<ans<<endl;
    return 0;
}

 

Complexity Analysis:

Time Complexity: O(N3)

Space Complexity: O(2*N2)

Approach 3: Dynamic Programming

When one player moves, the size of the question shrinks, but it remains the same question. Thus, we reduced the Problem to a smaller subproblem. To reduce the redundant calculations we have applied memoization.

Once we have our memoization solution, that can easily be converted to a bottom-up or top-down dynamic programming approach.

Also, we would try to use the suffix sum array to improve the efficiency of the program further.

Code

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
    
int stoneGameII(vector<int>& piles) {
    int n = piles.size();
    if(n == 0)  
        return 0;
    
    vector<int>sum(n+10);
    
    //suffix sum array
    for(int i=n-1; i>=0; i--){
      sum[i] = piles[i] + sum[i+1]; 
    }  
    
    vector<vector<int>>dp(n+1vector<int>(n+1,0));
    for(int i = 0; i <= n; i++){
        dp[i][n] = sum[i];
    }    
    
    for(int i=n-1; i>=0; i--){
        for(int j=n-1; j>=0; j--){
            for(int x=1; x<=2*j && i+x<=n; x++)
                dp[i][j] = max(dp[i][j], sum[i] - dp[i+x][max(j,x)]);
        }
    }
    return dp[0][1];
}

int main()
{
    vector<int> test={2,7,9,4,4};
    int ans=stoneGameII(test);
    cout<<ans<<endl;
    return 0;
}

 

Complexity Analysis:

Time Complexity: O(N3)

Space Complexity: O(N2)

Frequently Asked Questions

1. What is minimax in game theory?
In the Minimax Algorithm, the two players are called maximizer and minimizer, respectively. The maximizer tries to maximize the score and get the highest score possible, while the minimizer attempts to do the opposite and get the lowest score possible.

2. How to convert the recursive solution to a dynamic approach-based solution?
In the recursive solution, if we can observe repeated states, that solution can be further optimized by applying memoization. The memoization-based solution can be converted to a dynamic programming approach. For more insights about memoization and dynamic programming, you can visit here.

Key Takeaways

Minimax Algorithm in game theory is a very crucial algorithm. Minimax is a backtracking algorithm used in decision-making and game theory to determine the optimal move for a player, assuming that your opponent also plays optimally.

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think