5
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – Dave Clarke Nov 12 '10 at 10:41
  • $\begingroup$ 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?) $\endgroup$ – Daniel Apon Nov 12 '10 at 10:46
  • 1
    $\begingroup$ 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. $\endgroup$ – sentinel Nov 12 '10 at 10:47
  • 1
    $\begingroup$ 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. $\endgroup$ – Daniel Apon Nov 12 '10 at 10:58
  • 5
    $\begingroup$ This is solvable by dynamic programming. If you confirm it's not a homework problem, I can explain the answer. $\endgroup$ – Peter Shor Nov 12 '10 at 13:10
9
$\begingroup$

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

$\endgroup$
  • 4
    $\begingroup$ 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. $\endgroup$ – Peter Shor Nov 12 '10 at 23:54
  • $\begingroup$ My bad, of course it should be -. I've already edited my answer. $\endgroup$ – Tomek Tarczynski Nov 13 '10 at 2:06
5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ The description sounds right. So you can't have a polynomial-time algorithm? $\endgroup$ – sentinel Nov 12 '10 at 11:35
  • $\begingroup$ @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. $\endgroup$ – Daniel Apon Nov 12 '10 at 11:41
  • $\begingroup$ @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 $\endgroup$ – Rahul Savani Dec 28 '12 at 8:56
5
$\begingroup$

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

$\endgroup$
  • 3
    $\begingroup$ 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" $\endgroup$ – Tomek Tarczynski Nov 12 '10 at 18:48
  • 3
    $\begingroup$ i see. It was now confirmed that its not homework, so I'll leave this answer. $\endgroup$ – Noam Nov 12 '10 at 19:23
  • 2
    $\begingroup$ I can undelete Tomek's answer, or Tomek, you can do it. $\endgroup$ – Suresh Venkat Nov 12 '10 at 20:38
  • 3
    $\begingroup$ Yes, please undelete Tomek's answer. $\endgroup$ – Peter Shor Nov 12 '10 at 22:02
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.