Friday, April 30, 2010

Game Description: Fjords

First, a few administrative notes. Wittenberg's classes end on Wednesday, so this will be the last Friday post of the semester, and Tuesday will end the regular schedule. I have a list of potential topics on my whiteboard for Tuesday, but if there's something you'd like me to comment on, please let me know.

This summer I will be away from Internet access a great deal and I will not try to keep up any sort of scheduled postings. I'm sure there will be some posts, but not with any regularity.

Thanks also to everyone who has posted or emailed me about content this year! One of these people was Paul Ottaway, who suggested I try playing the game Fjords. He mentioned that this is half non-combinatorial and half combinatorial.

Earlier this month, I got a copy for my birthday and I've already played a bunch of games! It is just as Paul mentioned: the first stage (which actually takes a long time) uses a lot of random elements. The second stage (this goes pretty quick) is a pure combinatorial game. It is not, however, a game that I am aware of. Perhaps it exists and has already been studied! Perhaps you will have heard of it and can let me know! :)

The first stage of the game consists of the players "exploring" the land they will settle. Players flip over hexagons with field, mountain and sea patterns, fitting them together to form the landmass. The result of this is a hexagonal grid graph with some vertices missing (tiles were not placed or do not include any field area) or edges missing (field tiles with mountains or the sea between them are not adjacent). While placing these tiles, a player may elect to place one of their few farms on the most recent tile (it's stuck there for the rest of the game). Thus, the hexagonal graph has some of its vertices labelled either Red or bLue before the second stage.

The second stage of the game is then very simple: a players' turn consists of labelling a vertex. That vertex must be both uncolored and adjacent to a vertex already of that player's color. When one player cannot color a vertex, they lose. In the actual game, these newly colored tiles represent fields spreading from your farms. Also in the actual game, if you both get the same number of farms, it is a tie (instead of a second-player win).

The second half of this game seems very basic, however. I would be astonished if it didn't have a name in combinatorial games. Even if played on any (planar?) graph instead of only a subgraph of a hexagonal grid, this must be studied somewhere.

In any case, I highly suggest giving Fjords a try! It's an excellent game for two people, but do not believe the 30 minute time requirement the box suggests (they want you to play the whole thing three times). All my games take around 30-45 minutes each, meaning a WHOLE game would take around 2 hours!

Tuesday, April 27, 2010

Mall Madness

This weekend I did something I thought I would never do: I played Mall Madness.

Mall Madness is a board game where the players are shoppers, trying to visit different stores and to purchase something from each of them, then be the first to leave the mall. The game has been in production for over 20 years, and is targeted to middle-schoolish-aged girls. Since my sister didn't have a set, I never played. (I did play Pretty Pretty Princess, but that was for a babysitting gig.)

It turns out this game is not just about a shopping spree, but actually about finding the best order to visit different locations. Each of the different shops has an item you want to buy at different prices from the other stores. You could choose a path to purchase all the cheapest items, but those are not all located together. In addition, you don't begin with enough cash to buy everything and must periodically stop by the ATM to withdraw more money. I actually found myself not having enough time between turns to try to figure out the next two or three stops I should make. "I could go buy a 'Compact Disc' at the music store for pretty cheap, but the gift store and department store are a good deal, and they're on the other side of the mall..." I don't know if this is standard rules, but we didn't have to visit all the stores, just a subset of them of some given size.

Additionally, some stores run sales so that the price of their item is even cheaper. These change, so you have to make decisions about whether to try to make it across the mall for a given sale or just to ignore it and hope it changes soon. Thus, the more flexible your plan is, the better.

Unfortunately, this also means it doesn't pay off very much to actually plan ahead. There are a lot of widely varying random factors: you can move between 3 and 12 spaces each turn (or something like that), sometimes the stores have lines that prevent you from buying things, sometimes the stores charge more than they advertised (isn't that illegal?) and sometimes they have secret sales. I'm not sure if you can normally buy things even half the time; these other scenarios kept coming up! (The randomness in the game is controlled by an electronic component, so the probabilities aren't obvious.) Even when you went to the bank, you received a random amount of money somewhere between $50 and $100. (The phrase "Daddy doesn't love you as much as he loves me!" came up a bunch whenever someone received $50.)

