Tricky Last Moves and Schedule Change

There are two parts to this post. The first is actual content, but the second is some metaposting about the schedule. The short version is that I am switching to a Tuesday-Friday schedule instead of MWF. I am simply too busy to keep up with posting on my three busiest days of the week, so I will instead post twice per week.

Often, the end of a game is not when the difficult decisions arrive. There are certainly some sneaky final chess positions (I used to see them in the paper) but often either the last moves are a bit obvious or Chessmaster has already forfeited the game to you. (I'm not a good chess player... perhaps I'm completely wrong about this!)

Assume it's your turn and it's the last turn of a game. If that game is Amazons, it doesn't seem hard to determine if you've won. Similarly for Mancala. Each potential move is simple enough that you can try them all and see what the outcome is. In some games, however, there may be a large number of different potential final moves. What do you do in this case?

I picked up the game Cave Troll over the winter break and found myself taking way too long on the last turn of the game. The scores were close, and I had to figure out how to spend my four "actions" on my final turn to maximize the gold I would collect. Worse still, depending on which actions I might use, the game might not even end that turn!

Although I might have had a reasonable number of options for one action, say x, now I have a similar number of options for each of my four actions: meaning about x^4 in total. If we generalize this game, the number of actions might be one of the generalized variables, making it x^n options. Oof!

Which games are hard to make last-turn plays on? Are there lots of good examples of this?

Common Ground: EGT and CGT?

I took a Game Theory course as an undergrad in the fall of 2000. In this course, we studied a smattering of standard game theory as well as some voting theory. Now, I don't know exactly what is considered "game theory" but there are often some keywords that clue me in when someone is asking whether I know something about the economic side of game theory. I'm not ignorant of these terms, especially having taken a class, but I'm not a pro either! I have not tried to come up with utility functions as a model for different market outcomes. Nor am I familiar with different scenarios where a Nash Equilibrium exists and can be found quickly.

Still, as I mentioned recently, I dug into economic game theory definitions and used the term "symmetric game" to describe a game equal to its negative ("reflection"?). In both arenas, we still have players who make decisions and the game state they are looking at has a value. In both arenas, we talk about making a move and how to remove suboptimal choices.

How well do these different fields actually intersect, then? If a course were "team taught" covering aspects of both topics, would students be totally lost, or would there actually be some cohesion there?

Best CGT resources online?

One of the hopeful points of this site is to provide many links to other combinatorial game sites. Last semester I made many changes to the site in order to add and rearrange links. I continue to wish there were more links, however! In particular, I would like links to:


Your/Someone's CG site. If you are a gamester or know of someone else who is one, and have a website that mentions gamestering in any capacity, please let me know!

A playable game online. I have a few links up on the side, but I know I must be missing others! Let me know and I will add them!

Classic/Exciting/Good CG papers. I would love to add links to available papers!


At some point, I should also likely try to jazz up the layout of this blog more. Since the new semester has started, however, I know that won't be happening any time soon. I still wish there were a site with a table that compiled known properties of winnability of games. Perhaps I should start putting that together myself.

Sorry for the short post! See you again on Wednesday!

Game Description: Sprouts

Sprouts is a nice impartial game that two people can compete at using a piece of paper or chalkboard. This is true with lots of games, except that this game is extremely easy to set up.

Just draw a handful of dots on the paper at a reasonable distance from each other.

Each turn, a player chooses two dots and connects them with a line. In the middle of that line, the player draws a new dot. Then their turn is over. There are some restrictions here: the line may not cross any other lines (or go through any other dots) and, when finished, the dots cannot have more than three lines coming out of them. A player may choose just one dot and draw a looping line, but then this counts as two lines connected to that dot; the new dot drawn separates the line into two pieces.

In lieu of diagrams, here is a nice Java Sprouts applet.

Notice that the new dots drawn already have two lines coming out of them, so they can only be connected to one new line.

Sprouts is an extremely popular game in the Netherlands, with tournaments with large numbers of initial dots held.

