Winning Player Conjectures

The game Sprouts has a very interesting conjecture associated with it:

If the game starts off with n dots, then the first player has a winning strategy exactly when n mod 6 = 3, 4, or 5.

This seems strange. Why 6? How is this number inherent to the rules of Sprouts? Well, it's not clear that it is, because the conjecture has not been proven.

Nevertheless, supporting cases continue to be found. Somehow I am comforted by the idea that somewhere, there is a computer working to check cases for Sprouts. (Probably I feel the same way about the Collatz Conjecture. Someone is running that right now, right?) Sprouts is also studied in the misere version, with other cases being checked.

Along these same lines, there is a conjecture for Atropos:

If the game starts with n open circles along a side, then the first player has a winning strategy exactly when n mod 4 = 0 or 3.

This has a bit of intuition behind it: if the losing player can enforce that the game drags out to the last circle, then that last circle will cause the loss. Since the number of open circles at the beginning game are 1 + 2 + ... + n = n (n + 1)/2, this is even exactly when n mod 4 = 0 or 3.

Naturally, there is lots known about starting positions. Hex and Chomp both are wins for the first player, though the proof is non-constructive.

What about other games, such as Amazons? Which conjectures exist for the winning player from starting positions?

Game Description: Toppling Dominoes

I did a "tour" of classes the past few weeks, advertising my board game course next semester. While doing this, I brought my copy of "Lessons In Play" to show off. On the cover is the addition of a Konane game with a Toppling Dominoes game that equals an Amazons game.

I point out that it's pretty cool that we can express games this way. Unfortunately, I realized that I didn't really know anything about "that dominoes game". Hmmm...

It turns out the rules to this game are very simple! Here's how it works.

With a supply of dominoes, each colored green, blue or red, set some of them up in one row. Then the Blue and Red players alternate turns, each knocking one of their own colored dominoes (or any green domino) to the right or left, thus knocking down all the other dominoes on that side.

Notice that this game, just like normal Nim, is not terribly interesting alone. In just one row, any player who has a domino of their color (or green) on one of the edges of row can just topple that one, knock down all the other dominoes, and win as there are no more plays. In fact, in the case with only blue and red dominoes, if both ends are in your color, your opponent has no way to prevent you from winning.

With more than one game, however, this gets more interesting and it becomes important to find the actual value of each game to play best.

I don't know the complexity of analyzing this game, though.

Tournament Spectator Scoring

In late March in the United States, there is a college sporting event known as March Madness in which the top 64 (sort of) mens college basketball teams compete in a lose-once tournament to determine the annual champion.

I'm not a huge basketball fan---mostly because I have no sense of verifying whether a foul happened---but as with any sport, it can be tons of fun to watch. With March Madness, there is a different level of spectating that occurs. Instead of watching all the games, fans instead predict who will win each game by filling out a bracket (such as this one) before the tournament.

Fans then compete with others using their brackets. You gain or lose points by correctly or incorrectly predicting winners at each round, respectively. How does this scoring usually work?

The first time I did this with some friends in grad school, we scored by simply counting the number of incorrect guesses. The "contestant" with the least won.

Alternatively, you can assign a different number of points per incorrect guess at each round. For example, each correct guess in the first round could be worth 1 point, each in the second worth 2, then 4, then 8, 16, and the final game is worth 32 points if predicted correctly. This is apparently the preferred method (using the scientific method of web browsing).

The problem with this is that after the first few rounds, many of your teams have been eliminated. Sports are much more fun to follow if you always have a team to follow, independent of the game. If I didn't predict either of the teams to take part in a game, then I don't care who wins! Instead, whenever a team you picked loses, you cross them off everywhere in your bracket they appear (losing points at each step) and replace them with the team that beat them. This year, I picked Villanova to "go all the way" but they lost in the second round to St. Mary's College. Now, I am rooting for St. Mary's to win their next game.

This year, my competition is colleague Bill Higgins, who knows something about basketball. We agreed to score this way, with each "correction" costing 1 point. Villanova losing has already cost me 5 points, but it could cost me more if St. Mary's loses (especially if they lose soon).

One problem here is that the final game is likely not super exciting. It is only worth 1 point! Instead, each correction could cost different amounts depending on the round the correction was made. Then, using the 1, 2, 4, ... 32 sequence, I would have lost 10 points due to Villanova's loss instead of 5. In this case, everyone has a stake in the final game and it's worth 32 points. Here, however, because more than 32 points can be lost in any other round, it does not eclipse the weight of other rounds.

Perhaps that would be better to use...

Anyone familiar with other good scoring methods?

