Combinatorial Game Theory

Clearly Combinatorializing Connection Games: Un-all-smalling

2012-01-31T17:01:00.000-08:00

Game sums are at the heart of Combinatorial Game Theory. If you give me two different rulesets, a third exists that is the sum of those two and you don't have to specify anything new.

Unfortunately, some games add poorly or uninterestingly. Hex may be a good example, because the game is over when a path is created. The standard Hex rules cause the game to be all-small: if one player has a move option, then the other also does. As I mentioned before (late in the post) it's perhaps more exciting to redefine the game to make it more "sum-friendly" (very arguable). Instead of ending the game when one player has created a path, instead allow the path-creating player to keep painting uncolored hexagons. Thus, the rule is that you cannot play if the opposing color has formed a path. Now the game is no longer all-small.

Paul Ottaway and I had a conversation a year ago where we both argued for this change. I don't know how to change the rules to a 65-year old game, however. Luckily, when played atomically (not part of a sum), the new rules do not change the game play. Make the connecting path and you win.

This works for any connection game that I know of (Y, Twixt, etc). There are many inherently all-small games that cannot accommodate such a change, however. Clobber and MadRooks are games that are all-small and for which I don't see a method to fix that that doesn't change the original game.

The inherent problem here is that prior to combinatorial game theory, games were defined by explaining the conditions for one player to win the game. Under the normal play convention, that's not entirely relevant. Instead, the game author need only describe what the legal plays are for each player from any position. It's a subtle difference that is only important in the context of game sums.

Game Description: Connect Score

2012-01-27T06:33:00.000-08:00

Many combinatorial games that are studied in an academic setting have very simple rules. Just because a game has a multitude of rules does not remove it from the combinatorial setting, however. For example, Rick Nordal sent me a link to his game, Connect Score.

This game uses printable boards of chess pieces, each given a number. The game proceeds as a mix of Dots and Boxes and Chess. Each turn, a player first chooses to add one line which is the boundary of one or two boxes, just as in Dots and Boxes. Unlike Dots and Boxes, you do not earn additional turns by closing off boxes. Instead, the chess piece in that box becomes activated. (All pieces begin inactive.)

In the second phase of each turn, the player gets to use all activated pieces and have them shoot at each other. The colors do not matter; each player can shoot with any of the active pieces. Any piece which gets shot is then removed from the game, and the current player earns the number of points associated with the "killed" piece. Those pieces can then no longer shoot. Pieces shoot in any order the current player wishes, and can shoot multiple times per turn. They do have to shoot in order, so two pieces cannot shoot each other in the same turn. At the end of any turn after the first piece has been activated, there will still be at least one active piece.

Each Chess piece shoots in a different manner, so they can't (all) target each space on the board. The rules for each are described on the website; I will not list them here as they are too numerous. Most of the pieces shoot similar to the way they can move in Chess, so it's not terribly difficult to remember if you've played some Chess.

After the shooting phase, the current player's turn is over and the game proceeds to the next player.

When all pieces are either active (and can't shoot each other) or removed, the game is over and the player with the highest point total wins.

Rick has produced a bunch of starting boards available on his site. Ernie and I found it fun to both play with a bunch of different pieces and one where each piece was a rook.

If you wanted to play this game not on paper, you could presumably use actual chess pieces, each on a stack of coins to keep track of how many points they're worth, and dominoes to denote the edges drawn. Sounds like it might be more epic, but also harder to wrap your head around! :)

Partiality Continues to be Confusing, part 2

2012-01-25T11:58:00.001-08:00

Common Trip-Ups:

Confusing Impartiality with Symmetry. Symmetric positions seem impartial because each of the moves for one player has an opposite in the set of moves for the other player. Those opposing positions have opposite values, however. While it is true that all impartial games are symmetric, the converse does not hold.

Separate Scores. Many games are nearly impartial, except the players keep track of different scores. The game board (not including the scores) may be changeable in the exact same ways by both players, except that then the players get different scores. 3,6,9 and Odd Scoring are good examples of this. These games are not impartial, because the scores are different.

All the positions are impartial games. { 0, *, *2, *3 | 0, * } may look impartial because all the positions are impartial positions. This is not impartial, however, because the players don't have all the same move options.

The Position is equivalent to an impartial game or 0. A game equivalent to * is not necessarily impartial. The game could be: { 0 | 0, *2 }, which is equivalent to * but does not have the same options for both players. Equivalence does not preserve impartiality. (Perhaps not everyone agrees with this!)

What are some other common problems I didn't list here?

Partiality Continues to be Confusing

2012-01-17T04:56:00.000-08:00

Happy new semester & year! Let's dive right in!

I thought I had done a much better job explaining the difference between impartial and strictly partisan games last semester, but again far too many of my students claimed that their game was impartial during their presentations.

A few students presented symmetric games, and claimed they were impartial. A few made mistakes on games that were impartial except that each player had a separate score. These games, such as 3,6,9 and Odd Scoring, are not impartial because your turn affects your own score but does not affect your opponent's. Thus, the same moves are not allowed for both players.

For example, given the following Odd Scoring state: (parity of scores is given instead of actual numbers)

Left: Odd Right: Even
___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ _X_ ___ ...

One legal move for Left is to slide the marker one spot:

Left: Even Right: Even
___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ _X_ ___ ___ ...

Right does not have that move as one of its options. It can still slide the marker, but then the scores will both be odd instead of even. Thus, Odd Scoring is not impartial.

Last semester, I made a distinction to the class about impartial positions and impartial rulesets, defining each separately. A position is impartial if, recursively, all it's positions are impartial and if the set of Left positions is the SAME SET as the set of Right positions. (Not whether they are equivalent.) A ruleset is impartial if all positions available in that ruleset are impartial.

Before defining these, I defined symmetric positions as those equivalent to their opposite (G = -G means G is symmetric). I think this helped, because many students knew that their games were symmetric, but not impartial. This was a change from the previous year when most students claimed impartiality.

Perhaps it would be better next time to list common misconceptions about determining partiality.

Just a little Gamester humor.

2011-12-13T10:17:00.001-08:00

Drew this on the board during the final exam for my freshman CGT seminar. :)

NP-complete games?

2011-11-30T17:07:00.000-08:00

Are there any "balanced" games that are known to be NP-complete? I know that some are NP-hard (Clobber, Col, Graph NoGo) but I don't know of any that are NP-complete...

By balanced, I mean games that have symmetric starting positions (G = -G).

Are there any like this that don't require a hardness of choosing an appropriate move?

Extending a Pause

2011-11-29T15:43:00.000-08:00

First it was Supercomputing, then Thanksgiving. Now that I've returned, the end-of-semester crush has forced blog updates way down in the priority queue.

If I don't get anything else out this semester, I will return with the New Year. Happy Holidays!

Game Description: Battle Sudoku

2011-11-11T12:57:00.000-08:00

One thing I've slowly been chewing on this year is a two-player Sudoku game. The rules are very simple: each turn, you fill in a box with a number not yet in that row, column or sub-square (quadrant in the 4 x 4 case). As with normal play, if you can't move, you lose!

In January, I played with a bunch of games starting with an empty board, but realized there was a simple symmetry strategy for the second player. We brainstormed some potential starting boards to fix things, but more complicated symmetry strategies arose.

After returning to Wittenberg, Noam Elkies and I corresponded, finally working out the current starting board. All the flaws we'd seen were fixed.

Here is the starting board:

My plan was to bring the game to Integers to play with people. Beforehand, I tested it out on my WittSem class, and it proved challenging. My student Patrick also took interest and showed a pseudo-symmetry strategy I was afraid of could be broken! Awesome! (I still don't recall how he does it!)

Here is a .pdf of a sheet of games! :) Enjoy!

Next week, I will be in Seattle for Supercomputing for most of the week, so there may not be regular posts.

Somewhat Random Musings

2011-11-08T13:02:00.001-08:00

Yes, I didn't post at all last week. I am still very much catching up on things I missed while at Integers. Next week I will be at Supercomputing and will likely miss another post or both. I don't often have the desire to pause the teaching part of the semester to get research/blogging done, but this is turning out to be one of those semesters. Mostly, I want to make sure I write good posts about the game talks at Integers (or what I understood of them). I hope I can find extra time to spend on them, but it's more likely that they'll come out a bit less-than-perfect. Hopefully some of them are readers and can comment on all the errors

While at Integers, I spent a lot of time struggling with NoGo, only to run into problems I encountered at BIRS in January. While there, I found that NoGo on a graph is NP-hard, but was neither able to show that Graph NoGo was PSPACE-complete, nor show any hardness for standard NoGo (on a grid). The same thing happened last month: no new progress. So I tried flipping it around and started looking for an efficient algorithm for NoGo. Either Neil McKay or Alex Fink (I think it was Neil) asked me about it, and I told him what I was doing. He was surprised I had given up on computational hardness so quickly. His comment made sense: I have more experience finding hardness results than showing efficient algorithms for problems (though I would argue that hardness reductions ARE efficient algorithms). Research-wise, you strive for results! So, you should spend your time conquering problems you're good at. Instead, I was trying something a bit different.

Luckily my job is far more focused on teaching than research, so the pressure to publish is less intense. It's very nice to know I can try a completely different tactic if I get frustrated with a problem!

... not that I had any luck with this!

On a related note, student presentations have started in my games class! One question that came up is: What does it mean for a game to be solved? I answered that there's an easy way to evaluate the game without drawing out all of the game tree. I hope that's a good enough answer. For myself, it means there is an efficient algorithm to solve the problem. I generally consider a completeness result to be "solving" the game, though perhaps it's the opposite: the game (probably) cannot be solved!

Integers Liveblogging: Friday

2011-10-28T11:58:00.001-07:00

Some awesome quotes from today:

"Actually, I can say I played NoGo; I don't play Go!" -Aviezri Fraenkel

"'Every other weekend'? Other from what? What is the complement?" -Rebecca. ('Every other' is apparently not colloquial in Canada.)

"...and I am guilty of some of this research." -Florian Luca during his talk on Balancing Fibonacci Numbers. He went on to describe a problem as a mathematician trying to solve a system to find the street address for a party. :)

Last night, we had a little NoGo tourney between Canada, the US and Europe. Canada won, 5-4, but there may be a rematch tonight of sorts!

Integers liveblogging: Thursday

2011-10-27T20:04:00.001-07:00

Today a lot happened. I talked and I listened to lots of games talks, many of which will become their own posts in the future. Instead, I'll quickly mention some highlights thus far.

Rebecca confused me yesterday by saying "in P" which I automatically translated as "efficiently solvable" instead of "in Zero". I had just met her, so I asked excitedly if she was in computer science. She said this misconception is even more dangerous because she is dealing with misere games, and need to consider both outcome classes. Those in Fuzzy when playing misere, but in Zero under normal play are in N-,P+, pronounced "NP" (which computational complexity theorists use for another well-studied complexity class). Dangerous!

I've also seen a great bunch of non-games talks, mostly number theory, which I've understood a bit of. Particularly, Carl Pomerance gave a talk I understood most of about product free subsets of the Naturals (if x and y are in S, then x*y is not in S... usually x*y (mod p)). Neil Hindman gave an impressive talk, mostly because I don't think he looked at any notes and covered a lot of complex stuff using only a whiteboard! I also found out yesterday that Beatty sequences/ratios were used to help discover quasicrystals, something which had a lot to do with this year's Nobel Prize! Wow!

I've mostly had a blast meeting people and playing games. While playing FLex with Marla yesterday, she commented, "This is all very important!" Everything I explained about what I was thinking was quickly absorbed by her and Rebecca. Awesome!

Meeting people---especially over games---is great! I played some impartial games with Yuval Tanny and Shira Giat. At one point I made a winning move, but was afraid I hadn't gotten the parity correct. Neil put me to ease, saying, "Yes, you counted to two correctly." That's about as high as I feel I can count these days.

Yuval and Shira are clearly awesome; this seems to be the norm for gamesters! There's a lot of energy in the group---all positive---especially from Jess Enright, who gave an awesome talk today about set representation games. Here is a picture of her realizing she won a game with Marla during the talk.

I feel like a bit of a reporter, trying to keep up with everything, but it's very helpful to help me stay on point in the talks. Seriously, they were great and I can't wait to get some of those posts up.

I will try to get a post up tomorrow before the evening, but if not, I'll put in my final fake-liveblog next week. I'm leaving on Saturday morning, so I won't be around for the last day of the conference, sadly.

Integers Liveblog: Wednesday

2011-10-26T20:13:00.001-07:00

The first day of Integers has yielded many excellent number theory and combinatorics talks... which I didn't follow very well. After lunch, I spent much of the time playing FLex and Adjex with Alex Fink, Larry Rolen, Rebecca Milley and Marla Slusky, all of whom I just met today!

During lunch, Patrick played NoGo against Richard Nowakowski, winning two of three games! Afterwards, Richard said, "it's clear the american strategy is different from the canadian." Apparently in the states we play aggressively! ;)

With nine minutes left to go before the afternoon talks, Richard looked at Patrick and declared, "okay, one quick one!" Later, he explained, "there is no such thing as the last game."

Awesome!

The Difficulty of Making a Move in International Draughts

2011-10-25T06:13:00.000-07:00

As I begin the trip down to the University of West Georgia for Integers, I want to be sure to report on another awesome thing I saw in Banff back in January.