Just to really shake things up, at any point the game could have players "warp" across the board to visit the ice cream stand or other random locations.

I'm not entirely sure what lessons this game was teaching young girls. There were certainly some sexist elements, and having to make multiple trips to the ATM in one shopping adventure may be a bit dangerous of a plan. Still, even when you try to look ahead and figure out the next two stores you should visit, you have to do a bit of calculation. Any motivation to get kids to do that is good.

So, Mall Madness, I forgive you for thinking you are a completely ridiculous game since I was a kid and agree that you do have some good qualities.

Now please don't send me to the arcade again!

Friday, April 23, 2010

Combinatorial Games... Art?

I'm more than willing to grab on to any internet sensation that has fleeting relevance to combinatorial games. This post is proof of that. :)

Roger Ebert, a famous film critic, has recently sounded off on his webpage of some non-movie related items. Lately, his post on how video games are not art has stirred up a lot of frustration. Naturally, anything on the Internet seems to get people's blood boiling, and I only happen to know of this because I'm addicted to a few webcomics. As it is, I'm not very concerned about whether video games are considered art today. I barely understand what is considered art in the current sense, but figure that someday someone will ask whether some new-fangled form of entertainment is as artistic as the "classic" art of video games. That just seems to be the pattern. I've read some cool articles refuting Ebert's column, mostly because I thought they would be entertaining (they were) but the points don't resonate with me all that well, because I have a hard time understanding "what is art"?

But, then, I thought: What about board games? What about combinatorial games? Can this realm be considered art?

I don't know, but here are a couple of thoughts.

Yes-side: some board games have very artistic components. I have some beautiful boards for games that light up my eyes every time I open them up. Dragon Strike came with four sweet boards for adventures in different locations which are very nice. Alternatively, Hero Quest has a less impressive board by itself, but the design allows for a large number of very different scenarios that Dragon Strike can't match. Perhaps there is art in this configurable simplicity? Also, I have seen chess sets of varying levels of awesome figures, created either with expensive materials or just fashioned to look like the Looney Tunes characters.

Counter-argument: Board games may have nice pieces, but that does not necessary qualify the game itself as a piece of "artwork".

Another Yes-side: There is real elegance in the rules of games. Some games can take a simple, small amount of rules and be something very complex and beautiful. Very hard to understand, yet able to draw appreciation and analysis from onlookers (players). We can appreciate a game such as Kayles, not because it is a comment on society, but because it can evoke emotions in us.

Counter-argument: similar reasoning can be made for anything. We can appreciate nearly anything, but not everything is art. I can appreciate the way you do your job, but that does not make it art.

No-side: combinatorial games are a realm of scientific study. This is art in the same way that Chemistry is art. No one actually plays toppling dominoes as an artistic experience, so it is not a piece of art. A game is also not designed so that the study of it is an emotional experience.

Counter-argument: I don't really have one. Someone help me out! :)

In the end, though, I expect that if video games are considered art, then so must board games. As for straight-up combinatorial games, I'm not sure. Where do we draw the line between the idea and the implementation as far as artwork goes?

Tuesday, April 20, 2010

Candy Nim

On Friday, I mentioned Michael Albert's "Candy Nim" as a way to entertain yourself when you're losing a game of Nim.

The idea works as follows: you are in a losing Nim position (and the other player seems to know "the trick" to keep on winning). You decide to come up with a secondary goal: try to eat (take) as many of the remaining objects (pieces of candy) as possible. Michael proves that in this case, there is a way to eat at least half of the remaining objects!

