Partiality Continues to be Confusing, part 2

Common Trip-Ups:

Confusing Impartiality with Symmetry. Symmetric positions seem impartial because each of the moves for one player has an opposite in the set of moves for the other player. Those opposing positions have opposite values, however. While it is true that all impartial games are symmetric, the converse does not hold.

Separate Scores. Many games are nearly impartial, except the players keep track of different scores. The game board (not including the scores) may be changeable in the exact same ways by both players, except that then the players get different scores. 3,6,9 and Odd Scoring are good examples of this. These games are not impartial, because the scores are different.

All the positions are impartial games. { 0, *, *2, *3 | 0, * } may look impartial because all the positions are impartial positions. This is not impartial, however, because the players don't have all the same move options.

The Position is equivalent to an impartial game or 0. A game equivalent to * is not necessarily impartial. The game could be: { 0 | 0, *2 }, which is equivalent to * but does not have the same options for both players. Equivalence does not preserve impartiality. (Perhaps not everyone agrees with this!)

What are some other common problems I didn't list here?

Partiality Continues to be Confusing

Happy new semester & year! Let's dive right in!

I thought I had done a much better job explaining the difference between impartial and strictly partisan games last semester, but again far too many of my students claimed that their game was impartial during their presentations.

A few students presented symmetric games, and claimed they were impartial. A few made mistakes on games that were impartial except that each player had a separate score. These games, such as 3,6,9 and Odd Scoring, are not impartial because your turn affects your own score but does not affect your opponent's. Thus, the same moves are not allowed for both players.

For example, given the following Odd Scoring state: (parity of scores is given instead of actual numbers)

Left: Odd Right: Even
___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ _X_ ___ ...

One legal move for Left is to slide the marker one spot:

Left: Even Right: Even
___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ _X_ ___ ___ ...

Right does not have that move as one of its options. It can still slide the marker, but then the scores will both be odd instead of even. Thus, Odd Scoring is not impartial.

Last semester, I made a distinction to the class about impartial positions and impartial rulesets, defining each separately. A position is impartial if, recursively, all it's positions are impartial and if the set of Left positions is the SAME SET as the set of Right positions. (Not whether they are equivalent.) A ruleset is impartial if all positions available in that ruleset are impartial.

Before defining these, I defined symmetric positions as those equivalent to their opposite (G = -G means G is symmetric). I think this helped, because many students knew that their games were symmetric, but not impartial. This was a change from the previous year when most students claimed impartiality.

Perhaps it would be better next time to list common misconceptions about determining partiality.

Just a little Gamester humor.

Drew this on the board during the final exam for my freshman CGT seminar. :)

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!