<p>I've been working on war for the past couple of days.</p>

<p>In particular I've been interested in the longest possible game, given no cycles. By backtracking, starting from the end position, I managed to avoid anything that goes into cycles. I used a dynamic greater-than relation to avoid having to decide what cards had what value from the start.</p>

<p>Even with those optimizations, I've only managed to create the following table, where the left column is the number of cards in play, and the right column is the length of the longest possible game:</p>

<pre><code>1   0       13  62
2   1       14  467
3   3       15  85
4   7       16  261
5   9       17  107
6   17      18  &gt;=935
7   17      19  137
8   29      21  168
9   31      23  209
10  53          
11  45          
12  79          
</code></pre>

<p>Interestingly I found, that odd number of cards, give a much larger chance of cycles. This makes it much easier to find the longest game, as there are far fewer positions to consider. The maximum length of these games is ery close to a second order polynomial.</p>

CC BY-SA 3.0
2011-06-24T15:05:18.543Z
Could you explain what you mean by branch-n-bound?
Good Person
CC BY-SA 3.0
2011-06-23T20:25:00.350Z
2013-11-18T12:07:38.823Z
2013-11-18T12:07:38.823Z
Thomas Ahle
<p>I was thinking of determining the <a href="https://secure.wikimedia.org/wikipedia/en/wiki/War_%28card_game%29" rel="nofollow">game of war</a>. I could write a fairly simple game that takes two "decks" of cards, and plays them against each other but I do not think this is optimal. </p>

<p>Because in war the order of the cards matter it is also not a question of simply summing up the "power" of the cards. If the decks were Q-Q-J-J and K-K-1-1 then the game would go as follows even though the first player has more power:</p>

<p>Q-K (QJJ, K11)</p>

<p>Q-K (JJ, 11QK)</p>

<p>J-1 (J, 1QKQK)</p>

<p>J-1 (1J, QKQK)</p>

<p>1-Q (J1J, KQK)</p>

<p>J-K (1J, QK1Q)</p>

<p>1-Q (J, QK1QJK)</p>

<p>J-K (͏∅, K1QJK1Q)</p>

<p>∅ (͏∅, 1QJK1QJK)</p>

<p>I've been trying to think of a method of determine the winner of the game without going through the entire deck each and every time (and thus possibly going for thousands of iterations.)</p>

<p>If you could provide me with some pointers to start thinking about this question - that would be great!</p>

<p>I wasn't exactly sure where to ask this question: so if this is off topic here please redirect me.</p>

CC BY-SA 3.0
2011-04-22T22:24:53.800Z
Initially I don't want to care about "ties" but in the real game players "hide" 3 cards and show the 4th. The winner takes all.
Good Person
CC BY-SA 3.0
2011-04-23T06:00:23.543Z
You may or may not be aware that a (deterministic) game of war may be periodic, so deciding the winner isn't as trivial as it first seems; you have to watch out for repeated game states. See http://mathoverflow.net/questions/11503/does-war-have-infinite-expected-length
Ross Churchley
CC BY-SA 3.0
2011-04-24T00:30:08.633Z
@Ross: Yes, the worst case O is O(∞);  I am thinking about the average case. Thank you for pointing me to that question though
Good Person
CC BY-SA 3.0
2011-06-25T02:26:38.677Z
The worst case isn't O(infinity), since you can of course always detect the loop! (And if it _were_, it would immediately imply that your average case was O(infinity) too, since the worst case occurs with non-zero probability!).  I think this is an interesting question, but might be better suited for math.stackexchange.com (which handles more 'recreational' questions); try there, maybe?
Steven Stadnicki
<card-games><combinatorial-game-theory>
Is there a method of solving the game of "war"
Good Person
# Is there a method of solving the game of "war"

(Asked by: username_0 on 2011-04-22)

I was thinking of determining the [game of war](https://secure.wikimedia.org/wikipedia/en/wiki/War_%28card_game%29). I could write a fairly simple game that takes two "decks" of cards, and plays them against each other but I do not think this is optimal.

Because in war the order of the cards matter it is also not a question of simply summing up the "power" of the cards. If the decks were Q-Q-J-J and K-K-1-1 then the game would go as follows even though the first player has more power:

Q-K (QJJ, K11)

Q-K (JJ, 11QK)

J-1 (J, 1QKQK)

J-1 (1J, QKQK)

1-Q (J1J, KQK)

J-K (1J, QK1Q)

1-Q (J, QK1QJK)

J-K (͏∅, K1QJK1Q)

∅ (͏∅, 1QJK1QJK)

I've been trying to think of a method of determine the winner of the game without going through the entire deck each and every time (and thus possibly going for thousands of iterations.)

If you could provide me with some pointers to start thinking about this question - that would be great!

I wasn't exactly sure where to ask this question: so if this is off topic here please redirect me.

**Tags:** card-games, combinatorial-game-theory

> **Comments:**
> **username_0**: Initially I don't want to care about "ties" but in the real game players "hide" 3 cards and show the 4th. The winner takes all.  
> **username_1**: You may or may not be aware that a (deterministic) game of war may be periodic, so deciding the winner isn't as trivial as it first seems; you have to watch out for repeated game states. See http://mathoverflow.net/questions/11503/does-war-have-infinite-expected-length  
> **username_0**: @Ross: Yes, the worst case O is O(∞);  I am thinking about the average case. Thank you for pointing me to that question though  
> **username_2**: The worst case isn't O(infinity), since you can of course always detect the loop! (And if it _were_, it would immediately imply that your average case was O(infinity) too, since the worst case occurs with non-zero probability!).  I think this is an interesting question, but might be better suited for math.stackexchange.com (which handles more 'recreational' questions); try there, maybe?  

---

## 1 answers

### Answer by username_3 on 2011-06-23. Score: 4

I've been working on war for the past couple of days.
In particular I've been interested in the longest possible game, given no cycles. By backtracking, starting from the end position, I managed to avoid anything that goes into cycles. I used a dynamic greater-than relation to avoid having to decide what cards had what value from the start.
Even with those optimizations, I've only managed to create the following table, where the left column is the number of cards in play, and the right column is the length of the longest possible game:
1   0       13  62
2   1       14  467
3   3       15  85
4   7       16  261
5   9       17  107
6   17      18  >=935
7   17      19  137
8   29      21  168
9   31      23  209
10  53          
11  45          
12  79          

Interestingly I found, that odd number of cards, give a much larger chance of cycles. This makes it much easier to find the longest game, as there are far fewer positions to consider. The maximum length of these games is ery close to a second order polynomial.

> **Comments:**
> **username_0**: Could you explain what you mean by branch-n-bound?  

---

