Oops, I missed an extra week in there. For some reason, these papers don't get graded unless I look at them... ;)
Fraser Stewart has a wonderful (relatively) new blog up at: http://combinatorialgametheory.com/.
I will continue with more regular posts! I promise!
I've been thinking a lot about the dichotomy of game complexity. Are there any rulesets with symmetric starting positions where the complexity of the game is NP-complete? (Usually they are PSPACE-hard or in P.)
If you drop the symmetric aspect, then it's easy to design games that are NP-complete. Take, for example, the following coloring game on graphs. Starting positions consist of a single red-colored vertex and a connected, uncolored graph. The red vertex is then connected to each vertex in the uncolored graph. In addition, there are some number, k, of additional uncolored vertices, each connected only to a single blue-colored vertex.
Play proceeds as in Col, meaning on their turn, a player chooses an uncolored vertex that is also not adjacent to a vertex of their own color, then paints that vertex. This game is NP-complete because the blue player is essentially trying to find a maximum independent set on the connected uncolored graph, with size greater than k.
Not all starting positions are symmetric, however. Col doesn't fit this description, because the starting positions in Col are uncolored and thus are symmetric.
EDIT (3/29/12): Corrected some spelling.
A Domino-Covering Problem
2 months ago