Poset Games, a Clarification

One possible misconception from Daniel Grier's recent paper showing that the general partially-ordered set (poset) game is PSPACE-complete is that this property applies to all poset games.  Thus, Nim and Chomp are also PSPACE-complete.  For those who know the quick trick to evaluating Nim states, this doesn't quite match up.  Determining whether a Nim position has a win for the next player can be done very quickly.  What's wrong here?  Does this mean that PSPACE = P?

The unexciting answer is: No.  The issue is that Nim is played on very specific types of partially ordered sets.  The posets in Nim lend to this trick of quick evaluation.  Chomp also uses specific types of posets, and thus it also isn't immediately known to be PSPACE-hard.  (I believe it's unknown whether Chomp is a hard problem for either NP or PSPACE.)

One nice aspect of Grier's proof is that it uses posets that have chains (a <= b <= c <= d <=... <=z) with only three elements (a <= b <= c).  Thus, if you have another ruleset that has potential positions including all posets with chains of 3 (or 3 levels of elements) then that game is also PSPACE-complete.  Chomp's posets do not include all sets with chains of 3, so we can't directly infer that Chomp is PSPACE-complete.

Are there any rulesets out there that satisfy that condition?

Poset Games, part 2

Continuing from the last blog post, the reduction from Node Kayles to the General Poset Game is not difficult.  For each vertex, v, of the Kayles graph, G, add an element (also called v, let's say) to the partially-ordered set (poset), S.  Each of these elements should be incomparable with each other.  Thus, if there are no edges in G, all moves are equivalent and the game's value is *k where k is the parity of the number of nodes.

What if there are edges?  A-ha, then for each edge (u, v), in G, we add two elements to S: uv+, so uv+ > v and uv+ > u; and uv-, so that for all vertices w (in G) not equal to u or v, uv- < w.

Now the first player has a winning strategy in the Poset Game on the resulting set S exactly when they have a winning strategy in the Node Kayles game on G.  (This is not immediately obvious!)

... almost.  This construction always works if G has an odd number of edges.  This is not a terrible requirement, since Grier shows how to create an equivalently-winnable odd-edged graph from an even one.

I would like to post some pictures to explain the results of this reduction, but that might be wasted effort because the figures Grier supplies in his paper are very clear. 

Cool Board-Gaming "Tools"

I recently saw something cool about choosing which player should go first in a game.  A lot of people roll dice, though ties can happen.  One dice enthusiast came up with a set of four dice that can be used to determine who goes first among two players, with the awesome properties that:

  * The dice only need to be rolled once (no ties), and

  * Each die has an equal chance of being the highest among the four.

To do this, the dice cannot have any ties.  Four twelve-sided dice are used, so the numbers 1 - 48 must be on them.  The more complicated part is how to arrange the numbers so that each player has a 1/4 probability of winning the roll.

Is there a way to generalize this?  If you have n players, what size dice do you need?  (How many sides?)  If you have access to up to 20-sided dice, how many players does this support?  For four players, are 12-sided dice the smallest you need?

It seems like this must all be proven somewhere.

Another awesome thing I saw was this gaming shed someone built, mostly to house all their board games, but also with a place to play them.  That forum post shows all the steps to create the building.  Very cool!  I am extremely jealous!  Someday perhaps I'll have the funds to copy this exact thing. 

There are many other things I desire, but these two are definitely worth sharing.

High Schoolers and undergrads are awesome at Poset Games

A few weeks back, the Computational Complexity Blog had a great post about a PSPACE-completeness proof about games!  Even cooler, the result was found by an undergrad at the University of South Carolina!

This is the third result about games on partially-ordered sets (posets) from young researchers that I've heard of.  In 2003, Stephen Byrnes proved a cool theorem about the periodicity of chains in poset games.  Earlier this year, Adam Kalinich found a transformation that converts a current-player-is-winning poset game to an other-player-is-winning poset game.  (I'm less familiar with this result; I'm not sure whether it's assumed that these are all impartial games.)  Now, Daniel Grier has shown that the General Poset Game is PSPACE-complete.

What exactly is the General Poset Game?  It's a game played on elements of a partially-ordered set.  Each turn, a player removes an element from the set as well as all elements greater than the chosen element.  If there are no elements in the set at the beginning of your turn, then you can't make a move and lose the game.

Many games are examples of poset games, including Chomp and Nim.  This result does not immediately mean those games are PSPACE-complete to determine which player is winning!  (Nim is definitely not, since there's an easy way to evaluate Nim states.)  This says that the following problem is hard: given a set, S, and a partial ordering of S, P, determine whether the General Poset Game using P on S is in Fuzzy or Zero.  Thus, worst-case instances are going to be difficult, not just ones that are easily recognizable as a Nim state.

The reduction for this is extremely simple!  I'm out of time, however!  More next time! :)