DeepMind built sorting algorithms using the technology underlying AlphaZero for playing board games. Based on Google DeepMind's AlphaZero AI, an AI system made algorithms that, when translated into the standard programming language C++, can sort data up to three times faster than human-generated versions.

For decades, computer scientists have optimized how computers sort data to save key milliseconds when delivering search results or alphabetizing contact lists. DeepMind, located in London, has now dramatically improved sorting speeds by adapting the technology behind AlphaZero — their AI system for playing chess, Go, and shogi — to the game of constructing sorting algorithms. AlphaDev's approach has created faster algorithms already part of two mainstream C++ coding libraries and is utilized trillions of times per day by programmers worldwide.

AlphaDev 

AlphaDev was initially used by the team to sort numbers by their respective sizes. These algorithms began tiny, sorting only 3, 4, or 5 integers at a time; yet, they are crucial because they are employed by algorithms sorting longer lists. The instructions executed by AlphaDev were at the assembly level, which is the last step before the 1s and 0s of machine code are created from the C++ code written by programmers. Like its forerunner AlphaZero, AlphaDev uses a computational hybrid of deliberate thought and gut instinct to make strategic decisions during board games. Instead of selecting actions, AlphaDev selects code to insert into a method in a game developed by DeepMind's programmers called AssemblyGame.

AlphaZero uses deliberation to determine which decisions have the highest probability of leading to a victory at each decision point by considering all possible actions, all possible moves after each conceivable move, and so on in a branching fashion. It uses an intuition-like process to narrow its search since analyzing all conceivable forks would take longer than the universe's age. The state of the game is continuously fed into neural networks, which are complicated mathematical functions that may be tuned to emphasize the best possible movements. The networks are continually updated during training based on the results of the games. It also does move exploration by only sometimes going with the top-rated option.

Performance

AlphaDev can perform one of four distinct actions, each involving comparing values, relocating values, or skipping to a new section of the code. At the end of each stage, it tries to sort a new set of lists and is rewarded based on how many items it correctly sorted. It continues to run until all lists are perfectly sorted, or the programme length limit is reached. At this point, it restarts.

The programmes were judged and rewarded by neural networks considering accuracy and speed. Mankowitz's group programmed the system to rate performance based on the number of instructions executed or the required time. AlphaDev's top algorithms were between 4 and 71% faster than human methods in sorting large data sets, depending on the processor and the number of variables to be sorted. However, the cumulative time savings was just 1-2% while sorting lists of a quarter of a million values, as the algorithms were called several times and other code was not optimized.

Non-sorting algorithms

AlphaDev was also applied to non-sorting algorithms by the DeepMind team. Its version of a technique for converting data stored in a specific format into bytes used 67% less time than the standard one. Its hashing algorithm, used in data storage and retrieval, was 30% faster than a normal one. The team examined AlphaDev's algorithms to see where it made its money. They discovered two novel sorting strategies: the AlphaDev swap move and the AlphaDev copy move. Mankowitz compares them to 'Play 37,' an unexpected play performed by AlphaGo, AlphaZero's predecessor, against human Go champion Lee Sedol in a 2016 exhibition match in Seoul.

Image source: Unsplash