How AI and a popular card game can help engineers predict catastrophic failure – by finding the absence of a pattern

March 27, 2024

By John Edward McCarthy, Arts & Sciences at Washington University in St. Louis

Humans are very good at spotting patterns, or repeating features people can recognize. For instance, ancient Polynesians navigated across the Pacific by recognizing many patterns, from the stars’ constellations to more subtle ones such as the directions and sizes of ocean swells.

Very recently, mathematicians like me have started to study large collections of objects that have no patterns of a particular sort. How large can collections be before a specified pattern has to appear somewhere in the collection? Understanding such scenarios can have significant real-world implications: For example, what’s the smallest number of server failures that would lead to the severing of the internet?

Research from mathematician Jordan Ellenberg at the University of Wisconsin and researchers at Google’s Deep Mind have proposed a novel approach to this problem. Their work uses artificial intelligence to find large collections that don’t contain a specified pattern, which can help us understand some worst-case scenarios.

Can you find a matching set?
Cmglee/Wikimedia Commons, CC BY-SA

Patterns in the card game Set

The idea of patternless collections can be illustrated by a popular card game called Set. In this game, players lay out 12 cards, face up. Each card has a different simple picture on it. They vary in terms of number, color, shape and shading. Each of these four features can have one of three values.

Free Reports:

Sign Up for Our Stock Market Newsletter – Get updated on News, Charts & Rankings of Public Companies when you join our Stocks Newsletter

Get our Weekly Commitment of Traders Reports - See where the biggest traders (Hedge Funds and Commercial Hedgers) are positioned in the futures markets on a weekly basis.

Players race to look for “sets,” which are groups of three cards in which every feature is either the same or different in each card. For instance, cards with one solid red diamond, two solid green diamonds and three solid purple diamonds form a set: All three have different numbers (one, two, three), the same shading (solid), different colors (red, green, purple) and the same shape (diamond).

Marsha Falco originally created the game Set to help explain her research on population genetics.

Finding a set is usually possible – but not always. If none of the players can find a set from the 12 cards on the table, then they flip over three more cards. But they still might not be able to find a set in these 15 cards. The players continue to flip over cards, three at a time, until someone spots a set.

So what is the maximum number of cards you can lay out without forming a set?

In 1971, mathematician Giuseppe Pellegrino showed that the largest collection of cards without a set is 20. But if you chose 20 cards at random, “no set” would happen only about one in a trillion times. And finding these “no set” collections is an extremely hard problem to solve.

Finding ‘no set’ with AI

If you wanted to find the smallest collection of cards with no set, you could in principle do an exhaustive search of every possible collection of cards chosen from the deck of 81 cards. But there are an enormous number of possibilities – on the order of 10²⁴ (that’s a “1” followed by 24 zeros). And if you increase the number of features of the cards from four to, say, eight, the complexity of the problem would overwhelm any computer doing an exhaustive search for “no set” collections.

Mathematicians love to think about computationally difficult problems like this. These complex problems, if approached in the right way, can become tractable.

It’s easier to find best-case scenarios – here, that would mean the fewest number of cards that could contain a set. But there were few known strategies that could explore bad scenarios – here, that would mean a large collection of cards that do not contain a set.

Ellenberg and his collaborators approached the bad scenario with a type of AI called large language models, or LLMs. The researchers first wrote computer programs that generate some examples of collections of many that contain no set. These collections typically have “cards” with more than four features.

Then they fed these programs to the LLM, which soon learned how to write many similar programs and choose the ones that give rise to the largest set-free collections to undergo the process again. Iterating that process by repeatedly tweaking the most successful programs enables them to find larger and larger set-free collections.

Square of nine circles, four of which are colored blue, connected by grey, red, green, and yellow lines — This is another version of a ‘no set,’ where no three components of a set are linked by a line.
Romera-Peredes et al./Nature, CC BY-SA

This method allows people to explore disordered collections – in this instance, collections of cards that contain no set – in an entirely new way. It does not guarantee that researchers will find the absolute worst-case scenario, but they will find scenarios that are much worse than a random generation would yield.

Their work can help researchers understand how events might align in a way that leads to catastrophic failure.

For example, how vulnerable is the electrical grid to a malicious attacker who destroys select substations? Suppose that a bad collection of substations is one where they don’t form a connected grid. The worst-case scenario is now a very large number of substations that, when taken all together, still don’t yield a connected grid. The amount of substations excluded from this collection make up the smallest number a malicious actor needs to destroy to deliberately disconnect the grid.

The work of Ellenberg and his collaborators demonstrates yet another way that AI is a very powerful tool. But to solve very complex problems, at least for now, it still needs human ingenuity to guide it.

John Edward McCarthy, Professor of Mathematics, Arts & Sciences at Washington University in St. Louis

This article is republished from The Conversation under a Creative Commons license. Read the original article.