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!

Integers Liveblogging: Friday

Some awesome quotes from today:

"Actually, I can say I played NoGo; I don't play Go!" -Aviezri Fraenkel

"'Every other weekend'?  Other from what?  What is the complement?"  -Rebecca. ('Every other' is apparently not colloquial in Canada.)

"...and I am guilty of some of this research."  -Florian Luca during his talk on Balancing Fibonacci Numbers.  He went on to describe a problem as a mathematician trying to solve a system to find the street address for a party. :)

Last night, we had a little NoGo tourney between Canada, the US and Europe.  Canada won, 5-4, but there may be a rematch tonight of sorts!

Integers liveblogging: Thursday

Today a lot happened. I talked and I listened to lots of games talks, many of which will become their own posts in the future. Instead, I'll quickly mention some highlights thus far.

Rebecca confused me yesterday by saying "in P" which I automatically translated as "efficiently solvable" instead of "in Zero". I had just met her, so I asked excitedly if she was in computer science. She said this misconception is even more dangerous because she is dealing with misere games, and need to consider both outcome classes. Those in Fuzzy when playing misere, but in Zero under normal play are in N-,P+, pronounced "NP" (which computational complexity theorists use for another well-studied complexity class). Dangerous!

I've also seen a great bunch of non-games talks, mostly number theory, which I've understood a bit of. Particularly, Carl Pomerance gave a talk I understood most of about product free subsets of the Naturals (if x and y are in S, then x*y is not in S... usually x*y (mod p)). Neil Hindman gave an impressive talk, mostly because I don't think he looked at any notes and covered a lot of complex stuff using only a whiteboard! I also found out yesterday that Beatty sequences/ratios were used to help discover quasicrystals, something which had a lot to do with this year's Nobel Prize! Wow!

I've mostly had a blast meeting people and playing games. While playing FLex with Marla yesterday, she commented, "This is all very important!" Everything I explained about what I was thinking was quickly absorbed by her and Rebecca. Awesome!

Meeting people---especially over games---is great! I played some impartial games with Yuval Tanny and Shira Giat. At one point I made a winning move, but was afraid I hadn't gotten the parity correct. Neil put me to ease, saying, "Yes, you counted to two correctly." That's about as high as I feel I can count these days.

Yuval and Shira are clearly awesome; this seems to be the norm for gamesters! There's a lot of energy in the group---all positive---especially from Jess Enright, who gave an awesome talk today about set representation games. Here is a picture of her realizing she won a game with Marla during the talk.

I feel like a bit of a reporter, trying to keep up with everything, but it's very helpful to help me stay on point in the talks. Seriously, they were great and I can't wait to get some of those posts up.

I will try to get a post up tomorrow before the evening, but if not, I'll put in my final fake-liveblog next week. I'm leaving on Saturday morning, so I won't be around for the last day of the conference, sadly.

Integers Liveblog: Wednesday

The first day of Integers has yielded many excellent number theory and combinatorics talks... which I didn't follow very well.  After lunch, I spent much of the time playing FLex and Adjex with Alex Fink, Larry Rolen, Rebecca Milley and Marla Slusky, all of whom I just met today!

During lunch, Patrick played NoGo against Richard Nowakowski, winning two of three games!  Afterwards, Richard said, "it's clear the american strategy is different from the canadian."  Apparently in the states we play aggressively! ;)

With nine minutes left to go before the afternoon talks, Richard looked at Patrick and declared, "okay, one quick one!"  Later, he explained, "there is no such thing as the last game."

Awesome!