This article has been reviewed according to Science X's editorial process and policies. Editors have highlighted the following attributes while ensuring the content's credibility:

fact-checked

trusted source

written by researcher(s)

proofread

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

How AI and a popular card game can help engineers predict catastrophic failure – by finding the absence of a pattern
Can you find a matching set? Credit: Cmglee/Wikimedia Commons, CC BY-SA

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.

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.

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 1024 (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 , if approached in the right way, can become tractable.

How AI and a popular card game can help engineers predict catastrophic failure – by finding the absence of a pattern
This is another version of a ‘no set,’ where no three components of a set are linked by a line. Credit: Romera-Peredes et al./Nature, CC BY-SA

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

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

Provided by The Conversation

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

Citation: How AI and a popular card game can help engineers predict catastrophic failure by finding the absence of a pattern (2024, March 26) retrieved 18 May 2024 from https://techxplore.com/news/2024-03-ai-popular-card-game-catastrophic.html
This document is subject to copyright. Apart from any fair dealing for the purpose of private study or research, no part may be reproduced without the written permission. The content is provided for information purposes only.

Explore further

Expert reveals the fascinating link between math and card shuffling

2 shares

Feedback to editors