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.)

A Homework Worksheet

I am surprised by the success of my class audiences! They continue to be unbeaten against the speaker in our presentations. The class is now 5-0!

This week is Thanksgiving; there will be no post on Friday and today's post will be light.

As I mentioned, I have been making worksheets for homeworks for my class. I just finished the last (fourth) one this week. I won't hand it out to my students until next week. In case anyone's interested in seeing what these look like, here is the first one.

For those of you in the states, have a great thanksgiving!

Point-Value end states

Student presentations have been a huge success so far! Competition is a funny thing, though. Somehow the audience is unbeaten (through four presentations) even though things always begin with the students collaborating: "We shouldn't try too hard to win; we should let win so they can earn the bonus points!" By the middle of the game, this has been forgotten; the audience is trying to optimize their moves. For hard games, the collaborating audience apparently has the advantage here!

Today, during our Reversi presentation, the question came up about the value of the final game states. I mentioned that one interpretation was that the result is equal to the number of blue circles minus the number of red circles. Another way to think of it was to consider that immediately after the Reversi game ends, a new game is played equal to that number value. This avoids ties: if the score is the same at the end, then the last player to move on the original game wins.

The students grabbed on to this idea and ran with it, chatting about it as the game continued. This method extends to other similar games that normally end by comparing point scores: Dots 'n' Boxes, Flume, etc. Even Hex can be conceived like this: the "score" for the winner could be the number of uncolored hexagons remaining on the board. Thus, the faster you win, the more the game is worth.

Notice that this doesn't make a difference if this is not part of a game sum. Without other attached games (or bragging rights) the only important part is whether or not you can win this game. In this case, it is instead equivalent to say that after game play is finished, we just append a game of value either -1 or 1 after the original game ends, depending on who "earned more points".

Does anyone ever play game sums with either of these methods? Anyone prefer one over the other?

Lectures are over... how to make them better!

Thursday was our last "regular" class period. From today until the end of the semester, students will be presenting games they've researched on their own. If there is any extra time, I will fill in by attacking some of the topics we didn't cover throughout the semester.

There's a lot we didn't cover. Just on Thursday, I skipped ahead and covered Nimbers. We had only just started to cover infinitesimals: Up and Down. We hadn't quite gotten to DoubleUp = Up + Up. We were close to covering Switches.

I hope to teach this class again, but how could I improve things?

First off, Lessons in Play is an excellent text, but there are a number of things that should just be skipped. My students are not (all) math seniors, but instead a mix of computer science and math majors from sophomores to seniors. This means I should just skip more of the proofs in class. Many of the theorems are intuitive, and students are so hungry to learn how to evaluate these games, they want more statements of what is true and less explanations why. I think it's a shame I didn't get all the way to switches, these students really wanted to know what to do with {x | y} when x > y!

Second, I should use more worksheets. The last two weeks I started making worksheets for my students for their homework assignments. That worked really well. Somehow I didn't hammer it in hard enough that a game tree is the best proof. These worksheets take the students through the steps to prove the result, enforcing all the steps that are necessary.

Also, I think I need to choose better games to play during class time. Better doesn't mean more exciting, but instead more relevant to the topics we've chosen. Some games have more infinitesimals, while others are really great examples of employing the Simplest Number Theorem.

One thing that worked really well were the programming projects I assigned in class. For our last project, students must find the Grundy values of Cram games, implementing these properties straight from the definitions.

Exciting! I can't wait to teach this again!

Game Description: NoGo

I don't yet know how to play go. I just got my set in the mail last Monday, and I'm looking forward to finding someone at Wittenberg to help me get started. Luckily, there is the game NoGo. I may not know just how much this game is related to Go, but at least it is teaching me to play pieces on the intersections of lines instead of the boxes.

NoGo works in the following way: players alternate placing white or black stones on a grid. Each intersection is adjacent to the four connected intersections. In the game, a turn consists of adding one of your stones to the board on an empty intersection. Plays are otherwise restricted only by the following rule: each contiguous group of stones of one color must be adjacent to an empty intersection. Thus the board resulting from any move must have this property, both for your color and stones of the opposing color.

For example, look at these two game states:

On the left-hand-side board, neither player has a move, placing any stone in the lower-left corner will prevent all connected regions from touching an empty intersection. On the right-hand board, the Left player has a move: they can add a black stone. This move connects the two regions, which has two pieces still touching the empty spot. Right does not have a move; no white stone can be placed which will connect to any blank spots.

This game is a bit tricky. Sometimes you want to have more of a presence so that your components are large. Other times, you wish you had smaller connected pieces, feeding off of an empty space.

I don't know how this relates to the grand game of Go (I hope to soon) but NoGo has already been fun to play!

MCURCSM

Exciting news for my department: we are hosting the Midstates Conference for Undergraduate Research in Computer Science and Mathematics (MCURCSM) in just a few weeks on November 20th!

Liberal-arts undergraduate students often find themselves performing excellent research, and conferences such as these are perfect outlets for our students to show off their work. We're very excited to be holding this year's conference here at Wittenberg.

Unfortunately, I will be out of town that Saturday and will not be attending. Please come for the great student presentations and enjoy the awesome work performed by many first-time researchers!

Out of time!

Sorry! Today was more packed than expected!

More posts next week!

Impossible Game States

While preparing some old work to go into my thesis two years ago, I realized a potential hole in my construction: could the Atropos boards described always occur in the midst of a game? I had built some convoluted board pieces, then glued them together in PSPACE reductions. But could these monstrosities actually be the state of a half-played game? Atropos has a requirement that players must play adjacent to the last play (if possible, otherwise you may play anywhere). Thus, some game states are impossible to reach.

Here, the lone red circle and the green and blue to the right are disjoint sections that could not have occurred without a colored circle surrounded by colored circles.

Does this ever happen with other games? Naturally, we need to consider a game that has regular starting position(s). Assuming we always start from a full n-by-m grid in Chomp, we will never see a board that is missing cookies in the wrong places.

A cookie in Chomp cannot be missing when any cookies up and to the right are also present.

Some games aren't quite so clear-cut. In Domineering, we would never have a board with an odd number of checkers covered. However, we might have that board as a piece of a more complex partition of boards, so it could be a legitimate subsection!

Consider Alice and Bob, who sit down to play a game of Chess. After a while, Bob thinks he is winning, and gets up to find a snack in another room. He returns and looks at the game board, realizing that he is actually in a bad state. What happened? Perhaps Alice switched pieces around, or perhaps Bob does not correctly recall the position of pieces. If Bob knows that no pawns have reached the opposite edge of the board, does Bob have any chance to prove that the current board state is illegal?

Are there any games where it is difficult to determine whether the game is in an impossible state?