For most games I'm interested in, the rules are simple. Deciding whether one move is legal is usually an easy task. Usually, it's even easy to list all the moves. (Some games, such as Phutball, may have an exponential number of moves, so this task may not be considered "easy".) The challenge usually arises in finding the best move, not just one that works.

This is not always the case for International Draughts. For my American comrades, Draughts is the word the rest of the world uses for variations of the game Checkers. International Draughts is a variant played on a 10x10 board that is one of many "pub games" popular in Europe. The game is different from "standard" draughts in two big ways:

Regular pieces may jump other pieces forward or backward.
Crowned (Kinged) pieces can move as many spaces in one direction as desired, even after jumping another piece.
A turn must include capture of as many opponents' pieces as possible.

This last rule is extremely interesting! Not only must your turn consist of a capture (jumping a piece) if possible, it must capture as many pieces as it can. If you watch the animation on the wikipedia page, it becomes clear that once you have a crowned piece, this maximizing move is not always trivial to find.

In fact, this question was posed last year as a theoretical computer science question: Is it NP-hard to find a legal move? Bob Hearn rose to the challenge and showed that it is, in fact, an NP-hard question. Bob presented this result at BIRS. I've never seen a game where it's computationally difficult to figure out whether you made a legal move!

How is this policy enforced in the "real world" of international draughts?

Nimbers in Konane

2011-10-21T07:56:00.000-07:00

I saw a lot of awesome talks at the BIRS workshop in January that I still want to report about. One of these was an awesome talk by Carlos dos Santos that really struck me as a computer scientist. It used a real reduction-like strategy to prove that for any k, *k can be written as a Konane position! A cool result with a cool proof!

Gamesters are interested in which game values exist for different rulesets. Elwyn Berlekamp asked, "What is the habitat of *2?" meaning, which rulesets have a position equal to *2. For Domineering, it was quite complicated to find a *2 position!

Carlos dos Santos does infinitely better with Konane, finding an algorithm to construct a board of value *k for any natural number k. The paper is here. The algorithm is elegant and recursive, and each resulting position has a very clear focal point where one of two or three pieces will be able to make the first move. Naturally, the *4 Konane board is much more complex than the *4 Nim board, but the difficulty is showing that for each successive power of 2, that nimber can be generated. Indeed, I assumed *1, *2, and *3 could be created, but *4 would require a 3-dimensional board.

Instead, they all exist, and the result is something I wish I could ask my algorithms class to learn!

Presenting Neighboring Nim to Undergrads

2011-10-14T05:37:00.000-07:00

I replaced getting a post ready for Tuesday with preparing a talk for this past Monday. I spoke at our department colloquium about Neighboring Nim, describing the reduction from (Vertex) Geography. Two excellent things happened.

First, I had a great audience. While playing Neighboring Nim against them, they were very energetic to make good plays against me. Will, a senior student of mine, immediately took on the role of surveyor, collecting move nominations from the crowd, then calling for a vote. The discussions were loud and boisterous. At one point, I made a very fast response to one of the audience's moves, using the Quick and Confident method. Unfortunately, I moved to an N position, with two P options. The audience quickly picked the board apart (it was by no means trivial) and found the two winning moves. The problem was that, individually, they didn't see the viability of the other move. So there were two groups arguing vehemently for two separate perfect moves. The attitude nearly boiled over. Luckily, the audience finally agreed and they made one of the moves. It was very exciting to speak to such a charged group!

Second, I changed the order of my talk around regarding the proof of computational complexity. Usually I claim that a game is hard for some complexity class, explain what that means, then show the reduction. Talking about complexity classes to a general undergraduate audience is a bit of a speed bump, and often shakes people out of the rest of the talk, meaning they don't follow the steps of the reduction. This time, I just said that the two games were related, then explained the reduction. This kept the crowd interested, because it's a description of positions in a game they just learned how to play. At the end of the talk, I spoke briefly about the implications of the transformation: the PSPACE-hardness of Geography implies the PSPACE-hardness of Neighboring Nim. At that point, having seen the reduction in full, I hope it sank in. Although I wouldn't do this in the future when presenting to a primarily graduate-student/professor group, it seemed to work really well for people who hadn't seen computational complexity before.

The slides for the talk are here.

Next week is Fall Break at Wittenberg, so there will probably not be a post on Tuesday as I spend the time off preparing for Integers 2011 the week after. With any luck, once I'm there I'll get to post some notes each day.

Game Description: Matrix-Game-That-Needs-A-Name

2011-10-06T23:38:00.000-07:00

Games are fun and linear algebra is fun. Let's put them together! It's especially fun to try to determine whether a matrix is invertible. Here's a game that revolves around invertibility (it still needs a name).

The game begins with an invertible matrix of non-negative integers. Each turn ends with a player reducing one of the entries of the matrix, so that it is still a non-negative integer. If the resulting matrix is non-invertible, that is a losing move. Depending on how cutthroat you want to play, it might be up to the other player to notice you created a non-invertible matrix at the beginning of their turn.

I've played with my matrix algorithms class a few time|s this semester, using this as the starting position:

| 1 2 |
| 3 4 |

This position is in Fuzzy. What's the winning move?

Game Tree Woes

2011-10-04T07:58:00.000-07:00

Getting students to write proofs is an interesting pedagogical challenge. Which class in a math sequence should start requiring formal proofs? What does formal mean?

Luckily, for CGT this has a simple solution: the game tree. Want to prove something about a specific position? Just draw out the game tree and label the options appropriately. Students should learn this as soon as possible; I broke the news to my freshmen class right away.

Bad news: I'm expecting rigorous proofs in this class.

Good news: these can be a proof by picture.

Unfortunately, I didn't do a great job teaching the basic requirements. We had problems with:

* Arrows to left/right options of a position. These were sometimes nearly vertical so it was impossible to discern whether they were for right or left arrows. Other times they pointed up, which is often very difficult to read.

* Not drawing all the options. We hadn't learned about dominated options yet, so all options should have been listed.

I think that the next time I teach this sort of course, I will have to be far more explicit about what makes a game tree. Also, I've done a good job this semester of using examples to motivate, but perhaps I didn't do enough examples of game trees.

Tomorrow the students have their first exam. Dangerous! I've decided to include a question where the goal is to find errors in a given game tree. I really wish I'd included these sorts of questions in the first few homeworks! We'll see how it goes.

(Oops! I inadvertently took last week off from posting. Sorry!)

Game Description: Zuniq

2011-09-23T04:09:00.000-07:00

Wow, some good games were suggested by readers two weeks ago! In addition to Nick Bentley donating Y with Shifts, Marcos Donnantuoni commented about his own impartial game, Zuniq. Ernie and I tried this out on Monday, and we immediately liked playing this! Here's how the game works:

The starting board is a grid of dots, similar to dots and boxes. Each turn, a player connects two adjacent (vertical or horizontal; not diagonal) dots, but not exactly like dots and boxes. If a new line segment closes off a region, no future turns can be made inside that region. Also, no two regions can have the same size. Thus, you can't close off a region if a region of that size already exists.

The suggested starting 8x8 board is a bit large, but we gave it a go. (Video: [7:16]) Afterwards we tried with 3x3 boards, to quickly learn that they are not very interesting. (The first player can always win by being just a little bit smart.)

The 4x4 game is definitely more interesting. (Video of lots of little games. [6:08]) After a few of these games, and later with games played against Patrick and my WittSem peer mentor, Alec, I think I can consistently win going first there. Still, my initial guess is that the game is PSPACE-complete in general.

I feel like there are lots of nice theorems that can be shown about this game. At the same time, I'm not familiar with what sort of theorems are "useful" from a CGT perspective (aside from computational complexity results).

Quiz Time!

2011-09-20T10:44:00.000-07:00

I asked my students the following questions in class. We've covered outcome classes, but are not quite at game values yet.

Let X be the Domineering position that is two empty squares tall.

Let Y be the Domineering position that is four empty squares tall.

Find a Domineering position, G, such that X + G is in P (Zero) but Y + G is in L (Positive)

That one's not too tough. Neither is the next one:

Find G such that X + G is in R (Negative) but Y + G is in P.

This one's nice:

Find G such that X + G is in N (Fuzzy) but Y + G is in L.

My first solution for this one had a composite (sum) game for G, but I've since found a non-composite solution:

Find G such that X + G is in R, but Y + G is in L.

If you know a bunch about the values of Domineering positions, I guess these are relatively simple. If not (or if you are good at forgetting), perhaps they require a bit of extra time to consider.

Shifting Connection games

2011-09-16T07:54:00.000-07:00

After last Friday's post, reader Nick Bentley suggested playing again but allowing each player to not only place a new piece, but also shift an old piece each turn. Ernie and I easily spent all of our Monday meeting trying this out. Here's one of those games. During the game, we had a lot of questions about what was legal (e.g. declining the shift, etc). Hopefully Nick can answer those for us!

This really changes the game! You can see one point where I was about to lose because I hadn't anticipated the power of the shift. Ernie was nice enough to let me go back... :-D

Nick suggested another game to play, and then another reader, Marcos, suggested his own game. I guess Ernie and I have plenty on our plate! :)

I'm really interested in playing the shift version of Hex. Or the shift version of Adjex! Is there some ruleset to combine this with an adjacency restriction?

The Joy of Teaching Games

2011-09-12T22:10:00.000-07:00

Last Wednesday was the second day we just spent playing games in class, and the first one where they had learned some of the theory (specifically, outcome classes). What a blast! I started putting up Amazons positions for them to find the outcome classes of partway through the class. They picked up on this challenge immediately, students flocking to the boards to post the class they had found, then either verifying or questioning the results of others. I had about twenty positions around the room and only a few of them remained unexplored by the end of the hour. The air is very charged, but the feeling is very positive. Students are working together to solve the problems, and this requires them to try out moves on physical boards, then confer with the people around them. Your opponent quickly becomes your best teammate as you collaborate to test all possible game tree paths. For some of the harder boards I put on the marker boards, groups had banded together to discuss their results as a bigger team. There was not an unengaged mind in the room!

As I've mentioned, this class is a first-year-experience seminar at Wittenberg (a WittSem) and has the dual purpose of helping integrate the students into college life. After teaching the math/compsci-elective version of the class last year, I thought games could make for a nice WittSem topic. I was further spurred on by David Wolfe, who told me he had once taught a freshman-introduction class all about playing Go. (I only just played my first game of Go last week, so I wasn't ready for that!)

These new students have actually been very patient. I promised them early on we would spend entire class periods playing games, and it took over two weeks of class before we covered outcome classes; giving them something to analyze while playing.

Also on the point of teaching, I happened across an old reddit post of Joshua Biedenweg's, prior to his teaching a CGT course at UCSB. Josh finished teaching his course right as I was prepping for mine over a year ago; I took some good advice from him and unfortunately ignored some better advice! (Josh, I'm using Toads and Frogs more this year! Pictoral Evidence:

)

Next on the class agenda is Game Sums, and soon it will be time for them to find actual game values! Woohoo!

Conclusion: Teaching CGT is awesome. If you have the opportunity, take it!

Messing with Y

2011-09-08T21:27:00.000-07:00

Y is a game that is very similar to Hex: players take turns claiming hexagons with the hope of connecting sides. In Y, however, the board is a triangular array of hexagons, and the goal of each player is to connect all three sides instead of just their two sides. Perhaps more surprising than the Hex Theorem is the Y Theorem: if all hexagons are colored, exactly one contiguous group of same-color hexagons touches all three sides.

This game plays similarly to hex, except that there are, like, 1.5 sub hex games going on at the same time. Ernie has taken a quick liking to this game; he's very good at beating me before I know I'm beaten! To escape this dilemma, I proposed that we give this the same treatment we gave to Hex: let's force adjacent play. We spent a bunch of time trying out different starting positions, and unfortunately it always seemed that the first player to move had a strategic advantage, even if that first play was on different ends of the board (or smack in the center, of course). This means the second player always wants to evoke the pie rule. Earlier this week, we sat down for a few games and taped them. Our first game has Ernie starting in the center. Spoiler alert: he manages to get to all sides, but the game is quite close!

In the next two games, we try instead from the middle of one of the sides. These are both great games! We are already getting a handle on how this game works.

I'm not sure, however, that I like this as much as Adjacent Hex. Of course, I've gotten more interested in FLex (Follow-the-Leader Hex) so perhaps it's time for a game of FLY!

Does anyone have a story to share about trying out an "adjacent-enforced" version of another game?

An answer to an old Nimber question

2011-09-05T22:14:00.000-07:00

Near to the start of this blog, I posed a question:

if the nimbers for a game are bounded above, does this imply that there is an efficient algorithm, or shortcut, to evaluate impartial games?

I recently realized there is strong evidence against this. It is true that any impartial ruleset where all the nimber values are either *0 or *1 is very easy to evaluate---all options from one position have the opposite value (otherwise there would be *2 states)---so all paths down the game tree have the same parity. All that's needed to create PSPACE-hard instances, however, are states with the value *2. Why is this? Well, we can change the rules for any game with higher values into an equivalently-winnable* game with maximum nimber *2. The plan here is to break down the options from a game when there are more than two. We do this by splitting up those options into separate groups, then preventing the other player from being able to make any choices.

For example, we can transform the game G = {A, B, C} into the game G' = { { { A, B } }, { { C } } }.

Here's a diagram of the game trees, with the nimbers *0, *1, and *2 respectively assigned to A, B, and C.
For positions with more than 3 options, this splitting can be done in a recursive fashion. Thus, games with any range of nimbers can be transformed into a game with maximum nimber of *2.

