### Coding Games

10Nov07

I heard that a fellow UW student, who happens to be taking my game theory course this term, won a Rock-Paper-Scissors contest! You can see his explanation for his winning strategy here. It would be worth mentioning that he didn’t actually sit around and wiggle his hand thousands of times, but rather it was a programming contest; the code that he submitted was apparently both “smart” enough and fast enough to take home the top prize. (I don’t have a pointer to the official results…)

Coming up soon in that same course is a project on impartial combinatorial game theory. In an attempt to find a project theme that

• isn’t easily googlable
• isn’t too boring
• isn’t too impossible,

I’ve thought about a generalization of so-called subtraction games. Here is one example and a winning strategy for it.

10 coin game: there is a pile with 10 coins. on your turn, take 1 or 2 away. you play against one opponent, you move first, and the person to take the last coin wins.

how to win: take away one coin, leaving 9. on each remaining turn, do the opposite of your opponent, so after your next turn there are 6 left, then 3, then 0 (and you win).

A general subtraction game has a subtraction set (it’s {1, 2} for the 10-coin game) and an initial pile of n counters (=10 for the 10-coin game). On your turn you pick a number from the subtraction set, and take away that many counters; if you’re unable to do so (i.e., if all numbers in the subtraction set are greater than the # of counters left) you lose.

The generalization comes in when you say that, instead of a pile of one type of object, you have a pile of 2 types of objects (say apples and oranges), and can take away some specific combinations. E.g., one set of rules might be

• you can take away 2  apples and 1 orange
• you can take away 3 apples and 3 oranges
• you can transmogrify 2 oranges into an apple (i.e., take away 2 oranges and -1 apples).

There’s a standard way to analyze this type of game. In the 1-object variant, the set of winning positions is always a nearly-periodic set. But for 2-object games, more interesting patterns seem to occur. The picture below is a depiction of the “pattern” of winning strategies for the rules just described above… it was generated with this Java applet which will probably play some role in the project.