AI appears all-powerful when playing sophisticated games such as Chess and Go against human opponents. Moreover, recent developments in AI have allowed it to summarize bodies of complex text, generate images and even video. These developments come with warnings that AI could replace many jobs, undermine democratic elections or even pose a threat to the existence of humanity. However, AI is largely based on observing and learning patterns; so, what happens when there are no patterns? Professor Steven Brams of New York University and colleagues have analyzed the potential of beating AI when playing a deceptively simple game called Catch-Up, simply by making random moves. More

AI has enormous promise and huge risk. It is poised to become a significant disruptive force. However, much of the analysis of AI in the popular media leans on hype rather than fact. Understanding how AI functions, along with appraising some of its strengths, blind spots and weaknesses, may help to demystify this technology and allow us to assess its risks and potential more realistically.

Whereas fears about AI are justified, at its heart it is a sophisticated pattern recognition tool. These impressive pattern recognition properties, such as recognizing tiny subtleties in a medical image that betray the presence of a tumor, for example, are based on a computer’s ability to never tire, lose concentration or become bored, while analyzing thousands of medical images over thousands of hours.

This extensive training process is essential for AI to learn new skills. For instance, training an AI system to play Chess involves its playing itself over and over in thousands of games, each time learning new patterns that lead to victory. While the resulting pattern recognition may seem almost miraculous, allowing a computer to easily beat a Chess grandmaster, it is the result of hours and hours of this methodical searching and recognition that we never get to see.

This ability to recognize patterns that would escape most humans is both AI’s greatest strength and weakness. What happens if there is no pattern? This question is at the heart of research conducted by Brams and collaborators when they demonstrated that AI struggled with a very simple game called Catch-Up when the human opponent played randomly.

The rules of Catch-Up are as follows. Before the game starts, two players agree on a set of natural numbers. Natural numbers are essentially ‘counting numbers’, meaning positive numbers, excluding zero. Examples include 1, 2, 3, etc.

The two players take turns choosing numbers from the set. Once a number has been chosen, it is deleted from the set and cannot be chosen again. The game ends when all the numbers have been chosen and added together. If the sum of one player‘s numbers is greater than the other player’s sum, then that player wins and, if not, the game ends in a draw.

Call the player to take the first turn A, and the other player B. At the start, A can choose any number. Thereafter, the players take turns choosing a number, or a set of numbers, that equals or just exceeds the other player’s sum. This means that at every turn the winning player loses its lead when its opponent ties or just exceeds its sum. Consequently, neither player stays ahead for more than one turn.

We start with a simple example, in which the numbers are 1, 2, and 3. A can choose any one of the three numbers in the beginning, which can lead to different responses by B

- If A chooses 3, B can choose 1 and 2, in either order, and guarantee a 3-3 draw.
- If A chooses 2, B can choose 1 and 3 in that order and guarantee a 4-2 win. But if B chooses just 3, A can then choose 1, giving a 3-3 draw, which is an inferior outcome for B but better for A.
- If A chooses 1, B can choose 3, which guarantees a 3-3 draw when A chooses 2. But if B chooses 2, A can choose 3 and guarantee 4-2 win, which is a superior outcome for A but an inferior outcome for B.

Clearly, there are better or worse choices that each player can make, which can lead to wins, draws, or losses for either. Overall, A can guarantee at least a draw by choosing 1 or 3 at the outset, but it will lose if it chooses 2 and B follows with 1 and 3 in that order.

The example illustrates that although Catch-Up is very simple, there are some strategies that can lead to success, and blunders that can lead to failure. The researchers analyzed the game for sets of numbers ranging in size from just two numbers up to 20 numbers. They report that if the sum of all the numbers in the set is odd, then optimal play will result in victory for either player by a margin of 1. If the sum of the numbers in the set is even, then optimal play will result in a draw.

Determining the optimal move to make at any given juncture, however, is easier said than done, particularly for large sets of numbers. Even computers can struggle with this. Can players use particular strategies to maximize their chances of victory? Examples include choosing as many numbers as possible on your turn to reduce the numbers available to your opponent, choosing numbers to maximize your lead over your opponent or choosing numbers to minimize your lead, which restricts your opponent’s options, because it cannot massively exceed your running total on their turn.

Another strategy is to choose numbers at random. Whereas this may sound like a mindless strategy that is destined to fail, and it certainly would be in Chess or Go, the peculiarities of Catch-Up lend themselves to random play. The rules of the game mean that neither player ever has a devastating lead over the other, so there is everything to play for right to the end of the game. The researchers have analyzed the potential of random play against the other three non-random strategies by getting a computer to play itself thousands of times.

They found that random play wins 41.7% of the time against an opponent who acts to maximize its lead, 60.9% of the time against an opponent that minimizes its lead and 46.5% of the time against an opponent who picks as many numbers as possible. This illustrates that random play is not a bad strategy in Catch-Up.

So, where does this leave AI? How would it fare against the strategies above? Interestingly, as AI learns by recognizing patterns, it would be able to readily identify the patterns behind the three non-random strategies, and likely learn ways to circumvent them to achieve victory. A non-random player employing a specific strategy will always perform the same move given the same situation if playing optimally, making the non-random player vulnerable to a machine’s relentless ability to recognize and respond to play patterns.

However, the random player is a little different, as there is essentially no rhyme or reason to the moves it makes. The AI system could play billions of games against a random player, and still be no wiser as to how to beat it reliably. Intriguingly, this suggests that Catch-Up is likely beyond AI systems as they currently stand, despite its relative simplicity and the mindless nature of random play.

An AI player faces a similar problem against a randomizing player in Rock, Paper, Scissors, who on average chooses each object 1/3 of the time but doesn’t always come out ahead in the end. In Catch-Up, by contrast, there is a sure-fire winning strategy if the sum of the numbers is odd, but the AI player may not be able to discover it and, therefore, thwart it. Thus, the AI player may lose in Catch-Up when winning is possible and so be stymied.