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!

Catching up a bit...

Sometimes it seems like there's some catching up to be done. Let's go ahead and do a bit of that today...

First, I will be at Supercomputing 2009 until Tuesday of next week and I don't think my phone does blogger, so there will likely not be a post next Monday.

Next, on the Computational Complexity blog, I saw a link to a CS Theory blog. This blog updates with job postings and conference deadlines relevant to researchers in the theoretical cs community. Awesome! (If they want Computational Complexity papers, perhaps board game complexities are acceptable...)

A few weeks ago, I mentioned a paper about the winnability of misere Hex. Much like normal Hex and Chomp, they are able to determine non-constructively which player has a winning strategy. Unlike these other games, it turns out not to necessarily be the first player, but instead to be based on the parity of spaces on the game board. Still, their argument uses a strategy-stealing approach, just with a special twist. This is something I hope to talk about more in the near future.

On my office whiteboard there is a short list of potential post topics that I haven't yet got to. The list looks something like this:

* Locality of where-to-play in games.

* Strategies of initial positions

* Why do people seem to prefer partisan games?

There's another one: "* Complexity Results" but I can't recall which results I was talking about when I scribbled that down. In any case, if you'd like to hear about one of these, let me know.

Finally, there were some questions I posed on this blog that I haven't yet answered, mostly because I either haven't finished reading all the papers suggested or because I haven't been able to find those papers. Most notable is this question:

Question: If you add two instances of a game together which creates a new instance of the same game, does this imply that the game is easy?

I mentioned that the Nimania counterexample doesn't really apply for what I was looking for, but I was referred to some other papers:

(i) A.~S. Fraenkel and Y.~Yesha [1979], Complexity of problems in games,
graphs and algebraic equations, {\em Discrete Appl. Math.\/} {\bf 1},
15--30;
(ii) A.~S. Fraenkel and E.~Goldschmidt [1987], Pspace-hardness of some
combinatorial
games, {\em J. Combin. Theory \emph{(Ser.~A)}\/} {\bf 46}, 21--38;

I have not been able to get access to either of these papers electronically or in our library. (Wittenberg's library is not as grand as a research institution's, but is very good for a small school!) I may wind up just seeing if I can get them from tOSU, but if anyone else has a comment from the relevance of either of these, I would appreciate that also!

Have a great weekend! Another post arrives on Wednesday!

GenCon 2009

Today's is a short post, but that's okay. Here are some pictures of me and my fiancee at GenCon 2009 in Indianapolis.

The problem I've mostly had is how to explain what GenCon is, because it neither stands for something or is short for something meaningful. "Lake Geneva, Wisconsin" doesn't mean that much to a whole lot of people.

Summing with Misere Games (Part 3)

As I mentioned last Wednesday, I taught my software class how to perform the traditional (disjunctive) method for summing games. So far their projects have been excellent, but I think this one is complicated enough that they're getting an extra week to work on it. We'll see how they do (my class only has 2 students, so there is only one project turned in each period).

In order to describe the disjunctive sum, we did some examples. First, I added 1-2-3 Nim to a Kayles 4-line:

+

We played around with this a bit. My students are both very bright, and we've been moving pretty quickly through the class, so it was fine to take a big chunk of class time to actually try to win this summed game. My students correctly determined that you want to be the second player to go on this board (thus it's in "zero" or P... but not meaning Polynomial-time P... the other one).

I knew I also had to describe what to do with misere games. Thus, we played the same game as above, but with the nim side being misere. The class again correctly decided this game is in P.

For a last trick, I switched, making the nim game normal but the Kayles misere. The class now noticed that the game is in N! The amount of misereness hadn't changed, but where it was located had!

