5
$\begingroup$

No, not the war on drugs, but the game of War considered in Does War have infinite expected length? As noted in that discussion, the game of war can go on forever, but my question is: can it be decided in polynomial time whether a given configuration leads to a periodic or a finite game (the question is decidable, since you can just look at a sequence of $n n!$ moves (where $n$ is the initial number of cards), but $n n!$ is not so small.)

EDIT To answer Joel's very good question: the setup is: the two adversaries have decks $A$ and $B,$ both face down. they flip their top cards, call them $a_1$ and $b_1.$ If $v(a_1) > v(b_1)$ ($v()$ is the value), we put $a_1$ on top of $b_1,$ turn the stack of two cards upside down and add them to the bottom of $A$'s deck (and similarly if $v(b_1) > v(b_k).$ If $v(a_1) = v(b_1)$ we flip two more cards $a_2, b_2$ put them on top of $a_1, b_1$ respectively. If $v(a_2) > v(b_2)$ we put the stack of $a$s on top of the stack of $b$s, flip the resulting $4$-stack upside down, and add it to the bottom of the $A$ stack. If $v(a_2) = v(b_2)$ we continue as before. If we keep getting equal values, and one of the players runs out of cards, the other player wins. If both players run out of cards simultaneously, the game is declared a draw.

Improve this question
$\endgroup$
6
  • $\begingroup$ Could you clarify your reloading rule, by which the cards are returned to the deck? The answers to the previous question depended on the details of that rule. $\endgroup$
    – Joel David Hamkins
    Commented Dec 8, 2011 at 12:27
  • $\begingroup$ @Joel: check out the edit, hopefully it clarifies things... $\endgroup$
    – Igor Rivin
    Commented Dec 8, 2011 at 12:39
  • $\begingroup$ Igor, your rule for what to do in case of ties differs from the "official" rule, which has the players lay down three cards each without comparing them before playing a fourth that they do compare. Any reason for the change? $\endgroup$
    – Barry Cipra
    Commented Dec 8, 2011 at 15:00
  • $\begingroup$ @Barry: I am just reconstructing the rules I remember from my childhood (plus, what I suggest seems more canonical, but you might not agree...) $\endgroup$
    – Igor Rivin
    Commented Dec 8, 2011 at 15:02
  • $\begingroup$ Igor, your rule is also the rule I know from childhood (and we called it a "war," rather than a "battle"). And I also think that your rule for running out of cards, which also differs from the official rules, makes more sense than the official rule. $\endgroup$
    – Joel David Hamkins
    Commented Dec 8, 2011 at 15:06

1 Answer 1

Reset to default
2
$\begingroup$

Here is an observation which might be put to use by someone more clever than I.

The obvious fact is that if player A has all the cards of top value greater than the n+1st card, then during the play A keeps those n cards in Igor Rivin's version of the game. So when does A acquire all cards having the same value as the (n+1)th card? For many games, it is quite likely that A will acquire those cards, so the question now becomes: for which patterns is B able to keep his top value card indefinitely. This version should be should be tractable, although I don't know enough yet to say that it is decidable quickly. Probabilistically, I would say almost never.

Gerhard "Ask Me About Random Guessing" Paseman, 2011.12.08

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .