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

<ul>
<li>player 1 has a winning strategy – irrespective of what moves player 2 makes, player 1 will win.</li>
<li>player 2 has a winning strategy – irrespective of what moves player 1 makes, player 2 will win.</li>
<li>both players can force a draw.</li>
</ul>

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

<p>Any algorithm for computing this, such as the <a href="http://en.wikipedia.org/wiki/Minimax" rel="nofollow">min-max algorithm</a>, 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).</p>

CC BY-SA 3.0
2012-12-28T08:56:32.937Z
@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 http://www.maths.lse.ac.uk/personal/stengel/TEXTE/geb1996a.pdf
Rahul Savani
CC BY-SA 2.5
2010-11-12T11:35:23.177Z
The description sounds right. So you can't have a polynomial-time algorithm?
sentinel
CC BY-SA 2.5
2010-11-12T11:41:44.140Z
@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.
Daniel Apon
CC BY-SA 2.5
2010-11-12T11:29:12.107Z
2010-11-12T14:45:11.843Z
2010-11-12T14:45:11.843Z
Dave Clarke
<p>I'm not sure why Tomek removed <a href="https://cstheory.stackexchange.com/questions/2922/is-this-game-solvable/2927#2927">his answer</a>, 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).  </p>

<p>Entry(i,j) = max(stack1(i)-entry(i-1,j), stack2(j)-entry(i,j-1))</p>

<p>(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.) </p>

CC BY-SA 2.5
2010-11-12T18:48:26.003Z
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"
Tomek Tarczynski
CC BY-SA 2.5
2010-11-12T19:23:31.007Z
i see.  It was now confirmed that its not homework, so I'll leave this answer.
Noam
CC BY-SA 2.5
2010-11-12T20:38:27.133Z
I can undelete Tomek's answer, or Tomek, you can do it.
Suresh Venkat
CC BY-SA 2.5
2010-11-12T22:02:57.450Z
Yes, please undelete Tomek's answer.
Peter Shor 
CC BY-SA 2.5
2010-11-12T18:47:09.033Z
2010-11-12T18:47:09.033Z
2017-04-13T12:32:28.080Z
Noam
<p>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 <em>both</em> 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.</p>

CC BY-SA 2.5
2010-11-27T02:58:39.230Z
2010-11-28T19:50:34.773Z
2010-11-28T19:50:34.773Z
whuber
<p>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.  </p>

<pre><code>Best_Move(i,j)  
    return Max(Stack1[i]-Best_Move(i-1,j),Stack2[j]-Best_Move(i,j-1))
</code></pre>

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

