Game Description: Flume

A few weeks ago, Mark Steere emailed me with his latest game, Flume. If you are not familiar with Mark, he has designed a large quantity of combinatorial games, some of which take place on extremely creative boards!

Flume is played by placing colored stones on the intersections of a 6 x 6 grid (rules with pictures are available in this pdf). Before play starts, all intersections along the edge of the board are already covered by green stones that belong to neither player. The two players, Blue and Red take turns placing stones on the board. When you place a stone, however, you must look at the number of stones (of any color: green, blue or red) adjacent to your play. (Two stones can be adjacent only on the four cardinal directions, not on diagonals.)

This is where the game starts to look like Dots-and-Boxes: if your play is adjacent to three or four other stones, you get another play.

The game ends when the board is full; the winning player is the one who has played more stones. Since there are a total of 25 plays (5x5 intersections inside the green stones) there will never be a tie.

Mark gives some good examples in his rules explanation that show some cases where a player may not want to gobble up all the bonus-moves available that turn.

I got to play Flume here with a student last week and then again this week. Just yesterday, while playing, something exciting happened: the student realized she could use symmetric play to win when going first! The first move is to play on the center intersection. From then on, to counter the opponents' move, just make the same move reflected through that center point.

So, I would take the lower-right corner, and she would take the upper-left. I would play on the intersection just to the left of the center, and she would play just to the right.

This pattern worked well until I made an enticing move that opened up a free play. What is the best strategy here? Should she just play with the reflecting move? No, then I will take both of the bonus positions that turn, as well as any extra bonus moves created by them. After a little thinking, we realized the best solution: take the free space(s) and then make the same enticing move your opponent just made (unless you just ended the game by taking all the remaining positions).

Your opponent will gain (at most) the same number of "points" you just did. You will still have the upper hand since you went first and played the initial stone in the middle.

Of course, if the opponent decides not to take those bonus moves, then you can just claim them on your next turn.

The "tricky" part of this method (and the proof that it works) is putting your opponent in the same nice position they just put you in, and then showing that they won't be able to use those extra spaces to somehow jump ahead on their turn.

Naturally, this only works for play from the starting position and does not say anything about playing the game from an arbitrary position. There may be connections to Dots-and-Boxes there, but I don't know enough about the theory behind that game!

Funny thing...

Lately, Tuesdays have been "game lunch" here in the department. I head down to the Math/CS lounge and bring my lunch and a few different games in mind. We have one of those 7-game sets that has checkers, chess, etc, and a set of dominoes, which usually covers us for a lot of combinatorial games. We've also played some Gloom and other games the students are interested in.

Today a student told me she looks forward to this a lot. She explained that she feels like she's doing something really intelligent while playing. The games motivate the challenge of playing well, which is certainly a daunting task! Predicting, calculating, being precise... all must be employed.

Even games which use some randomness and might not be as tough (lately we've been playing Gloom, which is excellent) require some planning ahead and strategy.

The best part is that this apparently gets their minds running for the day and helps motivate them on their other work!

... at least, that's what they told me...

Game Description: Domineering

First, thanks to people who suggested I add rows to the game table page. Please suggest more games to add for rows!

In the past two weeks, I have gotten more chances to play games with Wittenberg students over lunch. This turns out to be one of the best ways to try out new games! Exploring them with other newbies is very helpful and the right attitude can add a non-competitive spin to the discovery of good strategies. Unfortunately, since these students have not been studying combinatorial games, I usually wind up with an unfair advantage. Not always, though. This is the best: getting beaten by missing a great strategy that gets pointed out by someone else! Seeing the realization of that great move in a student as they make it is wonderful!

Unfortunately, next I have to admit that I had never played Domineering before. Domineering is the guiding example for many basic combinatorial game aspects, yet I had never pulled out the dominoes and checkerboard before with another player. Actually, I don't even own dominoes; I had to borrow the set from our Math lounge.

Domineering is a partisan game between two players where each turn a domino is placed over two adjacent (share a side, not a corner) squares. The Left player must place dominoes vertically while Right must place them horizontally. You may not place dominoes on squares already occupied by a domino. Assuming normal play, the first player who cannot place a domino loses.

Domineering is a wonderful example for combinatorial games and game positions. It is used as the first guiding example in Lessons in Play, mostly because simple game values can be easily found. Good moves are sometimes very easy to spot, even long before the game ends. Perhaps most important, as the game continues, it clearly decomposes into smaller subgames that add together.

Still, while playing with students lately, one of them quickly became bored. "I wish we could play the pieces either way," she said (or something like that).

"That game's called Cram," I said. "I've also never played that one. Wanna give it a go?"

We played Cram, then quickly analyzed end game scenarios. We played it a bunch more times, allowing backtracking near the end and generally figuring out how a lot of the game worked. The next time, we skipped the Domineering and went straight to Cram.

This contradicted my assumption that many people prefer proper partisan games over impartial games. Is there a general consensus between these two games?

WittCon 2010!

At Wittenberg we have a very active gaming group, known as the Role-Playing Guild. This is a bit misleading, since they also have a weekly board game night that is well-attended. I've learned a bunch of new games there, and also gotten to show off some of my own!

When I arrived, I quickly got in touch with the group, and they mentioned they had tried to get integrate trading card games into the club. I have some experience in running limited Magic events, but I haven't kept to my every-other-week regimen that ran throughout graduate school.

However, each March, the guild hosts WittCon, and they have asked me to run a Magic draft this year. The con takes place March 27, so if you are near Springfield, OH that weekend, be sure to come by!

Adding more players

I love to play games with more than just one other player. Getting a bunch of people around a board or table to do something interactive is excellent.

I really enjoy playing Magic: The Gathering, and when the rules were generalized to encompass more than two players, I was thrilled. Unfortunately, standard rules for just playing a big multi-player game can be a bit strange. Luckily, I've become familiar with fitting formats for 3, 4, 5 and 6 players.

Some combinatorial games generalize very well in terms of how to make a turn. All impartial games just act the same as they do normally. The rule for winning/losing might be a bit different: does only the first player who can't move lose and everyone else win? Or does the player that made the last move win and everyone else loses? Or do some of those other players get a "draw"?

In any of these cases, the value of the games change as players are added. One can no longer check whether the nimber of an impartial game equals 0, as the parity has been altered! I don't know anything about the difficulty of these games, except that it seems immediately daunting. I can only assume that adding players normally makes things more difficult!

Thus I'm curious: are there any games that suddenly become easy (or trivial!) with more than two players?

An additional note: thanks to those who prompted me to add rows to the game table. I will continue to add entries/info as I think of it or as I am harassed :) We had a snow day here at Wittenberg, and that helped me catch up with work a bit.