* game states may not have the same value, but winning strategies from one translate into winning strategies in the other.

Game Descriptions: NimG and Neighboring Nim

2011-09-02T07:46:00.000-07:00

What happens if you restrict which games can be moved on in a game sum? This seems to be the idea behind NimG, a game played on a collection of Nim Heaps embedded in a graph. There are a few variants, but each turn a player does two things:

* traverse an edge of the graph adjacent to the last move, and
* remove sticks on the nim heap embedded either into the edge traversed or one of the vertices.

In the sticks-on-edges version, players remove sticks from the edges while traversing them during the turn. Naturally, if the heap on the edge is empty, it cannot be traversed. In other words, the player who starts their turn on a vertex where all incident edges have empty nim heaps loses. Masahiko Fukuyama studied this game a bunch and more recently Lindsay Erickson has looked into instances on the complete graph.

When sticks are embedded into the vertices, a move still consists of traversing one edge to arrive at a new vertex. Upon arriving at the new vertex, a move is made on the nim heap embedded there. Gwendolyn Stockman may have been the first person to analyze this game in an REU advised by Alan Frieze and Juan Vera. This is the version that interests me: the vertices act like different heaps in a game sum, but the edges restrict which heap can be chosen each turn. In this ruleset, the complete-graph version is equivalent to standard Nim. (If each vertex is adjacent to a "self-loop", an edge connected twice to the same vertex.) In this game, you lose if all vertices adjacent to the current location contain empty nim-heaps.

In order to avoid the self-loop issue, I altered the rules slightly and set out to do some analysis. Neighboring Nim is exactly the same game as (Vertex) NimG, but a player may choose not to traverse an edge and instead remove sticks from the current vertex (again).

I have actually played this game very rarely, mostly because I can't imagine a standard starting position. Nevertheless, I helped show that the game is PSPACE-hard. I was lucky enough to present this result at BIRS in January, which was quite pleasant. The paper should appear in Games of No Chance 5. (arXiV version)

The cool thing about the computational complexity of this game is that once all vertices have maximum heaps of size 1, the game is the same as undirected vertex geography, which is solvable efficiently. In order to get PSPACE-hard instances, we needed most vertices to have a heap of size 1, with only a few having a second stick on them (less than 1 in 7 of the vertices need the extra stick)! It's very interesting that such a small rule change can result in such a big complexity change!

New School Year!

2011-08-29T21:07:00.000-07:00

A busy summer has ended, and the school year begins anew. I worked on a lot of projects over break, and since I'm only slightly modest, I'm sure I'll mention them soon. Since the workshop in Banff in January was so helpful, I'm planning to attend and speak at Integers 2011 in October. I wouldn't have known about this conference had Richard Nowakowski not mentioned the 2009 version to me two years ago.

I spent a lot of time working on an applet for Adjacent Hex, but I didn't quite finish. I hope to get that done during this semester, but can't make any promises.

This semester I'm feeling like a Math professor. I'm teaching two math courses (Discrete Math and a freshman-only games course) and our Algorithms course, which is very math heavy. This is the least programming of any semester I've had here; I don't know how to deal with that!

In addition, I have two excellent senior students doing cool projects. Will is working on an implementation of a Savage Worlds character creator, and Patrick is going to implement a Monte Carlo game tree search in Chapel. Very exciting!

There's lots to talk about. As normal, if there's something you're particularly interested in, let me know.

Next Semester: Combinatorial Games "WittSem"

2011-05-08T20:39:00.000-07:00

Another semester draws to a close. Although I missed posting last week, today will be a bonus final post for the semester. There may be a few more comments during the semester as I figure out how to upload videos that my phone thinks are too big, etc. (Patrick and Ernie had an epic FLex battle a few weeks back.)

In addition, I have a bit of research to get done this summer, so there may be some mention of that. One of my big projects is to prepare for my board games "WittSem" class next semester. This will be a first-year-college-students-only class that has the dual purpose of acting as an introduction to university. I will spend time helping to impart good study habits (do I have these?) and instill a love for games and math.

These WittSems must include a multi-disciplinary spin; in addition to the math, I will talk about cultural/historical aspects of games. To this end I can cover many geographic regions with different games, but I'm not sure what the more interesting points I should definitly cover are. Some ideas:

* Follow the evolution of Chess across Asia and Europe.

* Compare rule sets of Go, which are different by country/region.

* Perhaps the same is true of Mancala?

* Look at origins of Konane as well as taboos while playing.

This last one may have a recurring theme. The name of the class is: "How to play board games: Culture and Tactics" (or something along those lines) so I was intending to talk about what was expected socially by players during the game.

Any additional help would be most excellent! If you know something interesting about the culture of games (from anywhere!) I would love to know!

Gamesters: only Extroverts?

2011-04-29T11:40:00.000-07:00

On my trip to BIRS in January, I met a slew of awesome gamesters. Everyone was extremely friendly and I had intense conversations with many different people. Perhaps this is easy when there is a common ice-breaker: "Want to play a game?" People only turned this down when it got late; otherwise they were all eager for the challenge.

Does this mean everyone there was an extrovert? Does combinatorial game theory lend itself more towards extroverts? Will introverts find a hard time breaking into the field?

As I think back to the workshop, I don't recall a single person that came across as shy. There may have been some language barriers, perhaps, but those don't usually cause a problem if both players know the rules to a game. Of course, if you sit down and play quietly, you may never find out whether your opponent is introverted.

I'm somewhat worried that introverts may have a hard time being interested in games and CGT as a result. (There are similar reasons I worry that introverted students aren't getting all the benefits my extroverted students are.) I can see that many people might be intimidated by a class based around something so inherently competitive. Despite the fact that no grades are determined by students' actual ability to play games, I understand the completely irrational fear of not wanting to die in a video game.

Perhaps I needn't worry. Perhaps games and puzzles attract an introverted personality. It is easy to confuse introverts with shy or quiet people; the two do not always go hand in hand.

Wikipedia describes introversion as "a personality trait involving a tendency to drive one's perceptions, actions, thoughts and emotions inside, resulting in reduced interest in activity directed to the outside world." Taking the time to study and consider a game state may induce the same sort of energy as spending time alone for some introverts.

Oh dear, I'm getting into a space I know nothing about. Anyone have any thoughts on this?

Recording games!

2011-04-22T04:58:00.000-07:00

On Monday I played some great games of FLex with Ernie and about midway through the first one, I wished we had been recording our experience. We were trying to determine what a good first play looks like, and were testing out playing right smack in the middle. We played 3.5 great games (the last one is on pause in my office until next week's meeting) but took the time to really talk about moves and discuss whether each one looked like a mistake to the other person. Many times we backed up to try another game path. So far, my general feeling is that playing in the middle is a really strong opening move... so you shouldn't do it. With the Pie Rule in place, the second player can choose to take that move from you.

Since Monday, I considered getting a webcam to point at my table to record the games. Then I realized I also want sound (I have an old webcam; does it even work?) so I thought it would be nice to use my phone and upload the videos to YouTube. Unfortunately, I'm not about to hold my phone up for such a long time and I didn't find a stand online that would support it directly above a game board.

So yesterday I got a bit inventive. I brought some wire hangers into the office and spent my lunch (eating and) building this contraption.

(Images courtesy of Patrick Copeland.)

With the wire hangers and some books, I suspended my phone above the game board, then wrangled one of my students into playing a few games with me. We played three games of FLex, one is here, and the end of another is here. The tests went very well and the board is quite visible. I hope to post more videos using this in the future! Many thanks to Patrick for testing this wobbly contraption with me!

Game Description: FLex (Follow-the-Leader Hex)

2011-04-15T13:48:00.000-07:00

After talking about Weak Hex (Whex) a few months ago, I tried playing it with some comrades here at Wittenberg. As a reminder, Whex is the version of Hex where both the first and second players must play adjacent to the first player's last move, with the winning condition exactly the same as before. Argimiro Quesada showed that this game is PSPACE-complete on general graphs, without needing to describe what happens if no adjacent move is possible (the graphs in his reduction are designed so that this never happens). When I asked him what the rule should be, he came up with the rule: if you can't play adjacent, then you lose.

This is a common first response for how to deal with this situation. While designing Atropos, I first considered using this same rule: if you can't play adjacent because there are no free spaces, you lose. Luckily, my advisor didn't like this and suggested the jumping: then you can play anywhere. These jumps greatly improve the game, and are also a big part of Adjex (Adjacent Hex).

While first sitting down with some other gamesters to play Whex, we tried the lose-when-no-adjacent-moves-

are-possible option, but found that to be a little unsatisfying. It is most exciting to have the game end when one player has built a path between their sides, not beforehand! We decided to add a jump rule here too.

Handling the jumps was a bit more tricky here, however, since the players have very different roles in Whex. Both players have to move adjacent to only the first player, not to whomever happened to play last. If the first player got to make a jump, then there is little question how to continue play. But what should you do if the second player gets to make the jump? Can they play anywhere they want? If so, are there any restrictions on where the first player goes afterwards? Can they play wherever they want, or do they have to play adjacent to where the second player just moved?

We came up with a nice solution for this case: switch the roles of the players. If the second player gets to jump, then they become the player who both have to play adjacent to instead of the first player.

Here are some more descriptive rules for the game, which we call Follow-the-Leader Hex (FLex):

This game is just like Hex, except at any time one player is the Leader and one is the Follower. On your turn, if possible you must play adjacent to the hexagon painted on the Leader's last move. If none are available, you may play on any unpainted hexagons on the board, and then you become the Leader, while your opponent becomes the Follower.

This game plays very nicely. In the first two games played between myself and Ernie, I won the first one without losing the "Leader" status, then won the second one starting as the Follower, fighting to become the Leader, getting the jump (and becoming the Leader) and using that to win. Having said that, in other games, we have seen the Follower force a win, so it's not clear which role is better. In fact, lately Ernie has had great insight into this game and playing as the Follower, who appears to have some advantage! Most of the games we play nowadays are determined by which player can get a jump first.

While playing, it is vital to use the Pie Rule to avoid a very simple immediate win (see this post on Whex). Unlike regular Hex, in FLex it may be more clear whether the second player should invoke the Pie Rule to win... maybe.

The credit for this game is really due to Argimiro; FLex is a minor tweak on Whex for a situation he had not previously considered. The tweak is due to Ernie, Obed and myself.

Enjoy! I am especially interested in hearing comparisons between Adjex and FLex. Which is more fun to play?

Combinatorial Games: a first-year class

2011-04-08T12:26:00.001-07:00

The past few months I have been working on some basic planning for teaching combinatorial games as a first-year college class. At Wittenberg, we have "WittSem" courses; each incoming freshman must take one. This is finally really coming together, so I will likely teach this course in the fall. Woohoo!

This is a bit of a tricky task. Last semester my course started off as too difficult because we were using a graduate-level math text and I didn't convert the book problems enough for the students. (Not to mention I was learning some of the material only slightly before teaching it.) My next batch of students will have less math background so I'm going to have to be even more careful. I will probably rely more heavily on worksheets and less on the book problems, though Lessons in Play will continue to be an excellent reference for the class.

I still plan on devoting one day per week to playing games and discovering outcome classes/values for different states. Each week we'll try to add some new evaluation tools and I'll look for great game examples of those tools.

All in all, the class will likely look a bit like the last, but without emphasis on proofs and programming. This last bit will be replaced by some discussion of cultural aspects of games throughout history. This is definitely a bigger task than I had last semester, but I'm already looking forward to it!

Once the semester starts, I'll link to the class page. Of course, if you are an incoming Wittenberg student and have any questions about how you can be allowed to play board games during class, please ask me!

PSPACE problems versus NP problems

2011-03-29T07:17:00.000-07:00

I've recently been paying attention to community theoretical computer science forums, including on sites such as StackExchange. This question recently came up:

Are PSPACE-complete problems inherently less tractable than NP-complete problems?

Naturally, since we don't know whether PSPACE is not equal to NP, there is not yet a formal answer to this question. Intuitively, however, this becomes a question of whether it is harder to figure out which player can win a game than to find the solution to a (one-player) puzzle. The link above provides a wonderful bunch of points, but let me mention a few specifically. :)

* Ryan Williams notes that some randomized game tree solvers are very effective, and perhaps solving games isn't quite as terrifying as many might think.

* Neil de Beaudrap notes that verifying solutions is still extremely important, which we know how to do for NP-complete problems. Aaron Sterling backs this up with a great comment about humans being able to remember and describe proofs.

* Lance Fortnow points out that we know how to create average-case PSPACE-complete problems, but don't yet know how to do this for NP.

* Suresh Venkat mentions that in practice, NP-solvers are actually often very fast, and NP-completeness is not always seen as a barrier to computing.

This is one of the few questions on the forum that I have actually read multiple answers to, and it's one I feel I can read over and over. Personally, I find it hard to believe that PSPACE isn't much harder than NP, and professionally I'm partly banking on it by spending my time finding PSPACE-complete games!

No posts this week, and slimming down for a bit

2011-03-25T11:48:00.000-07:00

Sorry to my readers (all seven of you, perhaps?) but I haven't had time to post this week due to some extra responsibilities. With doctor's appointments for pre-birth checkups increasing, I can already see I will need to slim down for the rest of the semester.

Next week and for the rest of the spring, I will be posting once per week.

Have a great weekend!

Game Description: Col

2011-03-18T03:55:00.000-07:00

Col is another "classic" game that was first deeply analyzed by John H. Conway. It is a game that is inherently a graph game, but is often played on a whole piece of paper divided up into regions by drawn shapes. Each turn, a player chooses a blank region and paints it their own color. You may not choose a region that is adjacent to any other regions of the same color. (You can see some turns of the game in this very descriptive wikipedia page.) I'm sure whenever my future children are learning to draw in the lines, I'll try to coax a few games of Col out of them.

Col has an amazing, but beautiful property for evaluation: each position has a value equal to either a number or a number plus star. No Ups, Downs, *k's (for k > 1), etc. The elegant proof is based completely on the simplicity of the game value, showing that all left options are less-than-or-equal-to all right options for any game. With this Col fact, you can inductively assert that game values of the form {x | x + *} cannot exist (when x is a number). The only remaining options are numbers and numbers plus a star. Check out pages 47 and 48 of Winning Ways for all the details.

I was recently asked whether I knew the computational complexity of Col. I don't know that this analysis exists, but it could be that it is not computationally hard since the different game values have the nice property above. So far I don't know of any relationship between game value ranges and computational complexity (aside from impartial games with only values of 0 and *---those are solvable in Polynomial-Time because you never have a choice on your turn).

Topics for this semester and questions about BIRS 2011

2011-03-15T05:56:00.000-07:00

I still have plenty of topics to cover from the BIRS workshop about Combinatorial Games from January, but I want to do each of them justice. At the same time, I'm hoping to get more playable games up and running on my website. With any luck, I'll get some of this accomplished. There is a strong possibility posts will end a bit early this semester, as I'm expecting my first child the first week of May. :)

I haven't gotten to reply to the first comment here yet, so let me do that now.

What did Fan Xie said?
How strong is he?
How did the program worked? (Monte Carlo?)

Can you elaborate on that ? :)

