JP Writes Code

I am an almost college student in the midwest who likes math, computers, and other interesting things

On Set

23 Jan 2014

For those not familiar, Set is a relatively simple board game played in real time by assembling "Sets" of cards. Each card in the game has four attributes (shape, color, number, and filling) which can each be any of three different values ((oval, squiggle, or diamond), (red, blue, or green), (one, two, or three), and (empty, shaded, or full), respectively). A "Set" is only valid if for each attribute, each of the three cards in the Set either has the same value or no two cards have the same value. For instance, one solid red diamond, two shaded blue ovals, and three empty green squiggles would make a Set because no two cards share an attribute. One solid red oval, two solid red ovals, and three solid red ovals are also a Set because they all have the same filling, color, and shape, but they all have a different number. In general, a Set has no pairs of attributes, just triplets or uniques.

For this reason, cards lend themselves to representation as a four-element array of ternary values representing their attributes. For instance, a 0 in the first element of the array could mean oval, a 1 diamond, and a 2 squiggle. The only question is whether to use standard ternary or balanced ternary. While balanced ternary has a number of computational advantages, for our purposes, standard 0-1-2 ternary actually allows us some computational shortcuts. Firstly, a function to find out whether a given triplet of cards is a Set, which would normally be horrendously ugly and check for any possible pair of matching values with no triplet can instead be written as below. Note that the sum function, which cleans up the code a bit, would not always work with balanced ternary.

1 is_Set :: [Int] -> [Int] -> [Int] -> Bool
3 is_Set card0 card1 card2
4   | sum (map (`mod` 3) (zipWith (+) card0 (zipWith (+) card1 card2))) == 0 = True
5   -- First we sum the numbers in each card mod 3, and then we sum the numbers in that array
6   -- This can only result in zero if the array is [0,0,0,0]
7   | otherwise                                                              = False

The above code hardly does anything to help the stereotype of Haskell as unreadable, but with a little analysis it is both clear and elegant. Given three lists, it creates a new list where each element is the sum of the elements in the same place in the original list modulo three, then checks if that list is entirely zeroes by summing it. So given [a,b,c,d], [e,f,g,h], and [i,j,k,l], if (a + e + i) % 3 + (b + f + j) % 3 + (c + g + k) % 3 + (d + h + l) % 3 == 0, it returns true. Otherwise, it returns false. This works because 3n % 3 == 0 while n is any number and (0 + 1 + 2) % 3 == 0, but (2n + m) % 3 != 0 while 0 <= n, m <= 2.

Another interesting problem is the number of total Sets. This can be approached from a number of different ways. Perhaps the most intuitive is by looking at the number of possible Sets in a game with only one attribute, a game with only two attributes, and so on onto a game of four attributes. While perhaps the most mathematically "pure" method, this is also challenging and an unnecessary amount of work. Instead, we can rely on the modulo arithmetic discussed above. Since a Set is only valid when the sum mod 3 of its attributes represented numerically is 0, given two attributes we can deduce the value of the third necessary to complete the Set. There will also be only one value between zero and two that works, so a pair of attributes implies a unique third to have a valid Set. This means that any pair of cards implies a unique third card that completes a Set with them.

The naive interpretation of this is that the number of possible Sets is equal to the number of possible pairs, but that forgets that a group of three cards contains three different pairs ((0,1), (1,2), (0,2)), and that each pair can be revealed one of two ways. Thus, the number of possible Sets is equal to the number of possible pairs divided by three times two. Since there are 81 cards, the total number of possible Sets is (81 * 80) / (3 * 2), which is the same as (27 * 40), which is 1080. This also means that drawing two cards off of a fresh deck, there is only one card in the deck that forms a Set with them, so the odds that three random cards form a Set is one over the number of cards in the deck minus two, or 1/79. Wikipedia confirms these numbers if not the reasoning behind them. This even solves our earlier problem about the number of possible Sets in a game with n attributes, because the only thing in our math that changes with a different number of attributes is the deck size, which is now equal to 3^n. Thus, the number of possible Sets in a game with n attributes, assuming there is exactly one card for every combination of attributes, is (3^n * (3^n -1)) / (6), which simplifies to (3^(2n -1) - 3^(n-1)) / 2.

Also interesting is the actual playing of Set. If we want to write a program to analyze an array of cards and select Sets from it, we have an huge selection of options. Perhaps the most tempting is just to create a list comprehension that looks at every triplet of cards and checks if it is a valid Set. This would be easy to implement, but would have something like O(n^3) runtime because it runs its large, complex operation for every possible triple of cards, which, if there are n cards, means that it runs (n)(n-1)(n-2) times. Reducing the runtime significantly below that is hard, because we fundamentally working with all possible triples (Assuming we don't just use some massive hash table of all possible groups of cards), and this lends itself heavily to what is essentially a triple nested loop, but we can optimize a lot by instead looking at every pair of cards, computing the third card necessary, and searching for it. Code to do that is shown below.

1 get_third_card :: [Int] -> [Int] -> [Int]
3 get_third_card card0 card1 = zipWith (-) [3,3,3,3] (map `mod` 3 (zipWith (+) card0 card1))

This is an improvement because the computationally expensive step is only performed a bit less than n^2 times, while the computationally cheap comparison takes up the rest of the cycles. Working this into actual code, we can see an improvement of almost n - 2 times, where n is the number of cards we are analyzing. Below is a four-line program to get a Set from a given group of cards.

1 cards = [a bunch of four-element arrays]
3 get_third_card :: [Int] -> [Int] -> [Int]
4 -- This is just a type definition.  It's a bit like declaring variables with types is a C like language.
5 get_third_card card0 card1 = zipWith (-) [3,3,3,3] (map (`mod` 3) (zipWith (+) card0 card1))
6 -- The third card will sum with the first two to [0, 0, 0, 0] mod 3, see code above for why
7 Set  = head [ [a,b,c] | a <- cards, b <- cards, c <- cards, get_third_card a b == c]
8 -- The Set found is just the first from the list of valid Sets.

One of the reasons I love Haskell is that it's possible to write an AI for a complex board game in four relatively simple lines of code, and that the way the algorithm plays Set is more or less the same way I do.