Misere Hardness

I'm very pleased with the way my software engineering class is going. I've accidentally asked the students to code up some difficult games at times, but they've done a good job of figuring out exactly how to fix these issues. For the most part, using a game suite as the continuing project has worked extremely well!

Early on, I asked them to include both nim and misere nim. As with all misere games, misere nim is the same game, except that the person who makes the last move loses. Thame Plambeck used to maintain Advances in Losing, a blog solely about misere games. My first combinatorial game, Atropos, was misere: the first player to create a 3-colored simplex (triangle) loses. The misere notion is very intuitive for many games.

As we continue with the ongoing class project, I have continued to add difficult parts but at some point I stopped asking them to add more games to the suite. Oops! Currently, I've given them another tricky task: have users make moves through a series of mouse clicks (instead of entering choices in text boxes). I figured it was time to throw in some new games along with that. At the same time, I hope they realize they can apply "misereness" with any games, and not just with Nim.

Solution? They've already programmed a simple version of Kayles and Hex, so why not include misere Kayles and misere Hex? Even after thinking about that, I became immediately interested in misere Hex. How does that game work? Whichever player first creates their bridge between both sides loses? Weird! Who wins misere Hex? What is the complexity of this game?

In 1999, Jeffrey Lagarias and Daniel Sleator tackled that first question. They find the immediate intuition---that the first player never has a winning strategy---incorrect and instead base the winnability on the parity of the board size. They do this by showing that the losing player can stretch out the game play until the final hexagon has been colored. Thus, on boards with an even number of hexagons, the first player can win! The proof they give applies to games starting from the initial (empty) game configuration.

Does this answer the complexity question? Not in any obvious way. In order for the complexity to be solved, an algorithm would have to work for any game state. One can invoke a board where the game cannot be dragged out to fill in all the cells. (Give red two nearly-complete paths with only one hex missing, and let the rest of the board be filled in. If it's red's turn, what can they do?) It could be that the proof generalizes well into an algorithm.

Thinking from the complexity angle, as this blog (too?) often does, is there anything we can say about the relationship between the complexity of a game and it's misere counterpart? Again, I am interested in considering Atropos, which is already misere. The non-misere version means that the first player to create a 3-colored triangle wins. In this impartial game, each player may choose to color one circle any of the three available colors. The circles are laid out similarly to hex---so that each has six neighbors---inside a triangle with borders colored to suffice for Sperner's Lemma. This means that any play along the borders can win: there are always two different neighboring colors, so simply paint that circle with the remaining color.

