Summing with Misere Games (Part 4)

I got some comments while I was gone, but I haven't even read them yet. No fear: they will be read! Currently I'd like to discuss another issue raised by my students as they continue to code up adding games together. I asked the following question in class:

If I add a misere game with a normal game, is the result misere?

Keep in mind that my students are not in a CGT course; they need to be able to process this information in order to elegantly determine who loses a game. They determined that, yes, the game is misere. When the game is over, that means that the last move from the misere subgame was made, and thus the last player should lose.

We then went about coding up the simple isMisere() function that each Game object should have. Someday I hope to talk more about programming this all up, but today is sadly not that day.

Instead, I realized there that there was still a problem. That sum is misere, but is very different than if it is a sum of normal play games, made to be misere. What do I mean with this?

Consider the sum of nim games (each of one heap) with values 1, 2 and 2, with the added property that the last game (one with 2 sticks) is a misere game. When determining whether the sum is misere, we find that it is. The last player to play will lose.

Now, however, consider the misere version of the sum of the same games, where none of those subgames is misere. Again, this is a misere game: the last player will lose. The games, however, are fundamentally different, causing strategies between the two to be unequal. In the first version, taking the non-misere pile of 2 results in a win; the opponent will soon be forced to take that last stick from the misere pile. In the second version---where the whole game is misere, but none of the subgames are---taking a pile of 2 is a losing move; the opponent will just take the other pile of 2 sticks.

They are both misere, but on a different level. On a final, programming note: depending on how your misereness is implemented, these levels can be represented differently, either as a public or private property.

Perhaps there will be more on this later!

Summing with Misere Games

Again, I have assigned a new project to my software design class, and again I ran into a bit of a descriptive challenge. This time my class must redesign the project to include game sums. It's not too bad to describe the rules of adding two games together (each turn, a player moves on one of the two boards that were added together) and who wins (the player that makes the last move in all game boards).

...until you add in misere games. These games are phrased in terms of the loser, not the winner. The most simple way to "normalize" them, then, is to assume that players cannot make that final move in the game. Thus, misere nim can be rephrased as nim where you are not allowed to take the final "stick". Now this version acts as a normal play game.

So what happens when you have two games, one of which is misere, and you add them together? When, exactly, does one player lose or win? When is the game over?

We can state it as follows: the game ends either whenever a player makes the last play in one of the misere subgames (that player loses) or when a player makes the last play overall (only if none of the games were misere; that player wins).

The interesting point is that this is not equivalent to just counting that "misereness" towards the entire game. For summing a normal with a misere game, you cannot just add the two non-misere versions together and then state that the last person to play loses in the sum instead of wins. Instead, the misereness of each particular subgame must remain attached to that game.

This is unfortunate, because there is no way to construct every misere nim game (namely those with more than one pile) as a sum of single nim heaps, each of which might be misere. Instead you have to sum from normal piles then declare the whole thing to be misere. (This does put a good spin on the structure of the code my class has to come up with, though!)

Strangely, the definition of this adding takes a second seat to straight up analysis in textbook descriptions of misere games. This is my first natural question: how do we add misere games to other games? Instead, the analytical side seems to come up first: how do we evaluate sums with misere games? For gamesters, that is certainly the most pressing question, but for recreational players, this is a bit frustrating.

Unfortunately, I've run out of time! I hope to continue with this Friday, though!

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.

Programming Hex

Oops!

Two weeks ago I assigned my software engineering students a new project: they were to add Hex to their collection of combinatorial games. To this point they had only implemented impartial games; this was to be a bit of a wrench in the mix.

Unfortunately, I picked a poor partisan game. Hex itself is an excellent game, but I forgot that it was a bit difficult to determine whether the game is over. The obvious approach to determine this comes down to graph connectivity, something beyond the scope of the project. Oops!

Luckily, I quickly recalled the proof of the Hex Theorem: when all hexes are colored, there will be exactly one winner of the game. The late David Gale does an excellent job of describing the theorem in this paper, showing the link between Hex and Brouwer's Fixed-Point theorem. I explained to the students that they should follow the boundaries from one of the corners of the board and see which corner it ends up at. For example, if they choose a corner where the blue side is on the left and red on the right, they can hug either the blue or red boundary (this might be the same if most of the board is colored).

