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.

Alleviating (some) Partiality Confusion

Perhaps it would be best for me to tell future classes: if at any place in a game, one player has a move that the other doesn't, then the game is not impartial. This seems like something very intuitive that one should be able to impart with a quick sentence, but there are many layers of confusion on this point. Perhaps one has to see many examples of impartial games first!

I often see an impartial game defined as one which has the same options for both players. Does that mean {1 | 1} is impartial? No... this is game is in Positive (L), and all impartial games should be in Fuzzy (N) or Zero (P).

In our text, impartial games are defined as follows (page 135 of Lessons in Play):

"If for a game and all its options, the left options equal the right options, then the game is dubbed impartial."

There could be some confusion here also. Is G = {{1|1} | {1|1}} an impartial game? Certainly the left options equal the right options. Additionally, of the options of G, the same is also true: the left options equal the right options. However, to see that it is not impartial, we have to go down one level further (the options of the options of the options). The necessary recursion of a definition of an impartial game may be implied, but it is probably important to note that the options must all also be impartial.

Is there some middle ground here? On Tuesday, I referred to the game {-1 | 2} being equal to 0, though not impartial. Being an element of either the class N (fuzzy) or P (zero) does not make a game impartial. Other games that aren't impartial:

G: {0 | 0, 1}. Even though G = * (0 dominates 1 for the right player) the options aren't strictly the same.

G: {0, 1 | 0, 1}. Even though the children are the same, those children are not impartial.

G: {X | -X} (where X is a set of games). Here, even though this game MUST be in either N or P, and any strategy for Left translates into a strategy for Right, the game is not impartial.

G: {* | *, *2}. G is in Zero, and all options are impartial, but Left does not have *2 as an option.

For one I'm not sure about, what about the Domineering game consisting of three open boxes in an L-shape? Both players can move to 0 as their only option (so the game is equal to *) but they move there in different ways. Is this game considered impartial?

I apologize above for not figuring out how to use nice and fancy letters for much of my notation!

Have a great weekend! Next week is our last week of classes here and will be my last week posting until next semester.

Confusion over partiality

Perhaps the confusion over partiality is not just limited to myself... or perhaps I'm just teaching it poorly.

For our presentations, most students have chosen partisan games, but somehow many students have declared that their games are impartial during the presentations. The reasoning, it seems, is that these games are "impartialish" from the initial position, since both players have similar moves and the value is either in N or P. This has a bit of logic to it; the strategies for each side is independent of the player's identification (Left, Right, Blue, Red, etc). This "fake impartiality" only exists for this initial state, however. Once a move has been made, the game is nearly always partisan.

I feel like there is more to think about here, but perhaps I'm headed down the path of trying to trisect an angle...

When we consider partiality of a game, it does not seem that this is consistent through equivalence. For example:

{ | } is impartial and is equal to zero, but

{ -1 | 2} is not impartial, but is still equal to zero.

Perhaps I'm wrong and we can consider {-1 | 2} to be impartial, but it seems dirty somehow.

Having now studied partisan games to the point where I could teach them for a semester (as far as we got, anyways) I'm very ready to retreat back to my happy, impartial-only world. Nimbers are fairly easy to work with; Ups and Switches and Dyadic Rationals and 3+DoubleUp+* is a bit more frightening. My respect for the effort needed to get Aaron Siegel's CGT Suite to work properly is moon-bound. This stuff is crazy-interesting, but I'll be happy to resume needing only a knowledge of mex and XOR to get some research done.

(As a side note, our presenter won a game today, so the record is now: 6-1 for the audience.)

Tsuro has dual-locality, why doesn't Geography?

I've mentioned before that I think Tsuro is a very elegant game. If I get a group of thoughtful people together to play, they will often notice some of the great properties that aren't immediately obvious. No cycles (for player tracks) and no overlapping paths make sense after some consideration, but it is still often asked as a question.

A quick synopsis of the game is that pieces move along paths printed on tiles. On your turn, you play a new tile on an untiled place on the board to move your piece further along. These tiles each have a different matching of paths connecting two sides. That place of a tile could move other pieces, also. A player loses when they either collide with another piece or follow a path off the board.