CC BY-SA 2.5
2010-11-12T23:54:34.227Z
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.
Peter Shor 
CC BY-SA 2.5
2010-11-13T02:06:40.453Z
My bad, of course it should be -. I've already edited my answer.
Tomek Tarczynski
CC BY-SA 2.5
2010-11-12T14:36:14.607Z
2010-11-13T02:05:56.023Z
2010-11-13T02:05:56.023Z
Tomek Tarczynski
<p>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?</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 2.5
2010-11-12T10:41:19.857Z
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?
Dave Clarke
CC BY-SA 2.5
2010-11-12T10:46:57.393Z
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?)
Daniel Apon
CC BY-SA 2.5
2010-11-12T10:47:11.457Z
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.
sentinel
CC BY-SA 2.5
2010-11-12T10:54:14.717Z
An additional comment, while you're editing your question, so you get the answer you're looking for: Are you just interested in whether it's solvable at all, or whether there is an efficient algorithm to solve it?
Daniel Apon
CC BY-SA 2.5
2010-11-12T10:56:58.490Z
Right, it should be solvable. But I'm guessing it can't be solved by starting from a successful final position and building on that since there is no such thing as a successful final position. Updated.
sentinel
CC BY-SA 2.5
2010-11-12T10:58:40.200Z
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.
Daniel Apon
CC BY-SA 2.5
2010-11-12T11:03:00.877Z
So how can we talk of "perfect play" in these games?
sentinel
CC BY-SA 2.5
2010-11-12T11:13:19.433Z
@sentinel, the way this would generally work is to make some assumption about the computational power of your adversary (unbounded, polynomially bounded, etc) in order to have some idea of which decision he/she would make in response to yours, and then figure out the computational resources necessary to compute a winning strategy yourself.
Daniel Apon
CC BY-SA 2.5
2010-11-12T11:13:42.370Z
From Wikipedia: "In game theory, perfect play is the behavior or strategy of a player which leads to the best possible outcome for that player regardless of the response by the opponent." If the best possible outcome cannot be decided, then yes, a winning strategy.
sentinel
CC BY-SA 2.5
2010-11-12T11:17:46.343Z
@Daniel: If we assume we both follow the same strategy, can we design an algorithm for it then?
sentinel
CC BY-SA 2.5
2010-11-12T11:27:59.620Z
@sentinel, there are some deck arrangements where you won't be able to win, so "winning strategy" is not the correct path. Coming up with an algorithm to decide whether you can win (if it's possible) is less trivial in general. However, if you impose the restriction that the other player MUST follow your strategy, then you can answer this as follows: Follow a greedy strategy (always pick the highest card; or randomly pick one, if there are identical values showing). Then, by simply summing the resulting final hands of both players, you can decide whether you'd win or not. [cont]
Daniel Apon
CC BY-SA 2.5
2010-11-12T11:28:52.287Z
[cont] So, I think the restriction that you hinted at in your original question -- that both players follow the same game plan -- is probably not quite what you want (unless that actually does solve the thing you're interested in, in which case - great!). Probably a better question is whether you can win assuming your adversary chooses a strategy designed to win; this matches up better with natural intuition of games anyway.
Daniel Apon
CC BY-SA 2.5
2010-11-12T13:10:14.597Z
This is solvable by dynamic programming. If you confirm it's not a homework problem, I can explain the answer.
Peter Shor 
CC BY-SA 2.5
2010-11-12T15:52:53.440Z
This is not a homework problem. I'd be happy with an explanation so I can fill the gap in my understanding of game theory.
sentinel
<gt.game-theory>
Is this game solvable?
sentinel
# Is this game solvable?

(Asked by: username_0 on 2010-11-12)

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.

**Tags:** gt.game-theory
> **Comments:**
> **username_1**: 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?  
> **username_2**: 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?)  
> **username_0**: 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.  
> **username_2**: An additional comment, while you're editing your question, so you get the answer you're looking for: Are you just interested in whether it's solvable at all, or whether there is an efficient algorithm to solve it?  
> **username_0**: Right, it should be solvable. But I'm guessing it can't be solved by starting from a successful final position and building on that since there is no such thing as a successful final position. Updated.  
> **username_2**: 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.  
> **username_0**: So how can we talk of "perfect play" in these games?  
> **username_2**: @sentinel, the way this would generally work is to make some assumption about the computational power of your adversary (unbounded, polynomially bounded, etc) in order to have some idea of which decision he/she would make in response to yours, and then figure out the computational resources necessary to compute a winning strategy yourself.  
> **username_0**: From Wikipedia: "In game theory, perfect play is the behavior or strategy of a player which leads to the best possible outcome for that player regardless of the response by the opponent." If the best possible outcome cannot be decided, then yes, a winning strategy.  
> **username_0**: @Daniel: If we assume we both follow the same strategy, can we design an algorithm for it then?  
> **username_2**: @sentinel, there are some deck arrangements where you won't be able to win, so "winning strategy" is not the correct path. Coming up with an algorithm to decide whether you can win (if it's possible) is less trivial in general. However, if you impose the restriction that the other player MUST follow your strategy, then you can answer this as follows: Follow a greedy strategy (always pick the highest card; or randomly pick one, if there are identical values showing). Then, by simply summing the resulting final hands of both players, you can decide whether you'd win or not. [cont]  
> **username_2**: [cont] So, I think the restriction that you hinted at in your original question -- that both players follow the same game plan -- is probably not quite what you want (unless that actually does solve the thing you're interested in, in which case - great!). Probably a better question is whether you can win assuming your adversary chooses a strategy designed to win; this matches up better with natural intuition of games anyway.  
> **username_3**: This is solvable by dynamic programming. If you confirm it's not a homework problem, I can explain the answer.  
> **username_0**: This is not a homework problem. I'd be happy with an explanation so I can fill the gap in my understanding of game theory.  

---

## 4 answers

### Answer by username_6 on 2010-11-12. Score: 9 | Accepted answer

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

> **Comments:**
> **username_3**: 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.  
> **username_6**: My bad, of course it should be -. I've already edited my answer.  

---

### Answer by username_1 on 2010-11-12. Score: 5

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](http://en.wikipedia.org/wiki/Minimax), 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).

> **Comments:**
> **username_0**: The description sounds right. So you can't have a polynomial-time algorithm?  
> **username_2**: @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.  
> **username_4**: @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 http://www.maths.lse.ac.uk/personal/stengel/TEXTE/geb1996a.pdf  

---

### Answer by username_5 on 2010-11-12. Score: 5

I'm not sure why Tomek removed [his answer](https://cstheory.stackexchange.com/questions/2922/is-this-game-solvable/2927#2927), 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.)

> **Comments:**
> **username_6**: 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"  
> **username_5**: i see.  It was now confirmed that its not homework, so I'll leave this answer.  
> **username_7**: I can undelete Tomek's answer, or Tomek, you can do it.  
> **username_3**: Yes, please undelete Tomek's answer.  

---

### Answer by username_8 on 2010-11-27. Score: 1

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.


---

