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?

Playing While Losing and Collecting Candy

Sometimes gamesters play games even when they are in a losing position. This means that even though we know there is no winning strategy from the current game state, they'll keep playing.

This happens for a lot of reasons. Often, this occurs because the winning strategy for the other player is not known (even though it is known that it exists). For example, the first player to move in Chomp is the winning player, though what that first move should be is unknown. Thus, if someone challenges me to a game of Chomp, but they are going first, I don't immediately quit the game. They will make their first move, and then who knows whether I'm still in a losing position?

Other times, even when a winning strategy is known, there is a chance it is not known by the player in the winning position. You might be in a losing position this turn, but if you make a sneaky enough move, perhaps they won't be able to do it again next turn...

There is the chance also that you play purposefully from a losing position, hoping your opponent will learn how to maintain their "winningness". If I am a parent someday, I bet I will do this more often!

As yet another option, it might just be that your opponent will take it badly if you quit on the game, even though it's clear who will win. You'd like to quit, but they want you to play the whole thing out. This is likely very instructive for them, so you should probably go ahead with it :)

Michael Albert found a way for the losing player to entertain themselves in (some of) these situations while playing the game Nim. The idea is to consider all the objects as pieces of candy, and by removing them from a pile, you get to eat the delicious candy! Naturally, this is not as rewarding as winning, but if you're going to lose, you might as well acquire as much of the candy as you can! He found interesting properties of the game when playing with three piles (most notably that it's always best to take candy from the biggest pile). This implies that the winning player will always make the best responding winning move.

I'll talk some more about "Candy Nim" next week. Have a great weekend!

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.