Aside from the parts mentioned up top, there are other cool aspects of Tsuro. One of these is the fact that it looks a lot like Geography.

Geography? How could that be? Geography is impartial! Tsuro is very partisan: each player has their own hand of tiles and their own piece.

Well, first of all, in order to make it more "combinatorial gamey" we have to consider removing the hands anyways to eliminate hidden information. (Perhaps instead there is just a communal pile everyone selects from.)

Now, what if instead of having two pieces, both players shared the same piece. Now you have to make sure you don't lead the piece off the board on your turn. This now looks a lot like geography, where players traverse a directed graph and must avoid crashing into an already-visited vertex.

There are plenty games that enforce a sort of locality---you have to play near the last play. Tsuro has a cool property where each player has their own sense of locality. They play not from the last play, but from their last play (unless they get moved).

What if the same were true in Geography? What if each player had their own piece moving through the directed graph, but you lose if you visit a vertex previously visited by either player? How difficult is it to play this version well?

In a very unrelated note, Molly points out this podcast, which contains a cool mention (near the end) of a board game enthusiast who uses analogical modelling to choose whether or not to buy a new board game. Ha!

Emotional Machines like Partisan Games

There is a real difference between impartial and partisan games. I don't just mean that analysis is different, or that impartial games will always evaluate to Nimbers. I'm referring to something more basic:

People generally like playing Partisan games.

I can best present evidence by looking at the vast array of published partisan board games. It is hard to find published impartial games! Instead, published games are able to support some sort of mantra. I have my pieces and you have yours. I will build up my position and at some points there may even be a lack of interaction with whatever you're doing. We will race towards some winning condition. I will be able to see my strategy materialize, whether or not it is a good one.

All of these are aspects of partisan games that are missing in impartial-land. In that mystical place, every move forcibly interacts with your opponent. Your board strength is tied precisely into who is the current player and not in some separate position that you can see. Instead of racing towards a finish line, both players are the same racer, just worried about which leg will be forward when the ribbon is snapped.

I think it's natural that we don't like these sort of games. I'm looking forward to playing a World War 2 simulation game with my dad this thanksgiving, but I wouldn't be looking forward to it if after each turn we swapped teams!

In the past few years, I've made some off-hand comments (not here, in "real life") about people being bad logical machines, but instead good emotional machines. We often allow our emotions to make decisions for us instead of precisely reasoning through all the logical details. Sometimes this causes bad decisions to be made, but sometimes it lets us get to the heart of the matter and make decisions quickly. I'm in no way a psychologist, so I won't attempt to back this up with any data and keep blundering ahead.

Partisan games really clue into this emotional capability. "Well, at this point, there are lots of my tanks on the board and not many of the opposing tanks... I must be winning." We hope to be able to evaluate the strength of our board position and we can at least approximate this by taking a look at the game state. "Is it better to go first in Hex? Yes, it's better to have more of your pieces on the board." That is the basic response, and it turns out to be true, though an actual proof is somewhat more involved.

