Note: This blog was first published on February 2, 2022. After the publication of the article in the field of science on December 8, 2022, we carried out slight text updates to reflect it.
Solving new problems and setting a new milestone in competitive programming
Creating solutions over unforeseen problems is the second nature of human intelligence – the result of critical thinking based on experience. The machine learning community has made great progress in generating and understanding text data, but the progress in solving problems remains limited to relatively simple mathematics and programming problems, as well as recovering and copying existing solutions.
As part Deepmind mission To solve intelligence, we have created a system called Alphacode, which saves computer programs at a competitive level. Alfacod achieved an estimated rank in 54% of participants in programming competitions by solving new problems that require a combination of critical thinking, logic, algorithms, coding and understanding of the natural language.
Published on the cover of scienceOur paper describes Alfacod in detail, which uses language models based on the transformer to generate code on an unprecedented scale, and then elegantly filter a small set of promising programs.
We have verified our performance using host competitions CodeA popular platform that takes regular competitions that attract tens of thousands of participants from around the world who come to check their coding skills. We chose for the last 10 competitions, each new than our training data. Alphakod placed at the level of the median competitor, which means that for the first time the AI code generation system has achieved a competitive level of performance in programming competitions.
To help others build our results, we issued our set of data on problems and solutions of competitive programming on githubIncluding extensive tests to ensure that the programs that undergo these tests are correct – there are no current sets of critical data. We hope that this reference point will lead to further innovations in solving problems and generating code.
The problem comes from codes and the solution was generated by alphakod.
Competitive programming is a popular and difficult action; Hundreds of thousands of programmers participate in coding competitions to gain experience and present their skills in fun and cooperation. During the competition, participants receive a series of long descriptions of problems and a few hours to write programs to solve them.
Typical problems include finding ways to place roads and buildings within specific restrictions or creating a strategy to win custom board games. Participants are then ranked mainly on the basis of the number of problems. Companies use these competitions as recruitment tools, and similar types of problems are common in the processes of employing software engineers.
“
I can safely say that the results of the alphacod have exceeded my expectations. I was skeptical, because even in simple competitive problems it is often required not only to implement the algorithm, but also (and this is the most difficult part) to come up with it. Alphacode managed to perform at the level of a promising new competitor. I can't wait to see what awaits us!
Mike Mirzaayanov, founder, code
Problem solving skills required to improve in these competitions go beyond the capabilities of existing AI systems. However, combining progress in large transformer models (which recently showed promising code generation ability) with a large -scale sampling and filtering, we have made significant progress in the number of problems that we can solve. We will initially train our model on a selected public GitHub code and tune it to our relatively small set of competitive programming set.
During the evaluation, we create a huge number of C ++ and Python programs for each problem, at a row of size greater than previous work. Then we filter, focus and process these solutions of a small set of 10 programs of candidates, which we submit for external assessment. This automated system replaces the trial process and competition errors in debugging, compilation, passing tests and ultimately transmission.
With the consent of the codes, we evaluated Alfacod, simulating participation in the last 10 competitions. The impressive work of a competitive programming community has created a domain in which problems cannot be solved through shortcuts, such as duplication of solutions seen earlier or trying any potentially related algorithm. Instead, our model must create new and interesting solutions.
In general, Alfakoda placed at the level of the middle competitor. Although this is not far from winning competitions, this result is a significant jump in the possibilities of solving AI problems and we hope that our results will inspire a competitive programming community.
“
Solving problems with competitive programming is really difficult to do, requiring both good coding skills and creativity to solve problems in humans. I was very impressed that Alphacodode can make progress in this area and excited to see how the model uses its statement to create a code and direct its random exploration to create solutions.
Petr Mitrichev, software engineer, competitive Google and World -class program
In order for artificial intelligence to help humanity, our systems must be able to develop problems. Alphacodode was in the top 54% in programming competitions in the real world, progress that shows the potential of deep learning models of tasks requiring critical thinking. These models elegantly use modern machine learning to express problems solutions as a code, returning to the symbolic source of AI from decades from decades. And this is just the beginning.
Our exploration of code generation leaves a vast room for improvements and tips on even more exciting ideas that can help programmers improve their performance and open the field for people who are currently not writing the code. We will continue this exploration and we hope that further research will cause tools to improve programming and bring us closer to solving problems.
See Alphacode solutions and explore the model at alphacode.deepmind.com