Thus, the strategy from the initial position is easy. Choose one of those bordering circles and paint it the third color. Game over. In mid-game positions, however, a player must choose to paint a circle that neighbors the last-painted circle (if an open circle exists). Thus, the game might not be quite as simple from any given situation; one of the border circles may not be adjacent to the last play. (But why wouldn't the first player have just won the game? Why would you ever get to this situation?)

In general, are there any results about misere games and complexity? It's been a while since we phrased a question, so let's do it: (I've been marking the relevant posts with question# labels).

Question (2): Given a game G and it's misere version, M, must the complexity of determining the winner of one of these games be in P?

I think this is the best way to phrase the "What is the relationship between the complexity of G and M?" question. Consider nim and misere nim: both are easy. With Hex and Atropos, each has a PSPACE-complete version, but the opposite looks like it might be easy. Is there a game I'm overlooking which is hard both normally and misere...ishly? (someone help me out with French!)

Of course, I'm still curious about misere Hex.

Question (3): What is the complexity of determining whether the current player in misere Hex has a winning strategy?

For those interested, user Zickzack at boardgamegeek.com has a good description and list of misere games.

Economic Game Theory vs CGT

When I started grad school in computer science, I quickly learned it was dangerous to admit that to people. "Oh, that's great! You can help me fix my computer!" Though I'm no Linux guru, it quickly became my safe haven: "Which OS are you using? Oh, I haven't run Windows in years... I don't know anything about that." At least that wasn't a lie; I just have no experience cleaning up viruses, etc. Still, I learned it was often easier to tell people I was studying math instead and save the whole explanation. Again, this wasn't too far from the truth. Theoretical Computer Science doesn't look much like computer science to most people.

Nowadays I'm faced with an alternate dilemma related to explaining my field. Talking with other computer scientists, I will often simplify things by saying I am studying "game theory". Sometimes there are no follow-up questions, but other times people will assume you mean economic game theory or derivations thereof. I still haven't mastered handling this situation, but here's how it seems to go.

Me: "Oh, I'm more focused in combinatorial game theory, which isn't quite the same."

Them: "Combinatorial?"

Me: "Yeah, like board games."

Them: "What is there to study there?"

Me (getting all excited): "Well, we try to say things about who can win a game."

Them: "So you could figure out who's going to win a game of Monopoly?"

Me (somewhat less excited): "Well, we try to work with simpler games, like Hex or Chess."

Them: "Chess is simpler than Monopoly?"

Me: "Well, Chess doesn't have any randomness in it-..."

Them: "I think Monopoly is much easier to play than Chess."

Me: "..."

I would much rather replace this with the following conversation:

Them: "Combinatorial?"

Me: "It's similar to the economic side. ."

Them: "Oh. How do you do that?"

Me: "We investigate these things by looking at simple board games. Sometimes what looks simple can wind up being very complex."

Them: "Wow, board games can do that? That's pretty cool!"

Me (beaming): "Yeah, totally!"

I know some of these similarities and differences, but how can I phrase them well? More importantly, how can I state this in a clean way that will not legitimately spark a "whatever!" from someone with a knowledge of economic game theory? A dangerous task indeed!

Ranking Football Teams... Again

A few weeks ago, I posted about tournament ranking algorithms. Since then, I wrote a little algorithm (the simplest I could think of) and have run it on this year's results after each week's games are over. I'm pretty proud of what's come out of it, but I realize there are still a few issues that may need to get smoothed out.

As I'm mentioning to my software engineering students, I'd really love to have the code be very reusable so it could be used as a ranker for other sorts of tournaments. With this in mind, I've tried to use all the OO-design principles I'm handing out in class. So far, this has been working very well!

I'm definitely at a point where I want to start talking about the algorithm, and listening to complaints about the rankings, etc. The latter is easy (I have Iowa up top) but the former is a bit more scary. If I had a paper, I would simply upload it to arXiv so that it was clearly dated and submitted by me. What do I do if I just have a code base?

One goal for this algorithm is for it to actually match up with rankings from previous years. If I can closely match to those, then perhaps I can not only say something about the strength of the algorithm, but also about how people determine which teams are better.

I mentioned above that this is the simplest algorithm I could think of... so how it is then that I am modifying small parts of it? Part of the flexibility of this system is that you can plug in different functions that reflect the value of a win or loss, difference in score. Thus, using different functions, I get different results (both of the ones I have created so far put Iowa up top; please feel free to complain).

There are a lot of these ranking algorithms (tons here) but how can I determine whether any are the same as mine without looking at the source of each of them? I think I'll probably just put something up on arXiv...

Conferences for Combinatorial Games

One thing I'd like to provide here is a list of good options to submit combinatorial game papers to. Unfortunately, I'm just unfamiliar with these options.

Two years ago, I managed to get a paper about Atropos into the Workshop on Internet and Network Economics (WINE) 2007, though I think I was just lucky enough to be covering a lot of current keywords. Nevertheless, it was a great workshop and I saw a lot of cool results as well as met a bunch of excellent people. The audience was very interested in Atropos, and people were immediately remarking on different aspects of the game ("What happens if you change the coloring of the background?"). At the end, someone came up to me and mentioned that this presentation was going to be one of the most memorable from the workshop!

I was ecstatic, but I also realized that I was probably very lucky; it would be unreasonable that I would have such luck again. Later, my adviser discovered the Fun With Algorithms conference, which seems to be a great place to submit future combinatorial games papers. I also know that many people submit CG papers to Richard Nowakowski's Games of No Chance compilations.

Unfortunately, that is about the limit of my familiarity with combinatorial games papers. I know that results have appeared in many different conferences/journals/etc in the past. These days, however, what are the suggested avenues for publishing CGT results?

Games and Surreal Numbers

At Colby College, where I did my undergrad, a visiting math professor named Leon Harkleroad gave a talk on Surreal Numbers. Being a good math major, I went to the talk, even though my interests were sharply drifting towards computer science. In high school I had been very interested in the notion of infinity, and I was quickly drawn into the material as the discussion of omega and other non-real numbers began.

In surreal-land, numbers are built from two sets of numbers with non-overlapping ranges. The sets, say L and R are then written in the form {L | R}. Since they are non-overlapping, without loss of generality, we can say that all elements of L are less than all the numbers in R. (This is the aspect that separates surreal numbers from games, wherein L and R can overlap.) Then the "value" of that surreal number is directly between the largest value in L and the lowest value in R.

Thus, you can define an infiniteish number, ω, as: {1, 2, 3, 4, ... | }. The amazing thing about surreal numbers is that you can perform basic arithmetic on ω: 2ω, ω + 1 and ω - 1 are all attainable in surreal number land. Leon gave a great talk and was very accessible to the undergraduate level, though I didn't give it too much thought for a long while.

A year after Leon's talk, however, I was lucky enough to hear John Conway give the keynote at a small-college computer science conference in Rhode Island where I presented my first paper (in poster form). He played some dots-and-boxes against a member of the audience on a small board, promising that his opponent would soon figure out how to beat him. Unfortunately, "soon" took quite a long time and his allotted time quickly began to run out; we students were quite anxious for our poster session and for the attention to be lavished on us. After the game was solved, he swiftly started drawing some basic Hackenbush figures on a new slide. Time was of the essence, but he showed how in this game, players could derive numeric values from the game positions. The figures were nothing more than line-graphs sticking out of the ground, but the intuition behind their evaluations was clear.

Then he drew another line, and used a vertical ellipsis to show that it continued infinitely skyward. Even as he was saying, "We refer to this value..." a light in my head went off: "... as ω". The connection to surreal numbers was there.

Unfortunately, time was up. John was forced to end on that note and may have missed getting to connect that to computer science. We hurried out of the room and to the poster hall.

Fall Break

I forgot to mention last week, but Wittenberg has Fall Break this week; there will be no post today, though I will post on Wednesday!

Complexity of Games with Randomness

It is known that Hex is a PSPACE-hard game. (See this page, it is the "Hex ist PSPACE-vollstaendig" paper by Stefan Reisch.) Once we add a bit of randomness, however, the strategies suddenly become far easier! As I think I've mentioned before, if you change the game so that the current player is chosen by the flip of a coin, the winning strategy becomes simple.

I'm also interested in trying to analyze some games by removing their sources of randomness. Instead of relying on die rolls, for example, give each player the set of potential die rolls and let them choose one at a time, then removing that "roll" from their set of available moves. Once all options are chosen, either the player has no more moves or they get a new set of false rolls. I don't know of any analytical results like this, but I would love to see them!

On the other hand, I also have some interest in answering complexity questions of games that include randomness. For example: What is the probability that the current player has a winning strategy? Alternatively, rephrasing as a decision question, does the current player have a strategy that will allow them to win with probability > .5?

I don't know of any results like this. Do they exist?