This is more difficult with impartial games. Near the beginning of a long game of Kayles on a complicated graph, I am not sure whether I'm winning or losing unless I check all the possible moves. Oof! That is a logical problem my brain doesn't want to have to work through. (At least, not on it's own.)

I may continue challenging my students to impartial games, but soon they're going to get sick and ask me to break out a Hex board.

P.S. Enjoy the greatest rivalry in sports this weekend!

Partisan Game states that are Impartial

Partisan games are those where the different players do not have the same options for moves (such as in Hex or Chess, but not like Nim). Some states of partisan games, however, mimic impartial games.

This is demonstrated clearly in the game of Domineering, where players alternate placing dominoes on a checkerboard, each taking up two spaces. The Left player must play dominoes vertically (meaning they take up one space and the space directly below that) while the Right must play them horizontally. No pieces are allowed to overlap on the same square of the board.

Some situations in Domineering behave like impartial games, however. Suppose the only free space to play on a board is three squares arranged in the following way: (forgive my ascii art)

XXXX
XOOX
XOXX
XXXX

(Legend: X means this space is covered by a domino. O means this space is uncovered.)

Here, either player may play, but afterwards there are no available plays on the board for anyone. This is much different from

XXXX
XOOX
XOOX
XXXX

where after one of the two players makes a move, they will then be the only one left able to play there. For example, if Left plays on the above board, the situation then becomes:

XXXX
XXOX
XXOX
XXXX

leaving Left able to play again but Right with no such options. With our top example, however, either may play here, but only that one play is left. This is equivalent to the Nim state where there is one pile with only one stick in it. Either player may move by taking that stick, but then no more moves are available.

In 2005, Gabriel Drummond-Cole found positions in Domineering (and Chess!) equivalent to a Nim pile with two sticks. These Domineering states are quite a bit more complicated than those above. The most simple he finds is:

XXXXXXXXX
XXXOXOXXX
XXOOOOOXX
XOOXOXOOX
XXOOXOOXX
XOOXOXOOX
XXOOOOOXX
XXXOXOXXX
XXXXXXXXX

The ascii art here shows its inability to describe what is really happening here (see the paper for better pictures). Gabriel goes on to describe more such situations and even detail the patterns that cause this. One interesting note in this instance is that the covered square in the exact middle can also be uncovered: the value is still equivalent to the Nim-heap with 2 sticks.

Gabriel points out a problem with his constructions, however: there is no way to reach this game state from an initial board! Notice the blocked spaces (X's) in the middle of the diagram: they are each just one blocked square surrounded by unblocked squares. Thus, no domino could have been placed there.

Constructing these situations is a large task, aided often by evaluating software such as Aaron Siegel's Combinatorial Game Suite. Gabriel laments he has "not been able to find any ordinary Domineering positions" equivalent to the Nim-heap of size 2.

Finding other partisan situations equivalent to Nim-heaps is a continuing study. A Nim-heap of size 3 is equivalent to a game with two heaps, of sizes 1 and 2. Thus, we see that we can already have an equivalent domineering game by appending our two boards together:

XXXXXXXXXXXX
XXXOXOXXXOOX
XXOOOOOXXOXX
XOOXOXOOXXXX
XXOOXOOXXXXX
XOOXOXOOXXXX
XXOOOOOXXXXX
XXXOXOXXXXXX
XXXXXXXXXXXX

Work on finding partisan states equivalent to a Nim heap of size 4 is the next big task, and I have heard of some potential results... :)

Running out the Clock

This past weekend was an exciting week for college (American) football. During the game I watched, however, a thought struck me: was it really a good idea for these teams to be running out the clock?

Michigan was battling Notre Dame in Ann Arbor. Both of these teams have had some recent awkwardly bad seasons, but the rivalry is big enough that this was sure to be a good test.

The last quarter of the game was full of both sides scoring only touchdowns (usually worth 7 points) as each tried to get their offense past the opposing defense. In American Football, at any given time one team has their offensive players out, while the opponents have their defense out. The offense tries to advance down the field with the ball while the defense tries to stop them. A touchdown is scored by getting one of your players through the defense and down to the other end of the field. How's that for a simplification?

The fourth quarter consisted of Michigan's offense scoring a touchdown, putting them 11 points ahead (there are other ways to score points, but let's forget about that for a second). Notre Dame's offense then had the ball, and scored their own touchdown. Michigan had the ball again, but failed to score, thus Notre Dame had another shot and scored again, putting them up by 3 points. Michigan attempted to score and failed, then Notre Dame had another go, but failed as well. On their next turn to be offense, Michigan scored another touchdown, putting them on top by 4 points. With only 11 seconds left to play, Notre Dame did not score again.

The exact amount of time remaining is a big part of the strategies that I think are a little short-sighted, and it happens with every team. After both teams had scored their first touchdown of the quarter and with Michigan up by 4 points, Michigan had the ball with about 8 minutes left to go in the game. They failed to score on this drive, but they used tactics that spent more time on the clock. The logic is that since they were ahead, "running out the clock" would give the opponents less time in which to score.

Of course, after Michigan failed to score and Notre Dame responded by getting a touchdown themselves, the Wolverines were suddenly fighting against the clock. Now it was them who needed to score within the remaining time.

