Problem-solving algorithm

AlphaCode was tested on tasks from ten recent programming competitions held by Codeforces. The algorithm ended up in the top 54% of the participant ranking, which, according to the developers, equals the results of an average programmer. This wouldn’t be a major achievement for a real person but for AI, it’s a huge step forward. In programming, this is the first time that an algorithm was able to come up with a new and original solution instead of generating it based on pre-existent ones. 

AlphaCode employs a scalable transforming architecture. In such models, all data is processed simultaneously, not in sequence. This makes them more flexible and trainable. Such architecture was created in 2017 by scientists from Google Research and Google Brain and soon became the top trend in machine learning. For example, it lies in the foundation of the GPT-3 language model, which is able to generate meaningful texts that are sometimes hardly distinguishable from those written by a human. Initially, this type of architecture was meant for natural language (both text and speech) processing but has been adapted to suit various tasks, including programming.

“The problem-solving abilities required to excel at these competitions are beyond the capabilities of existing AI systems. However, by combining advances in large-scale transformer models (that have recently shown promising abilities to generate code) with large-scale sampling and filtering, we’ve made significant progress in the number of problems we can solve. [...] AlphaCode ranked within the top 54% in real-world programming competitions, an advancement that demonstrates the potential of deep learning models for tasks that require critical thinking. [...] And this is only a start,” according to DeepMind.

DeepMind model's progress in problem solving as compared to human competitors. Credit:

DeepMind model's progress in problem solving as compared to human competitors. Credit:

How it was created and assessed

In this article, the authors thoroughly explain how the model was created and trained and which challenges they had to face. The process of solving a task consists of several stages that are much harder to do for AI than for humans. For example, at the first stage, the algorithm has to understand and analyze the task description, focus on important information, and assume what the result should look like. The second stage is even harder: it has to come up with a solution, which requires a lot of expertise in algorithms and data structures, as well as a deep understanding and comprehension of the problem. Previously, these tasks were considered impossible for AI to complete, so AlphaCode made a huge step forward in the field of artificial cognitive skills.

The model was loaded with code samples from GitHub and a relatively small dataset of competition tasks. The algorithm was taught to create a large number of programs (in C++ and Python) for each task. Their complexity increased with each iteration. Then the results were filtered and classified. According to the developers, they managed to create an automated tool that looks for solutions through trial-and-error.

A total of 10 best solutions were assessed by external experts. In particular, the algorithm was presented to Mikhail Mirzayanov, the founder of Codeforces, and Petr Mitrichev, one of the world’s top 10 competitive programmers. They both were impressed by AlphaCode.

Why AI won’t replace humans

However, no one is saying that automated systems will be able to replace programmers anytime soon. Still, they can become a useful tool for developers and help automate some of the processes, such as the trial-and-error search for solutions, debugging, compiling, etc.

Mikhail Mirzayanov, Codeforces founder, assistant at ITMO’s Information Technologies and Programming Faculty

Mikhail Mirzayanov. Credit: ITMO.NEWS

Mikhail Mirzayanov. Credit: ITMO.NEWS

“Of course, AlphaCode’s abilities are impressive. It truly can solve competitive programming tasks of average complexity. It’s pretty amazing, as solving such tasks requires lots of skills and knowledge. However, it’s safe to say that machines won’t replace humans in terms of more complex programming tasks, especially when it comes to the actual work in the industry. We should keep in mind that programming competitions are more suitable for such research. They include a formal task, examples of solutions, and an automated assessment system. I think such projects won’t lead to the replacement of human programmers but will change their toolsets and shift the focus. Perhaps, AI will become smart helpers embedded in the development system and will be able to solve routine and easy tasks.”