"What is the maximum that Player 1 can win?"

Question

This is a question that I encountered in one of the competitive coding tests. The question goes as follows:

A 2-player game is being played. There is a single pile of stones. Every stone has an amount (positive) written on top of it. At every turn, a player can take the top 1 or 2 or 3 stones and add to his kitty. Both players want to maximize their winnings. Assuming both players play the game optimally and Player 1 starts the game, what is the maximum amount that Player 1 can win?

I have devised the following recursive approach:

class Main {
  public static void main(String[] args) {
    int a[] = {1,2,3,7,4,8,1,8,1,9,10,2,5,2,3};
    int sum = 0;
    for (int i=0;i<a.length; i++) {
      sum += a[i];
    }
    System.out.println(maxPlayer1(a, 0, sum, 0, a.length));
  }
  public static int maxPlayer1(int[] a, int currSum, int sum, int start, int len) {
    if (len-start <=3) {
      int val = 0;
      for (int i=start; i<len; i++) {
        val += a[i];
      }
      return val;
    }

    int v1 = a[start] + (sum - currSum - a[start]) - 
    maxPlayer1(a, currSum + a[start], sum, start + 1, a.length);

    int v2 = a[start] + a[start+1] + (sum - currSum - a[start] - a[start+1]) - 
    maxPlayer1(a, currSum + a[start] + a[start+1], sum, start + 2, a.length);

    int v3 = a[start] + a[start+1] + a[start+2] + (sum - currSum - a[start] - a[start+1] - a[start+2]) - 
    maxPlayer1(a, currSum + a[start] + a[start+1] + a[start+2], sum, start + 3, a.length);

    return Math.max(v1, Math.max(v2, v3));
  }
}

I have checked my solution on a few inputs. Is my algorithm correct?

Answer 1

The natural way to tackle this problem (as in many similar games) is starting from the final position.

Let B[k] be the maximum score that Player 1 can get if the game starts with only the last k stones left. B[1], B[2], B[3] are initial values that can be computed directly (just take all remaining stones), and then you can fill in B[4], B[5], B[6], ... in this order, since B[k] only depends on B[k-1], B[k-2], B[k-3]; so you can write your code as a loop for k=4,5,6,..., a.length. The resulting algorithm is linear, without no recursion, branching, or approximations required.

Instead, it looks like you are trying to compute the entries B[i] starting from B[a.length]. This leads to a more complicated structure where you make recursive calls, and re-compute the same values B[i] multiple times, as pointed out also by @vnp's answer.

Once you have figured out how to fill the B array in this way, a further improvement is realizing that you only need to keep the last three values B[k], B[k-1], B[k-2] at each step (and possibly also the partial sum a[k-2] + ... + a[a.length]). This gives a solution in \$O(1)\$ space.

If you want to compare with another famous function in which f(n) depends on its previous values, what you wrote is like computing Fibonacci numbers recursively via return fibonacci(n-1) + fibonacci(n-2). What I suggest above is computing iteratively f[0], f[1], f[2], ... starting from f[0].

Answer 2

Usability

I have a remark about defining recursive functions. You don't want consumers of your API to think about the intermediate variables and their initial value. The consumer does not care you are using recursion internally.

Make your recursive function private.

private static int maxPlayer1(int[] a, int currSum, int sum, int start, int len) 

And create a public API entrypoint.

public static int maxPlayer1(int[] a) {
     final int sum = IntStream.of(a).sum();
     return maxPlayer1(a, 0, sum, 0, a.length);
}

The consumer can now call your API without getting a headache:

public static void main(String[] args) {
     final int a[] = {1,2,3,7,4,8,1,8,1,9,10,2,5,2,3};
     System.out.println(maxPlayer1(a));
}

As compared to the original code the consumer had to write.

public static void main(String[] args) {
    int a[] = {1,2,3,7,4,8,1,8,1,9,10,2,5,2,3};
    int sum = 0;
    for (int i=0;i<a.length; i++) {
      sum += a[i];
    }
    System.out.println(maxPlayer1(a, 0, sum, 0, a.length));
  }