No FUN for me. :( Other conferences?

FUN with Algorithms 2010 is taking place in Italy in early June. I submitted two papers, but neither of them made it in.

I would normally still probably try to go, but I'm getting married shortly afterwards. (Woohoo!) Without the excuse of presenting a paper, I won't attempt to squeeze these things together.

I've missed a lot of following paper deadlines, and there are others that I am either interested in or would consider submitting to. Here's a little list of what's already passed by (but might be candidates in future years):

FUN 2010
AOFA 2010
SWAT 2010
ICALP 2010
COCOON 2010
FAW 2010

Those still coming are:

GandALF 2010
FOCS 2010
SAGT 2010
COMSOC 2010
ICS 2011
INTEGERS 2010 (I don't have a site for this yet. INTEGERS 2009 had a very short submission/acceptance time.)
LAGOS 2011

(These are listed in order of (expected) submission deadline, not actual conference dates.)

I mostly catch these as they come through Theory Net. I'm likely out of touch with some more math-based feeds, though. Can anyone suggest other conference options?

Also, I've played a bunch of games of bOOleO this week already! This is an excellent card game! If I ever teach a machine organization course, I will somehow work this in as an example of logic gates!

Oops and Updates!

Hmmm...

I see that I missed Friday. As soon as I noticed that, I feared that I had missed last Tuesday also, but, no, I showed up that day. Last week was spring break, but I did not intend to take as much time off from work as I did. I apologize for missing on Friday!

One of my big tasks for this past week was to make sure everything was okay to close down my web account from BU's CS department. Sad! Now the Atropos and Matchmaker applets are hosted on Wittenberg sites, and they seem to work just fine. Please let me know if you notice any problems with either of them, and I'll fix them immediately! (If you don't have Java enabled on your browser, there's not much I can do for you.)

I am expecting to get a copy of bOOLeO delivered soon! That game looks excellent! There is something very enticing about seeing game pieces in pictures and coming up with what you expect the rules to be before actually reading any.

I realize that of Atropos and Matchmaker listed above, I have only actually published (thesis not counting) about one of them. I have never submitted a paper about Matchmaker anywhere, though it might be a topic that could sneak in somewhere. Still, I am a bit loathe to do this until after I prove something concrete about the difficulty of the game. Either showing that it can be solved in polynomial time or finding a completeness result would be enough for me (I haven't worked on this game in a long time).

Is this legitimate? I've noticed that in some of my presentations, no one cares about solving the game, but are instead more interested in the origins and rules (and implementations) of the game. Perhaps it is more vital to get playable versions of games out and introduce them that way than to make sure something is known about them first.

Double Games

Sometimes it's fun to try and combine multiple game boards or sets at the same time. We can always use the normal ways of adding two games together, but there are some other alternatives too...

In high school, a friend of mine mentioned he used to play "boxcar chess" with his family. This is a version of chess using two sets and four players on two teams. Two games went on at the same time, except whenever you capture an opponent's piece, your teammate gets to add that piece to their board. Thus, you had to play the opposite color of your teammate.

I don't know the details of how you add "new" pieces, but I assume you can spend a turn to place one of them in your back row.

I tried to adapt this for Stratego, since my family had two sets. I made the rules a bit too strict, however, and it wasn't all that interesting. I'd like to give it another try some day with more flexible rules.

Then, just last week, I was chatting with Brian about old war games (I really am only familiar with Risk and Diplomacy) and he mentioned enjoying "Double Risk" using two boards. The boards interact by including adjacencies between each pair of countries with the same names. Thus, if I wanted to get past Central America on board A (which has a bunch of armies on it) and I have a big force on Venezuela on board A, I could instead attack Venezuela on board B, then Central America on board B, then, say, Western United States on board B and on to Western United States on board A. I don't actually think this is a good Risk strategy, but I'm still bitter at that game for the power of cards...

Undergrad CGT Course

I have good news for next semester! The CGT course has been approved and I am already preparing material. The course will be cross-listed in math and computer science. The broad goal of this course is to explore combinatorial game theory as deep as is feasible with extra attention paid to programming and algorithm design.

Some games, even if they defy the proper definition of "combinatorial", may have special purpose here. One of these is RoboRally.

About a month ago, I played RoboRally for the first time. It was advertised to me as a game that "used programming". I did not believe this at all (I was hoping to play a game of Kingsburg that night) but then after playing for a just a few minutes, I was hooked. In the game, you have a robot to move around the board. Each round, everyone is dealt a hand of cards, each of which is an atomic command for your robot (move or turn a certain direction) and you immediately choose a subset of those cards, then order them. Your robot then makes those moves in that order, but might interact with the orders of other robots. It's great because you have to think very carefully about the "program" you give your robot.

Additionally, I do want to be able to get into some of the details of complexity classes, but without going through an entire algorithms/complexity course. The only prereqs for this course are Programming I and Discrete Math. Somehow I will have to convince the students that you "probably can't" solve some of these games.

If anyone has any good suggestions for games or other resources, I would love to hear them!

Also, has anybody played this game? I can't seem to find any information about it anywhere, but it looks like it could be cool!

Updates to the game table have been slow, but I continue to make 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!