Steven J. Brams, hailing from New York University, unveils a game that poses a challenge to artificial intelligence
Artificial intelligence (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 never to 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 it 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 beat a Chess grandmaster easily – it is the result of hours and hours of this methodical searching and recognition that we never get to see.
A game poses a challenge to artificial intelligence
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? My collaborators and I have demonstrated that AI struggles with a straightforward game called Catch-Up when the human opponent plays randomly.
The rules of Catch-Up are as follows. Before the game starts, two players agree on a set of positive numbers, excluding zero, such as 1, 2, 3, etc.
The two players take turns choosing numbers from the set. Once a number has been selected, it is deleted from the set and cannot be chosen again. The game ends when all the numbers have been selected. 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 select 1, giving a 3-3 draw.
- 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 three and guarantee a 4-2 win.
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.
More on artificial intelligence game research
This example illustrates that although Catch-Up is very simple, some strategies can lead to success, and blunders can lead to failure. We analyzed the game for sets of numbers ranging in size from 2 up to 20 numbers. 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 be thwarted by this task. Can players use particular strategies to maximize their chances of victory, for example,
by choosing as many numbers as possible on your turn to reduce the numbers available to your opponent or choosing numbers to maximize your lead over your opponent?
One strategy is to choose numbers at random. Whereas this may sound like a desultory strategy that is destined to fail, and it certainly would in Chess or Go, the peculiarities of Catch-Up lend themselves to random play. In fact, random play holds its own against non-random strategies like those just mentioned above.
So, where does this leave AI? Because AI learns by recognizing patterns, it would be able to readily identify the patterns behind non-random strategies and learn ways to circumvent them to achieve victory. But playing against a randomizing player, an AI player faces a big problem. Because there is essentially no rhyme or reason to the moves a randomizing player makes, AI could play billions of games against such a 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 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 one-third 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.
Sources
This is an abbreviated version of the script of a podcast, “A Game That Stymies AI,” which contains one color image. It is available at https://www.scipod.global/professor-steven-brams-a-game-that-stymies-ai/
A 2022 article on which the podcast is based, with references and more information on the author, appeared in the following Cambridge University magazine, Plus: Bringing Mathematics to Life: /https://plus.maths.org/content/game-stymies-ai
This work is licensed under Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International.
