UGrad Course Update and a Mini Course in Amsterdam

So far, things are going well with the combinatorial games course I am teaching this semester. This is an undergraduate level course, aimed at both Math and CS students, and includes sophomores, juniors and seniors. Today it came up that the class feels both like a graduate-level course and the third grade. We are covering advanced material, but at a reasonable pace and with a very excited audience.

The class meets two days a week for 90 minutes. I try to spend the majority of one day letting students play a new game, asking them questions while they are playing. So far, this has gone very smoothly, alternating between game-playing days and note-taking days. I keep track of the games we've played on our class schedule. (Notice I haven't chosen anything in advance!)

I have assigned programming assignments as well as written homework. The students will end the semester giving oral presentations covering games not studied in class. I'm already looking forward to this!

I've already gotten some advice, but I'd naturally love to get more. If you've taught or attended a CGT course (even if you're one of my current students) any comments would be welcome.

On another note, I saw this announcement for a Mini-course in positional games next week in Amsterdam. I have the sudden desire to be in Amsterdam! :)

Game Description: Martian Chess

Just last week, I forced my aide to sit down and play Martian Chess with me. This is one of the games I was introduced to at Origins this past year, and have been looking forward to the start of the semester to try it out more.

This game is sort of a more complex version of Clobber: pieces are arranged on a checkerboard, and they "clobber" pieces near them---except that there are 3 different types of pieces and they move in different ways. Pawns move one space in any direction (including diagonal), drones may move up to two spaces (but only horizontally and vertically) and queens may move exactly as queens in Chess. Pieces may not jump over other pieces. Okay, maybe it is more like Chess than Clobber...

Nevertheless, the goal is to take opponents' pieces. 3 points are given for a queen, 2 for each drone and 1 for each pawn captured. The game ends when a player no longer controls any pieces. The twist, however, is that when you capture an opponents' piece, they now take control of your piece on the board. This occurs because each player "owns" two opposite quadrants of the board: they may move any pieces in their quadrant. Capturing an opponents' piece means moving into an opponents' section and surrendering the piece you just owned.

Martian Chess is a really fun game that forces you to think on your toes. Just about when I seemed to be coming up with a strong strategy, Ernie pulled a new trick on me and had me completely second-guessing myself. I would really like to play this game in class, but, alas, I don't think I have enough Icehouse pieces!

Let's use this wacky ownership in a variant of Clobber: Reverse Clobber. Now, when I clobber an opposing piece, I instead lose my own piece. How much fun is this to play? (Maybe not so much...)

Mentionables

A few nice things to note as we head into the weekend!

First, wouldn't it be nice to have all your board games played on an electronic surface? Apparently the iPad might be able to handle this task! I'm not sure whether this is entirely feasible for a few reasons, but it might be good for enforcing playing by the rules for many games.

Also, it's nice to see some engineering sites mentioning board games. In this Ars Technica article, the game Drakon is reviewed. I am a bit easily influenced; perhaps I should add this game to my collection! I wonder if they would ever review a bad game...

My papers didn't make it into FUN 2010, and it was so close to my wedding I couldn't otherwise attend. Sad! I wish I'd been around to hear about these papers!

On a very happy note, I am overjoyed by my students attitude in our games class. This week we learned Clobber, and I encouraged my students to try to work out a strategy based on symmetry. Every student was engaged trying to play this game well! Also, even though we are only in the second week, students have already begun selecting games for their final project. Very exciting!

Writing Game Rules

I often can't stop thinking about board games that are not completely combinatorial (they have some randomness or hidden information, etc). Often this happens in games where I'm trying to figure out exactly how the rules work.

After thinking about programming all day, it's not difficult to pick apart game rules and consider potential ambiguities. I'm teaching my algorithms class to be sure that any algorithm they write by hand be precise, and I often wish game rules were spelled out with a similar notation.

(Example using a property-type board game.)

Step 1: Set the board up according to the section Setup.

Step 2: Let p be 1.

Step 3: Player p rolls the two dice, then advances their piece clockwise around the board.

Step 4: Let s be the square containing their piece. If s contains an unowned property, continue to step ?.

Step 5: Let h be the number of houses on s and q be the player who owns the property at square s. p owes q $X where $X is the amount listed in the h-th entry of property s. Go to step 7.

Step 6: p may purchase the property... ...

Step 7: Increment p. If p is greater than the number of players, let p = 1. Continue to step 3.

Using the standard notation for Combinatorial Games, this is not an issue; all rules for play are considered the same! All the necessary information is which moves are available to each player.

