Friday, December 10, 2010

XKCD love

I love XKCD. This is beautiful.

Card Game: Xactika

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.

Tuesday, December 7, 2010

Length of Games

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?

Friday, December 3, 2010

Alleviating (some) Partiality Confusion

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.