Wednesday, November 30, 2011
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?
Tuesday, November 29, 2011
Friday, November 11, 2011
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.
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!)
Next week, I will be in Seattle for Supercomputing for most of the week, so there may not be regular posts.
Tuesday, November 8, 2011
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!