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.
Red, Yellow, and Green Hats
17 hours ago
Hey Kyle thanks for the shout out. Say did you ever get a chance to read my thesis or any of my papers? If you do let me know what you think, and take it easy.
ReplyDeleteFraser
I haven't had a chance to read anything yet, sadly. Does one of yours mention the topic about point-based games from a few weeks ago? If not, do you know where I can go to look that up?
ReplyDeleteYes, I developed an entire theory for those types of games, and also wrote a paper explaining in detail why the theory in the book Mathematical Go is flawed.
ReplyDeleteIf you click on the link "Papers and Preprints" you can find all of it. The two you'll probably be most interested in are "Scoring Play Combinatorial Games" and "Impartial Scoring Play Games".
Basically the reason the theory in the book Mathematical Go appears to work is down to sheer coincidence, if it was another game, with another set of rules it would not work at all.