Google DeepMind, the UK-based AI research company, has achieved two major breakthroughs in computer science using its game-playing AI, AlphaZero. DeepMind used a new version of AlphaZero called AlphaDev to make significant advancements in sorting algorithms and cryptography. AlphaDev has discovered a method to sort items in a list up to 70% faster than the existing best human-devised method. It has also accelerated a key cryptographic algorithm by 30%. These findings are crucial as these algorithms serve as the foundation for various software applications, and even small improvements can lead to significant cost savings and energy conservation.
“Moore’s Law is coming to an end, where chips are approaching their fundamental physical limits,” says Daniel Mankowitz, a research scientist at Google DeepMind. “We need to find new and innovative ways of optimizing computing.”
AI-devised Algorithm Triumphs
Although DeepMind’s research is just published in Nature recently, the new sorting algorithms developed by AlphaDev are already being used by millions of software developers. The organization submitted its algorithms to the organization overseeing C++, a widely used programming language, resulting in the first update to C++’s sorting algorithms in over a decade and the first algorithm update inspired by AI.
AlphaDev is built on top of AlphaZero, the reinforcement-learning model famous for mastering games like Go and chess. DeepMind’s approach involves treating the problem of finding faster algorithms as a game, training AlphaDev to discover winning moves. The game revolves around selecting computer instructions and arranging them to form an algorithm. AlphaDev wins by creating algorithms that are not only correct but also faster than existing ones.
To tackle the challenge, AlphaDev works with assembly, a programming language that provides specific instructions for manipulating data on computer chips. DeepMind chose assembly because it allows algorithms to be broken down into fine-grained steps. By playing the game and experimenting with adding assembly instructions, AlphaDev learned to generate correct and efficient algorithms.
The initial focus was on optimizing sorting algorithms for short lists of three to five items. DeepMind’s researchers were surprised to find that AlphaDev improved upon the best human-devised algorithm for sorting three items, reducing the number of instructions needed from 18 to 17. While it didn’t surpass the best human algorithm for sorting four items, it did outperform it for five items, reducing the instructions from 46 to 42.
These optimizations translate into significant speed-ups. For example, the existing C++ algorithm for sorting five items took around 6.91 nanoseconds on an Intel Skylake chip, whereas AlphaDev’s algorithm completed the task in just 2.01 nanoseconds, representing a 70% improvement.
What’s Next
While impressed with the results, experts caution that machine learning has not yet reached the point of inventing entirely new and better algorithms. AlphaDev only explores a subset of assembly instructions, limiting direct comparisons with existing algorithms that employ different instructions. Moreover, AlphaDev’s capabilities are restricted due to the vast number of possible algorithms that it must evaluate. DeepMind plans to address these limitations by adapting AlphaDev to work with C++ instructions, incorporating human-devised methods and intuition.
Not the First Breakthrough
In 2022, DeepMind has already used AlphaZero to make significant advancements in matrix multiplication, a fundamental computation used in various applications. By transforming the problem into a three-dimensional board game and training a new version of AlphaZero called AlphaTensor, DeepMind was able to discover faster algorithms for multiplying matrices. AlphaTensor outperformed existing algorithms for over 70 different matrix sizes, including a 1969 method by mathematician Volker Strassen. It reduced the number of steps required for matrix multiplication and identified algorithms that were 10 to 20% faster on common computer chips. DeepMind plans to apply AlphaTensor to search for other types of algorithms, heralding a new approach to computer science.
Closing
DeepMind’s achievements highlight the potential of AI to optimize computing and pave the way for innovative approaches to problem-solving. By leveraging machine learning and reinforcement learning techniques, Google DeepMind continues to make groundbreaking discoveries in fundamental computer science.
This article is drafted with the assistance of A.I. and referencing from the sources below:
https://www.nature.com/articles/s41586-023-06004-9
The work described in this article was supported by InnoHK initiative, The Government of the HKSAR, and Laboratory for AI-Powered Financial Technologies.
AIFT strives but cannot guarantee the accuracy and reliability of the content, and will not be responsible for any loss or damage caused by any inaccuracy or omission.
