The card game Push is played between two people. A deck is shuffled then divided in half, with each player receiving a half (face down). During a round, both players reveal the top card of their deck; the high card scores a point. (Ties are handled in a special way.) The winning player is whoever has the most points after all of the cards have been revealed. Obviously players can control the outcome of the game by magically manipulating probabilities.  In this brief note, I discuss optimal strategies for increasingly complex variations of the game. I describe the variant in one paragraph, followed by the solution. You should feel free to read the variant and discover the solution on your own.

1 Two full decks

Problem: Suppose you are playing a simpler version of this game where you and your opponent each get a full deck of cards. Suppose the cards are numbered, say 1 through 52. Finally, suppose you know the exact order of your opponent's cards, which will not change. How should you, through tychokinesis, order your cards so as to achieve the highest possible score?

Solution: The [only?] optimal solution is whenever your opponent plays a card, you play the card ranked one above it. The only card for which this strategy is impossible is when your opponent plays the highest-ranked card in the deck (which is unbeatable) in which case you play the lowest-ranked card in the deck. This "rotate by one" strategy is optimal because you win every round except the one in which your opponent plays a card that can never lose and you match it with a card that can never win.

2 Splitting one deck

Problem: Now suppose we split a single shuffled deck in half, giving one half to you and one half to your opponent. Suppose you still have perfect knowledge in this variant: you know exactly the shuffled order of your opponent's cards, which will not change. Consequently, you can determine which cards you've been dealt. How should you, through tychokinesis, order your cards so as to achieve the highest possible score?

Solution: Note that we are trying to decide which cards in your deck to match against which cards in your opponent's deck. Once we've decided on that matchup policy, it doesn't matter how the opponent's deck is shuffled; just play the corresponding matched card. Here's an optimal strategy: You know which cards you have and which cards your opponent has. Mentally arrange your deck in ascending order of rank, and arrange your opponents cards the same way. Look at your opponent's highest-ranked card, and pair it with the lowest-ranked card you have that can beat it. (If none of your cards can beat it, pair it with your lowest-ranked card overall.)  Eliminate those two cards from consideration and repeat the matching process. This strategy is at least locally optimal because whenever you play a high card, you win, and whenever you don't, it's impossible to win. I suspect it is globally optimal as well. This strategy is also very general: it subsumes the strategy from the previous section, and actually applies to any two decks of the same size (not just decks created by splitting a single deck in half).

3 Opponent plays at random

Problem: Now suppose you only know the contents, but not the order, of both decks: we split a single shuffled deck in half, giving one half to you and one half to your opponent. You know which cards each person has, and your opponent's cards are in a fixed but unknown order. How should you, through tychokinesis, order your cards so as to achieve the highest possible score?

Solution: Perhaps surprisingly, you can't do anything strategic against a random opponent. Regardless of your chosen strategy, your expected score is equal to the probability that you win a random matchup between one of your cards and one of theirs, times the number of cards you have. You can prove this by induction, using an n-by-n matrix which has a 1 in entry (i,j) if your ith card beats their jth card and a 0 otherwise. Regardless of strategy, your expected score is equal to the sum of the entries in this matrix, divided by n.

4 Paying for entropy

Problem: Next, we introduce tychokinetic costs. Again, a shuffled deck is split in two, with both players receiving a half. You know the contents of both decks, and as with the deterministic variant, suppose you know the fixed order of your opponent's deck. Normally, when you play a card, you are drawing uniformly from the set of all cards you haven't played yet. Using tychokinesis, you may instead choose to draw uniformly from a smaller subset. The smaller subset consists of your choice of one or more cards that you haven't played yet. When drawing from a smaller subset, you must pay an entropy cost of (n/k) log(n/k), where k>0 is the size of the subset and n is the total number of unplayed cards in your deck. Suppose you just want to win, not necessarily by the largest possible margin. Find the strategy that minimizes the amount of entropy you pay for, subject to the condition that you still win the game if possible.

Solution: ???

5 Adversarial zero-cost

Problem: In the ordinary game, you and an opponent have a face-down shuffled deck split between you. You draw the top card of your deck and your opponent does the same; then you reveal both cards and whoever's card has higher rank wins a point. The two cards are discarded and the process is repeated. The winner of the game is whoever has the most points when the decks are depleted. (If we suppose players do not know the contents of either deck, it is equivalent and conceptually simpler to model the game with both players drawing cards from a single face-down deck instead.) Now for tychokinesis. Before revealing a card, you may secretly, and at no cost, choose any subset of two or more specific cards that haven't been played yet. Your card will be drawn uniformly at random from this subset. Your opponent may do the same. (Neither of you has any information about whether the other person has used tychokinesis or which subset they've chosen, and the choice of subset is made before any cards are drawn that round.)  Cards are guaranteed by the laws of physics to be distinct. Is there an effective strategy for cheating that improves your chances of winning over playing fairly, or is the best strategy to play fairly?

Solution: If you draw the card of highest rank, you win with certainty. If you draw the card of next-highest rank, you win unless your opponent draws the card of highest rank. If you draw any card of lower rank, you are less likely to win against any particular subset of cards; therefore, to maximize your expected winnings, you should choose the subset consisting of the two highest-ranked cards. By symmetry, so should your opponent. Also by symmetry, your probability of winning when both players use this strategy each round is 50%. Finally, each round, there are always at least two cards remaining in the shared deck. Because this strategy does not otherwise depend on which cards are in the deck, this strategy is optimal each round and your probability of winning the game overall is 50%.

Other variants

  1. Minimax: You and an opponent play the game adversarially. Contents of both decks are unknown. You and the opponent may each pay entropy to draw from a smaller subset of /two/ or more cards that haven't been played yet. (You and your opponent are guaranteed by the laws of physics to draw distinct cards.)  Win, according to some metric of energy and points.
  2. Energy profiles: If you and your opponent have available entropy budgets of H_1 and H_2, respectively, does this uniquely determine your expected probability of victory? (Or is uniform play still optimal so that the budget is never used?)