Algorithm for game with coins [closed]

Question

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center.

Closed 7 years ago.

Let's play a game:

There are n stacks of coins in a row. i-th stack consists of d_i coins. Two players: Player1, Player2 make moves alternately. Player in his turn can only take first stack or last stack or both of them. The game ends when there are no coins left. Each player wants to have as many coins as possible at the end. Player1 starts.

I was wondering about algorithm (sounds like greedy algorithm) to count how many coins each player has at the end of the game when both plays optimal.

I don't have any idea how to approach such algorithms. Just guess strategy or there is some way to deduce it? Or maybe it's rather too weird problem to implement an algorithm?

Examples (coins in stacks from first to n-th):

1, 100, 1 - players have 2 and 100 coins respectively (unfortunately first player can only take first and last stack - second player will always take stack with 100 coins)

1, 1, 100, 1, 1, 5 - players have 8 and 101 coins respectively (I think this is after optimal game - first take 5 and 1, then second take 1 to prevent player1 from taking stack with 100 coins. If player1 take less than 6 coins in his first move, he will always have less than 8 coins).

I hope I specified enough the problem. Do you agree that it is interesting? :) Can anybody help?

Answer 1

Adding to @Peter's dynamic programming solution:

I think the recurrence would look somewhat like following:

Considering the coin stacks ranging from A[i,..j]
Let, dp[i, j] represents the max score that Player1 can possibly get. Then,

dp[i, j] = MAX {
                MIN( dp[i+2, j], dp[i+1, j-1], dp[i+2, j-1]) + A[i], //Case when Player2 will try to make the most of it if Player1 picks ith coin.
                MIN( dp[i+1, j-1], dp[i, j-2], dp[i+1, j-2]) + A[j], //Case when Player2 will try to make the most of it if Player1 picks the jth coin.
                MIN( dp[i+2, j-1], dp[i+1, j-2], dp[i+2, j-2]) + A[i] + A[j] // Case when Player2 will try to make the most of it when Player1 picks both the ith and jth coins.
               }

As there are only N^2 possible game states. It can be implemented by filling up a dp table of size N^2.

For C++ fans:

#include<iostream>
using namespace std;
int Solve(int A[], int N, int **dp, int i, int j){
        if(dp[i][j] != -1)
                return dp[i][j];
        if(j<i)
                return 0;
        else if(j==i)
                return A[i];
        else if( (j-i) == 1)
                return (A[i] + A[j]);
        else{
                int opt1 = min(Solve(A, N, dp, i+2, j), Solve(A, N, dp, i+1, j-1));
                opt1 = min(opt1, Solve(A, N, dp, i+2, j-1));
                int opt2 = min(Solve(A, N, dp, i+1, j-1), Solve(A, N, dp, i, j-2));
                opt2 = min(opt2, Solve(A, N, dp, i+1, j-2));
                int opt3 = min(Solve(A, N, dp, i+2, j-1), Solve(A, N, dp, i+1, j-2));
                opt3 = min(opt3, Solve(A, N, dp, i+2, j-2));
                int res = max(opt1+A[i], opt2+A[j]);
                res = max(res, opt3+A[i]+A[j]);
                dp[i][j] = res;
                return res;

        }
}
int main(){
        int N;
        int A[N];
        cin >> N;
        for(int i=0; i<N; ++i)
                cin >> A[i];
        int **dp;
        dp = new int* [N];
        for(int i=0; i<N; ++i)
                dp[i] = new int[N];
        for(int i=0; i<N; ++i)
                for(int j=0; j<N; ++j)
                        dp[i][j] = -1;
        Solve(A, N, dp, 0, N-1);
        cout << dp[0][N-1] << endl;
        for(int i=0; i<N; ++i)
                delete [] dp[i];
        delete []dp;
        return 0;
}

Also, as @Peter pointed out your analysis for 2nd example is wrong. Player1 actually has a strategy to win that game by scoring 102 coins.

Answer 2

You can solve this via dynamic programming in O(n^2) by solving the subproblem of what is the best strategy if only stacks in the range a to b-1 are present.

Python code:

A=[1, 1, 100, 1, 1, 5]
#A=[1, 100, 1]

cache={}
def go(a,b):
    """Find greatest difference between player 1 coins and player 2 coins when choosing from A[a:b]"""
    if a==b: return 0 # no stacks left
    if a==b-1: return A[a] # only one stack left
    key=a,b
    if key in cache:
        return cache[key]

    v=A[a]-go(a+1,b) # taking first stack
    v=max(v,A[b-1]-go(a,b-1)) # taking last stack
    v=max(v,A[a]+A[b-1]-go(a+1,b-1)) # taking both stacks

    cache[key]=v
    return v

v = go(0,len(A))
n=sum(A)
print (n+v)/2,(n-v)/2

This says that the optimal game for your second case is actually for the first person to take just the leftmost 1. From then on he can guarantee that he will capture the 100, so he wins.

(Player 1 wins 102, player 2 wins 7)

There are O(n^2) subgames so this algorithm takes time O(n^2)

The subgames (and optimal first player/second player coins) are:

 [1, 5] 6 0
 [1, 1] 2 0
 [1, 100] 101 0
 [100, 1] 101 0
 [1, 1] 2 0
 [1, 100, 1] 2 100
 [1, 1, 5] 6 1
 [100, 1, 1] 101 1
 [1, 1, 100] 101 1
 [100, 1, 1, 5] 105 2
 [1, 100, 1, 1] 101 2
 [1, 1, 100, 1] 101 2
 [1, 100, 1, 1, 5] 7 101
 [1, 1, 100, 1, 1] 102 2
 [1, 1, 100, 1, 1, 5] 102 7

So, for example, suppose that we have found all the optimal plays for the smaller games and wish to find the best play for [1,1,100,1,1,5].

All we do is consider each move in turn:

1. Take first stack, this would win us 1, and leave the game [1,100,1,1,5] which we know from our subproblem would win us 101 for a total of 102.
2. Take last stack, this would win us 5, and leave the game [1,1,100,1,1] which would only win us an additional 2 for a total of 7.
3. Take both stacks, this would win us 6, and leave the game [1,100,1,1] which again would only let us win 2 more if player 2 plays optimally, for a total of 8

So the best move is to take the first stack only.