tommyodland.com

The card game “SET” as a binary Integer Program

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

\begin{align} x_{i}= \begin{cases} 1 \quad \text{ if card } i \text{ is chosen }\\ 0 \quad \text{ otherwise}. \end{cases} \end{align}

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

\begin{align} \sum_i x_i = 3. \end{align}

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

\begin{align} c_{iv}= \begin{cases} 1 \quad \text{ if card } i \text{ has color } v\\ 0 \quad \text{ otherwise}. \end{cases} \end{align}

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

\begin{align} N_v = \sum_i x_i c_{iv} \qquad \forall \ v. \end{align}

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.”

\begin{align} (N_1 = 1 \wedge N_2 = 1 \wedge N_3 = 1) \vee ((N_1 = 3 \vee N_2 = 3 \vee N_3 = 3)) \end{align}

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

\begin{align} y = \begin{cases} 1 \quad \text{ if the chosen cards have different colors}\\ 0 \quad \text{ otherwise}. \end{cases} \end{align}

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

\begin{align} z_v = \begin{cases} 1 \quad \text{ if the chosen cards all have color } v\\ 0 \quad \text{ otherwise}. \end{cases} \end{align}

The constraints become

\begin{align} N_v &= y + 3z_v \quad \forall \ v \\ \sum_v z_v &= 1 - y. \end{align}

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

\begin{align} & \text{maximize} && \sum_i x_i \\ & \text{subject to} && \sum_i x_i = 3 && \\ & && \sum_i x_i c_{iv} = y + 3z_v && \forall \, v \\ & && \sum_v z_v = 1 - y && \\ & && x_{i}, z_v, y \in \{0, 1\}. && \\ \end{align}

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

\begin{align} d_{ipv}= \begin{cases} 1 \quad \text{ if card } i \text{ has value } v \text{ for property } p\\ 0 \quad \text{ otherwise}. \end{cases} \end{align}

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

\begin{align} & \text{maximize} && \sum_i x_i \\ & \text{subject to} && \sum_i x_i = 3 && \\ & && \sum_i x_i d_{ipv} = y_p + 3z_{pv} && \forall \, (p, v) \\ & && \sum_v z_{pv} = 1 - y_p && \forall \, p \\ & && x_{i}, z_{pv}, y_p \in \{0, 1\}. && \\ \end{align}

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.