Integers Liveblogging: Friday

Some awesome quotes from today:

"Actually, I can say I played NoGo; I don't play Go!" -Aviezri Fraenkel

"'Every other weekend'?  Other from what?  What is the complement?"  -Rebecca. ('Every other' is apparently not colloquial in Canada.)

"...and I am guilty of some of this research."  -Florian Luca during his talk on Balancing Fibonacci Numbers.  He went on to describe a problem as a mathematician trying to solve a system to find the street address for a party. :)

Last night, we had a little NoGo tourney between Canada, the US and Europe.  Canada won, 5-4, but there may be a rematch tonight of sorts!

Integers liveblogging: Thursday

Today a lot happened. I talked and I listened to lots of games talks, many of which will become their own posts in the future. Instead, I'll quickly mention some highlights thus far.

Rebecca confused me yesterday by saying "in P" which I automatically translated as "efficiently solvable" instead of "in Zero". I had just met her, so I asked excitedly if she was in computer science. She said this misconception is even more dangerous because she is dealing with misere games, and need to consider both outcome classes. Those in Fuzzy when playing misere, but in Zero under normal play are in N-,P+, pronounced "NP" (which computational complexity theorists use for another well-studied complexity class). Dangerous!

I've also seen a great bunch of non-games talks, mostly number theory, which I've understood a bit of. Particularly, Carl Pomerance gave a talk I understood most of about product free subsets of the Naturals (if x and y are in S, then x*y is not in S... usually x*y (mod p)). Neil Hindman gave an impressive talk, mostly because I don't think he looked at any notes and covered a lot of complex stuff using only a whiteboard! I also found out yesterday that Beatty sequences/ratios were used to help discover quasicrystals, something which had a lot to do with this year's Nobel Prize! Wow!

I've mostly had a blast meeting people and playing games. While playing FLex with Marla yesterday, she commented, "This is all very important!" Everything I explained about what I was thinking was quickly absorbed by her and Rebecca. Awesome!

Meeting people---especially over games---is great! I played some impartial games with Yuval Tanny and Shira Giat. At one point I made a winning move, but was afraid I hadn't gotten the parity correct. Neil put me to ease, saying, "Yes, you counted to two correctly." That's about as high as I feel I can count these days.

Yuval and Shira are clearly awesome; this seems to be the norm for gamesters! There's a lot of energy in the group---all positive---especially from Jess Enright, who gave an awesome talk today about set representation games. Here is a picture of her realizing she won a game with Marla during the talk.

I feel like a bit of a reporter, trying to keep up with everything, but it's very helpful to help me stay on point in the talks. Seriously, they were great and I can't wait to get some of those posts up.

I will try to get a post up tomorrow before the evening, but if not, I'll put in my final fake-liveblog next week. I'm leaving on Saturday morning, so I won't be around for the last day of the conference, sadly.

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