______________________
OPTIMAL TYCHOKINESIS
Dylan Holmes
______________________
23 Feb 2019
Table of Contents
_________________
1 Two full decks
2 Splitting one deck
3 Opponent plays at random
4 Paying for entropy
5 Adversarial zero-cost
6 Other variants
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
=======================
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%.
6 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?)