Answer 3

A note on efficiency. Currently the code exhibit an exponential time complexity. It can be reduced significantly.

Notice that the same position is inspected more than once. For example, the opening sequences 3, 1, 2, 2 and 1, 3 all lead to the same position. Further down the game the situation aggravates.

Keep track of the positions already inspected, and before diving into the recursion check whether it is still unknown. Since the position is just an integer (an amount of stones remaining), the cost of tracking is \$O(n)\$ space.

Further improvement is of course alpha-beta pruning.

Answer 4

I am not too happy about the variable name currSum, it is hard to see the meaning of this variable from the name alone.

Consider takenValue or something similar as a variable name.

Note that

a[start] + (sum - currSum - a[start])

Simplifies to

sum - currSum

And similarily for the other cases so;

    int v1 = a[start] + (sum - currSum - a[start]) - 
    maxPlayer1(a, currSum + a[start], sum, start + 1, a.length);

    int v2 = a[start] + a[start+1] + (sum - currSum - a[start] - a[start+1]) - 
    maxPlayer1(a, currSum + a[start] + a[start+1], sum, start + 2, a.length);

    int v3 = a[start] + a[start+1] + a[start+2] + (sum - currSum - a[start] - a[start+1] - a[start+2]) - 
    maxPlayer1(a, currSum + a[start] + a[start+1] + a[start+2], sum, start + 3, a.length);

simplifies to

    int v1 = sum - currSum - 
    maxPlayer1(a, currSum + a[start], sum, start + 1, a.length);

    int v2 = sum - currSum - 
    maxPlayer1(a, currSum + a[start] + a[start+1], sum, start + 2, a.length);

    int v3 = sum - currSum -  
    maxPlayer1(a, currSum + a[start] + a[start+1] + a[start+2], sum, start + 3, a.length);

We should also try to capture the meaning of a[start]+...a[start+n], we can do this by introducing a new variable takenInCurrentStep

Also

  int val = 0;
  for (int i=start; i<len; i++) {
    val += a[i];
  }
  return val;

Is needlessly complicated. We can write this as :

  return sum-currSum;

Bringing this all together :

  public static int maxPlayer1(int[] a, int takenValue, int sum, int start, int len) {
    if (len-start <=3) {
      return sum-takenValue;
    }

    int valueTakenInCurrentStep = 0;
    int lasttokensTakenInCurrentStep = start;
    int valueTakenInCurrentStep = a[lasttokensTakenInCurrentStep];

    int v1 = sum - takenValue -
    maxPlayer1(a, takenValue+ valueTakenInCurrentStep, sum, lasttokensTakenInCurrentStep+1  , a.length);

    int lasttokensTakenInCurrentStep ++;
    int valueTakenInCurrentStep = valueTakenInCurrentStep + a[lasttokensTakenInCurrentStep ];

    int v2 = sum - takenValue -
    maxPlayer1(a, takenValue+ valueTakenInCurrentStep, sum, lasttokensTakenInCurrentStep+1  , a.length);

    int lasttokensTakenInCurrentStep ++;
    int valueTakenInCurrentStep = valueTakenInCurrentStep + a[lasttokensTakenInCurrentStep ];
    int v3 = sum - takenValue - 
    maxPlayer1(a, takenValue+ valueTakenInCurrentStep, sum, lasttokensTakenInCurrentStep+1  , a.length);

    return Math.max(v1, Math.max(v2, v3));
  }
}

The algorithm can be described as;

We have a method that calculates the maximum that the current player can get from the remaining of the game. The method takes the value of all the tokens, the value of the tokens that are no longer available, the value of all tokens, the index of the first currently available token, and the total number of tokens.

It works by if there are 3 or less tokens left return the value of the remaining tokens, which is equal to the value of all tokens minus the value of the tokens already taken. If there are more than 3 tokens return the maximum of the value of remaining tokens minus the amount that the other player gets if current player takes 1,2 or 3 tokens.

This is a correct algorithm, and we can prove this by incursion.