## Tuesday, November 2, 2010

### 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?

#### 1 comment:

1. Ok, I know you were looking for real examples, but here's a silly toy one:

3-SAT, the game:

On the first move, a player names a positive integer n. Thereafter, players name 3-SAT clauses in x_1 through x_n, subject to the condition that the complete set of clauses named to that point is satisfiable.