In Peter Norvig’s interesting post The Odds of Finding a Set in The Card Game SET, he concludes that the odds against there being no set in 12 cards, during a game, is 16:1. This is an average value, but it doesn’t tell the whole story.
A more detailed analysis shows that the odds when playing a game of SET start off at 30:1 for the first round. Then they quickly fall, and after about the 4:th round they are 14:1 and for the next 20 rounds they slowly fall towards 13:1. So for the majority of the rounds played, the odds are between 14:1 and 13:1.
Is there a set here?
Sometime in early 2011 I stumbled upon Peter Norvig’s blog post on the SET probabilities. I had never heard of SET before, but it seemed really neat, so I ordered a deck and started playing. I also brought it along to our annual ski trip to Norway (3 families in total), and it was an immediate hit in the evenings, with the adults and kids alike.
Since several of the adults are, shall we say, mathematically inclined, we soon got into the subject of probabilities, in particular the probability of not finding a set. Once home again, I decided to write my own SET simulator and play around with it. The first one I wrote was in Ruby, and with it confirmed Peter’s findings.
Peter Norvig realized that the odds vary when playing a whole game, as opposed to simply picking 12 cards out of a shuffled full deck of 81 cards. His simulation arrives at the odds of 30:1 against there being no set in 12 cards from a full deck, and 16:1 when averaged over a whole game.
As I was playing around with my Ruby simulator, I realized two interesting things that affect the probability that Peter’s simulation arrived at:
- The odds vary quite a bit depending on how far into the game you are
- A simulation that always picks the first found set introduces a bias that is not realistic
I decided to tabulate the result per round played, or equivalently, per the number of cards left in the deck. After the first 12 cards are placed on the table, 69 cards remain in the deck. The number remaining is reduced by three with every round, until there are no cards left in the deck. When I did this, I saw that the odds start off at 30:1, but quickly (after about 4 rounds) fall down to a fairly stable level, and stay there for the remainder of the game. This is shown in the graph below (I’ll get to why there are 3 curves soon).
The graph shows that for most of the game (except for the first 4 rounds), the odds are between 14:1 and 13:1. When averaging over a whole game, the 30:1 odds in the beginning skew the result a bit (in the sense of “the most commonly encountered odds”).
The second realization I had was that Peter’s program (and, in the beginning, mine too) always took the first set it found, regardless of whether there were other possible sets to chose from. This introduces a bias in the set selection that is unrealistic. To check what difference it made, I changed my program to pick a set randomly among all the available sets each time.
In the graph above, the blue curve uses the original selection mechanism – pick the first found set – and the average odds using it are 15:1. The red curve shows the random selection mechanism, and the average odds for it are 14:1. The difference, 15:1 compared to 14:1, is not earth-shattering, but enough to notice.
When I got this far, I sent a mail to Peter, telling him what I had found. I got a very nice answer the next day (thank you Peter!), where he suggested another selection algorithm that might be even more realistic. In his words: “Even better might be to try to mimic the chances of a human selecting the set first — for example the set {1,2,3 red filled diamond} is probably easier to find than {1 green solid squiggle, 2 purple striped ovals, 3 empty red diamonds}.”
By this time the Ruby program was a bit messy, so I decided to re-write the whole thing in Java. This also sped up the simulations nicely. I added a third selection mode (cleverly named “3”), which I describe as “Random among ‘most similar’ sets”. Among all the possible sets, you first find the ones which are ‘most similar’, i.e. which have the most number of attributes the same. Then one of these sets is picked at random. The yellow curve shows the result using this selection mode, but there is not a big difference compared to pure random selection.
However, using either the pure random selection mode, or the random among the most similar sets, you can see that the odds against there being no set in 12 cards after a few rounds of play become between 14:1 and 13:1.
All of the figures in this post are from simulation runs that played 10 million games for each selection mode, using the Java program. I’ve tabulated the results in all three cases for no set among 12, 15, 18 and 21 cards (it has been shown that it is always possible to find a set among 21 cards). Here are the full simulation results for First found Set, Random among available Sets, and Random among ‘most similar’ Sets. The simulation program is available at github.
For the odds against there being no set among 15 cards, it is not relevant to pick 15 cards out of a shuffled full deck and then see how often there are no sets, since this situation never occurs during game play. You have to have had no set in 12 cards, then add three cards, and then see what the odds are. From my simulations, the odds are 90:1 when always picking the first found set, and around 88:1 for the other two selection modes. It is interesting to note that the odds in these cases don’t vary much, regardless of when in the game it is.
Some other fun statistics can be had from the simulations. For example, there are about 10 cases in each run where no set was found among 18 cards. In other words that happens in around one in a million games.
The average number of sets available to chose from when there are 12 cards on the table are 2.4, and 3.3 with 15 cards on the table. Around 31 % of the games always has a set among the 12 cards, and thus never needs to go to 15 cards. And finally, in 1 % of the games it was possible to clean up completely so no cards remain on the table in the end. In practice, this could happen a bit more often if a conscious effort is made to pick the last remaining sets in an order that facilitates cleaning up – in the simulations they are always picked according to the selection mode.
So, for next year’s ski trip, I’ve got all the probabilities worked out. All that remains for me now is to practice actually playing SET, so I’ll at least have some chance of beating my 11-year-old and 8-year-old.
Edit: If you have read this far, you may also want to read about a variation of Set called Complementary Pairs.
SET is a registered trademark and the SET cards are a copyright of Cannei, LLC. Used with permission from Set Enterprises, Inc.
Henrik Warne's blog 
Very interesting and nicely presented. An additional comment may be that while the computer really analyzes all possible combinations without making mistakes, IRL the players may sometimes jointly, but erroneously, conclude that there is no set on the table and therefore agree to lay new cards which should not have been laid. These new cards may then generate new sets the computer would never find and the result (at least temporarily?) diverging away somewhat from the outcome as emulated above. Likely a bit tricky to simulate though. Who knows how often these human mistakes happen ?
Now it anyway remains to be seen if this increased knowledge in SET probabilities gives Henrik an upper hand when playing SET at the next gathering in Norway.
When determining odds based on calculations, I come up with roughly 21:1 odds against there being no set in 12 cards from a full deck. The calculation takes the probability for each of the 220 possible combinations. For example, c1-c2-c3 has a 78/79 chance of no set, c1-c2-c4 has a 77/78 chance (one less since c3 can be removed from the equation), etc. By multiplying the 220 combinations you get .046477 or 20.516:1 odds against. Why is it that simulations have greater odds against (30:1)?
Hi Jim,
Thanks for your comment. Given 12 cards, there are 220 different 3-card combinations, and if none of these 3-card combinations form a set, then there is no set among the 12 cards. Further, the number of ways to pick 12 cards out of 81 is “81 choose 12”, or about 7.07 x 10^13. So to find the probability of no set among 12 cards chosen from 81, we would have to find how many of the 7.07 x 10^13 combinations don’t contain any set, and divide that number by 7.07 x 10^13. The problem is how to calculate how many of all those 12 card combinations don’t contain any set.
I guess you based your calculation on the fact that the probability of producing a set from 3 randomly drawn cards from a complete deck is 1/79. But multiplying this probability is only applicable if the different combinations of 3 cards are independent of each other. In the case of 12 cards, the 220 combinations of 3 cards are not independent of each other. The problem is further compounded by the fact that any given card can be part of many different sets, and you only need one combination out of the 220 to have a combination that contains a set.
Anyway, it is fascinating that the relatively simple features of Set can lead to so many interesting math problems (not to mention enjoyable game-play).
As you mentioned there are ~7.07 x 10^13 possible 12 card deals that the game could start off with (i.e. round 1). Your simulation involved only 10 million different games so there were only 10 million different starting deals that your simulation saw. That is a very small fraction of the total possible 12 card deals (~1.41 × 10^-7 to be exact). How can you claim the results of your simulation to be statistically significant?
Hi Eric,
Good comment! I agree that the simulations only cover a fraction of all possible games, but I believe (without being able to prove it) that the simulated games are representative of the total distribution of games with regards to the different probabilities. But I am always interested in hearing about improvements in methodology, or alternative ways of finding the probabilities (including finding analytical expressions).
There are some additional comments on the results pages here and here.
I’m curious to find out what blog system you’re using? I’m experiencing some small security problems with my latest blog and I’d like to find something more safe. Do you have any suggestions?
I am using wordpress.com (with the Coraline theme).
Hmm. By my exact computations, your estimates of the average number of sets in an array are off by about 0.4 in the case of twelve cards and by over 2 in the case of fifteen cards. I am dubious of your latter calculation. What are your confidence intervals?
I’d share my method, but I intend to publish this problem in a journal (e.g., The American Mathematical Monthly). I found this site when researching if the problem had been considered before. BTW, one can also determine the variances.
Oh, wait a minute. I guess your averages apply to all the boards in a game. My calculations apply to only the first twelve cards dealt. I see the discrepancy now. Each time you remove a set from the deck, the number of remaining sets reduces quite a bit. For example, after removal of the first set, the number of set in the deck is reduced by 238. Also, you deal out fifteen cards (i.e., three more) only if you know there are no sets in the first twelve.
Yes, the average number of sets available (2.4) is across all rounds of a game. In the tables, the number of sets is listed per round of play. So the average number of sets among 12 cards drawn from a full deck (i.e. 69 cards remaining in the deck) is 2.78 in my simulations (which I guess agrees with your result since it is around 0.4 more than 2.4). And as you point out, you only go to 15 cards if there was no set among the 12 previous cards.
It would be interesting to read your paper – feel free to add a link to it when it has been published.
My daughter and I tried to solve this problem more or less rigorously today. We reformulated it as follows. We add one card at a time to the pile untill we reach 12 cards. What is the probability P that we end up with no sets at the 12th step of this process?
Tentative solution:
P(no set at step 12)=P(no set at step 1) x P(no set at step 2) x … x P(no set at step 12);
where
P(no set at step n)=1-P(at least one set exactly at step n);
The latter we compute as:
P(at least one set exactly at step 1)=0
P(at least one set exactly at step 2)=0
P(at least one set exactly at step 3)=1/79
P(at least one set exactly at step 4)=P(no set at step 3) x (1/78) x (ways to choose 2 cards out of 3)
P(at least one set exactly at step 5)=P(no set at step 4) x (1/77) x (ways to choose 2 cards out of 4)
…
P(at least one set exactly at step 12)=P(no set at step 11) x (1/70) x (ways to choose 2 cards out of 11)
A simple iterative routine in Python gives the answer:
P(no set at step 12)=0.0704595188679
I am not sure, what exactly the term “odds” means. However, following the calculations of Jim above we get 1/0.0704595188679:1 or 14.2:1
This seems close to the lower part of the simulated graph.
Cheers.
Hi Neil,
Thanks for reading, and for reporting your findings. I used odds since Peter Norvig used it in his blog post, and I think he in turn used odds (as opposed to probability) since the SET manual uses it.
The odds are simply the number of favorable outcomes divided by the number of unfavorable outcomes. For example, what are the odds of not rolling a 1 when rolling a regular 6-sided die? There are 5 outcomes that are not a 1 (getting 2, 3, 4, 5 or 6), and only one outcome that is a 1. Therefore the odds are 5:1. So odds are related to the probability, but not quite the same.
I don’t quite follow your calculations. You use “at least one set exactly” – but what about cases where there are more than one set present? I also think it is quite difficult to come up with the expression for the probability of getting a set when there are already many cards present, simply because sets can be formed in so many ways.
In my simulations, the odds of no set in a random draw of 12 cards from the deck (i.e. the first round of play) are 29.9:1. This can be seen from the first line (69 cards in the deck) of the results shown in Random among available Sets. It is only after a few rounds of play that the odds fall to 14:1.
After I published my findings, I found the Donald Knuth had written a program to enumerate all cases of no sets in n cards drawn at random (refered to in the answer here). The values given for n=12 work out to odds of about 29.958:1, which is close enough to what I found in my simulation to make me believe that my results are correct.
Anyway, thanks again for your comment. It definitely is fun to try to figure out the probabilities of Set – even the great Donald Knuth thought it was worth investigating, so we are in good company.
Hi Henrik,
Thanks for explaining the odds to me! Yes, it is a very interesting problem, indeed. Of course, you are right. There are, in fact, several “approximations” in our calculations:
1) The assumption that the total probability is the product of probabilities is only true for independent events which may not be the case here.
2) I should have written “at least one set, exactly at step n” – comma is missing 🙂 The term “at least one set” is supposed to take care of all the ways that sets can be formed at a given step. In our calculation we simply add up the probabilities of getting each of the possible sets for the n-1 cards on the table. That is why we multiply each term of our recurrence relation by the “ways to choose 2 cards out of n-1”, i.e., C(n-1,2). However, of course, we cannot interpret “1/(81-(n-1)) times C(n-1,2)” as a genuine probability for a large number of steps, since it becomes greater than one already at step 13. The reason behind this is the possibility for one new card to form several sets simultaneously with different pairs on the table. In that case we cannot add all the different probabilities as the events are not mutually exclusive. Unfortunately, the exact combinatorics becomes pretty complex here.
4) We write “exactly at step n” to make sure that the set has not yet been formed at the previous step. So, we multiply by P(no set at step n-1). This shows that we cannot actually assume that the steps (n-1) and n are independent: probability to have no set (exactly) at step n depends on the probability to have no set at step n-1, etc.
5) Finally, as a result of all these “approximations”, our algorithm computes P=3.3e-6 for step n=21, but it should be exactly zero at n=21, since 20 is the maximal number of cards without a set. So, that clearly indicates that our combinatorics is off.
It was funny though (perhaps pure luck) to see your 14:1 odds to come out of such a simple albeit approximate calculation. I think it should be possible to work around some of the problems mentioned above to get the 29.9:1 result. Anyway, thanks for sharing!
Pingback: Clearing the table in the game SET® | mitchell faulk's blog
Great post on how to end up with no cards left on the table:
A book on SET (referencing this post in the bibliography):
“The Joy of Set: The Many Mathematical Dimensions of a Seemingly Simple Card Game”
https://www.goodreads.com/book/show/30009098-the-joy-of-set
Pingback: Revisiting “SET® Probabilities Revisited” | mitchell faulk's blog
Pingback: Clearing the table in the game SET® (Part 2) – mitchell faulk's blog
Pingback: Clearing the table in the game SET® (Part 3) – mitchell faulk's blog