Locality of Plays

When I'm looking at a game for the first time, before I think about strategies and analysis there are two properties I first consider. First, is the game partisan or impartial? Second, can moves be made anywhere, or not? The answers to these help package the game into one of four buckets.

Though I may not have that many game complexity results under my belt, I can't even fathom how else to begin hoping to prove a relationship between games. Those shown links between relationships are always amazing to me.

Consider the computational complexity of determining who will win a game and then narrow your gaze further towards those games which are PSPACE-complete (no one has complained yet that I talk too much about this...). The basic PSPACE problem of satisfying quantified boolean formulae (QBF) is the setting for a game: players alternate choosing boolean values for the variables, starting with 1 and going up to n. In the end, if the formula is satisfied, then "there exists" player wins, otherwise the "for all" player wins. To say this differently (and more correctly), if the last (nth) quantifier is "there exists" then the last player wins exactly if the formula is satisfied. If it is instead "for all", then the last player wins exactly if it is not satisfied.

This game falls into the impartial-and-restricted box: the identity of the current player doesn't matter, but moves are restricted in that you can't choose the value of any variable: only the next one in the list.

Thomas Schaefer made a big jump in his collection of game complexity results (On the Complexity of Some Two-Person Perfect-Information Games) by showing that Kayles is PSPACE-complete. Yes, it is true that both games are impartial, but he uses the QBF game to show that Kayles is hard, despite the fact that general Kayles does not enforce any restrictions on where a player can move.

In his proof, Schaefer creates a reduction to Kayles that simulates the forcing, making players take specific nodes or immediately lose. This is one of those beautiful jumps that opens things up for everyone else. Personally, I would always look at Kayles first if I hoped to prove an unrestricted game to be complete for PSPACE.

Are there other excellent jump examples? Do you think other properties deserve this? I considered planarity, but it doesn't seem difficult to overcome this.

Initial Game Positions

Note: it's unlikely there will be a post on Wednesday, as I am traveling to Massachusetts for American Thanksgiving.

We know the following non-constructive result about Hex and Chomp: the first player has a winning strategy.

This only applies to games in the starting position, and for different reasons for both games (although they both go by the "strategy-stealing argument" monker). In Hex, we know that it is better to have more tiles of your color on the board, so it is naturally better to be playing first. In Chomp, we have a very special move from the first board. This move has, as children, all the other children of the initial position. Thus, if you go first, there are two possibilities: either one of those other children is a winning move (make it!) or none are, meaning that the special move is a winning move (make it!).

As mentioned, neither of these are constructive as in neither hint at the best strategy. They just mention that such a strategy exists. We've noticed a similar situation with Atropos (at least as far as brute force searches have allowed so far). A repeating pattern of winnability appears: boards with n open circles along a side have a winning strategy for the first player exactly when n is congruent to 0 or 3 modulo 4. The other two (1 and 2) have a winning strategy for the second player. This may seem a bit convoluted (especially since it's only been shown up through boards of size 11 or so) but it is the same as saying that the first player has a winning strategy when there's an even number of open circles on the initial board, and doesn't when there are an odd number.

In general, Atropos and Hex are difficult to analyze (both PSPACE-complete) and Chomp has resisted all efforts to figure out. Could it be that for many games, the complexity of those initial positions is just inherently easier than a general game state? To some, this is very disconcerting. In some cases, the general state argument is a bit distracting: it could be that a winning strategy exists from that initial position and is easy to describe. Complexity results come from reductions that don't usually say anything about the difficulty of the game in common positions.

Could it be, then, that this easiness comes from the size of information needed to describe those initial positions? In a game of Hex, to describe an intermediate state, you need to list the color (or lack of) for each hexagon. With an initial state, however, you only need to specify the size of the game board.

Have a great Thanksgiving! Also, if you will happen to be in the South-Central Ohio area next week, I will be giving a talk here at Wittenberg on Matchmaker on Thursday (Dec. 3). More info about that soon!

Emotional Machines like Partisan Games

There is a real difference between impartial and partisan games. I don't just mean that analysis is different, or that impartial games will always evaluate to Nimbers. I'm referring to something more basic:

People generally like playing Partisan games.

I can best present evidence by looking at the vast array of published partisan board games. It is hard to find published impartial games! Instead, published games are able to support some sort of mantra. I have my pieces and you have yours. I will build up my position and at some points there may even be a lack of interaction with whatever you're doing. We will race towards some winning condition. I will be able to see my strategy materialize, whether or not it is a good one.

All of these are aspects of partisan games that are missing in impartial-land. In that mystical place, every move forcibly interacts with your opponent. Your board strength is tied precisely into who is the current player and not in some separate position that you can see. Instead of racing towards a finish line, both players are the same racer, just worried about which leg will be forward when the ribbon is snapped.

I think it's natural that we don't like these sort of games. I'm looking forward to playing a World War 2 simulation game with my dad this thanksgiving, but I wouldn't be looking forward to it if after each turn we swapped teams!

In the past few years, I've made some off-hand comments (not here, in "real life") about people being bad logical machines, but instead good emotional machines. We often allow our emotions to make decisions for us instead of precisely reasoning through all the logical details. Sometimes this causes bad decisions to be made, but sometimes it lets us get to the heart of the matter and make decisions quickly. I'm in no way a psychologist, so I won't attempt to back this up with any data and keep blundering ahead.

Partisan games really clue into this emotional capability. "Well, at this point, there are lots of my tanks on the board and not many of the opposing tanks... I must be winning." We hope to be able to evaluate the strength of our board position and we can at least approximate this by taking a look at the game state. "Is it better to go first in Hex? Yes, it's better to have more of your pieces on the board." That is the basic response, and it turns out to be true, though an actual proof is somewhat more involved.

This is more difficult with impartial games. Near the beginning of a long game of Kayles on a complicated graph, I am not sure whether I'm winning or losing unless I check all the possible moves. Oof! That is a logical problem my brain doesn't want to have to work through. (At least, not on it's own.)

I may continue challenging my students to impartial games, but soon they're going to get sick and ask me to break out a Hex board.

P.S. Enjoy the greatest rivalry in sports this weekend!

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?