The Markovian State Space of War

When I was a kid, one of my favorite card games was War. In retrospect, I don’t really understand why I got so much enjoyment out of it, given that there is absolutely no strategy to the game whatsoever. If you happened to miss this game during your childhood, the rules are simple:

The deck is divided evenly between the players face-down. Each player reveals his top card, and the player with the higher card puts both the cards on the bottom of his deck. If the cards are of equal value, each player plays three face-down cards and a fourth face-up card, and the higher-valued card wins all the cards on the table. This is known as a war. In the case of another tie, the process is repeated until there is no tie.

A player wins by collecting all the cards. If a player runs out of cards while dealing the face-down cards of a war, he may play the last card in his deck face-up and still have a chance to stay in the game.

As you can see, since the player has no knowledge of which cards are in their initial hand, and no choice in which cards to play, this game could just as easily be played by a properly trained parakeet. The mechanical gameplay and lack of strategy, however, makes certain questions about the game mathematically interesting.

The other day when this game popped into my head, one of the first things I remembered about it was how many games I left unfinished due to their sheer length. I suddenly became curious about the expected number of turns required to finish a game of War.

It turns out that the answer is “about 277” (which is considerably less than I expected). You see, people on the Internet tend to be pretty big nerds, and certainly I wasn’t the first one to consider writing a War simulation to figure out these kind of statistics. What I didn’t see discussed, though, is any treatment of the structure of a game of war.

Unstumping the Internet and New Interesting Links

Two new items have been added to Nerdland today.

First, on the left hand side you will see a link to a new section entitled “Unstumping the Internet“. The purpose of this section, as its index page explains, is

This set of pages is for cataloging relatively brief answers to questions that I had to figure out myself after being unable to find the answer on the Internet. […] When I encounter a question that I cannot find an answer for on the Internet, and especially if in my searching I notice that several other people have asked this question with no satisfactory answer, I will post the answer here when I discover it. The hope is that next time someone searches the Internet for this question, they will find my answer.

So this section is not something that I expect anyone to read frequently, or even at all. I’m not going to be posting to the front page when I add new articles there, as the whole point of this section is to not clutter the front page with items of limited interest and minimal depth. Instead, I hope that these pages will visited primarily as the results of search engine queries.

Secondly, on the right hand side, there is a new section of links entitled “Interesting Items Elsewhere”. This is a listing of the last few items from other weblogs (or other sorts of feeds) that I have found most interesting. This is in fact tied to my Google Reader account, and displays items that I have “shared”, so these may not always be completely serious or computer-related. You can click on the “more” link at the bottom to see everything I’ve shared, as opposed to just the few most recent items.

Islanded in a Stream of Chars

From the “things that really shouldn’t be difficult, but for some reason are anyway” department comes the following. Do you think you know how to program in C++? Familiar with objects and polymorphism and templates and everything? Then this should be dead easy. Should, I said.

Problem: Write a function that takes in a `std::istream` and a size `n` and returns a `std::string`. The string should contain the first `n` characters of the input stream, with all formatting (whitespace, newlines, etc) preserved.

You can ignore all concerns about multi-byte characters for the sake of this problem. Sounds simple, right? You’d be able to crank this out in ten seconds if someone asked you this in an interview, right? Okay, now try it with this caveat.

Caveat: You must do this in a purely C++ “style”. To be precise, you must do this without using any character variables or character arrays. Use only a `std::string` object (or some other memory-managed object in the standard library) as your input buffer.

For as much as the C++ STL tries to encourage you to use RAII-oriented containers instead of raw arrays, this seemingly trivial task requires some surprisingly baroque coding. If you want to test yourself, try writing the function before you click more.