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 branch-n-bound'ing, starting from the end position, I managed to avoid anything that goes into cycles. I used an incremental cycle detection to avoid having to decide on 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, are also very close to a second order polynomial.