Table of Known Game Facts

Recently, I asked whether there was some online table of known facts about algorithmic combinatorial game theory. I didn't get any answers, so I decided to start something of my own.

This site contains a table of game properties. At the time of this there are only 5 games listed, and I haven't yet started to add links to back up the cells. I plan to keep adding to this as I can. Please let me know if you can help me fill in cells. Also, perhaps there should be additional columns I should include! I came up with these off the top of my head, but it might be that more are appropriate.

Naturally, if you would like to see a specific game added, just let me know either via comments or emails!

Game Description: Phutball

Michael Albert responded to my last post by mentioning the game Phutball as a classic result in exactly what I was looking for. Luckily, it is Friday and I haven't done a "game description" post in a while. Here goes!

Phutball is short for Philosopher's Football and is played on the intersections of a 19 x 15 grid (though other sizes are often used). On either end of the long side are the "end zones". There is one ball on the field and any number of "men" (I'll call them athletes). All of these objects reside on the intersections of the grid (see the wikipedia page for nice pictures). The goal of each player is to end a turn with the ball inside the opponents' end zone.

A turn consists of either creating a new athlete in any unoccupied intersection or moving the ball. The ball is moved by "jumping" one or more athletes, removing those athletes, then moving the ball again if the current player wishes. Each jump consists of moving the ball in any of the 8 cardinal directions as long as there is one or more neighboring athlete in that direction (diagonal intersections are considered adjacent). The ball is moved to the next open space in that direction (it may not be moved if no adjacent spaces are available) and the athletes that were jumped are then removed.

I have never played this game, so I have no idea how game play goes. Luckily, I have found some people here to play games with over lunch and this week have played my first ever games of Domineering and Cram! I think next week will consist of some Phutballing!

It relates to Tuesday's post because it is a game where figuring out whether you can win this turn is NP-complete. Furthermore, the game has been shown to be PSPACE-hard to determine which player is winning.

I am looking forward to giving this game a try!

End States: Hardness without Randomness

My last post was about trying to show some games were (NP) hard to play even near the end. I have a few motivations for thinking this way, and some tie more into the basis of combinatorial games than others.

In the post I mentioned the game Cave Troll, which is a cool fantasy-setting board game. Each player controls a cohort of adventurers and monsters which meander around a cave, sometimes avoiding each other and sometimes ganging up on characters of other players. Every so often (determined randomly) the board is "scored" and players gain points based on the value of each room they have more adventurers in than those of other players.

The randomness comes from card drawing. Each player has their own small deck of cards and when they draw the last card, the game ends after after the card is played. Some cards are marked and after enough of them are played, the board is scored. Other than this, there are no sources of randomness in the game. Players can only take actions on their own turns. Thus if a player has only one card left in their deck, they know what that card is and can determine whether any sequence of actions on their turn will win the game. (Actions include moving characters one space or using their abilities, as well as drawing and playing one card. A player is limited to a certain number of actions per turn.) Without the randomness, this situation acts a lot more as a combinatorial game.

Thus, if the current player has only one card in their deck, we can ask the question: "Do you have a winning strategy this turn?" The hope is that this is NP-hard. (It would explain why my last turns always take too long!)

There is another reason to investigate end states instead of general states: I cannot think of another way to approach other analysis! Our game Dictator (sorry, no link yet!) is like this. This game simulates investigation of a set of ballots, until a dictator is found (or IIA is violated) as per Arrow's Theorem. Instead of trying to show hardness at any turn, I hope to show that it is hard to come up with a proof enabling you to win that turn.

In any case, there are a variety of games where the last few turns are meaningless, but some others where everything can change in the last few decisions! Which actual properties make these games different?