FunSearch, an artificial intelligence system based on large language models, has made groundbreaking progress in solving combinatorial problems inspired by the card game Set. The method, described in Nature, showcases the potential for AI to generate new mathematical solutions and could have far-reaching applications in various fields.
The game Set, known for its intricate combinations of cards based on shape, color, shading, and number of symbols, has long captivated mathematicians. Now, a breakthrough AI system called FunSearch, powered by large language models (LLMs), is demonstrating that artificial intelligence can push the boundaries of mathematical problem-solving. FunSearch has made significant advancements in combinatorics, a branch of mathematics that explores the counting and arrangement of sets with a finite number of objects. By leveraging the capabilities of LLMs, FunSearch has surpassed existing knowledge in the field, opening up new possibilities for mathematical exploration.
The Power of Language Models in Mathematics:
Pushmeet Kohli, head of the AI for Science team at Google DeepMind, emphasizes that FunSearch represents the first instance in which an LLM-based system has surpassed known mathematical solutions. Previous experiments with large language models focused on solving problems with established solutions. FunSearch, however, breaks new ground by utilizing LLMs to generate novel solutions that outperform existing ones. This breakthrough showcases the potential of AI to enhance mathematical research and computer science.
The Creativity Engine:
FunSearch functions as a creativity engine, automatically generating requests for a specially trained LLM to write computer programs capable of solving specific mathematical problems. The system then evaluates these solutions against known ones, providing feedback to the LLM to refine its approach in subsequent rounds. While not all programs generated by the LLM prove useful, the system rapidly filters out incorrect solutions, allowing for efficient testing of the correct ones.
Exploring the Cap Set Problem:
The team behind FunSearch tested its capabilities on the “cap set problem,” which originated from the game Set. Invented by geneticist Marsha Falco in the 1970s, Set features a deck of 81 cards, each displaying one, two, or three symbols that share identical color, shape, and shading. Mathematically, this translates to 3 × 3 × 3 × 3 = 81 possible combinations. The objective of the game is to identify special sets of three cards. While mathematicians have determined that players are guaranteed to find a set if at least 21 cards are revealed, more complex versions of the game with five or more properties present unsolved mysteries. For instance, the minimum number of cards required to guarantee a solution remains unknown when there are n properties, where n is any whole number.
FunSearch’s Advancements:
FunSearch successfully improved the lower bound for n = 8 by generating sets of cards that satisfy all the game’s requirements. Although the team did not prove that further improvement is impossible, they did surpass previous knowledge by providing a construction that goes beyond existing solutions. Notably, FunSearch’s approach enables human mathematicians to study and learn from the successful programs created by the LLM, setting it apart from other AI applications that operate as black boxes.
Conclusion:
The groundbreaking achievements of FunSearch, an AI system based on large language models, demonstrate the potential for artificial intelligence to revolutionize mathematical problem-solving. By leveraging LLMs, FunSearch has surpassed known solutions in combinatorics, offering new insights and possibilities for mathematicians and computer scientists. The collaboration between humans and machines, facilitated by FunSearch’s transparency, presents an exciting new model for future exploration and innovation in the field of mathematics. While AI systems like FunSearch will not replace human mathematicians, they serve as powerful tools to augment and amplify human capabilities, driving progress in mathematics and beyond.
