An AI system based on Google DeepMind’s AlphaZero AI created algorithms that, when translated into the standard programming language C++, can sort data up to three times as fast as human-generated versions. Computer scientists have, for decades, been optimizing how computers sort data to shave off crucial milliseconds in returning search results or alphabetizing contact lists. Now DeepMind, based in London, has vastly improved sorting speeds by applying the technology behind AlphaZero (its AI system for playing the board games chess, Go and shogi) to a game of building sorting algorithms. The system, AlphaDev, has invented faster algorithms that are already part of two standard C++ coding libraries, so are being used trillions of times per day by programmers around the world. The researchers first applied AlphaDev to the task of sorting numbers by size. They started small, with algorithms that sorted only 3, 4, or 5 numbers at a time, but these are important because they’re used by algorithms that sort longer lists.
AlphaDev operated at the level of assembly instructions: code generated by automated compilers from code that programmers write in C++, before it is translated into the 1s and 0s of machine code. AlphaDev works similarly to its predecessor, AlphaZero, which combines computer versions of deliberation and intuition to choose moves in a board game2. AlphaDev can take one of four types of actions that involve comparing values, moving values between locations, or jumping to a different part of the program. After each step, it tries sorting a set of lists and receives a reward for how many items in the lists it sorted correctly. It plays until it sorts all the lists perfectly or reaches a program length limit, then starts a new program from scratch. The DeepMind team also applied AlphaDev to non-sorting algorithms. Its version of an algorithm used to convert data stored in a particular format into bytes took 67% less time than a standard version. And its hashing algorithm took 30% less time than a standard one.
More information: