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!

In-Depth look at Chess (link)

Ken Regan guest posts about solving chess here:

http://rjlipton.wordpress.com/2010/05/12/can-we-solve-chess-one-day/

Enjoy! :)

Implementing a Game Class (type, not course)

In the fall of 2009, I taught a software engineering course. As our on-going project for the semester, I had students code up a bunch of different combinatorial games. One of the major goals of the course is to teach students the benefits of employing object-oriented design. As I tack on new aspects to the project each week, code that follows more OO-principles will be easier to upgrade.

Together, this begs the question: how should a game be implemented? More generally, what should be common to the interface for all games? What methods should a Game class contain?

Looking at this from a pure mathematical perspective, there should be only two methods: getLeftChildren and getRightChildren. If those return collections of game objects, then you're done. Everything you really need to know about a game is contained there. Other convenience methods would probably exist, such as leftHasMoves and rightHasMoves, etc., but these two are sufficient.

In the practical view, however, this is a problem. Some games have a very limited number of possible moves from any single state, but other games, such as Phutball, can have an exponential number of children. Yikes! You would never want to generate that collection for big-enough games!

Instead, consider replacing getLeftChildren and getRightChildren with the methods isLeftChild and isRightChild that return whether a given game is a child of the subject game. Could this work as a proper interface?

One obvious advantage is that we do not have to find and return all possible child states. One disadvantage, however, is that for many games, returning that set might be easier to code up than determining the validity of a child. The easiest "cop out" of this argument is to generate those children, then test whether the passed child is an element of those children. This doesn't solve the efficiency problem, however.

Is that problem solvable, though? Again, using Phutball as an example, it is NP-hard to determine whether a player can win on a given turn. Is it also as difficult to determine whether a child of a game exists? It seems trivial that this must also be NP-hard; use a winning position of Phutball as the potential child and ask the same question.

This argument does not immediately prove the hardness, as in Phutball there are potentially an exponential number of final board positions that result in a win. We cannot just test whether the ball ends in the end-zone as our final child state, but must also include whether any prior-existing players also remain on the board.

What is the complexity of this problem? How hard is it to tell whether a game is a child of another game?

This ends the regular posts for the semester! I will make a few posts over the summer (especially if I get a sexier phone) and will return to a regular schedule in the fall. I apologize in advance if those posts are very teaching related...

Thank you to everyone who has chimed in, both via email and in comments! I got a lot of vital advice, including material I may be able to include in teaching next semester. I'll still be listening all summer long! :)

Final Post of Semester: Thursday (not today)

I have been unexpectedly swamped today. I do not want a haphazard post today, so I'm pushing it back until Thursday.

Sorry!

Post with Games on Goedel's Lost Letter

Goedel's Lost Letter has a post with some combinatorial games.

I should start adding more pictures...