Stone Game

Rhythm Jain
Last Updated: May 13, 2022

Introduction

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. The total number of piles is an even number, and the number of stones in each pile is an odd number.

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 (even number of piles) piles arranged in a row, each containing some positive number of stones (odd number of stones). The game will always begin with Player A. A and B are supposed to pick all the piles one by one, either from the beginning or the end of the row, until there are no more piles left. The goal is for Player A to have the most stones at the end of the game. Return true if Player A can win the game; else, return false.

Example:

INPUT:

[5,3,4,5]

OUTPUT:

True

Explanation:

  • A is the first to go and can only take the first 5 or last 5.
  • Assume A takes the first 5, making the row [3, 4, 5].
  • If B takes 3, the row becomes [4, 5], and A takes 5 to win with 10 points.
  • If B takes the final 5, the row becomes [3, 4], and A takes four to win with 9 points.
  • This demonstrated that A’s decision to take the first 5 was a winning one, so we return true.

Approach 1: Dynamic Programming

This Problem is an 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).

Algorithm

  1. Initialize a 2D-DP array of size (N+2) x (N+2) where N is the number of piles and set all values as 0.
  2. Suppose we currently have piles[i], piles[i+1],.....piles[j].
  3. In order to maximize its stones, Player A selects either piles[i] or piles[j].
  4. In order to minimize stones of A, Player B selects either piles[i] or piles[j].
  5. If A has more stones than B, return true.

Code

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

bool stoneGame(vector<int>& piles) {
    int n = piles.size();
    vector<vector<int>> dp(n+2,vector<int> (n+2,0));
    for(int size = 1; size <= n; ++size)
        for(int i = 0, j = size - 1; j < n; ++i, ++j){
            int turn = (j + i + n) % 2
            if(turn == 1)
                dp[i+1][j+1] = max(piles[i] + dp[i+2][j+1], piles[j] + dp[i+1][j]);
            else
                dp[i+1][j+1] = min(-piles[i] + dp[i+2][j+1], -piles[j] + dp[i+1][j]);
        }
    return dp[1][n] > 0;
}
    
int main()
{
    vector<int> piles={5,3,4,5};
    bool ans=stoneGame(piles);
    if(ans){
        cout<<"True\n";
    }
    else{
        cout<<"False\n";
    }

    return 0;
}

Output

True

Complexity Analysis

Time Complexity: O(N2)

Space Complexity: O(N2)

Approach 2: Mathematics

Interesting observation about the Stone Game Problem. Because Player A is the first to choose a stone pile and the number of piles is even, an interesting fact emerges: Since Player A starts first, he/she has the choice to always choose the odd indexed piles or always choose even indexed piles.

Case 1: A chooses even piles.

If Player A wants to pick piles in even positions and chooses the first pile, which is pile at index 0, then Player B can pick piles[1] or piles[n-1].

Player A can always choose piles in even places during his turn, while Player B can only choose piles in odd positions.

Case 2: A chooses odd piles.

If Player A wants to pick piles in odd positions and chooses the last pile, which is pile at index n-1, then Player B can pick piles[0] or piles[n-2].

Player A can always choose piles in odd places during his turn, while Player B can only choose piles in even positions.

As we all know, the total number of stones in the piles is odd.

Player A just picks all evens and wins if the amount of piles[even] is greater than the sum of piles[odd].

Player B just picks all odds and wins if the amount of piles[even] is less than the sum of piles[odd].

So regardless of the case, There always exists a winning move for Player A.

Code:

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

bool stoneGame(vector<int>& piles) {
    return true;
}
    
int main()
{
    vector<int> piles={5,3,4,5};
    bool ans=stoneGame(piles);
    if(ans){
        cout<<"True\n";
    }
    else{
        cout<<"False\n";
    }

    return 0;
}

Output:

True

Complexity Analysis

Time Complexity: O(1)

Space Complexity: O(1)

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. What is the most efficient solution to the problem Stone Game?
    The Stone Game problem can be solved in O(1) space and time complexity because there always exists a winning move for the first player. So we can always return true.

Key Takeaways

Stone Game question is asked in numerous interviews based on dynamic programming and game theory. You can learn more about dynamic programming here.

Although it's always suggested to solve the problem using a naive approach but observing the solution and problem carefully can yield great results. Observation is a great tool in developing the most efficient solutions and can improve our problem-solving skills.

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think