Sometimes, the legal moves are not always obvious in board games, however. I've been playing Set Cubed with other members of our department, and this is a very fun game. The basic premise is a mix of Set and Scrabble, where players score points by creating new Sets each turn, filling up a 2 x 2 grid. (A 'Set' is a triple of pieces where, for each property of the pieces, either all three have the same value or all three have different values. (Each property can have one of three values.)) The rules for this game are available here, including many nice pictures.

In the game, an often-occurring move is to play a piece that creates a set in one direction (horizontally or vertically), but doesn't in another, even though it lines up with those pieces. This is perfectly legal, which is clear according to the rules. On a turn, a player may play up to three dice on the board. What is not clear is whether those dice must be played one at a time, pausing in-between to determine the legality of that play alone, or whether a first die may be followed immediately by a second so that the trio form a set, even if the first doesn't create any.

As it turns out, you have to allow this in order to play in other directions besides a straight line, but later on it seems awkward to play a piece that creates one or more non-Set groups of three, then immediately cover that up with a second piece. It could be that this is not legal!

Since it looks like my lunch group will be playing this game a lot, I emailed the makers of Set for a clarification. They responded very quickly and told me that this is legal, as examples were shown in the online tutorial.

Either way, I'd like to try playing under both rules! This is a very nice game that employs a nice amount of randomness without removing all the strategy involved. Also, it is not trivial each turn to see where your available moves are, as it is not trivial to see all set combinations. It also removes the speed aspect of Set, as players take distinct turns instead of calling out the Sets they see.

Game Description: A Collatz Game

I just learned about the Collatz Conjecture last year, and it is a wonderful problem to play around with in semi-free time.

So much fun, in fact, that it was time to make a game out of it. The plan is to move from one number in a Collatz sequence to another "neighboring" integer, and be the player to reach the number 1. Obviously, the game gets boring if players always have to choose the next number in the sequence, so we let people go "backwards".

As a quick review, the Collatz Conjecture states that the following process will terminate, starting with any positive number. First, check if the number is 1. If so, stop. Otherwise, check the parity of the number. If it's even, divide it by two and start over. If it's odd, instead multiply it by 3, then add 1 and start over. It's not known whether this is actually true for all numbers, but it's been tested up through something astronomical (and continues to be tested for higher numbers).

For the game, we need to be a bit less strict about what the next number is. Instead of always going "forward" we will allow some backwards moves. So, if on your turn the current number is n, you get one of the following options:

• Move to 2n
• Move to 3n + 1
• Move to n/2, if n is even
  
• Move to (n-1)/3, if n-1 is divisible by 3

Unless, of course, the value is 1. Then there are no further moves, and you've lost.

Also, to prevent boring back-and-forth strategies, you are not allowed to just reverse the last player's move. Thus, each turn, there are between 1 and 3 possible moves. For many cases, your next move is decided for you.

Last weekend, my brand-new aide, Ernie, and I gave this a shot, and we quickly realized we needed restrictions on when a player could make either of the moves that increase the current value. After a few rules changes, we both realized that players should be forced to move downwards if possible.

On our first try with these rules, played the following game: 11, 34, 17, 52, 26, 13, 4, 1 (a win for the first player!). In this case, only the first move and the last move actually were decision-making points. Curious, we looked at what happened making the other move from 11:

11 -> 22 -> 7 -> 2 -> 1 (second player wins) which didn't have any other decisions available.

This seems like a boring game, until we tried starting at 10: (D's indicate places where decisions were made)

10 D-> 3 -> 6 D->12 D->37 D->74 D->148 ->49 ->16 D->8 ->4 D->1

Then 16:

16 D->5 -> 10 -> 3 ->6 D->12 D->24 D->48 D->145 D->436 ->218 -> 109 -> 36 -> 18 -> 9 -> 28 ->14->7->2->1

Some of the rules need to be ironed out here to prevent the number from getting too big too quickly. We wound up adding a stipulation that the number can't be doubled three times in a row helping enforce that the number will drop at some point. It could be that other additions help out, without completely limiting player choices.

As it is, this is a nice impartial game to play that requires only a pen and paper and some basic arithmetic. Also, it's likely okay to ignore determining the computational complexity when it's still not known whether all Collatz sequences terminate. Give it a try, and let me know which rules worked for you!

Kicking Off: Fall 2010

I hoped to write a smattering of blog posts this summer, but then a lot of things happened this summer and then I only posted once. Some of these affected me very personally, for example:

• I drove back-and-forth across my time zone twice.
• I learned that paying extra for first-class plane seats does not give you more leg room.
  
• Vinay Deolalikar tried to show that solving Atropos is not in P. There is some disagreement about how close he came (he continues working on this) but it's very nice that everyone cares so much!
• I miss winter.
  
• I am now happily married.
  

For those who I promised to chat with this summer, I apologize for not doing that. Please resume contacting me!

Luckily, Wittenberg's fall semester begins early and with that comes a return to a regular schedule. I will plan on two posts per week, and this time I will have some help preparing them. Beyond this, there are other benefits for this semester:

• I'm teaching a CGT course! I look forward to chatting about that.
  
• I will refrain from polluting this blog with mentions of college football, despite the up-and-coming season. Instead, I just started a separate blog dedicated to my automated ranking.
• I have some help prepping things this semester! Hooray!
  

The planned schedule for this semester is for updates on Tuesdays and Fridays. As usual, please feel free to request material to cover. If there's something interesting in CGT you've done, and feel too modest to tell me yourself, feel free to have a friend contact me! :)

