# Is this game solvable?

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.

• What do you mean by sum? The sum of the face values of the cards? Are cards face-down or face-up? All cards or just top card? Nov 12, 2010 at 10:41
• Along the same lines, I assume you're talking about a standard 52-size deck of playing cards? (And with your last sentence, do you mean that both players must follow the same strategy?) Nov 12, 2010 at 10:46
• Yes, the sum of the face values. 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. If it makes it easier to solve, then yes, both players can follow a perfect game plan. Nov 12, 2010 at 10:47
• In fact, a successful final position is any situation where you hold a set of cards with a higher sum than the other player. By analogy, any set of piece positions on a chess board that cause a checkmate is a successful final position in chess. Neither is uniquely defined. Nov 12, 2010 at 10:58
• This is solvable by dynamic programming. If you confirm it's not a homework problem, I can explain the answer. Nov 12, 2010 at 13:10

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).

• It should be Max(Stack1[i] - Best_Move(i-1,j), Stack2[j] - Best_Move(i,j-1)), since if one player makes a move when the stacks are at (i,j) height, his opponent makes the next move. Nov 12, 2010 at 23:54
• My bad, of course it should be -. I've already edited my answer. Nov 13, 2010 at 2:06

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).

• The description sounds right. So you can't have a polynomial-time algorithm? Nov 12, 2010 at 11:35
• @sentinel, two-person zero-sum normal-form games can be computed in polynomial time. However, I believe in this case, the transformation from an extensive game to a normal-form game causes an exponential blow-up in size. Until someone else confirms this, I'd take this as soft evidence that there isn't a known better algorithm than the type of backward induction you described earlier (traversing the entire decision tree). Edit: Or rather, Dave already said as much -- I missed his reference to the min-max algorithm. Nov 12, 2010 at 11:41
• @Daniel Apon: Note that zero-sum extensive-from games can be solved in polynomial time using the sequence form, rather than the strategic form. See: B. von Stengel (1996), Efficient computation of behavior strategies. Games and Economic Behavior 14, 220-246, available at maths.lse.ac.uk/personal/stengel/TEXTE/geb1996a.pdf Dec 28, 2012 at 8:56

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.)

• I removed it after reading Peter Shore comment: "This is solvable by dynamic programming. If you confirm it's not a homework problem, I can explain the answer" Nov 12, 2010 at 18:48
• i see. It was now confirmed that its not homework, so I'll leave this answer.
– Noam
Nov 12, 2010 at 19:23
• I can undelete Tomek's answer, or Tomek, you can do it. Nov 12, 2010 at 20:38