Integers Liveblog: Wednesday

The first day of Integers has yielded many excellent number theory and combinatorics talks... which I didn't follow very well.  After lunch, I spent much of the time playing FLex and Adjex with Alex Fink, Larry Rolen, Rebecca Milley and Marla Slusky, all of whom I just met today!

During lunch, Patrick played NoGo against Richard Nowakowski, winning two of three games!  Afterwards, Richard said, "it's clear the american strategy is different from the canadian."  Apparently in the states we play aggressively! ;)

With nine minutes left to go before the afternoon talks, Richard looked at Patrick and declared, "okay, one quick one!"  Later, he explained, "there is no such thing as the last game."

Awesome!

The Difficulty of Making a Move in International Draughts

As I begin the trip down to the University of West Georgia for Integers, I want to be sure to report on another awesome thing I saw in Banff back in January.

For most games I'm interested in, the rules are simple. Deciding whether one move is legal is usually an easy task. Usually, it's even easy to list all the moves. (Some games, such as Phutball, may have an exponential number of moves, so this task may not be considered "easy".) The challenge usually arises in finding the best move, not just one that works.

This is not always the case for International Draughts. For my American comrades, Draughts is the word the rest of the world uses for variations of the game Checkers. International Draughts is a variant played on a 10x10 board that is one of many "pub games" popular in Europe. The game is different from "standard" draughts in two big ways:

• Regular pieces may jump other pieces forward or backward.
  
  
• Crowned (Kinged) pieces can move as many spaces in one direction as desired, even after jumping another piece.
  
  
• A turn must include capture of as many opponents' pieces as possible.

This last rule is extremely interesting! Not only must your turn consist of a capture (jumping a piece) if possible, it must capture as many pieces as it can. If you watch the animation on the wikipedia page, it becomes clear that once you have a crowned piece, this maximizing move is not always trivial to find.

In fact, this question was posed last year as a theoretical computer science question: Is it NP-hard to find a legal move? Bob Hearn rose to the challenge and showed that it is, in fact, an NP-hard question. Bob presented this result at BIRS. I've never seen a game where it's computationally difficult to figure out whether you made a legal move!

How is this policy enforced in the "real world" of international draughts?

Nimbers in Konane

I saw a lot of awesome talks at the BIRS workshop in January that I still want to report about. One of these was an awesome talk by Carlos dos Santos that really struck me as a computer scientist. It used a real reduction-like strategy to prove that for any k, *k can be written as a Konane position! A cool result with a cool proof!

Gamesters are interested in which game values exist for different rulesets. Elwyn Berlekamp asked, "What is the habitat of *2?" meaning, which rulesets have a position equal to *2. For Domineering, it was quite complicated to find a *2 position!

Carlos dos Santos does infinitely better with Konane, finding an algorithm to construct a board of value *k for any natural number k. The paper is here. The algorithm is elegant and recursive, and each resulting position has a very clear focal point where one of two or three pieces will be able to make the first move. Naturally, the *4 Konane board is much more complex than the *4 Nim board, but the difficulty is showing that for each successive power of 2, that nimber can be generated. Indeed, I assumed *1, *2, and *3 could be created, but *4 would require a 3-dimensional board.

Instead, they all exist, and the result is something I wish I could ask my algorithms class to learn!

Presenting Neighboring Nim to Undergrads

I replaced getting a post ready for Tuesday with preparing a talk for this past Monday. I spoke at our department colloquium about Neighboring Nim, describing the reduction from (Vertex) Geography. Two excellent things happened.

First, I had a great audience. While playing Neighboring Nim against them, they were very energetic to make good plays against me. Will, a senior student of mine, immediately took on the role of surveyor, collecting move nominations from the crowd, then calling for a vote. The discussions were loud and boisterous. At one point, I made a very fast response to one of the audience's moves, using the Quick and Confident method. Unfortunately, I moved to an N position, with two P options. The audience quickly picked the board apart (it was by no means trivial) and found the two winning moves. The problem was that, individually, they didn't see the viability of the other move. So there were two groups arguing vehemently for two separate perfect moves. The attitude nearly boiled over. Luckily, the audience finally agreed and they made one of the moves. It was very exciting to speak to such a charged group!