This pattern went back and forth a few times, with the clock obviously running out on Notre Dame at the end. This strategy continues to confuse me, however. For a large portion of the game, Notre Dame showed that they were able to move the ball very well, meaning that if they were on the offense, they had a very good chance of being able to score. With eight minutes left to go in the game, it seems more likely to consider: "How long will the rest of our offense last? If they get possession again, will they be able to score? If so, will they be able to eat up the rest of the time during their possession, so that the clock actually runs out on us?" Michigan barely scored their last touchdown in time; the running of the clock earlier was almost their undoing!

This really starts to look a bit like an impartial game. Instead of determining how to control as much of the time of possession as possible, how can we instead control the parity of the clock so that on our last drive towards the end zone, we will have enough time, but the opponent won't have much after we're done.

Naturally, there are a lot of probabilistic factors in there, ignoring the fact that I've over simplified things. Still, it seems like some better form of analysis could be employed there.

Nimbers

I was going to write a short post asking another question I've had in the course of my research, but then I realized I should try to explain some of the terms behind it first.

Thus: Nimbers.

Nimbers are a way of evaluating impartial games in a way that describes more than just "which player can win" (though it does that too). The simplest example is the term's namesake, Nim. I won't go in to describing the many versions of Nim, just the most basic: you are given a bunch of piles of objects (say sticks). Each turn, a player may take as many sticks as they like from one pile. The winner is the player who takes the last stick.

This is very simple in the case of only one pile: take all the sticks. With multiple piles, the winning move is to take from the larger pile so that the two have the same number of sticks (if they already do, you're in trouble). It turns out that we can quickly evaluate the winnability of a situation with any number of sticks: count the sizes and xor them together. If the total is zero, there is no winning strategy.

Thus, while the pile containing 4 sticks has a winning strategy (take them all) a game consisting of two piles of 4 cannot always be won (4 xor 4 = 0).

Also, the game consisting of the three piles 3, 5 and 6 has no winning strategy (3 xor 5 = 6, which xor'ed with itself is 0).

This reality comes from an evaluation technique that can be used to identify any impartial game! This is drawn recursively from the values of the children---the games which can occur from the parent in one move. In Nim, if we just have one pile, then the children of that pile are all piles with less sticks. Thus, that pile has the "power" to be changed into any smaller pile. If we have a pile of size 5, it could be turned into a pile of size 0, 1, 2, 3 or 4. Although in the case where there is only the one pile, the correct move would be to 0, there are still some more options here.

In the case where we have two piles, say 1 and 3, we have the power to move to any of those children: 0 and 3, 1 and 2, 1 and 1 and 1 and 0. Using our evaluation trick from before, we find those games have nim-values 3, 3, 0 and 1 respectively. Thus, this game should be inherently different from the game where we had a pile of size 5. Indeed, look at those values. The above one has a value of 5 (it's just one pile; that's easy). The second has a value of 2 (1 xor 3 = 2). Why is this?

Notice that for the second one, 2 is the first nim value that is not included in the children, which we also call the "mex" or "minimum excluded number". More formally, for any set S of natural numbers,

mex(S) = min{x in N | x not in S} where N are the natural numbers

This really gives us the power of an impartial game by seeing how many continuous values are included in the children. This is what we call the nimber of an impartial game, G:

nimber(G) = mex({x in N | there exists child G' of G where nimber(G') = x})

We can compare and see that the nimbers of our above two games match exactly with the nim-values we calculated (with xor'ing) before. The above principle can be applied to any impartial game, however. Unfortunately, this is a recursive operation which takes, in general, an exponential amount of time to calculate. Nim is easy to evaluate because there is the simple xor-trick to shortcut past the nimber definition.

Having said all that, here is a question I encountered while trying to evaluate some board games: if the nimbers for a game are bounded above, does this imply that there is an efficient algorithm, or shortcut, to evaluate impartial games? Further, if the bound is not a constant but a slowly-growing function, can we find efficient evaluation?

In the course of wishing I knew the answer to this (I was evaluating a game that appeared to have some sort of efficient patterns) I found nimbers emerge for the game that were higher than I thought were possible. I still hope there is some kind of relationship here, however...