Google DeepMind has made groundbreaking advancements in the field of AI with its Alpha series. Widely recognized for AlphaGo’s victory over the world champion in the ancient game of Go, DeepMind has since ventured into various domains. AlphaFold and AlphaCode, are another offsprings of the Alpha AI, where one revolutionized protein structure analysis, and the latter was hailed as having the potential to beat computer programmers by parsing algorithms and generating complex programs.
Google DeepMind has now introduced AlphaDev — a faster algorithm for sorting, a method for ordering data. Sorting algorithms underpin everything from ranking online search results and social posts to how data is processed on computers and phones. Using reinforcement learning, AlphaDev has discovered enhanced computer science algorithms, outperforming those that have been refined by scientists and engineers over decades.
The new sorting algorithms discovered by AlphaDev are up to 70% faster for shorter sequences and about 1.7% faster for sequences exceeding 250,000 elements.
These algorithms are now open-sourced in the main C++ library, making them accessible to millions of developers and companies worldwide. This marks the first change to this part of the sorting library in over a decade, and the first time an algorithm designed through reinforcement learning has been added to this library.
AlphaDev’s approach to uncovering these faster algorithms began at the computer’s assembly instructions. Assembly instructions are used to create binary code for computers to put into action. While developers write in coding languages like C++, this must be translated into ‘low-level’ assembly instructions for computers to understand.
AlphaDev transformed sorting into a single-player’ assembly game’. At each turn, AlphaDev observes the algorithm it has generated and the information contained in the CPU. Then it plays a move by choosing an instruction to add to the algorithm.
After discovering faster sorting algorithms, DeepMind tested whether AlphaDev could generalize and improve a different computer science algorithm: hashing. Hashing is a fundamental algorithm in computing used to retrieve, store, and compress data. When applied to the 9-16 bytes range of the hashing function, the algorithm that AlphaDev discovered was 30% faster.
DeepMind sees AlphaDev as a step towards developing general-purpose AI tools that could help optimize the entire computing ecosystem and solve other problems that will benefit society. While optimizing in the space of low-level assembly instructions is very powerful, there are limitations as the algorithm grows. DeepMind is currently exploring AlphaDev’s ability to optimize algorithms directly in high-level languages such as C++, which would be more useful for developers.