Yes, I certainly can elaborate! I did not get to know Fan Xie terribly well, except to help badger him into joining the NoGo tournament. (He nearly did not play! Luckily, Neil McKay is a persuasive individual!) I didn't pay a great amount of attention to Fan's games, aside from his game against the winning NoGo program. This was a wonderful match, because Fan spent too much time analyzing and explaining whether the computer's moves were good or not (and he did not write that program). Instead of focusing on winning, he was answering everyone else's questions, so the computer came out ahead.

I believe all the computer programs used Monte Carlo (multiple random trial) techniques. From what I understand, they were all modified versions of UAlberta's Go-playing program FueGo. I would like to spend more time talking about this, but the most interesting thing is that these Monte Carlo programs are so easily adaptable from one game to the next. In fact, I believe much of the software is written independent of the different game rules. If you supply the rules, the simulations will run and choose a probable good move.

I am not convinced that this works well for all games, however! I'd like to know how well the algorithm plays Chess, or even Nim! (Maybe impartial games are tough...)

Yet another Table Update Post

2011-03-04T13:06:00.000-08:00

Today I'm replacing a usual post here with another big round of updates to this table of game rules.

The biggest update is adding links to websites where you can play the game listed. I didn't find links for all of them, but if you know of one (or a better one than what I have listed) please let me know so I can add it to the list! Additionally, I added links to posts labelled: "Game Description: X" where X is that game.

Since no one complained to me, I removed the column about the complexity of winning the game on that turn, replacing it with a column for general game properties.

As usual, I make some errors here, so please let me know if you find anything I need to fix!

Next week Wittenberg has spring break, so I won't have any new posts until Monday the 14th.

More Tsuro Combinatorics

2011-03-01T12:34:00.000-08:00

I keep coming back to the game Tsuro, which I've mentioned in this blog several times.

Let me describe the rules quickly. The game consists of a 6 x 6 grid of empty squares. The border of this grid has two white lines leading in to each side of a square (12 per side, so 48 lines total along the border). Players begin by putting their marker on one of these lines.

There are 35 tiles in the set, of the size of the empty squares on the board. Each side of each tile has two path ends that line up to the two white lines on the border (see the picture at the end for an example of some tiles). Each tile has four path pieces, each with two ends at different places on the boundary of the tile. These paths can cross, and there is a tile for each combination of paths (more on this later). Players keep hands of three tiles, drawing a new one every time they play one.

Each turn, the current player chooses a tile from their hand and lays it on the board in front of their marker. This new tile continues the path their piece was on, and they move their piece to follow that path until its end (it may link to other already-played tiles, so it could go longer than just one tile). The player also moves any other pieces that had their paths extended by this tile, again as far as they can until they reach their path's end.

For all those pieces that moved, if the path either leads them off the board or collides with another marker, then they have lost and are out of the game. The winner is the last one standing (or tie if multiple people lose on the last turn). Since there are only 35 tiles and 36 squares, it is possible all tiles can be played without anyone losing. In fact, the game comes with enough markers for 8 players. Can they all complete the game? Can they all complete it if they all have access to all tiles from the beginning (instead of having separate hands)?

While showing Tsuro to my aide this week, we raised this question. Ernie quickly became interested in trying out the combinations to see if he could get a working solution. This is an excellent challenge; I would guess the problem is NP-complete for general sets of tiles.

The question also came up of whether there are only 35 possible tiles, or whether the game is missing some possible combinations. I'm terrible at counting, but Ernie had some good insight and we worked it out. Here's a sketch of our logic:

Consider a single tile and count the possible configurations of paths in that tile. Choose one of the incoming path locations. There are 7 places that path could connect to. Now go clockwise around the tile to the next not-yet-connected path end. From here there are now 5 possible places this could connect to. After that, there are 3 more for the last one. In total that gives us 105 possible total configurations.

The game doesn't have this many, so there must be some symmetry that is not being considered. Since 35 = 105 / 3, it seems likely that rotational symmetric positions are not being used (which is the case). Now can we find cases where other symmetry is used? Yup!

Each right piece is symmetric with the corresponding left piece! I think the game uses all pieces. It's excellent that this works out to exactly 35 pieces, leaving that extra final open square. Very elegant!

Game Description: Mad Rooks

2011-02-25T03:47:00.001-08:00

This semester I am lucky enough to be working with a student on an implementation of Mad Rooks for the Android OS. In a previous post, I talked a bunch about the length of a Mad Rooks game, but I realized I didn't have a stand-alone post on the game itself.

Mad Rooks is another game developed by Mark Steere who has created a large number of excellent combinatorial games. This particular game is a sort of King-of-the-Hill Long-Distance Clobber. Both players begin with pieces that act like rooks in Chess in that they can move as many spaces horizontally or vertically on a checker board without jumping pieces. If a rook moves onto a space occupied by an opponent, the opponent's piece is removed (captured). A rook is called "engaged" if it can make a capturing move. Each turn, a player either uses one of their rooks to capture a piece or moves one of their unengaged rooks so that it is engaged.

Just as with Clobber, this game is all-small, which means if there is a move for one player, then both players have a move. Although this does not mean that each game has a nimber value (though it always seems like it should to me) it does mean that every instance of an all-small games has an infinitesimal value. Infinitesimals are smaller than all positive numbers, yet greater than all negative numbers (the only infinitesimal number is 0). Values such as Up, and * are infinitesimals.

It is especially interesting to look at end states in Mad Rooks, where suddenly making engaging moves instead of capturing with another piece is a better move, though engaging when you have to is often disastrous. It doesn't always even matter who has more pieces. Consider a board with rooks only on every square along the diagonal of the checkerboard. Now, if only one of those is Blue but the rest are Red, the next person to play loses the game, despite the fact that Red outnumbers Blue seven-to-one! (Try it!)

One reason some players may prefer this game to Clobber is that in the end all pieces of one player are captured, leaving the winner as the last color standing. In Clobber, you can't look at the final position and determine who won the game, but you can in Mad Rooks!

What are we taking in Nim?

2011-02-22T11:11:00.000-08:00

Nim is a game with many different incarnations. In some cases, it concerns removing items from just one heap, but with restricted amounts. In others, there are multiple heaps on the table at any time. These variations are played by many people, all using the name "Nim" and all with different rules (some people learn the normal play rules, others learn misere). There are many near-gamesters who are an expert at their version of Nim, but have problems if you vary even just the starting position.

Forgetting all this, however, what are those items that players are removing? What are the heaps made out of? I have heard uses of counters, sticks, beans, pennies/coins and others.

