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!