Catching up a bit...

Sometimes it seems like there's some catching up to be done. Let's go ahead and do a bit of that today...

First, I will be at Supercomputing 2009 until Tuesday of next week and I don't think my phone does blogger, so there will likely not be a post next Monday.

Next, on the Computational Complexity blog, I saw a link to a CS Theory blog. This blog updates with job postings and conference deadlines relevant to researchers in the theoretical cs community. Awesome! (If they want Computational Complexity papers, perhaps board game complexities are acceptable...)

A few weeks ago, I mentioned a paper about the winnability of misere Hex. Much like normal Hex and Chomp, they are able to determine non-constructively which player has a winning strategy. Unlike these other games, it turns out not to necessarily be the first player, but instead to be based on the parity of spaces on the game board. Still, their argument uses a strategy-stealing approach, just with a special twist. This is something I hope to talk about more in the near future.

On my office whiteboard there is a short list of potential post topics that I haven't yet got to. The list looks something like this:

* Locality of where-to-play in games.

* Strategies of initial positions

* Why do people seem to prefer partisan games?

There's another one: "* Complexity Results" but I can't recall which results I was talking about when I scribbled that down. In any case, if you'd like to hear about one of these, let me know.

Finally, there were some questions I posed on this blog that I haven't yet answered, mostly because I either haven't finished reading all the papers suggested or because I haven't been able to find those papers. Most notable is this question:

Question: If you add two instances of a game together which creates a new instance of the same game, does this imply that the game is easy?

I mentioned that the Nimania counterexample doesn't really apply for what I was looking for, but I was referred to some other papers:

(i) A.~S. Fraenkel and Y.~Yesha [1979], Complexity of problems in games,
graphs and algebraic equations, {\em Discrete Appl. Math.\/} {\bf 1},
15--30;
(ii) A.~S. Fraenkel and E.~Goldschmidt [1987], Pspace-hardness of some
combinatorial
games, {\em J. Combin. Theory \emph{(Ser.~A)}\/} {\bf 46}, 21--38;

I have not been able to get access to either of these papers electronically or in our library. (Wittenberg's library is not as grand as a research institution's, but is very good for a small school!) I may wind up just seeing if I can get them from tOSU, but if anyone else has a comment from the relevance of either of these, I would appreciate that also!

Have a great weekend! Another post arrives on Wednesday!