As far as I am aware, the computational complexity of playing Sprouts is unknown. There is an interesting conjecture about the winnability from the starting position using a period of 6. The Sprouts Conjecture says that if the game begins with n dots and n is equivalent to 0, 1 or 2 modulo 6, then the second player has a winning strategy. Otherwise, the first player has a winning move. This seems like a high number for periodicity, especially for a game where there is no quick-trick to evaluate. Lots of effort has been put into supporting this conjecture, however. All starting positions up to n = 32 have been confirmed, including a few higher scattered cases!

Need a simple-to-play game? Pull out some paper, draw a few dots, and you're ready for Sprouts!

Is there such a game...

My lack of knowledge of all the material in CGT often comes out when I try to talk about a general aspect. Luckily, there are enough people reading this that they let me know about it and correct me! Sweet!

Other times, this happens when I'm trying to prove something and realize I'm just not familiar with enough games out there. This morning, I was considering a game and hoping I could show it was PSPACE-complete. Then I realized that the method of play was dissimilar from any other games I knew anything about.

I have mentioned before that I think those reductions that transcend locality or number of players are excellent. Now I'm curious about involving the number of pieces.

What is known about games where each player has only one "piece" or one "location" at each game state? Through the course of the game, the two pieces may traverse the board. Are there any proven-hard games out there with a property like this?

Many games could be considered to have only one "location" per move, such as with Kayles. In that example, though, the location of your last move does not restrict the location of your next move; you can still make the next move wherever you like. This is not true if you're playing Amazons and each player has only one Queen; your options for movement are restricted by the current position of that Queen.

Double Misere

Is Chomp actually a misere game? Naturally, it seems easy to describe it as such: there is a grid of cookies, and if you have to take the upper-left cookie (or just take it on a whim) then the game is over and you lose. That cookie is poisonous, after all!

When I first heard it, however, it was described using normal play: you just weren't allowed to take that last cookie.

Sometimes this is how misere games are described: that last losing move just isn't an option. Strategies for those games are then equivalent to the misere description. You can no longer make that last move, so the current final move wins the game.

If we consider more flipping between misere and normal play, this is a bit nicer. Before, if we consider Chomp to be a misere game with the poison cookie, then flipping to normal play makes the game extremely trivial: eat that upper-left cookie and win the game instantly! Great!

If instead we consider the normal-play version where we cannot take the upper-left cookie, and we toggle the misereness, the game might be slightly more interesting. Here, a player loses if they take the last-remaining non-upper-left-poison cookie. This game is not as trivial as the other (how trivial is it? I have no idea!).

We could then convert this misere game into an equivalent normal-play game by removing all moves that are leaves on the game tree. Now we have a game which ends when two cookies are left: the top-left cookie and either the one directly beneath or to the right of it.

This is different than just toggling the misereness twice: we are building a new game by twice rewriting the misere-version of a game as a normal-play game. Otherwise, we would be left with the original game.

Bonus-play Hex

Though I keep talking about the game Hex, please do not assume that I'm a good player at all! I don't know why I have this fascination with a game I rarely play, but apparently I do. Perhaps the reason I like it is that you can define interesting variations on it. The study of Misere Hex has a nice proof that from the staring position, optimal strategies will force the board to fill up.

Alternatively, we could define Either-Color-Hex, which allows a player to paint either red or blue on their turn, but you still only win if a path uses your color. That doesn't change much of anything from standard Hex (why play the other person's color instead of your own?). Now, however, Misere Either-Color-Hex has similar strategies to regular Hex; you're always going to try to create a bridge with the other player's color.

... depending on how you define "winning" and "losing". It seems like we'd like to say that in Hex, you win if you complete your path. However, as we've covered before on this blog, we define this by describing when no further moves are available. Then, under Normal play, you lose if you cannot play on your turn. With Misere play, the opposite is true: you win if you cannot play on your turn. Hex games are "over" when a connecting path is created. Thus, you create your path and now the other player cannot make a move.

