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.

Breaking Symmetry

Right away while teaching combinatorial games, my students latched on to the idea of symmetric arguments. It comes early in the book and is more convincing of a good plan of attack than greedy strategies (and is easier to use than finding transformations to other games). Whenever we play a new game, the students first look for ways to play symmetrically and then how to escape such a situation. This is an excellent pattern, since symmetry is not always a trivial venture, and likely a good indicator you are competing with a gamester.

Okay, so say your opponent in a game is employing a symmetry-based strategy, which will be successful unless you break it. You see an opportunity to break the symmetry, but it's something you can do now or later. When should you do it?

I bring this up because Neil McKay noticed a flaw in the symmetry argument for the first player in Flume. Gasp! I have amended the game table but hope to have the matter resolved. I will present Neil's illuminating break at a later date (after it is not immediately relevant to my class; some students are actually reading this!) but it's great that he found a counterexample to the strategy.

This event makes me curious about symmetric strategies in general. Flume was a bit of a special case, because the symmetry employs two steps each turn: first be greedy and take all the free spots, then turn around and make the same move your opponent did, allowing them to make the same great moves you just did. (Luckily, you should always be ahead by one piece.) This seems to me as a bit of an "impure symmetry" (perhaps more so now that there's an escape). I still hope that there is a method to restore the symmetric state in Flume, though I'm likely biased at finding out I was wrong.

Even more so, I'm interested in other surprising examples of symmetric strategies. Are there any examples of games where symmetry can win you the day, even when you wouldn't expect it? Are there any other examples of impure symmetry that wind out working great? Are there any examples of breakable symmetry strategies that are actually robust enough to be restored?

I'd love to hear about them!

Playing without Giving away your Strategy

Perhaps you are about to play a series of three games of cram against an opponent in the final round of a cram tournament. Your scored better than your opponent in the tournament thus far and must play first in the first and third games. The winner of the tournament will be the player that wins 2 of those 3 games.

While playing the first game, you can see that you are losing, but suddenly realize there is an really good strategy for winning from the start as long as you go second. Since this tournament uses initial 8 x 8 boards, you can use a symmetry strategy to mimic the other player's moves! Great! The next game is yours!

Unfortunately, you also realize the strategy is easy to follow. As soon as you use it against your opponent, they will be able to implement it themselves in the final game and win.

Is there a way to implement the symmetric-play strategy but disguise it at all? In general, is there a way to mask the fact that you are using a simple strategy to win?

In Nim, it is difficult to follow someone making the correct moves if you do not know how to evaluate the game boards. If it was plainly obvious what the other player was doing (perhaps XOR is your favorite math operator) then perhaps you would pick up on it quickly.

I tried this once, keeping a "turn behind" in the symmetric-play strategy. I kept making the play my opponent had made two turns ago, whenver possible. As I recall, it got messed up and I had to ditch it part way through. Is there any good way to keep this going? I feel this would be more difficult for an opponent to follow... if it works!