This is what is a bit startling. Namely, the misereness can make a difference depending on which side of the summand it's on! I can't think of a better example for students to use the Composite design pattern (I'm putting a strong Object-Oriented emphasis on the software course). This curve ball of misereness can be a bit frustrating, but it can be a fun curve ball to play with as well!

As a question for this post: nim is solved for both the normal and misere versions. What about versions where some of the piles are misere and some are not? Additionally, what if we designate certain subsets of piles to all be misere. As with examples above, that doesn't mean that each of the piles is misere, but that that collection of piles as a whole has misere status. Can we efficiently evaluate all those piles? What if some of the misereness groupings overlap? (Notice this last one doesn't fall into the theory of summed games, which break down as trees of subgames. Does it matter?)

Summing with Misere Games (continued)

As I mentioned before, it's actually a bit difficult to find a good definition of how to take game sums when including misere games. The rule that a player loses if they make the last move in a misere game seems a bit "tacked on". Then the overall rule is very inelegant: a player loses when they can either no longer make a move or when they make the last move in a misere subgame. The first part needs to be in there in case there are no misere subparts.

This sort of inelegant construction reminds me of defining exponents back in grade school. I understood that 10^2 was 10*10 = 100 and that 10^1 was 10. 10^0, though? Why is that 1? Why not 0? Sure it fits the pattern, but the definition is still a bit skewed. I reasoned that there had to be a patch. 10^x was really 1*10*...*10 instead of just 10*...*10. Thus, 10^1 was 1*10 and 10^0 is just 1. That patch made things made sense. Excellent!

I think a similar patch could be used here. Notice that if we add to any game a one-move misere component (say, a misere nim game with a heap of size 1) the strategy of the game doesn't change at all; a player with a winning strategy should never choose to take the stick in that heap. Now, whenever we sum games together, we'll also add in that one-move misere game, just like we also multiplied by 1 above. With this, we can get rid of the dual rules for who loses a combinatorial game. The rule is now just: whoever makes the final move in a misere subgame loses. While it's true that the boardscape may be polluted with lots of these single misere games, neither of the players will pay them any attention until the final turn.

Yes, this logic may just be trading one patch for another, but this very strongly hints that misere should be the basic form of play instead of "normal" play.

It's hard to agree with this, however, when we are painting games in such a pessimistic light, basing results off the loser instead of winner!

Okay, I still have more to say... hang on until Monday. :)

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!

Best Intro Game?

I just had a wonderful visit this weekend with my soon-to-be-in-laws and they described playing Candy Land with their grandkids. Although I never played much as a kid, I think it's a good introductory board game. The game has good visuals, both using the imagery of delicious candy, but also using colors instead of words or numbers to describe moving around the board. This definitely appeals to 3-5 year olds---whatever that age range is called---and is likely the first board game many American children play.

What about when it's time to play games in the classroom? What should a student's first game be then?

I'm focused on impartial games, and versions of Nim had popped up in my elementary and middle school classes. Basic Nim is a candidate for a good introductory game: it is both simple and (surprisingly) has a very sneaky trick to determine who is winning. This gives it a very satisfying quality: we learn about the rules of a game and some of it's underlying details and then, happily, we find a strategy to play the game well! This is unlike some other games that are more fun to play but might be disappointing to students because they don't reach this step.

The text Lessons in Play decides not to introduce impartial games until much later, instead beginning with Domineering. This is another nice game, due partly to its simplicity. Another key point here, though, is that this game uses pieces from other known games: a checkerboard and dominoes. This can lend a sense of creativity to students. "Use your imagination to create your own games from the pieces around you!"

I've also heard from people who swear by Hackenbush. This is a game where your turn consists of erasing an edge of a graph (usually drawn on a whiteboard) that corresponds to your color. After your turn, if there are any subgraphs not connected to a ground node, those are also erased. This game has the excellent feature that it is super customizable and doesn't need to use a parallel-to-the-ground board at all. Again, this sort of thinking outside the box can be very beneficial to students!

Note that both Domineering and Hackenbush have easy extensions to impartial games. Thus, that transition can be made easily.

What else do people prefer? Are these two the most common? Is there anyone out there who advises doing impartial games first?