# Algorithmic war

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.

• 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. – Joel David Hamkins Dec 8 '11 at 12:27
• @Joel: check out the edit, hopefully it clarifies things... – Igor Rivin Dec 8 '11 at 12:39
• 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? – Barry Cipra Dec 8 '11 at 15:00
• @Barry: I am just reconstructing the rules I remember from my childhood (plus, what I suggest seems more canonical, but you might not agree...) – Igor Rivin Dec 8 '11 at 15:02
• 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. – Joel David Hamkins Dec 8 '11 at 15:06