Consider the case where there are two piles of objects, both with the same number (they have to be the same, otherwise you're not in a losing position). In this case, no matter how many you eat, the other player will take the same amount, and you'll eat exactly half the candy.

In some cases, there is a better "strategy". For example, if there are three piles, and one of them has size 1, then the other two must look like 2k and 2k + 1 for some k. Now, there is a way to net a 3-to-1 advantage in this situation: take 3 from the pile with 2k+1.

Then our piles go from: 1, 2k, 2k+1 to: 1, 2k, 2k-2. To counter this move, and not lose, the opposing player will take 1 from the second pile. The situation is now: 1, 2k-1, 2k-2 = 1, 2(k-1) + 1, 2(k-1). So long as k-1 isn't 0, lather, rinse, repeat! Continuing this leads to the losing player eating 3k+1 candies, while the winning player eats k+1 candies over the course of the game.

Are there any other good entertainment "games" you can play as a losing player?

Friday, April 16, 2010

Playing While Losing and Collecting Candy

Sometimes gamesters play games even when they are in a losing position. This means that even though we know there is no winning strategy from the current game state, they'll keep playing.

This happens for a lot of reasons. Often, this occurs because the winning strategy for the other player is not known (even though it is known that it exists). For example, the first player to move in Chomp is the winning player, though what that first move should be is unknown. Thus, if someone challenges me to a game of Chomp, but they are going first, I don't immediately quit the game. They will make their first move, and then who knows whether I'm still in a losing position?

Other times, even when a winning strategy is known, there is a chance it is not known by the player in the winning position. You might be in a losing position this turn, but if you make a sneaky enough move, perhaps they won't be able to do it again next turn...

There is the chance also that you play purposefully from a losing position, hoping your opponent will learn how to maintain their "winningness". If I am a parent someday, I bet I will do this more often!

As yet another option, it might just be that your opponent will take it badly if you quit on the game, even though it's clear who will win. You'd like to quit, but they want you to play the whole thing out. This is likely very instructive for them, so you should probably go ahead with it :)

Michael Albert found a way for the losing player to entertain themselves in (some of) these situations while playing the game Nim. The idea is to consider all the objects as pieces of candy, and by removing them from a pile, you get to eat the delicious candy! Naturally, this is not as rewarding as winning, but if you're going to lose, you might as well acquire as much of the candy as you can! He found interesting properties of the game when playing with three piles (most notably that it's always best to take candy from the biggest pile). This implies that the winning player will always make the best responding winning move.

I'll talk some more about "Candy Nim" next week. Have a great weekend!

Tuesday, April 13, 2010

Teaching with a Game

Someday I will be asked to teach a class about logic gates. At that point, I will (want to) use bOOleO as a teaching tool.

bOOleO is a card game where two players race to be the first to complete a logic "pyramid". Each card is either an AND, OR or XOR gate and an output of 0 (False) or 1 (True). This means that a player can't use an OR-1 card on two 0-inputs.

The base row of cards are just randomly either 0 or 1, and a player has to build a triangle down from this until they have just one card at the end.

I've only played with a few students, but they already have made excellent comments I won't be able to ignore when it is my turn to teach. First, the deck comes with two "cheet sheat" cards that list all the input-output combinations for each gate. This is a useful aid for those new to boolean logic. After a couple bOOleO games, however, these reference cards are no longer necessary.

Considering strategies leads to a stronger understanding of logic gates. One facet of the game are NOT cards, which invert one of the base row of cards, switching a 0 to a 1 and vice versa. Any gate cards that then have incorrect outputs for their inputs are discarded. Some gates are more susceptible to this than others. OR-0, AND-1 and both XOR cards will always be destroyed when their input changes. For OR-0 and AND-1, this occurs because they have only one working input combination. XOR, on the other hand, changes values with a change in any input.

AND-0 and OR-1 are a bit more robust: one in four input combinations are safe! Because of this, I usually find these cards to be more valuable than the other gates. Between the two of them, I favor the OR-1 cards, since a player has more flexibility with more 1s in their circuit.

Why is that? Well, since there are no NOR or NAND cards (NOT cards are not used as gates, but as the inverters as described above) there is no way to have a gate take two 0-inputs and output a 1, though XOR-0 will do the opposite.