First note that this path created by the boundary cannot end; it will exit through one of the other board corners. Note next that it cannot exit through the corner exactly opposite; the colors there are on the opposite sides! Thus, the path will veer either right or left (from the point of view of the entering corner). If, like we said, blue is on the left and red the right and while hugging the blue boundary we exit to the left, it means blue has not yet won the game. If, on the other hand, the path exits to the right, then there are blue hexes connecting the two sides of the board: blue wins! The opposite is true for red.

My students coded up their project and it works very nicely! Still, next time I think I'll assign Clobber instead!

Special Sunday Bonus Edition

Yes, I was ill through Friday. Thus, I am having an extra post today. Enjoy!

I am currently teaching a software engineering course, and am assigning an on-going project. Each week, the students update the project to the new specifications as well as fix any errors I found in the previous round. So far it's going great, and I don't even have any CS majors in the class!

On one of the recent parts, they were asked to implement Nimania, which I mentioned in this post. I gave them rules, but, being good students, looked around for more about it online. They found... this post (it's the same link).

I'm really enjoying teaching this class. It seems important that theoretical computer scientists keep up with their programming skills. As a grad student, I was somewhat surprised to find that the theory professors were quite competent programmers: keeping up with current languages and teaching some of the intro CS sequence. By next semester, I will have to learn Python in order to teach our CS1 class, which will be completely new for me. I'm looking forward to this challenge but I'm also grateful for the motivation to learn another language.

Even more so, I am anxious to see how my students will model some specific combinatorial game fundamentals. I see two potential paths for one point, and I'm curious to see which way they go. Will they model things to follow basic CGT, or will they do something else? So far, they have had to only model impartial games, and only one at a time. I will introduce adding games together as well as partisan games as separate projects, and it could certainly make a difference which comes first! I'd like to see if I can get them to go the non-traditional route, but without any actual pushing. This seems unlikely, but I'll see what I can do.

Games and Difficulty to Just Play

I got the chance to play a handful of games of Equations yesterday with my department chair. This is a game I was introduced to in the eighth grade in a half-semester math games course. I finally tracked it down on the Internet last year and got a set at Christmas. Woohoo!

Until yesterday I had only played two or three games with my set.

It's hard to convince people to play Equations, mostly because you have to find someone willing to spend time playing a game and also who isn't bored by elementary math. The intersection of these sets isn't tiny, but it also isn't prevalent. Add to this that the rules are pretty complex and it's very hard to get random people to make it all the way to one game.

There is a reason I'm more interested in games with simple rules: it's easier for people to learn to play right off the bat. Whether or not it is easy to determine who can win is often second-hand to making the game accessible for many players. I love the game Equations---and I don't think it could exist without all the complicated rules---but it takes a few games to really understand what all the possible moves are. It's possible that you can make a winning, game-ending move this turn, but never see it (and no one else at the table might see it). Games are often like this. You can fully listen to or read the rules, but unless you see some of the moves acted out by people, you may not comprehend how the rules can be used. It often takes a few plays of any game before people have an understanding of all the moves they can make.

The above difficulty of seeing immediate-winning moves could be taken a step farther, though.

Question: is there a game where it is hard to get the set of all possible moves?

In the project my students are working on, one of the methods for their game class is: getChildren() which gives them all the potential moves from the current state. Are there games for which this is an unreasonable request?

I can see the following potential clarifications/things-I-am-interested-in/etc

Yes: there might be games that have an exponential number of children, relative to their size. I would rather, however, say that we should consider the complexity in terms of (size of game + number of children) since otherwise Nim already has this property.

Maybe: I'm kinda interested in games engineered around this question. I suspect they exist, mostly because I don't think it would be hard to throw in solving a 3-SAT question as part of each turn.

Totally: I want to know if there are already any games like this, either games that are played or games that are studied (or both!).

Today's post is a bit brief, as I will be driving this afternoon. This is not a long weekend for me, however; there will be the usual post on Monday! :) Have a great weekend!