Impossible Game States

While preparing some old work to go into my thesis two years ago, I realized a potential hole in my construction: could the Atropos boards described always occur in the midst of a game? I had built some convoluted board pieces, then glued them together in PSPACE reductions. But could these monstrosities actually be the state of a half-played game? Atropos has a requirement that players must play adjacent to the last play (if possible, otherwise you may play anywhere). Thus, some game states are impossible to reach.

Here, the lone red circle and the green and blue to the right are disjoint sections that could not have occurred without a colored circle surrounded by colored circles.

Does this ever happen with other games? Naturally, we need to consider a game that has regular starting position(s). Assuming we always start from a full n-by-m grid in Chomp, we will never see a board that is missing cookies in the wrong places.

A cookie in Chomp cannot be missing when any cookies up and to the right are also present.

Some games aren't quite so clear-cut. In Domineering, we would never have a board with an odd number of checkers covered. However, we might have that board as a piece of a more complex partition of boards, so it could be a legitimate subsection!

Consider Alice and Bob, who sit down to play a game of Chess. After a while, Bob thinks he is winning, and gets up to find a snack in another room. He returns and looks at the game board, realizing that he is actually in a bad state. What happened? Perhaps Alice switched pieces around, or perhaps Bob does not correctly recall the position of pieces. If Bob knows that no pawns have reached the opposite edge of the board, does Bob have any chance to prove that the current board state is illegal?

Are there any games where it is difficult to determine whether the game is in an impossible state?

Winning Player Conjectures

The game Sprouts has a very interesting conjecture associated with it:

If the game starts off with n dots, then the first player has a winning strategy exactly when n mod 6 = 3, 4, or 5.

This seems strange. Why 6? How is this number inherent to the rules of Sprouts? Well, it's not clear that it is, because the conjecture has not been proven.

Nevertheless, supporting cases continue to be found. Somehow I am comforted by the idea that somewhere, there is a computer working to check cases for Sprouts. (Probably I feel the same way about the Collatz Conjecture. Someone is running that right now, right?) Sprouts is also studied in the misere version, with other cases being checked.

Along these same lines, there is a conjecture for Atropos:

If the game starts with n open circles along a side, then the first player has a winning strategy exactly when n mod 4 = 0 or 3.

This has a bit of intuition behind it: if the losing player can enforce that the game drags out to the last circle, then that last circle will cause the loss. Since the number of open circles at the beginning game are 1 + 2 + ... + n = n (n + 1)/2, this is even exactly when n mod 4 = 0 or 3.

Naturally, there is lots known about starting positions. Hex and Chomp both are wins for the first player, though the proof is non-constructive.

What about other games, such as Amazons? Which conjectures exist for the winning player from starting positions?

Oops and Updates!

Hmmm...

I see that I missed Friday. As soon as I noticed that, I feared that I had missed last Tuesday also, but, no, I showed up that day. Last week was spring break, but I did not intend to take as much time off from work as I did. I apologize for missing on Friday!

One of my big tasks for this past week was to make sure everything was okay to close down my web account from BU's CS department. Sad! Now the Atropos and Matchmaker applets are hosted on Wittenberg sites, and they seem to work just fine. Please let me know if you notice any problems with either of them, and I'll fix them immediately! (If you don't have Java enabled on your browser, there's not much I can do for you.)

I am expecting to get a copy of bOOLeO delivered soon! That game looks excellent! There is something very enticing about seeing game pieces in pictures and coming up with what you expect the rules to be before actually reading any.

I realize that of Atropos and Matchmaker listed above, I have only actually published (thesis not counting) about one of them. I have never submitted a paper about Matchmaker anywhere, though it might be a topic that could sneak in somewhere. Still, I am a bit loathe to do this until after I prove something concrete about the difficulty of the game. Either showing that it can be solved in polynomial time or finding a completeness result would be enough for me (I haven't worked on this game in a long time).

Is this legitimate? I've noticed that in some of my presentations, no one cares about solving the game, but are instead more interested in the origins and rules (and implementations) of the game. Perhaps it is more vital to get playable versions of games out and introduce them that way than to make sure something is known about them first.

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.

Good Abstract Games

Before choosing to come to Wittenberg University, I got in touch with the school's role-playing group. I had recently started playing the recent edition of D&D back in Boston and was hoping to find a new group. I was assured there would be a campaign starting up after I got there. Sweet!

I went to the group's opening meeting a few weeks back, even though I had already figured out who I was going to be playing with. Once there I realized that this is actually a full-fledged gaming group, not just focused on role-playing. In particular, the club is proud of the number of board games they have amassed! Every Saturday night, they hold an open gaming night, where most people play some board games.

I will likely be showing up this week, bringing Atropos and Tsuro with. I am curious, though, which good board games people know of that are interesting theoretically---either because they have difficult strategies not overwhelmed by randomness, or they look more like abstract combinatorial games. I know that there are already well-known games like this (Chess, Go, etc) but which lesser-known games fit into this category?

Let me know and I will have them ready for Saturday!

As a note: I have been getting plenty of emails about topics mentioned in these posts. I will try to address everything and will post my own thoughts in comments... when I have a chance. I love getting the emails, but please consider posting a comment directly to the blog. :)

Games and Teaching

Here at Wittenberg we start early: Monday is the first day of classes, meaning we will have six school days before September even starts!

It also means that the incoming freshman class is moving in to campus this weekend, trying to learn how to be college students before they get into their courses and trying to figure out what they might want to do here. At the time, I was excited about doing creative writing, which I wouldn't be allowed to do until my sophomore year due to over-demand. Before then I would take four math classes and one cs class: my path quickly shifted to a math-cs double major that sophomore year.

What it means now is that today we will have department information sessions, in which each department will do their best to lure students into trying classes in their discipline. We expect to see students who already know they want to succeed in Math and CS (we have a join department here) but what about students like myself who had a weird senior year as far as math was concerned (another story for another day) and had never taken a serious CS course? My hope today is to help attract those students with games. I found a laminating machine here in my first week and have a nice Atropos board, complete with poker chips and even some cards. (Sadly I left my Atropos dice at home! Oops!)

I'm psyched to use games as both an attention grabber and a teaching tool. Although it might be too late to use today, does anyone have any advice for brief comments that tie CGT and math or cs together. Usually I try to talk about the complexity side of things, but it's not always easy to field follow-up questions while avoiding actually naming complexity classes.

We'll see how I do today... :)