In elementary school, I learned the one-pile game as "Nim" and later the multi-pile game as "Sticks". With this second influence, it's very hard for me to not "pick up sticks" when I'm taking my turn in Nim. Not certain this was standard, I consulted Mike Weimerskirch and Thane Plambeck last month. Both of them referred me to the surreal movie Last Year at Marienbad, in which two characters compete at Nim. The games played in the film use matchsticks as props; perhaps sticks are the way to go! (This guy uses sticks, but he also cheats, so perhaps that's a point against it.)

If we consult the authoritative Winning Ways, however, we see that Nim is played with heaps of counters. It's hard to argue with this text! Indeed, Lessons in Play continues this tradition, referring to heaps of counters in the game Nim. Also, Mike told me straight-up that he's a counter man. Again, hard to argue with these Nim masters!

Beans? Beans are gross; who wants to think about playing games with food that will later be cooked. Didn't your parents teach you anything?

Candy, however, is another matter. Candy is delicious (and doesn't get cooked). Who wants to play Candy Nim?

Pennies and various coins make sense, except that the goal of the game is not to make money, but to make (or not make) the last move. Still, I bet these are often used as the "counters".

I'm still not sure what to use, but I'm going to keep with sticks until someone convinces me otherwise!

Game Description: Weak Hex (Whex)

2011-02-18T05:55:00.000-08:00

When I was first interested in Adjacent Hex (Adjex) a few years back, a friend of mine pointed out another similar game to me: Weak Hex. Weak Hex, or Whex, is extremely similar to adjacent hex because both players must move adjacent to another player's move. Instead of playing next to the last move of either player, however, both must play adjacent to the last move of the red player!

Here is the description from the original Whex paper by Argimiro A. Arratia Quesada:

Players can not colour an arbitrary vertex but must proceed as follows: Player
1 begins the game and he must do it by colouring red a vertex adjacent to
the source. From this move and on, Player 2 must colour blue an uncoloured
vertex adjacent to the vertex last coloured red (i.e. coloured by Player 1), and
Player 1 replies by colouring red an uncoloured vertex adjacent to the vertex
that he coloured red last.

(If no adjacent moves are available, the next player immediately loses.)

This game is intended for play on a graph instead of the standard hex board, but we can consider that also. In this case, the "source" is likely to be an entire red side (the sink, then, is the other red side). The goal for the red player is to connect the two red sides, and the goal for the blue player is to prevent such a connection. This matches up precisely with the winning conditions of standard Hex, so it is possible to play Whex on the regular hexagonal grid.

Additionally, the game is shown to be PSPACE-complete, so it is certainly hard to play in the general case! This is the same as with Hex and Adjex. In Hex, it is known that the first player has a winning strategy, but that strategy itself is not known. In Whex, however, not only does the first player have a winning strategy, but it can be described very quickly! In fact, I bet you can come up with it yourself!

(Find an opponent, see if you can come up with a method to always win playing first (as red), then come back and finish reading!)

Okay, on your first turn, play in the hexagon "on the bottom"

On each subsequent turn, play in one of the hexagons directly towards the upper-right-hand (red) side. Blue can only choose to occupy (at most) one of those on their turn, so you will get to take the other. Since you don't have to worry about playing adjacent to them, they can't deter you (as is possible in Adjex). Enjoy your march to victory!

If you play with the pie rule, I'm not sure what happens!

Blog Layout & Table Updates!

2011-02-15T07:10:00.000-08:00

Thanks for tuning in! Molly Dannaher, one of my students in combinatorial games last semester, provided the excellent artwork here, which comes straight from my marker board!

Also, I have many several updates to the game table over the past week, but there's still much more to add.

There was no update Friday as I was home sick.

Thank you for all the emails about potential post topics. I've been a bit weighed down with other work, but I do have lots I want to talk about!

Why bother about Computational Complexity?

2011-02-08T10:51:00.000-08:00

In a recent phone call with my Ph.D. advisor, Shang-Hua Teng, I was reminded how important the computational complexity is for combinatorial games. The punchline is very simple:

"Hard games give humans a chance to beat machines."

If no efficient algorithm exists to determine who wins a game, then a program cannot always efficiently choose the best move to make. Hardness results are evidence that this is the case (although we still don't know that no efficient algorithm can solve NP-hard or PSPACE-hard problems). These games give us some sense of safety that the computer doesn't already have the game won.

This also applies to the concept of experts and novices. It's not too hard to become an expert in an easy game like Nim. Learn the evaluation trick (computable in polynomial time) and you're good to go. At this point, if you play against someone who doesn't know that simple trick, you can beat them every time (unless they are very lucky). In a game such as Go, much more practice is required to become an expert. There is no quick evaluation algorithm to learn. However, since the strategies are not as clear cut, there is a bigger chance that the novice will be able to beat the expert.

When first designing Atropos, our goal was not just to find a 2-player game, but to find a (PSPACE) hard game. We changed the rules until we could get a proof of the hardness working. At that point we were quite satisfied! Some other games I've defined seem less impressive without a similar result. Learning that games are provably hard usually makes me want to play them more!

(I'm trying to keep track of game facts on this table, with quite a bit of bias towards computational complexity! Please let me know if there's something you'd like to add!)

Game Description: Wythoff's Nim/Game

2011-02-04T05:20:00.000-08:00

Last semester, one of my students presented Wythoff's Nim and did a great job explaining all the theory behind it. This is a simple, classic game with some beautiful properties, and something people continue to study variants of.

Wythoff's Nim (often called "Wythoff's Game") is just like playing "regular" Nim with two piles of sticks, except that you are also allowed to take X sticks from both piles, where X is any number. Thus, from the situation where the piles are of size 2 and 4 (we refer to this as (2,4)) legal plays include moving to (1,4) [taking one stick from the first pile], (2,0) [taking all four sticks from the second pile] and (1,3) [taking one stick from each pile]. Just as in Nim, the only location where no plays are available is (0,0).

This game is often envisioned as a Queen moving across a chess board, who starts anywhere on the board, and cannot move up or to the right. Players can thus move her left any number of spaces (subtracting from the first pile), down any number of spaces (subtracting from the second pile), or diagonally down and to the left (subtracting from both piles). This version of the game is visualized in the playable applet on this site.

This is naturally an impartial game, so the question arises: where are the P positions? (0,0) is automatically one, but (1,2) also does not have a safe move (all moves lead to N positions). (3,4) is not, (you can move to (1,2)) but (3,5) is. It turns out there is a very fancy trick for finding the P positions! This is a surprising application of the golden ratio, φ!

All P positions are of the form: (floor(k*φ), floor(k²*φ)) or the reverse. If we think about these as a sequence of pairs, ((a, b)_k), then the sequences (a_k) and (b_k) are Beatty sequences, meaning that they intersect nowhere and contain all the natural numbers (not including zero, so we consider only those where k > 0). Try out the first few pairs, and you'll see that this makes sense. Thinking in terms of the Chess board and the queen, each row should have a P position, and can't have more than one.

Many variants of this game have been studied, many relating to the relevance of Beatty sequences, which I hope to talk about more in the future. This is otherwise an excellent game to learn to exploit the winning "trick" and then show off to your friends with.

Graph NoGo is NP-hard

2011-02-01T07:21:00.000-08:00

Last week, I mentioned we had some computational complexity results concerning the game NoGo, which was the "new game" played at the game workshop at BIRS this year. After getting more comfortable with the game play, it felt like the game might be another great example of PSPACE-completeness. I put some effort into solving this, knowing it would be great to resolve the complexity while at the workshop.

Finding gadgets is tough, sometimes especially when dealing with the sort of grid-geometry of the NoGo board. Thus, I took a step backwards and considered NoGo played on a general graph. The rules to this game are still the same: each connected subgraph where all vertices have the same color must be adjacent to a vertex in the graph which is uncolored. Still, I had no luck finding a PSPACE-complete reduction. Instead, I took another step backwards and considered showing NP-hardness for Graph NoGo.

Woohoo! Success! Here is the plan for this proof: we will reduce from the Independent Set problem, known to be NP-hard. Given an instance of the Independent Set Problem (G, k), construct a Graph NoGo situation, G', that only the black player can move on, where each play corresponds to choosing a vertex in G, the original graph, to be part of the independent set. If the black player can make k plays on the new game, G', then there will exist a corresponding independent set of k vertices on G. To turn this into a Graph NoGo situation where the only question is: "Can the black player win if they are playing next?" instead of "Can the black player make k plays?" we will add (k-1) unconnected nodes where only the White player can move. Now, in order for Black to win, they must be able to make k (or more) plays (assuming they are going first).

So, there are two things to show. First, we need gadgets in Graph NoGo where only one of the players can play. Second, we need to be able to glue those pieces together so that playing in one of these locations means you can't play in an "adjacent" one. As it turns out, neither of these is terribly hard.

As above, if G is our graph for the Independent Set problem, then for each vertex in G, we will use the following gadget for our game of Graph NoGo:

Here, x is the place Black can choose to play their stone in. The only other blank spot cannot be played by either Black or White. Notice that White cannot play on vertex x.

Now, for each edge in G connecting two vertices, we will connect only the x vertices of the gadgets with another gadget:
Now, if Black plays in one of the vertex-gadgets, he can't play in the neighboring ones. Thus, any set of Black plays on the Graph NoGo board G' corresponds to an independent set on G. For example, two adjacent vertices in G, x and y, and the edge that connects them will look like this:
Thus, if we can always efficiently answer the question "Can the Black player win this game of Graph NoGo?" we can also solve Independent Set in polynomial time. Thus, Graph NoGo is NP-hard.

One nice property of this reduction is that it preserves planarity of the graph. Thus, if Independent Set is hard on a planar graph (is it?) then so is Graph NoGo.

So, how do we now take either of those two steps forward, to reach a PSPACE result or an actual NoGo result? Perhaps next week...

Game Description: Adjacent Hex

2011-01-28T03:26:00.000-08:00

While at the CGT (Combinatorial Game Theory) workshop earlier this month, I watched Ryan Hayward give an excellent talk about Hex and "Rex" (Misere Hex). Ryan is an excellent Hex player and even better Hex theorist (and also a good curling skipper). I was determined to play some Hex with him, but needed a little extra help since I had played so little. Thus, I suggested we play a variant: Adjacent Hex.

The game is exactly like standard Hex, except it mimics the play restrictions like Atropos: after an opponent paints a hexagon their color, you must play adjacent to their last move. If all the adjacent hexagons are already colored, you may choose to play in any uncolored hexagon on the board. (We've been referring to this as a "jump".)

Ryan and I played one game with these rules. At one point, I thought I was doomed, but Ryan pointed out a really good move for me. I can't recall whether that move led me to win, but either way it was clear his Hex skills were helping out. We proceeded to play two other games using different rules for jumping, but both agreed the original game was best.

I convinced Alan Guo to play a few games with me. We went back and forth, winning and losing, but building up some good intuitive strategies for the game.

Since returning to Wittenberg, I am undefeated. (My aide, Ernie, would like to add: "So far.") I've played against a number of students, and even beat the combined talents of my aide and teaching assistant, Patrick, earlier this week. Obed, the director of our math resource center, has vowed to get a set to practice with his own students.

This game plays very nicely: knowledge of Hex will help out, though knowing that playing in one hexagon will win you the game doesn't always help if your opponent never plays adjacent to that spot. In most of the games I've played, players are usually fighting to be the one working on their own path, which is sometimes harder than it sounds. Usually one player is currently working on a path, while the other player is just trying to derail that path using the adjacency rule. If their derailing is successful (this can be quite tricky) then that player starts building a path fragment and the other player is now trying to thwart that plan.

Sometimes play moves into an area that is closed off where the color of the hexagons does not matter. Now both players are competing to force their opponent to paint the last hexagon in the region, ensuring that they will be the one to "get the jump" and play wherever they want. A few times I've been in great situations where I decided not to connect two of my important paths because doing so would give my opponent a jump. This is a tough choice!

One nice property of this game is (I think) that it is "automatically" PSPACE-complete. If I understand Stefan Reisch's original "Hex is PSPACE-complete" proof, the gadgets in the reduction don't have any adjacent uncolored hexagons [citation needed], thus ensuring that each move gives the opponent a jump and the adjacency rule doesn't come into play. (I wonder how helpful it would be to produce a translation of Reisch's paper.)

In my office, I have a 14 x 14 hex board, just ready for adjacent-minded opponents!

Computational Complexity of Games

2011-01-25T05:07:00.000-08:00

At BIRS this year, the game everyone was interested in was Go.

I guess it's hard to compete with that! Aside from Go, one of the big features was NoGo. We had the first ever NoGo world tournament, both for humans and computers. After those tournaments were over, Fan Xie, the reigning human champion, battled Bob Hearn's champion NoGo-playing program. When presented with a new game like NoGo, as a computer scientist I'm always interested in the computational complexity: how hard is it to determine which player has a winning move? How long would it take a computer program to figure this out?

For some games, we have a bad (or good, depending on how you see it) answer: a lot. For Chess, for example, an algorithm that can evaluate the "winnability" of every game requires an exponential number of steps in the worst case. When I say "exponential", I mean, "exponential in the amount of information needed to describe the game board". Thus, if I look at all Chess boards that can be described using 1,000,000 bits of information, some of those require around

a^1,000,000

steps to figure out who is going to win where a is some constant greater than 1. This is not a feasible amount of time even for computers to have. As the boards get bigger, the number of steps increases by a multiplicative factor of a. We say that these problems are in the class EXPTIME because they take an exponential amount of time. (Figuring out who wins a game of Go is also one of these problems.) To be more general, we also include problems which can be solved in less time. Thus, the "complexity class" EXPTIME is the set of all problems which can be solved in an exponential amount of time (or less).

In general, if you want to figure out who wins a game by just trying all the options, this method usually takes an exponential amount of time because there are an exponential number of scenarios to reach the end of the game which must be tested.

However, for some games, the player with a winning strategy can be figured out really quickly! In the game Nim, for example, there is a fast procedure ("trick") to figure out whether the next player can win. This can be done in a polynomial amount of time, meaning there is a polynomial function that describes the number of steps needed for a computer to determine who has a winning strategy, again in terms of the size of the information needed to describe the game state. Although polynomials can have large exponents, for any one given polynomial, that exponent remains constant. We say that problems that be answered in a polynomial amount of time are in the complexity class P. Since these are both sets, and anything that can be solved in exponential time can also be solved in polynomial time, we know that P is a subset of EXP-TIME and that the two are not equal.

For some games, we don't know how long the fastest algorithm to determine winnability takes. Sometimes we describe these in terms of resources other than time. The complexity class PSPACE is the set of problems which can be solved with a polynomial amount of "space" meaning a polynomial amount of room to keep a record of important information in the algorithm. The space can be reused; erasing is allowed! Imagine that instead of restricting the amount of time you have to take a test, you are instead restricted by the amount of scrap paper you are given to do your calculations. It has been shown that P is a subset of PSPACE, which is in turn a subset of EXPTIME. It is not known whether either is equal to PSPACE (obviously both cannot be).

We can, however, say that there are some games that REQUIRE a polynomial amount of space to solve, and are thus among the hardest problems in PSPACE. These are known as PSPACE-complete. We show that a game (or any sort of computational problem) is PSPACE-complete by showing two things:

The game is in PSPACE
Any other problem in PSPACE can be efficiently rewritten as an equivalent instance of this game. (Known as hardness. Proving this means the game is PSPACE-hard.)

The notion of completeness works for any complexity class. Thus, for some class XXXXX, proving that a problem is in XXXXX and is XXXXX-hard means that the problem is XXXXX-complete. Chess, for example, is known to require and exponential amount of time because it has been shown to be EXPTIME-complete.

To show the second part (hardness) for a game, Y, means starting with any other PSPACE-complete game, X, and showing that any instance of X can be rewritten as Y where the next player wins Y exactly when the next player would win X. This is known as "finding a reduction" or "reducing X to Y". This is where the fun is! Check out this game table to see some known complexity results for games.

Why bother to show that a game is PSPACE-complete? Although we don't know whether P = PSPACE, it is likely that the two are not equal. Solutions to problems are generally considered "efficient" if there is a polynomial-time algorithm, so then PSPACE-complete problems cannot be solved "efficiently".

This post has gotten long, but I realized I should explain a bit more about computational complexity before blundering forward into some complexity results from BIRS. Next week I will talk more about that, and especially how it relates to NoGo.

I'm sure I left lots out! Please help me out in the comments!

Updated Game Table

2011-01-21T11:14:00.000-08:00

I made some updates to this game table with suggestions from others (and many things I learned at BIRS).

I am considering removing the last column ("Can I win this turn?") mostly because it's only interesting for a few combinatorial games. Anyone have a strong feeling about this?

BIRS Workshop, 2011

2011-01-18T07:12:00.000-08:00

Last week I was at the Banff International Research Station for a workshop on Combinatorial Game Theory. It was excellent! I got to meet many CGT bigwigs, play a lot of great games, present some things and even prove a few things.

Here were some highlights:

Presenting Atropos
Meeting 35 new friends
Playing Cookie Cutter with creator Paul Ottaway
Listening to current NoGo World Champion, Fan Xie, explain why he was losing to Bob Hearn's NoGo program while playing it.
Proving something on Tuesday and seeing the result mentioned in a talk on Wednesday morning!
Learning to Curl
Witnessing Zhujiu Jiang take on eight mathematicians at once in Go. (He only lost one of the matches.)
Playing Games... and losing most of them.

I learned a lot, and once I sort out all my notes I'll have a number of good blog topics from the meeting.

In other news, welcome to the Spring semester! I will return to the schedule of posting Tuesdays and Fridays. As normal, let me know if there's anything interesting you'd like me to cover! :)

XKCD love

2010-12-10T12:14:00.000-08:00

I love XKCD. This is beautiful.

Card Game: Xactika

2010-12-10T11:51:00.000-08:00

I'm a fan of card games. Rook and Euchre were common activities growing up in my family (though I probably play both a bit too haphazardly). When I first learned about Magic: the Gathering in 1994, I quickly jumped on board and became an addict. Every time I find myself in Germany, I relearn how to play Skat. It was easy, then, for the Xactika box to lure me in by advertising "Calling all Euchre players!" (Note: this quote is likely wrong. I don't know where my box is anymore. Does anyone have the actual quote?)

Xactika is a card game with an amazing slice of combinatorics. In this game, each card has four different kinds of "shapes" drawn on it: balls, stars, boxes and cones. For each of these shapes, the card has either one, two, or three included. Thus, one card might have three cones, one ball, two stars and two boxes. No two cards have the same numbers of shapes. Thus, there are 81 cards in the deck. Each card also has a number which is the sum of all the shapes drawn on it. Thus there is one 4-card (one of each shape), four 5-cards (two of one shape, one each of the rest), all the way up to one 12-card (three of each shape). The example with three cones, one ball, two stars and two boxes would have the number 8. Having a knowledge of how many cards have which numbers of shapes becomes very useful during play!

Each card belongs to four different suits represented by the shapes on it (there are twelve in total). Our example belongs to the suits of Three Cones, One Ball, Two Stars and Two Boxes.

Xactika is a trick-taking game. The first player to start each trick chooses a card from their hand and picks one of the suits on that card as they play it. Everyone else must play a card in the called suit if they have one (or playing another card from their hand if they don't). The highest-numbered card played that follows suit wins the trick. In the case of a tie, the last-played card takes priority. Thus, if two 10's were played in one trick (and both followed suit), the second one would win the trick.

In some situations, you can be sure to win a trick. For instance, if I have the 10 with three balls, three cones, three boxes and one star, and I'm leading, I can play the card and confidently say "One star", knowing I'll win the trick; there are no other cards with that value (or higher) that only have one star!

However, it often happens that you don't want to win a trick. After dealing out all the hands, but before play begins, each player "bids" the number of tricks they think they will take. After the hand is played, each player scores points if they made their bid exactly, otherwise you lose points! Thus, you often play a card, intentionally hoping you will lose the trick. In this case, it's better to play a low-valued card and call the suit with the most shapes. A 6 with three of one shape is a great move; any other card in the suit will be above it.

Although this deviates a bit (again) from our topic of combinatorial games, this is an excellent card game with a real unique twist. After learning Xactika, I often would rather play that than other trick-taking games! The box does not lie; I highly recommend this for card game fans!

Note: My Faculty Aide, Ernie, found this excellent video, explaining how to play Xactika.

Have a great Winter Break! I plan to post again the week of January 16, 2011.

Length of Games

2010-12-07T04:08:00.000-08:00

How quickly can a game end? This question came up during a presentation on Thursday of the game Mad Rooks. In this game, Chess-Rook-Like pieces from two teams move around, capturing each other until only one color of rooks remains (then that player wins). If the board starts completely full, then on an 8x8 board, 63 rooks might need to be taken before the game ends.

The presenter noted that he found a scenario where the game could end in 64 moves. Naturally, I wondered whether it could be done in one less. In general, the questions of how fast a game can end, or how long a (short) game can be drawn out are very interesting. I'd also like to know how long a Mad Rooks game can be drawn out. This does not seem trivial!

I could spend tons of class time talking about this last point. Mad Rooks is one of Mark Steere's games (these have been very popular amongst my students for these projects) which are carefully designed to avoid loops. This is often implemented by enforcing the continued reduction of some potential function on the game state from each move. In Mad Rooks, the potential function could map game states into two-element vectors: f(S) = [x, y], where x is the number of uncaptured rooks in the state S, and y is the number of unengaged rooks in the state S. (A rook is "engaged" if it is in line with an opposing rook.) Our potentials can be measured by giving x priority in comparisons, so [x1, y1] < [x2, y2] if: (x1 < x2) or (x1 = x2 and y1 < y2). Now, if for each move, the potential value of the game drops AND we show it can only drop a finite number of times, then at some point the number of uncaptured rooks will be small enough that the game is over.

The rules enforce that if a player moves an engaged rook, it must capture an opposing piece, and if they move an unengaged rook, it must become engaged. Thus, we see that any move must either decrement x (potentially increasing y) or decrement y but leave x alone. Since capturing a rook can only increase y by a bounded value, there is a maximum number of states that can occur during the play of a game.

What is an upper bound we can derive from this? Well, the game starts off with all 64 rooks engaged. Thus, our potential is: [64, 0]. At any given point in the game, capturing a rook could (at most) cause three engaged rooks to no longer be engaged (x decrements, y increases by 3). Also, an engagement move could only cause one previously unengaged piece to be engaged (x remains the same, y decrements). Thus, for each capture, there could be three additional moves to engage pieces. If 63 pieces need to get captured, we see that at most 252 (4 x 63) moves are required.

This is, however, an unreachable upper bound; no matter which piece is killed first, no pieces become unengaged. Also on that last kill, there are no more moves, so three additional engagements are not available; the game is just over. By how much is this upper bound too high, though? In general, for an nxn board, what are the upper and lower bounds on the number of moves?

Alleviating (some) Partiality Confusion

2010-12-03T08:04:00.000-08:00

Perhaps it would be best for me to tell future classes: if at any place in a game, one player has a move that the other doesn't, then the game is not impartial. This seems like something very intuitive that one should be able to impart with a quick sentence, but there are many layers of confusion on this point. Perhaps one has to see many examples of impartial games first!

I often see an impartial game defined as one which has the same options for both players. Does that mean {1 | 1} is impartial? No... this is game is in Positive (L), and all impartial games should be in Fuzzy (N) or Zero (P).

In our text, impartial games are defined as follows (page 135 of Lessons in Play):

"If for a game and all its options, the left options equal the right options, then the game is dubbed impartial."

There could be some confusion here also. Is G = {{1|1} | {1|1}} an impartial game? Certainly the left options equal the right options. Additionally, of the options of G, the same is also true: the left options equal the right options. However, to see that it is not impartial, we have to go down one level further (the options of the options of the options). The necessary recursion of a definition of an impartial game may be implied, but it is probably important to note that the options must all also be impartial.

Is there some middle ground here? On Tuesday, I referred to the game {-1 | 2} being equal to 0, though not impartial. Being an element of either the class N (fuzzy) or P (zero) does not make a game impartial. Other games that aren't impartial:

G: {0 | 0, 1}. Even though G = * (0 dominates 1 for the right player) the options aren't strictly the same.

G: {0, 1 | 0, 1}. Even though the children are the same, those children are not impartial.

G: {X | -X} (where X is a set of games). Here, even though this game MUST be in either N or P, and any strategy for Left translates into a strategy for Right, the game is not impartial.

G: {* | *, *2}. G is in Zero, and all options are impartial, but Left does not have *2 as an option.

For one I'm not sure about, what about the Domineering game consisting of three open boxes in an L-shape? Both players can move to 0 as their only option (so the game is equal to *) but they move there in different ways. Is this game considered impartial?

I apologize above for not figuring out how to use nice and fancy letters for much of my notation!

Have a great weekend! Next week is our last week of classes here and will be my last week posting until next semester.

Confusion over partiality

2010-11-30T10:25:00.000-08:00

Perhaps the confusion over partiality is not just limited to myself... or perhaps I'm just teaching it poorly.

For our presentations, most students have chosen partisan games, but somehow many students have declared that their games are impartial during the presentations. The reasoning, it seems, is that these games are "impartialish" from the initial position, since both players have similar moves and the value is either in N or P. This has a bit of logic to it; the strategies for each side is independent of the player's identification (Left, Right, Blue, Red, etc). This "fake impartiality" only exists for this initial state, however. Once a move has been made, the game is nearly always partisan.

I feel like there is more to think about here, but perhaps I'm headed down the path of trying to trisect an angle...

When we consider partiality of a game, it does not seem that this is consistent through equivalence. For example:

{ | } is impartial and is equal to zero, but

{ -1 | 2} is not impartial, but is still equal to zero.

Perhaps I'm wrong and we can consider {-1 | 2} to be impartial, but it seems dirty somehow.

Having now studied partisan games to the point where I could teach them for a semester (as far as we got, anyways) I'm very ready to retreat back to my happy, impartial-only world. Nimbers are fairly easy to work with; Ups and Switches and Dyadic Rationals and 3+DoubleUp+* is a bit more frightening. My respect for the effort needed to get Aaron Siegel's CGT Suite to work properly is moon-bound. This stuff is crazy-interesting, but I'll be happy to resume needing only a knowledge of mex and XOR to get some research done.

(As a side note, our presenter won a game today, so the record is now: 6-1 for the audience.)

A Homework Worksheet

2010-11-23T11:11:00.000-08:00

I am surprised by the success of my class audiences! They continue to be unbeaten against the speaker in our presentations. The class is now 5-0!

This week is Thanksgiving; there will be no post on Friday and today's post will be light.

As I mentioned, I have been making worksheets for homeworks for my class. I just finished the last (fourth) one this week. I won't hand it out to my students until next week. In case anyone's interested in seeing what these look like, here is the first one.

For those of you in the states, have a great thanksgiving!

Point-Value end states

2010-11-19T05:07:00.000-08:00

Student presentations have been a huge success so far! Competition is a funny thing, though. Somehow the audience is unbeaten (through four presentations) even though things always begin with the students collaborating: "We shouldn't try too hard to win; we should let win so they can earn the bonus points!" By the middle of the game, this has been forgotten; the audience is trying to optimize their moves. For hard games, the collaborating audience apparently has the advantage here!

Today, during our Reversi presentation, the question came up about the value of the final game states. I mentioned that one interpretation was that the result is equal to the number of blue circles minus the number of red circles. Another way to think of it was to consider that immediately after the Reversi game ends, a new game is played equal to that number value. This avoids ties: if the score is the same at the end, then the last player to move on the original game wins.

The students grabbed on to this idea and ran with it, chatting about it as the game continued. This method extends to other similar games that normally end by comparing point scores: Dots 'n' Boxes, Flume, etc. Even Hex can be conceived like this: the "score" for the winner could be the number of uncolored hexagons remaining on the board. Thus, the faster you win, the more the game is worth.

Notice that this doesn't make a difference if this is not part of a game sum. Without other attached games (or bragging rights) the only important part is whether or not you can win this game. In this case, it is instead equivalent to say that after game play is finished, we just append a game of value either -1 or 1 after the original game ends, depending on who "earned more points".

Does anyone ever play game sums with either of these methods? Anyone prefer one over the other?

Lectures are over... how to make them better!

2010-11-16T04:57:00.001-08:00

Thursday was our last "regular" class period. From today until the end of the semester, students will be presenting games they've researched on their own. If there is any extra time, I will fill in by attacking some of the topics we didn't cover throughout the semester.

There's a lot we didn't cover. Just on Thursday, I skipped ahead and covered Nimbers. We had only just started to cover infinitesimals: Up and Down. We hadn't quite gotten to DoubleUp = Up + Up. We were close to covering Switches.

I hope to teach this class again, but how could I improve things?

First off, Lessons in Play is an excellent text, but there are a number of things that should just be skipped. My students are not (all) math seniors, but instead a mix of computer science and math majors from sophomores to seniors. This means I should just skip more of the proofs in class. Many of the theorems are intuitive, and students are so hungry to learn how to evaluate these games, they want more statements of what is true and less explanations why. I think it's a shame I didn't get all the way to switches, these students really wanted to know what to do with {x | y} when x > y!

Second, I should use more worksheets. The last two weeks I started making worksheets for my students for their homework assignments. That worked really well. Somehow I didn't hammer it in hard enough that a game tree is the best proof. These worksheets take the students through the steps to prove the result, enforcing all the steps that are necessary.

Also, I think I need to choose better games to play during class time. Better doesn't mean more exciting, but instead more relevant to the topics we've chosen. Some games have more infinitesimals, while others are really great examples of employing the Simplest Number Theorem.

One thing that worked really well were the programming projects I assigned in class. For our last project, students must find the Grundy values of Cram games, implementing these properties straight from the definitions.

Exciting! I can't wait to teach this again!

Game Description: NoGo

2010-11-12T07:23:00.000-08:00

I don't yet know how to play go. I just got my set in the mail last Monday, and I'm looking forward to finding someone at Wittenberg to help me get started. Luckily, there is the game NoGo. I may not know just how much this game is related to Go, but at least it is teaching me to play pieces on the intersections of lines instead of the boxes.

NoGo works in the following way: players alternate placing white or black stones on a grid. Each intersection is adjacent to the four connected intersections. In the game, a turn consists of adding one of your stones to the board on an empty intersection. Plays are otherwise restricted only by the following rule: each contiguous group of stones of one color must be adjacent to an empty intersection. Thus the board resulting from any move must have this property, both for your color and stones of the opposing color.

For example, look at these two game states:

On the left-hand-side board, neither player has a move, placing any stone in the lower-left corner will prevent all connected regions from touching an empty intersection. On the right-hand board, the Left player has a move: they can add a black stone. This move connects the two regions, which has two pieces still touching the empty spot. Right does not have a move; no white stone can be placed which will connect to any blank spots.

This game is a bit tricky. Sometimes you want to have more of a presence so that your components are large. Other times, you wish you had smaller connected pieces, feeding off of an empty space.

I don't know how this relates to the grand game of Go (I hope to soon) but NoGo has already been fun to play!

MCURCSM

2010-11-09T03:51:00.000-08:00

Exciting news for my department: we are hosting the Midstates Conference for Undergraduate Research in Computer Science and Mathematics (MCURCSM) in just a few weeks on November 20th!

Liberal-arts undergraduate students often find themselves performing excellent research, and conferences such as these are perfect outlets for our students to show off their work. We're very excited to be holding this year's conference here at Wittenberg.

Unfortunately, I will be out of town that Saturday and will not be attending. Please come for the great student presentations and enjoy the awesome work performed by many first-time researchers!

Out of time!

2010-11-05T13:28:00.000-07:00

Sorry! Today was more packed than expected!

More posts next week!

Impossible Game States

2010-11-02T05:41:00.000-07:00

While preparing some old work to go into my thesis two years ago, I realized a potential hole in my construction: could the Atropos boards described always occur in the midst of a game? I had built some convoluted board pieces, then glued them together in PSPACE reductions. But could these monstrosities actually be the state of a half-played game? Atropos has a requirement that players must play adjacent to the last play (if possible, otherwise you may play anywhere). Thus, some game states are impossible to reach.

Here, the lone red circle and the green and blue to the right are disjoint sections that could not have occurred without a colored circle surrounded by colored circles.

Does this ever happen with other games? Naturally, we need to consider a game that has regular starting position(s). Assuming we always start from a full n-by-m grid in Chomp, we will never see a board that is missing cookies in the wrong places.

A cookie in Chomp cannot be missing when any cookies up and to the right are also present.

Some games aren't quite so clear-cut. In Domineering, we would never have a board with an odd number of checkers covered. However, we might have that board as a piece of a more complex partition of boards, so it could be a legitimate subsection!

Consider Alice and Bob, who sit down to play a game of Chess. After a while, Bob thinks he is winning, and gets up to find a snack in another room. He returns and looks at the game board, realizing that he is actually in a bad state. What happened? Perhaps Alice switched pieces around, or perhaps Bob does not correctly recall the position of pieces. If Bob knows that no pawns have reached the opposite edge of the board, does Bob have any chance to prove that the current board state is illegal?

Are there any games where it is difficult to determine whether the game is in an impossible state?

Breaking Symmetry

2010-10-29T05:40:00.000-07:00

Right away while teaching combinatorial games, my students latched on to the idea of symmetric arguments. It comes early in the book and is more convincing of a good plan of attack than greedy strategies (and is easier to use than finding transformations to other games). Whenever we play a new game, the students first look for ways to play symmetrically and then how to escape such a situation. This is an excellent pattern, since symmetry is not always a trivial venture, and likely a good indicator you are competing with a gamester.

Okay, so say your opponent in a game is employing a symmetry-based strategy, which will be successful unless you break it. You see an opportunity to break the symmetry, but it's something you can do now or later. When should you do it?

I bring this up because Neil McKay noticed a flaw in the symmetry argument for the first player in Flume. Gasp! I have amended the game table but hope to have the matter resolved. I will present Neil's illuminating break at a later date (after it is not immediately relevant to my class; some students are actually reading this!) but it's great that he found a counterexample to the strategy.

This event makes me curious about symmetric strategies in general. Flume was a bit of a special case, because the symmetry employs two steps each turn: first be greedy and take all the free spots, then turn around and make the same move your opponent did, allowing them to make the same great moves you just did. (Luckily, you should always be ahead by one piece.) This seems to me as a bit of an "impure symmetry" (perhaps more so now that there's an escape). I still hope that there is a method to restore the symmetric state in Flume, though I'm likely biased at finding out I was wrong.

Even more so, I'm interested in other surprising examples of symmetric strategies. Are there any examples of games where symmetry can win you the day, even when you wouldn't expect it? Are there any other examples of impure symmetry that wind out working great? Are there any examples of breakable symmetry strategies that are actually robust enough to be restored?

I'd love to hear about them!

Nothing Tomorrow

2010-10-25T14:10:00.000-07:00

I hope your tomorrow is full of wonderful things. Sadly, a post here will not be one of them.

I have spent lots of time out of the office due to unexpected appointments. Teaching is my number-one work priority, and so other things must fall to the wayside a bit.

Also... I need to figure out how to get Blogger to report the post as being dated with the day I actually Post it, not the day I first start editing it.

I do hope to return on Friday with another post!

Chickening out on Chess

2010-10-22T05:21:00.000-07:00

I haven't played a game of Chess in years. I was recently approached by some students asking to start a Chess Club, and we're going ahead with that. I hope I'll be able to learn to play moderately from them!

Yesterday we were set to have another "Game Day" in class where students would find values (and outcome classes) of different game states. I was hoping to do Chess, and had been flipping through Noam Elkies' paper on Chess end games. A lot of stuff in there was excellent and would really get my class thinking.

But I chickened out. I know that most of my students know how Chess works, but I wasn't sure if they'd be able to see some of the acceptable moves quickly. I was nervous teams might spend half the class figuring out what was going on in one example. Worse, I was afraid I wouldn't be able to cook up new examples on the fly as I have the rest of the year. I have to really be careful with Chess to avoid instances that are not short games.

Instead, I introduced Konane (I'll write separately about this game some time; it's very nice). I played a few times with my aide the day before, then threw a bunch of boards up on the whiteboards. The students dove in immediately; writing up outcome classes, values, and questioning or confirming the results of other teams. I stopped every so often to explain how to derive some values and to switch up partners.

So far, we have only covered Nimbers (defined only via equivalence to Nim heaps) and positive and negative integers, so some of the boards were not given explicit values by the students, as expected. It is almost equally rewarding when students express frustration over not knowing the value of Up---I know they're interested to hear more from our lecture days.

We really should do Chess, though. There are only a few more weeks before we get deep into the student presentations, so I'll have to introduce it soon! Hopefully I'll have good news to report then.

Updated Game Table

2010-10-15T12:56:00.000-07:00

I updated this table of Combinatorial games and some of their known properties. This time I added a column to list variants of games. I still want to add more games and properties, please inform me of more results to add! These could include:

More Games! I'd love to add more rows.

Properties! I'm sure there are some incomplete cells that could be updated. This time I added "Open" if the problem is known to be open (there must be more of these).

References! I added a bunch of links, but there must be more (or better) supporting documentation for some things. I would love to add more links.

Game Description: Toads and Frogs

2010-10-13T11:41:00.000-07:00

Prior to this semester, I got a lot of helpful suggestions for preparing to teach Combinatorial Games. One reader, Joshua Biedenweg (instructing at UC Santa Barbara while an undergrad!), was in the middle of teaching his own CGT class and suggested I include Toads and Frogs in the class. I liked his reasoning, but wound up using Domineering as the main guiding example, as it is used throughout our text.

For our recent "game day" class, I tried out his suggestion, and Toads and Frogs worked out really well. Students quickly figured out the value of many games, including some games of arbitrary sizes!

Toads and Frogs is a game invented by Richard Guy. A game state consists of a horizontal row of "spaces", each of which either empty or inhabited by a Toad or Frog. Toads face right (but are controlled by the Left player), and Frogs face left (controlled by Right), and may only move in the direction they are facing(Toads move "to", Frogs move "fro"). Each turn, a player chooses one of their amphibians and moves it. An amphibian may move one space if that space is empty, or may instead jump over an adjacent opposing piece if the space behind that piece is empty.

For example, in the following situation a T is a Toad, an F is a Frog, and an underscore, _ is a blank space. Then in this game:

T _ _ T F _

Left can move both of his amphibians, resulting in either _ T _ T F _ or T _ _ _ F T. Right only has one frog to move, and can move to T _ F T _ _. As my class found out, it is fairly easy to evaluate a lot of different positions, and as Josh explained to me, this is a great demonstration of different game values. Sums are also very easy to do: just draw the rows on top of each other.

Simple rules, simple game description. And, fortunately, this game is hard to play well! Jesse Hull showed that NP-hard instances of the game exist (using techniques I am not familiar with). I wonder whether it can be shown that determining a winner is also PSPACE-complete.

The best challenge I came up with for my class was to add two games together:

T _ _ ... _ _ _ F
+
T _ _ ... _ _ F

Where the top row has one more space between amphibians than the bottom. The result is very nice (* = {0|0}) especially since students' intuition had them first thinking it depended on whether the top or bottom game had the odd number of spaces.

Thanks Josh, for telling me to check this game out!

Still no post...

2010-10-12T13:14:00.000-07:00

I just returned to the office today and have been busy all day catching up. I am planning on having a new post ready on Friday.

Sorry again!

No post: sick!

2010-10-08T12:39:00.000-07:00

I've had a cold all week. More posts next week!

Nearly Shooting Myself in the Foot with Misere Sums

2010-10-01T12:10:00.000-07:00

Oops!

Last week, in an effort to relive my success with finding negative games by summing to zero, I tried the same thing with a new game. The plan was to add states of a new game to states of games we had already covered, then see if they sum to zero. I wrote up states of the new game, and challenged students to find states in Clobber, Amazons, Nim, etc, that summed with the original game to get zero. Unfortunately, I hadn't had a good idea for a new game, so instead I decided we would play Misere Clobber.

Pretty quickly, students asked me: "Wait, how do we add a normal play game to a misere game?"

Oops!

Somehow I did some quick thinking (I usually can never seem to do this in front of a class) and reminded myself of how to make this "legitimate". I wound up writing two options on the board:

Either players are not allowed to make the last play in the misere game, or whenever a player makes the last move in the misere game, they immediately lose.

Whew! Things progressed pretty nicely at that point. Still, I was wary of teaching them that games can have the misere property instead of attaching that property to the method for playing a game. At least this took care of covering all the mechanics we needed to find negative games.

I took a number of wonderful pictures of the boards and of my students playing, but my new phone seems to have trouble with its camera and the pictures were never stored. Instead, enjoy these pictures one of my art-minded students drew on my whiteboard after we covered the definition of a game negative. :)

Searching for Games

2010-09-28T05:45:00.000-07:00

There is no final exam in my combinatorial games class. Instead, the last four or so weeks will consist of student presentations. Each student is tasked with choosing a combinatorial game (that we haven't covered heavily in class) and researching "something interesting" about that game. Students will then present their findings.

The interesting thing does not need to be something super heavy, but should be non-trivial. So far I have three students who have chosen their games: Flume, Reversi and Hex. Of those three, two students have picked their "interesting things": one will code a playable version of Hex, while the other will describe the first-player winning strategy in Flume. In addition to these sort of options, students could write a program to determine the outcome class of their game, or just describe some interesting property (for example, that Hex cannot end in a tie or that the first player has a winning strategy in Chomp).

Part of my hope here is to learn more combinatorial games myself. I continue to work on expanding this table of games.

The other ten students have yet to choose a game. I have directed them to check out some resources such as Mark Steere's extensive list of creations, as well as the long appendix of games in our text, Lessons in Play.

Do you know of any other places I can point them to to find games? Certainly there is also a degree of procrastination, but it would also be great to give my students more resources. Also, it might come down to the point where I am forcing games upon the students. In that case, suggestions will be very helpful! Perhaps you've developed a game you'd like someone to check out!

Two turning points in my Games Class

2010-09-27T04:31:00.000-07:00

Teaching this combinatorial games class has been tough. I am simultaneously teaching Software Engineering and Algorithms, and while both are challenging courses for students, they are going pretty smoothly. I know what I can expect from those students and know what I need to get across to them.

Combinatorial Games, on the other hand, is an adventure into some tricky territory. Since I have a wide variety of math and computer science students, I'm having a hard time making the correct assumptions about what my students already know. Since this is a new-fangled elective, I also don't have specific goals I need to communicate.

The structure of the course has been to spend one of the two class periods each week focusing on playing a new game. (Here is the class schedule so far.) The first week we played Domineering, then Clobber, then Toppling Dominoes. Students would play a bit amongst themselves, and do a great job answering questions I posed. But, after a few games and a few opponent-switches, they would get a bit bored. The 1.5 hour class started to drag on and a few students would actually ask me to return to lecturing. (Luckily, I brought some notes with me!)

Then, in the fourth week, we played Amazons. Wow. The students responded to this by actively getting into the game and trying to figure out good moves. The idea of outcome classes started to click and when I called for a change of opponents, very few people got up in the first minute.

Last week, we did something even better. I had the students play game sums (Note to me: I should have done this sooner!) and try to find different games that summed to zero. The base game was Amazons, and I drew different instances on the whiteboard and challenged the students to find different Domineering, Clobber and Toppling Dominoes games that, when added to the Amazons board, summed to zero. The result was possibly the best class period I have ever taught... even though I personally did very little. Students quickly took to their game boards, reasoned about some sums, then started filling up the marker board. Almost immediately some things written on the board were challenged (though no one was brash enough to erase another student's work without permission) and some excellent discussion began to take place.

Wow.

It's hard to describe that level of engagement by students. Everyone was knee-deep in advanced mathematical material, experiencing it first-hand. We haven't yet defined many possible game values (I'm not sure we've defined anything rigorously yet) but students were quickly clamoring for an explanation of different fuzzy games and non-number values.

As I continue this semester, I think I need to make sure that every topic is motivated, and perhaps play games in each class (instead of every other). These last two game days have made an amazing argument for that!

Out again tomorrow

2010-09-23T05:56:00.001-07:00

Unfortunately I will be out again tomorrow. With any luck I'll be back in action next week.

Quantum Chess

2010-09-15T10:51:00.000-07:00

Recently there was some cool board game buzz about combining quantum super-positions and chess: Quantum Chess.

The game was designed by Selim Akl as a response to the brute-force superiority of computers in standard chess. Alice Wismath, working with Dr. Akl, implemented a non-quantum version (they point out: "a true quantum board may be a few years in the future") as a Java 1.6 applet (I had to upgrade my browser's Java).

The basic idea behind this game is that the identity of each piece (aside from Kings) exists in a super-position before it is moved. The actual piece will be one of two different options (for example, either a rook or a knight) which is only known once you decide to move that piece. Thus, each turn consists of first choosing a piece to move, then determining what type of piece it actually is, then moving that piece.

Naturally, since the value of the pieces is based on some randomness (quantumness is considered randomness, right?) this is not strictly a combinatorial game. Until we have quantum boards, it's not exactly a board game either... Still, we can implement this in a non-quantum way using a big checkerboard and two sets of chess pieces. By putting two pieces on the same square to indicate the super-position for non-collapsed pieces, you can then decide the actual value by flipping a coin once the piece is chosen.

In any case, this is an extremely original game and an excellent work by Akl and Wismath. With any luck this will bring interest into both games and general quantum... ness. As you can see, I need a lesson on quantum mechanics and quantum computing!

Note: I will be out of action on Tuesday, so the next post will probably not occur until next Friday.

Oops!

2010-09-14T17:52:00.000-07:00

Hmmm, apparently I've been a bit confused recently about getting posts out at the correct time. I somehow posted twice last week on Tuesday without realizing it until Friday.

Hmmm...

Unfortunately, I have just run out of time today.

I will have something new to say on Friday and will get back on my regular schedule.

Sorry!

UGrad Course Update and a Mini Course in Amsterdam

2010-09-07T12:16:00.000-07:00

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

2010-09-07T11:31:00.000-07:00

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

2010-08-31T13:23:00.001-07:00

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

2010-08-27T10:49:00.000-07:00

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

2010-08-24T10:34:00.000-07:00

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

2010-08-16T08:34:00.000-07:00

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

2010-06-28T11:11:00.000-07:00

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)

2010-05-18T06:42:00.000-07:00

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)

2010-05-06T06:13:00.000-07:00

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)

2010-05-04T12:37:00.001-07:00

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

2010-05-03T08:03:00.000-07:00

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

I should start adding more pictures...

Game Description: Fjords

2010-04-30T12:26:00.000-07:00

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!

Mall Madness

2010-04-27T13:01:00.000-07:00

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!

Combinatorial Games... Art?

2010-04-23T06:04:00.000-07:00

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?

Candy Nim

2010-04-20T12:16:00.000-07:00

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?

Playing While Losing and Collecting Candy

2010-04-16T10:49:00.000-07:00

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!

Teaching with a Game

2010-04-13T13:07:00.000-07:00

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?

No Post Today

2010-04-09T11:11:00.000-07:00

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!

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

2010-04-06T09:41:00.000-07:00

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!

Game Description: Hanoi Stick-up

2010-04-02T13:27:00.000-07:00

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!

Winning Player Conjectures

2010-03-30T13:21:00.000-07:00

The game Sprouts has a very interesting conjecture associated with it:

If the game starts off with n dots, then the first player has a winning strategy exactly when n mod 6 = 3, 4, or 5.

This seems strange. Why 6? How is this number inherent to the rules of Sprouts? Well, it's not clear that it is, because the conjecture has not been proven.

Nevertheless, supporting cases continue to be found. Somehow I am comforted by the idea that somewhere, there is a computer working to check cases for Sprouts. (Probably I feel the same way about the Collatz Conjecture. Someone is running that right now, right?) Sprouts is also studied in the misere version, with other cases being checked.

Along these same lines, there is a conjecture for Atropos:

If the game starts with n open circles along a side, then the first player has a winning strategy exactly when n mod 4 = 0 or 3.

This has a bit of intuition behind it: if the losing player can enforce that the game drags out to the last circle, then that last circle will cause the loss. Since the number of open circles at the beginning game are 1 + 2 + ... + n = n (n + 1)/2, this is even exactly when n mod 4 = 0 or 3.

Naturally, there is lots known about starting positions. Hex and Chomp both are wins for the first player, though the proof is non-constructive.

What about other games, such as Amazons? Which conjectures exist for the winning player from starting positions?

Game Description: Toppling Dominoes

2010-03-26T13:04:00.000-07:00

I did a "tour" of classes the past few weeks, advertising my board game course next semester. While doing this, I brought my copy of "Lessons In Play" to show off. On the cover is the addition of a Konane game with a Toppling Dominoes game that equals an Amazons game.

I point out that it's pretty cool that we can express games this way. Unfortunately, I realized that I didn't really know anything about "that dominoes game". Hmmm...

It turns out the rules to this game are very simple! Here's how it works.

With a supply of dominoes, each colored green, blue or red, set some of them up in one row. Then the Blue and Red players alternate turns, each knocking one of their own colored dominoes (or any green domino) to the right or left, thus knocking down all the other dominoes on that side.

Notice that this game, just like normal Nim, is not terribly interesting alone. In just one row, any player who has a domino of their color (or green) on one of the edges of row can just topple that one, knock down all the other dominoes, and win as there are no more plays. In fact, in the case with only blue and red dominoes, if both ends are in your color, your opponent has no way to prevent you from winning.

With more than one game, however, this gets more interesting and it becomes important to find the actual value of each game to play best.

I don't know the complexity of analyzing this game, though.

Tournament Spectator Scoring

2010-03-23T09:10:00.000-07:00

In late March in the United States, there is a college sporting event known as March Madness in which the top 64 (sort of) mens college basketball teams compete in a lose-once tournament to determine the annual champion.

I'm not a huge basketball fan---mostly because I have no sense of verifying whether a foul happened---but as with any sport, it can be tons of fun to watch. With March Madness, there is a different level of spectating that occurs. Instead of watching all the games, fans instead predict who will win each game by filling out a bracket (such as this one) before the tournament.

Fans then compete with others using their brackets. You gain or lose points by correctly or incorrectly predicting winners at each round, respectively. How does this scoring usually work?

The first time I did this with some friends in grad school, we scored by simply counting the number of incorrect guesses. The "contestant" with the least won.

Alternatively, you can assign a different number of points per incorrect guess at each round. For example, each correct guess in the first round could be worth 1 point, each in the second worth 2, then 4, then 8, 16, and the final game is worth 32 points if predicted correctly. This is apparently the preferred method (using the scientific method of web browsing).

The problem with this is that after the first few rounds, many of your teams have been eliminated. Sports are much more fun to follow if you always have a team to follow, independent of the game. If I didn't predict either of the teams to take part in a game, then I don't care who wins! Instead, whenever a team you picked loses, you cross them off everywhere in your bracket they appear (losing points at each step) and replace them with the team that beat them. This year, I picked Villanova to "go all the way" but they lost in the second round to St. Mary's College. Now, I am rooting for St. Mary's to win their next game.

This year, my competition is colleague Bill Higgins, who knows something about basketball. We agreed to score this way, with each "correction" costing 1 point. Villanova losing has already cost me 5 points, but it could cost me more if St. Mary's loses (especially if they lose soon).

One problem here is that the final game is likely not super exciting. It is only worth 1 point! Instead, each correction could cost different amounts depending on the round the correction was made. Then, using the 1, 2, 4, ... 32 sequence, I would have lost 10 points due to Villanova's loss instead of 5. In this case, everyone has a stake in the final game and it's worth 32 points. Here, however, because more than 32 points can be lost in any other round, it does not eclipse the weight of other rounds.

Perhaps that would be better to use...

Anyone familiar with other good scoring methods?

No FUN for me. :( Other conferences?

2010-03-19T12:09:00.000-07:00

FUN with Algorithms 2010 is taking place in Italy in early June. I submitted two papers, but neither of them made it in.

I would normally still probably try to go, but I'm getting married shortly afterwards. (Woohoo!) Without the excuse of presenting a paper, I won't attempt to squeeze these things together.

I've missed a lot of following paper deadlines, and there are others that I am either interested in or would consider submitting to. Here's a little list of what's already passed by (but might be candidates in future years):

FUN 2010
AOFA 2010
SWAT 2010
ICALP 2010
COCOON 2010
FAW 2010

Those still coming are:

GandALF 2010
FOCS 2010
SAGT 2010
COMSOC 2010
ICS 2011
INTEGERS 2010 (I don't have a site for this yet. INTEGERS 2009 had a very short submission/acceptance time.)
LAGOS 2011

(These are listed in order of (expected) submission deadline, not actual conference dates.)

I mostly catch these as they come through Theory Net. I'm likely out of touch with some more math-based feeds, though. Can anyone suggest other conference options?

Also, I've played a bunch of games of bOOleO this week already! This is an excellent card game! If I ever teach a machine organization course, I will somehow work this in as an example of logic gates!

Oops and Updates!

2010-03-16T07:09:00.000-07:00

Hmmm...

I see that I missed Friday. As soon as I noticed that, I feared that I had missed last Tuesday also, but, no, I showed up that day. Last week was spring break, but I did not intend to take as much time off from work as I did. I apologize for missing on Friday!

One of my big tasks for this past week was to make sure everything was okay to close down my web account from BU's CS department. Sad! Now the Atropos and Matchmaker applets are hosted on Wittenberg sites, and they seem to work just fine. Please let me know if you notice any problems with either of them, and I'll fix them immediately! (If you don't have Java enabled on your browser, there's not much I can do for you.)

I am expecting to get a copy of bOOLeO delivered soon! That game looks excellent! There is something very enticing about seeing game pieces in pictures and coming up with what you expect the rules to be before actually reading any.

I realize that of Atropos and Matchmaker listed above, I have only actually published (thesis not counting) about one of them. I have never submitted a paper about Matchmaker anywhere, though it might be a topic that could sneak in somewhere. Still, I am a bit loathe to do this until after I prove something concrete about the difficulty of the game. Either showing that it can be solved in polynomial time or finding a completeness result would be enough for me (I haven't worked on this game in a long time).

Is this legitimate? I've noticed that in some of my presentations, no one cares about solving the game, but are instead more interested in the origins and rules (and implementations) of the game. Perhaps it is more vital to get playable versions of games out and introduce them that way than to make sure something is known about them first.

Double Games

2010-03-09T08:44:00.000-08:00

Sometimes it's fun to try and combine multiple game boards or sets at the same time. We can always use the normal ways of adding two games together, but there are some other alternatives too...

In high school, a friend of mine mentioned he used to play "boxcar chess" with his family. This is a version of chess using two sets and four players on two teams. Two games went on at the same time, except whenever you capture an opponent's piece, your teammate gets to add that piece to their board. Thus, you had to play the opposite color of your teammate.

I don't know the details of how you add "new" pieces, but I assume you can spend a turn to place one of them in your back row.

I tried to adapt this for Stratego, since my family had two sets. I made the rules a bit too strict, however, and it wasn't all that interesting. I'd like to give it another try some day with more flexible rules.

Then, just last week, I was chatting with Brian about old war games (I really am only familiar with Risk and Diplomacy) and he mentioned enjoying "Double Risk" using two boards. The boards interact by including adjacencies between each pair of countries with the same names. Thus, if I wanted to get past Central America on board A (which has a bunch of armies on it) and I have a big force on Venezuela on board A, I could instead attack Venezuela on board B, then Central America on board B, then, say, Western United States on board B and on to Western United States on board A. I don't actually think this is a good Risk strategy, but I'm still bitter at that game for the power of cards...

Undergrad CGT Course

2010-03-05T12:00:00.000-08:00

I have good news for next semester! The CGT course has been approved and I am already preparing material. The course will be cross-listed in math and computer science. The broad goal of this course is to explore combinatorial game theory as deep as is feasible with extra attention paid to programming and algorithm design.

Some games, even if they defy the proper definition of "combinatorial", may have special purpose here. One of these is RoboRally.

About a month ago, I played RoboRally for the first time. It was advertised to me as a game that "used programming". I did not believe this at all (I was hoping to play a game of Kingsburg that night) but then after playing for a just a few minutes, I was hooked. In the game, you have a robot to move around the board. Each round, everyone is dealt a hand of cards, each of which is an atomic command for your robot (move or turn a certain direction) and you immediately choose a subset of those cards, then order them. Your robot then makes those moves in that order, but might interact with the orders of other robots. It's great because you have to think very carefully about the "program" you give your robot.

Additionally, I do want to be able to get into some of the details of complexity classes, but without going through an entire algorithms/complexity course. The only prereqs for this course are Programming I and Discrete Math. Somehow I will have to convince the students that you "probably can't" solve some of these games.

If anyone has any good suggestions for games or other resources, I would love to hear them!

Also, has anybody played this game? I can't seem to find any information about it anywhere, but it looks like it could be cool!

Updates to the game table have been slow, but I continue to make them!

Playing without Giving away your Strategy

2010-03-02T11:45:00.000-08:00

Perhaps you are about to play a series of three games of cram against an opponent in the final round of a cram tournament. Your scored better than your opponent in the tournament thus far and must play first in the first and third games. The winner of the tournament will be the player that wins 2 of those 3 games.

While playing the first game, you can see that you are losing, but suddenly realize there is an really good strategy for winning from the start as long as you go second. Since this tournament uses initial 8 x 8 boards, you can use a symmetry strategy to mimic the other player's moves! Great! The next game is yours!

Unfortunately, you also realize the strategy is easy to follow. As soon as you use it against your opponent, they will be able to implement it themselves in the final game and win.

Is there a way to implement the symmetric-play strategy but disguise it at all? In general, is there a way to mask the fact that you are using a simple strategy to win?

In Nim, it is difficult to follow someone making the correct moves if you do not know how to evaluate the game boards. If it was plainly obvious what the other player was doing (perhaps XOR is your favorite math operator) then perhaps you would pick up on it quickly.

I tried this once, keeping a "turn behind" in the symmetric-play strategy. I kept making the play my opponent had made two turns ago, whenver possible. As I recall, it got messed up and I had to ditch it part way through. Is there any good way to keep this going? I feel this would be more difficult for an opponent to follow... if it works!