Second, I changed the order of my talk around regarding the proof of computational complexity. Usually I claim that a game is hard for some complexity class, explain what that means, then show the reduction. Talking about complexity classes to a general undergraduate audience is a bit of a speed bump, and often shakes people out of the rest of the talk, meaning they don't follow the steps of the reduction. This time, I just said that the two games were related, then explained the reduction. This kept the crowd interested, because it's a description of positions in a game they just learned how to play. At the end of the talk, I spoke briefly about the implications of the transformation: the PSPACE-hardness of Geography implies the PSPACE-hardness of Neighboring Nim. At that point, having seen the reduction in full, I hope it sank in. Although I wouldn't do this in the future when presenting to a primarily graduate-student/professor group, it seemed to work really well for people who hadn't seen computational complexity before.

The slides for the talk are here.

Next week is Fall Break at Wittenberg, so there will probably not be a post on Tuesday as I spend the time off preparing for Integers 2011 the week after. With any luck, once I'm there I'll get to post some notes each day.

Game Description: Matrix-Game-That-Needs-A-Name

Games are fun and linear algebra is fun. Let's put them together! It's especially fun to try to determine whether a matrix is invertible. Here's a game that revolves around invertibility (it still needs a name).

The game begins with an invertible matrix of non-negative integers. Each turn ends with a player reducing one of the entries of the matrix, so that it is still a non-negative integer. If the resulting matrix is non-invertible, that is a losing move. Depending on how cutthroat you want to play, it might be up to the other player to notice you created a non-invertible matrix at the beginning of their turn.

I've played with my matrix algorithms class a few time|s this semester, using this as the starting position:

| 1 2 |
| 3 4 |

This position is in Fuzzy. What's the winning move?

Game Tree Woes

Getting students to write proofs is an interesting pedagogical challenge. Which class in a math sequence should start requiring formal proofs? What does formal mean?

Luckily, for CGT this has a simple solution: the game tree. Want to prove something about a specific position? Just draw out the game tree and label the options appropriately. Students should learn this as soon as possible; I broke the news to my freshmen class right away.

Bad news: I'm expecting rigorous proofs in this class.

Good news: these can be a proof by picture.

Unfortunately, I didn't do a great job teaching the basic requirements. We had problems with:

* Arrows to left/right options of a position. These were sometimes nearly vertical so it was impossible to discern whether they were for right or left arrows. Other times they pointed up, which is often very difficult to read.

* Not drawing all the options. We hadn't learned about dominated options yet, so all options should have been listed.

I think that the next time I teach this sort of course, I will have to be far more explicit about what makes a game tree. Also, I've done a good job this semester of using examples to motivate, but perhaps I didn't do enough examples of game trees.

Tomorrow the students have their first exam. Dangerous! I've decided to include a question where the goal is to find errors in a given game tree. I really wish I'd included these sorts of questions in the first few homeworks! We'll see how it goes.

(Oops! I inadvertently took last week off from posting. Sorry!)

Game Description: Zuniq

Wow, some good games were suggested by readers two weeks ago! In addition to Nick Bentley donating Y with Shifts, Marcos Donnantuoni commented about his own impartial game, Zuniq. Ernie and I tried this out on Monday, and we immediately liked playing this! Here's how the game works:

The starting board is a grid of dots, similar to dots and boxes. Each turn, a player connects two adjacent (vertical or horizontal; not diagonal) dots, but not exactly like dots and boxes. If a new line segment closes off a region, no future turns can be made inside that region. Also, no two regions can have the same size. Thus, you can't close off a region if a region of that size already exists.

The suggested starting 8x8 board is a bit large, but we gave it a go. (Video: [7:16]) Afterwards we tried with 3x3 boards, to quickly learn that they are not very interesting. (The first player can always win by being just a little bit smart.)

The 4x4 game is definitely more interesting. (Video of lots of little games. [6:08]) After a few of these games, and later with games played against Patrick and my WittSem peer mentor, Alec, I think I can consistently win going first there. Still, my initial guess is that the game is PSPACE-complete in general.

I feel like there are lots of nice theorems that can be shown about this game. At the same time, I'm not familiar with what sort of theorems are "useful" from a CGT perspective (aside from computational complexity results).