Happy (Academic) Fall!

Origins 2010

Wooo!

I am back home in Springfield, Ohio, for the first time in a month. The vast majority of the trip was dedicated to getting married, but the tail end was a trip to the Origins Game Fair in Columbus, OH.

Unlike GenCon last year, this year I prepared by registering for a bunch of events and got to play a bunch of games. Many games don't quite fall under the "combinatorial" heading, due to their inclusion of random elements or imperfect information, but they all have elements of looking ahead necessary for playing games well. Sometimes these elements can be modified to either publicize or derandomize information. Othertimes, other combinatorial aspects can be extracted into their own game. In any case, playing any board game can always be a useful exercise for gamesters!

Okay, I'm going to try to recall the games I played. If I forget any and add them later, I'll add a bolded note and a comment. Unfortunately, I don't have pictures now; when I take the initiative to put up all my pictures, I'll add links to the origins pics.

I missed the first few days of the convention and showed up on Friday morning. That morning, I was lured into the Looney Labs room by a bunch of people playing World War 5. I got in on the next game and pulled off a sneaky win with the luck of the dice. This continued a pattern of other games using Treehouse pieces, starting with Volcano, an actual combinatorial game. After this, I sat down and was introduced to Martian Coasters, then Treehouse, the original game for the pieces, then Martian Chess (another combinatorial game!) and finally Pikemen (combinatorial again!). Pikemen was especially fun, since we played on a three-player chess board someone there had!

I stayed extra long at the Looney Lab site, and had to race to my D&D appointment with some other folks from Wittenberg. After that fun excursion, I played Age of Conan, which was a bit disappointing. Saturday started off with my first game of Arkham Horror, which is perhaps the first time I've ever played a co-operative board game. Here, all the players work together to complete a task (sealing away an ancient, Lovecraftian demon) while the game mechanics work to try to unleash the monster into the world. Definitely not combinatorial, but definitely very fun.

Arkham Horror was followed by Robo Rally, which I had played once before. This is a great board game that really uses some programming aspects. In this game, players move robots around a grid by choosing individual move or turn cards from a dealt hand. Those cards are placed face down in an order to be executed, then all players' first cards are revealed and executed, followed by the second, and so on. My first sequence of moves was miscalculated and landed me in a pit obstacle on the grid. Oops! While at Origins, I tried to find a copy, but didn't find one reasonably priced. This is by far one of my favorite games from the weekend.

Heroscape came next, a strategical battle game with very beautiful pieces and an easy-to-understand hexagonal layout. I generally swoon for hexagons, but I didn't expect I would enjoy playing this game as much as I did.

Next, I headed over to the Mayfair room, expecting to get roped into some form of Settlers---I've never played! Instead, I got in on a demo of a not-yet-produced gem, slated to be named Lords of Vegas. This game simulates casino bosses building up the Las Vegas strip. As the rules were described, I thought it was going to be overly complex, but then everything came together as we played. We were easily the loudest table in the whole Mayfair room that night, and the game came down to a roll of dice at the last moment. This was tons of fun, and actually one of those times where some simple probability analysis can really help out.

My last scheduled event was Runewars on Sunday morning. This game did not inspire me (though there were hexagons) as much as others, mostly because there were a few too many things going on all at the same time, and just too many rules to keep track of. Some board elements didn't seem to interact in any way, and I lost interest pretty quickly. I did make up for this by spending the afternoon browsing the dealer hall and demoing a few games that caught my eye. I spent some time at the Out of the Box booth, meeting some people there and trying out some other games. I also met the creator of WEGS and learned the basics for that role-playing system. I made sure to get a set of Treehouse pieces to play around with later.

Did anyone find any great combinatorial (or combinatorialish) games at Origins? If so, I'd love to hear about them!