Unfortunately, now Either-Color-Hex doesn't work as anticipated. If the Left (Blue) player is about to complete a blue path, the Red (Right) player can color the last open hex blue to complete it. Then a path is complete and Right wins, despite the fact that the path was blue. That doesn't work as expected! (In fact, this game is now an impartial game, which isn't what was expected either.)

Misere Hex still works pretty correctly. Instead of trying to avoid creating a path in your color, you try to avoid creating a path of either color. However, since you can't play opposing pieces, their path will never end the game against your favor. Misere Either-Color-Hex, though, just has the same problem as Either-Color-Hex: both players will avoid creating a path of any color.

Let's see if we can fix this by changing the rules slightly. Instead of ending a game when a path is created, let's rule that a player cannot make a move when a path of the opposing color exists.

Now the Either-Color version of this game works just fine. Right can play the blue hexagon if they want, but the blue path "belongs" to Left. Left will continue to be able to make plays on the board, but Right will not. On their next turn, Left will paint a hexagon and then Right will have no more legal moves. Left wins.

Now the Misere Either-Color version does something strange: players are actively trying to create a path in only the opposing color. Once that is complete, the opponent will have another turn, but you won't have any. This works almost the same as standard Hex, but with the player roles switched! (The exception is on the last move. If Left makes the last hexagon and completes the red path, they won't be able to make any more moves. Unfortunately, since there are no more hexagons, Right wins anyways.)

This Bonus-play Hex has another nice property. When adding with other combinatorial games, it offers a bunch of extra free moves to the player who completes their path. If the board is mostly empty, the winner can keep making moves on that board later on in the game sum. This gives the Hex summand more priority: the winner will be able to use those extra plays later.

I should print out a board for Hex!

Have a great weekend, everyone!

Symmetric Games?

While working on one of my submissions for FUN over break, I tried to use a definition I was certain was a standard part of CGT. Much to my surprise, I couldn't find the term "symmetric game" in any current literature.

Google was able to find the term under standard "economic" game theory. The Wikipedia definition I found is almost precisely what I was looking for:

In game theory, a symmetric game is a game where the payoffs for playing a particular strategy depend only on the other strategies employed, not on who is playing them. If one can change the identities of the players without changing the payoff to the strategies, then a game is symmetric.

Instead of "payoff" however, we are comparing which strategy resulted in the game ending. Thus, if we switch which player uses which strategy, (and also swap which player goes first) then the player whose move ends the game should also switch.

More formally, in combniatorial game theory, we can say that a game G is symmetric if G = -G. (-G is recursively defined as: {-R | -L} where G = {L | R}.)

Is this already a known property for some games? Is this definition already named something else?

Where does this definition come into place? For many combinatorial games, the starting situation has this property. At the beginning of a game of Hex, for example, strategies for either side are equivalent. Both players have the same options for moves from that starting position: each child for the Red player is equivalent to the negative of a child for the Blue player.

Somehow, somewhere, this must already be defined! Please tell me where!

Break is over!

Break is over, and classes are in full swing here at Wittenberg. Since I'm hoping to teach my board games course next semester, I'm already trying to figure out how to peddle that notion to students.

I'm excited to be teaching the Intro Programming Languages course, as well as the Intro to Programming course. For this semester I'm learning two new languages and "recovering" two. Very exciting!

Similarly exciting, I'm hoping to get my research drive kicked in a bunch. I acquired four different games this holiday season (Boggle, Bananagrams, Mancala and Cave Troll). I've already played a bunch of that last one, and I think it must be NP-hard to figure out if you can win...

... which I'll hope to discuss later! I'm also preparing two papers for submission to FUN 2010 (due Friday!) so I can pretend that this blog is not my only research activity. :)

I actually have a bunch of Calls for Papers taped to my wall, but I'm not sure how relevant any of them are. We'll see what gets done!

I have some notes on my board about potential posts, but I'm still interested in talking about what people want to hear about! Let me know if there's anything you'd like me to discuss!

Happy New Year!