The Future of Coding: AlphaDev's Game-Changing AI-Generated Sorting Algorithms
DeepMind's AlphaDev has discovered faster sorting algorithms that can transform the foundations of computing. Sorting algorithms, which are used trillions of times a day, are crucial in our increasingly digital society and can be found in everything from ranking online search results to how data is processed on computers and phones. With the physical limits of microchips being approached, improvements to the code that runs on them are vital, especially those for sorting algorithms.
AlphaDev, which is based on AlphaZero, uses reinforcement learning to discover enhanced algorithms, surpassing those developed by scientists and engineers over decades. It starts from scratch, focusing on assembly instructions (low-level language that computers understand) rather than high-level coding languages like C++. The system believes that improvements can be found at this lower level that may be difficult to discover in higher-level coding languages.
To train AlphaDev, sorting was transformed into a single-player 'assembly game'. At each turn, AlphaDev observes the algorithm it has generated and the information in the central processing unit (CPU), then chooses an instruction to add to the algorithm. AlphaDev is rewarded for sorting numbers correctly and for how quickly and efficiently it does so.
The new algorithms discovered by AlphaDev led to improvements in the LLVM libc++ sorting library of up to 70% faster for shorter sequences and about 1.7% faster for sequences exceeding 250,000 elements. These algorithms were then reverse-engineered and translated into C++, making them available to millions of developers and companies around the world.
In addition to finding faster algorithms, AlphaDev also uncovered novel approaches. Its sorting algorithms contain new sequences of instructions that save a single instruction each time they're applied. These novel approaches, called 'AlphaDev swap and copy moves', show AlphaDev's ability to uncover original solutions and challenge the way we think about improving computer science algorithms.