NP-complete games?

Are there any "balanced" games that are known to be NP-complete? I know that some are NP-hard (Clobber, Col, Graph NoGo) but I don't know of any that are NP-complete...

By balanced, I mean games that have symmetric starting positions (G = -G).

Are there any like this that don't require a hardness of choosing an appropriate move?

Extending a Pause

First it was Supercomputing, then Thanksgiving. Now that I've returned, the end-of-semester crush has forced blog updates way down in the priority queue.

If I don't get anything else out this semester, I will return with the New Year. Happy Holidays!

Game Description: Battle Sudoku

One thing I've slowly been chewing on this year is a two-player Sudoku game. The rules are very simple: each turn, you fill in a box with a number not yet in that row, column or sub-square (quadrant in the 4 x 4 case). As with normal play, if you can't move, you lose!

In January, I played with a bunch of games starting with an empty board, but realized there was a simple symmetry strategy for the second player. We brainstormed some potential starting boards to fix things, but more complicated symmetry strategies arose.

After returning to Wittenberg, Noam Elkies and I corresponded, finally working out the current starting board. All the flaws we'd seen were fixed.

Here is the starting board:

My plan was to bring the game to Integers to play with people. Beforehand, I tested it out on my WittSem class, and it proved challenging. My student Patrick also took interest and showed a pseudo-symmetry strategy I was afraid of could be broken! Awesome! (I still don't recall how he does it!)

Here is a .pdf of a sheet of games! :) Enjoy!

Next week, I will be in Seattle for Supercomputing for most of the week, so there may not be regular posts.

Somewhat Random Musings

Yes, I didn't post at all last week. I am still very much catching up on things I missed while at Integers. Next week I will be at Supercomputing and will likely miss another post or both. I don't often have the desire to pause the teaching part of the semester to get research/blogging done, but this is turning out to be one of those semesters. Mostly, I want to make sure I write good posts about the game talks at Integers (or what I understood of them). I hope I can find extra time to spend on them, but it's more likely that they'll come out a bit less-than-perfect. Hopefully some of them are readers and can comment on all the errors

While at Integers, I spent a lot of time struggling with NoGo, only to run into problems I encountered at BIRS in January. While there, I found that NoGo on a graph is NP-hard, but was neither able to show that Graph NoGo was PSPACE-complete, nor show any hardness for standard NoGo (on a grid). The same thing happened last month: no new progress. So I tried flipping it around and started looking for an efficient algorithm for NoGo. Either Neil McKay or Alex Fink (I think it was Neil) asked me about it, and I told him what I was doing. He was surprised I had given up on computational hardness so quickly. His comment made sense: I have more experience finding hardness results than showing efficient algorithms for problems (though I would argue that hardness reductions ARE efficient algorithms). Research-wise, you strive for results! So, you should spend your time conquering problems you're good at. Instead, I was trying something a bit different.

Luckily my job is far more focused on teaching than research, so the pressure to publish is less intense. It's very nice to know I can try a completely different tactic if I get frustrated with a problem!

... not that I had any luck with this!

On a related note, student presentations have started in my games class! One question that came up is: What does it mean for a game to be solved? I answered that there's an easy way to evaluate the game without drawing out all of the game tree. I hope that's a good enough answer. For myself, it means there is an efficient algorithm to solve the problem. I generally consider a completeness result to be "solving" the game, though perhaps it's the opposite: the game (probably) cannot be solved!