Most importantly, this is an involved game, but with enough randomness to prevent it from being too serious. Interacting this way with logic gates can really help to bring the point home.

If I used this in class, though, I might try to create some more complex boards for game play that more closely resembles circuitry.

What other games are great as examples for teaching "non-game" subjects?

Friday, April 9, 2010

No Post Today

I forgot to mention yesterday, but I am at a workshop all day today and won't be able to write a usual post.

Also, you are interested in me covering a topic soon, let me know and I'll do my best to talk about it!

Tuesday, April 6, 2010

Tsuro has dual-locality, why doesn't Geography?

I've mentioned before that I think Tsuro is a very elegant game. If I get a group of thoughtful people together to play, they will often notice some of the great properties that aren't immediately obvious. No cycles (for player tracks) and no overlapping paths make sense after some consideration, but it is still often asked as a question.

A quick synopsis of the game is that pieces move along paths printed on tiles. On your turn, you play a new tile on an untiled place on the board to move your piece further along. These tiles each have a different matching of paths connecting two sides. That place of a tile could move other pieces, also. A player loses when they either collide with another piece or follow a path off the board.

Aside from the parts mentioned up top, there are other cool aspects of Tsuro. One of these is the fact that it looks a lot like Geography.

Geography? How could that be? Geography is impartial! Tsuro is very partisan: each player has their own hand of tiles and their own piece.

Well, first of all, in order to make it more "combinatorial gamey" we have to consider removing the hands anyways to eliminate hidden information. (Perhaps instead there is just a communal pile everyone selects from.)

Now, what if instead of having two pieces, both players shared the same piece. Now you have to make sure you don't lead the piece off the board on your turn. This now looks a lot like geography, where players traverse a directed graph and must avoid crashing into an already-visited vertex.

There are plenty games that enforce a sort of locality---you have to play near the last play. Tsuro has a cool property where each player has their own sense of locality. They play not from the last play, but from their last play (unless they get moved).

What if the same were true in Geography? What if each player had their own piece moving through the directed graph, but you lose if you visit a vertex previously visited by either player? How difficult is it to play this version well?

In a very unrelated note, Molly points out this podcast, which contains a cool mention (near the end) of a board game enthusiast who uses analogical modelling to choose whether or not to buy a new board game. Ha!

Friday, April 2, 2010

Game Description: Hanoi Stick-up

I have to get a set of Towers of Hanoi now!

Some of my CS professors had wooden Towers of Hanoi in their offices. These are used to demonstrate a cool process (usually described recursively) to move a stack of different-sized discs from one place to another. The stack starts off with the largest disc on the bottom, with successively smaller discs all the way up. At each step of the moving process, no discs are allowed to be placed on discs smaller than themselves. While moving the stack from one location to the next, you are only allowed to use one other place to stack, besides the start and ending places.

No matter how high the stack of discs begins, you are always able to move the discs, one at a time, to shift the stack at the destination.

Cool problems like this are often the best inspiration for new combinatorial games, and the Towers of Hanoi are no different! The result is the game Hanoi Stick-up. (Does anyone know who created this game?)

In this game, all discs start off on their own separate stack. A move consists of moving one stack on top of another; the whole thing, not just one disc. The bottom disc on the stack being moved must still be placed on top of a larger disc. Under normal play, you lose the game if you cannot move a stack on top of another.

Hanoi Stick-up is an impartial game, since both players can move whichever discs they like. This is a game with very simple rules, but it misses one of the main concepts of the Towers by allowing players to move more than one disc in a turn. However, trying to enforce doesn't lead to an interesting game; both players will just move the same disc back and forth without going anywhere. If you're going to lose the game, you can instead just undo the last move. In Hanoi Stick-up, you have to combine two stacks together each turn. Perhaps a partisan game with a coloring of the discs could lead to something more "traditional".

On a less relevant, but cool note, Andy posted about WittCon from this past weekend! Bonus!