Is this game solvable?

Question

Suppose we have two stacks of cards on a table. On each turn, each of two players draws a card from the top of one of the stacks. The game ends when there are no cards left in either stack. The person with the greatest sum then wins. If this were a chess problem, for example, one could attempt to solve this game by starting from a winning final position, and then inducting backwards. However, in this game, the final card picked up has little bearing, as it is the overall sum that results in a winner. Is it possible to find a game plan for perfect play, assuming both players pursue this game plan?

EDIT: The values of all the cards are known by both players, i.e. the players are omniscient when it comes to information about the cards. The card deck need not be complete, just some random cards in two stacks on a table, and we only care about the values.

EDIT 2: I'm wondering whether this can be solved efficiently with an algorithm that does not have to go through all the potential decisions in a decision tree.

Answer 1

I haven't thought it carefully, but I think You can use dynamic programming. If we have n cards in first deck and m cards in second deck, then there is n*m possible states of stack.

Best_Move(i,j)  
    return Max(Stack1[i]-Best_Move(i-1,j),Stack2[j]-Best_Move(i,j-1))

You just have to remember all partial results, so they won't be calculated twice. This should give You the bes strategy in O(n*m).

Answer 2

The game you describe can be modelled using an extensive game with perfect information, a finite one at that. Such games are determined: you will have one of the following cases:

• player 1 has a winning strategy – irrespective of what moves player 2 makes, player 1 will win.
• player 2 has a winning strategy – irrespective of what moves player 1 makes, player 2 will win.
• both players can force a draw.

The theorem that this corresponds to is known as Kuhn's Theorem and it states that Every finite extensive game with perfect information has a subgame perfect equilibrium. Basically, each player has a strategy which will result in the best result for them, regardless of what the other player plays.

Any algorithm for computing this, such as the min-max algorithm, will potentially have to explore the entire game tree. There will of course be whole subtrees that can be pruned, if for example, the value of the remaining cards is less than the difference between the two players' scores. If you also keep track of the fact that you will see various positions multiple times throughout the game, you can make further, possibly significant, savings (using dynamic programming).

Answer 3

I'm not sure why Tomek removed his answer, but it seems right to me. The dynamic programming algorithm will compute for each (i,j) the maximum advantage that the first player can have over the second player starting with only the last i cards of the first stack and the last j cards of the second stack. (advantage = sum of cards of first player minus sum of cards of second player, when both play optimally -- may be negative).

Entry(i,j) = max(stack1(i)-entry(i-1,j), stack2(j)-entry(i,j-1))

(the minus sign is since after the first player's move, it is the second player who moves and thus gets the advantage promised by the entries.)

Answer 4

I hope I haven't misunderstood, because its seems that in some circumstances a winning strategy is easily computed without looking at the entire decision tree. For example, when both stacks have even numbers of cards and the total of the odd-numbered cards (from both stacks) exceeds the total of the even numbers, then the second player has a simple winning strategy of always responding in the stack from which the first player draws. When exactly one stack has an odd number of cards, the first player might have a similar winning strategy after taking the top card from the odd stack. Simple heuristics like these can potentially simplify a dynamic programming approach by quickly identifying obvious wins.