by People are very good at seeing patterns, or features that people might recognize again. For example, ancient Polynesians navigated across the Pacific Ocean recognizing many patterns, from star constellations to more subtle ones such as the directions and sizes of ocean swells.
Recently, mathematicians like myself have begun to study large collections of objects that do not have any particular patterns. How large can collections be before a specified pattern must appear somewhere in the collection? Understanding such scenarios can have significant real-world implications: For example, what is the smallest number of server failures that would take the internet apart?
Research by mathematician Jordan Ellenberg at the University of Wisconsin and researchers at Google’s Deep Mind has proposed a new approach to this problem. Their work uses artificial intelligence to find large collections that do not contain a specified pattern, which can help us understand some worst-case scenarios.
Patterns in the card game Set
The idea of a collection without a pattern 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. They vary in number, colour, shape and shading. Each of these four elements can have one of three values.
Participants race to search for “sets,” which are groups of three cards in which each feature is either the same or different in each card. For example, cards with one solid red diamond, two solid green diamonds and three solid purple diamonds form: The three have different numbers (one, two, three), the same shading (solid), different colors (red, green, purple) and the same shape (diamond).
A set can usually be found – but not always. If none of the players can get a set from the 12 cards on the table, then they pass over three more cards. But they may not be able to find a set in these 15 cards just yet. The players continue to flip over cards, three at a time, until someone sees a set.
So what is the maximum number of cards you can lay out without making a set?
In 1971, the mathematician Giuseppe Pellegrino showed that the largest collection of cards without a set is 20. But if you picked 20 cards at random, “no set” would only happen about one trillion times. And solving these “no set” collections is a very difficult problem.
Finding ‘no set’ with AI
If you wanted to find the smallest collection of cards with no set at all, you could, in principle, do an exhaustive search of every possible collection of cards chosen from the 81-card deck. But there are many possibilities – about 1024 (that’s “1” followed by 24 zeros). And if you increase the number of card features from four to, say, eight, the complexity of the problem would overwhelm any computer that would exhaustively search for “no set” collections.
Mathematicians love to think about computationally difficult problems like this. These complex problems, if dealt with in the right way, can be traced.
The best cases are easier to find – here, that would mean the fewest number of cards a set could contain. But there are few well-known strategies that can explore bad situations – here, that would mean a large collection of cards that don’t have a suit.
Ellenberg and her colleagues tackled the problem with a type of AI called large language models, or LLMs. The researchers first wrote computer programs that generate several examples of collections with many containing no set. These collections usually have “cards” with more than four elements.
They then gave these programs to the LLM, who soon learned to write many similar programs and select the ones that resulted in the largest free collections of sets to repeat the process. Repeating that process by changing the most successful programs over and over again enables them to find larger and larger collections without sets.
This method allows people to explore unordered collections – in this case, collections of cards that do not contain a set – in a whole new way. It does not guarantee that researchers will find the worst case, but they will find cases that are much worse than random generation would produce.
Their work can help researchers understand how events could align in a way that would lead to catastrophic failure.
For example, how vulnerable is the electrical grid to a malicious attacker who destroys selected substations? Say it’s a bad collection of substations that don’t form a grid connection. The worst case scenario now is a very large number of substations that, when they are all taken together, do not yet provide a grid connection. The number of substations excluded from this collection is the smallest number that a malicious actor would need to destroy to intentionally disconnect the grid.
The work of Ellenberg and her collaborators shows another way that AI is a very powerful tool. But solving very complex problems, at least for now, still requires human intelligence to guide it.
This article is republished from The Conversation, a non-profit, independent news organization that brings you facts and analysis to help you make sense of our complex world.
It was written by John Edward McCarthy, Arts and Sciences at Washington University in St. Louis.
Read more:
John Edward McCarthy is supported in part by National Science Foundation Grant DMS 2054199. Opinions, findings, and conclusions or recommendations expressed in this material are those of the author and do not necessarily reflect those of the National Science Foundation.
