Algorithm Generation

The goal of this project is to teach AI to devise and implement better algorithms than human programmers. This is done in a self-play loop using language models (such as GPT) to generate and solve their own novel programming problems. In order to describe these algorithms challenges, we focus on challenges where the success criteria can be described by a program, rather than English or examples. This includes problems ranging for trivial sorting tasks to classic puzzles, such as the Towers of Hanoi or the Sliding 15 puzzle, to super-hard algorithmic challenges like integer factorization. All major algorithmic tools, such as recursion, dynamic programming, and depth-first search, are useful in solving these problems. Take a look at our open-source Python Programming Puzzles dataset (opens in new tab) for some examples, or read our papers (opens in new tab).

Building such a system not only has the potential to lead to breakthroughs in the field of algorithms, but may also lead to improvements in other AI program synthesis systems. For example, current AI coding completion systems, like the impressive GitHub Copilot (opens in new tab), have a wide breadth of knowledge and predictive power, but still lack certain coding “common sense” that is possessed by novice programmers. To make matters worse, these AI systems must deal with understanding English task descriptions while they are trying to learn to code. In this project, we teach computers to code using program-based specifications, so the AI systems must learn to understand programs rather than deal with all the ambiguities of English or examples while learning to program.