**Need help with data science or mathematical modeling?**I do consulting work in Norway. Read about my previous work experience and reach out to me for more information.

# The card game “SET” as a binary Integer Program

- 5. December 2019 (modified 13. December 2019)
- #optimization

The card game “SET” works as follows: 12 cards are put on a table, and the player that first finds a valid combination of 3 cards wins a point.
Each card has four *properties*: color, shape, number of shapes and fill.
See the picture below.
Each property has 3 possible *values*, and each card has one value for each property, e.g. the color of a specific card may be green, purple or red.

For each property, the chosen combination of 3 cards must either have all different values, or all equal values. For instance, the color of the three cards can be “green”, “purple” and “red” (all different) or “green”, “green” and “green” (all equal).

When you play “SET,” you feel like you’re running a graph search on a feasibility problem.

Let’s formulate it as a binary Integer Program and give it to a solver.

## Table of contents

## “SET” with color as the only property

We first solve a special case in which there is only one property: color. The three chosen cards must either all have the same color, or all have different colors. Once we have solved this special case we will be prepared to solve the general case.

To start, we define decision variables \(x_i\) as

Since we are picking three cards, the first constraint is naturally

From the cards on the table we get a parameter \(c_{iv}\), which we define as

Since each card must have one and only one color, the parameter must obey \(\sum_v c_{iv} = 1\) for all cards \(i\).

Let \(N_v\) be the number of cards with color \(v\) chosen. Then \(N_v\) can be expressed as the sum

There are three colors, e.g. \(v=1\) is “green”, \(v=2\) means “purple” and \(v=3\) means “red.” Now that we have introduced the obvious variables we need, we turn our attention to the more challenging task of writing logical constraints as strict inequalities.

### Linearizing the logical constraints

Recall that the chosen combination of 3 cards must either have all different colors, or all equal colors. For instance, the color of the three cards can be “green”, “purple” and “red” (all different) or “green”, “green” and “green” (all equal).

The following logical constraints mean “either all colors are different, or all are equal.”

A more verbose equation would lead to explicitly constraining the colors that do not appear \(3\) times to appear exactly \(0\) times, but this is already handled by the constraint \(\sum_i x_i = 3\).

We now introduce some additional binary variables. It’s not immediately obvious, but these variables will capture the required logic. It helps to write out a small example by hand while studying the equations.

The logical constraints above can be linearized by introducing a binary variable \(y\) with the interpretation

Finally we introduce binary variables \(z_v\) with the interpretation

The constraints become

The reader is advised to run through the equations above mentally. If \(y=0\), then one of the \(z_v\) must be \(1\) and the remaining must be \(0\). If \(y=1\), then all of the \(z_v\) must be \(0\).

### Full binary IP for “SET” with color as the only property

Below I have removed the auxiliary variable \(N_v := \sum_i x_i c_{iv}\) and substituted \(\sum_i x_i c_{iv}\) directly.

The binary IP becomes

Let’s generalize to every property instead of just colors.

## The card game “SET” as a binary IP

Let’s solve the general case with many properties, not just color. We define \(x_i\) as \(1\) when card \(i\) is picked, just like we did in the section above.

Instead of defining colors by \(c_{iv}\), we introduce a more general parameter \(d_{ipv}\) as

This parameter is constrained by \(\sum_v d_{ipv} = 1\) for every card \(i\) and property \(p\).

- The variables \(z\) are now specific to both properties and values, so we need two subscripts: \(z_{pv}\).
- Similarly, we need one \(y\) for every property, so we need a subscript: \(y_p\).

The full binary IP becomes

# Summary

We have reduced the popular card game “SET” to a binary integer program. The solver employs sophisticated search algorithms to find solutions faster than a human ever could.

Someone noted that I probably enjoy reducing games to mathematical problems because it makes them less interesting, and if they are uninteresting it justifies how bad I am at them. This might be true - I did lose every round of “SET” when I played it.