Xiao Cha was sent from The Temple of Oufei
Qubits | Official account QbitAI
Today, DeepMind's "Alpha" family adds a new member:
AlphaCode, which can brush up on programming competition questions, is coming!
In fact, AlphaCode "sneaked into the village" a few months ago, and no one noticed it.
It silently participated in 10 recent programming competitions held by the famous website Codeforces, and the score exceeded half of the human race.
It wasn't until today that DeepMind announced the final results: AlphaCode ranked in the top 54.3% of these 10 races, with an Elo score of 1238.
More importantly, in the problem of examining the creativity of algorithms such as programming competitions, AI has finally not fallen behind, which is exactly what AI has lacked in the past.
If you put this score into the overall view of the past six months, AlphaCode's score is even better, because it has only brushed the questions for 10 weeks, and it has already reached the level of the top 28% of users.
Codeforces is a programming competition website founded by Russian programmer Mikhail Mirzayanov that holds a programming competition called "Codeforces Rounds" about once a week.
Codeforces' Elo score allows a measure of a programmer's level of programming.
△ Codeforces founder Mikhail Mirzayanov
When he saw AlphaCode's achievements, even the founder Mirzayanov was surprised.
He was originally skeptical of AI, because the programming competition tested the ability to invent algorithms, which was the most difficult, and did not expect that the results of AlphaCode completely exceeded his expectations.
DeepMind posted the news only half a day ago, and has already been retweeted more than 2,000 times and liked more than 5,000 times on Twitter.
How AlphaCode is programmed
Having said all that, let's take a look at how AlphaCode became a "programming problem solver".
Here are the 1553D issues on Codeforces:
(Link: https://codeforces.com/problemset/problem/1553/D)
There are two strings, s and t, both of which consist of lowercase letters. For strings s, we scan the entire string from front to back.
If you press the Backspace key, all characters between the previous cursor and the previous undeleted character are deleted.
For example, the string s is "abcbd", and if you press Backspace in the first and fourth positions, respectively, you will get the string "bd".
Because there are no characters before the first cursor position, there is no action the first time. The character before the fourth cursor position is c and the previous undeleted character is a, so pressing Backspace will remove the first three characters "bd".
Okay, now here's the question:
Can we scan the s string once from front to back and make the s become t? If yes can be output, otherwise no is output.
AlphaCode gives the code like this:
t=int(input())
for i in range(t):
s=input()
t=input()
a=[]
b=[]
for j in s:
a.append(j)
for j in t:
b.append(j)
a.reverse()
b.reverse()
c=[]
while len(b)!=0 and len(a)!=0:
if a[0]==b[0]:
c.append(b.pop(0))
a.pop(0)
elif a[0]!=b[0] and len(a)!=1:
elif a[0]!=b[0] and len(a)==1:
if len(b)==0:
print("YES")
else:
print("NO")
Enter 4 sets of strings into the above program:
4 ababa ba father bb aaa aaa aaaa father
The resulting output is:
YESNONOYES
Here, AlphaCode is no longer a black box.
Not only does it solve the problem successfully, but it also displays the corresponding position of the code and attention highlight.
A netizen said: Since AI can see so finely, it is better if you can add comments after the code.
As for more cases, you can go to the AlphaCode website to observe.
principle
DeepMind said the problem-solving skills needed in the Codeforces race have exceeded the capabilities of existing AI systems.
The flow of the entire AlphaCode model is as follows:
Pre-train a Transformer-based language model on GitHub code with standard language modeling targets. This model can reasonably represent the space for humans to write code, greatly reducing the search space for problems.
Fine-tuning models on competitive programming datasets, using GOLD and tempering as training targets, further reducing search space, and utilizing pre-training to compensate for small amounts of competitive programming data.
Generate a very large number of samples from the model for each problem.
Samples are filtered to obtain a small selection of candidate submissions (up to 10) and evaluated on hidden test cases by using example testing and clustering to select samples based on program behavior.
All in all, by combining a large-scale Transformer model with large-scale sampling and filtering, DeepMind has made significant progress in the number of problems that can be solved, an order of magnitude higher than previous work.
Brushing people resist
As the codeforces founders said, inventing algorithms is the hardest in programming problems.
Peter Mitrichev, a Google engineer who has been ranking in the top of the global programming competition website for many years, said:
Solving the problem of programming competitions is a very difficult thing. It requires both good code skills and human creativity to solve problems.
AlphaCode isn't the first programming tool, and Codex, along with GitHub Copilot, has been impressive.
But DeepMind believes that AlphaCode is very different from its predecessors:
Recent large-scale language models have demonstrated the amazing ability to generate code and are now able to accomplish simple programming tasks. However, these models still perform poorly when evaluated for more complex, invisible problems that require problem-solving skills rather than just translating instructions into code.
Unlike twitter, Codeforces experts are more resistant.
One programmer said, "This AI is really a rookie." ”
Because AlphaCode only has 1238 points, it is only equivalent to a student level, and a middle school student participating in the Informatics Olympiad can also brush this level.
While DeepMind claims that AlphaCode is meant to assist humans, some programmers are starting to worry:
Now even the world of brushing questions is occupied by AI, originally this is a place for programmers to compete, AI should be appropriate, leaving a pure land for programmers!
Reference Links:
[1]https://deepmind.com/blog/article/Competitive-programming-with-AlphaCode
[2]https://alphacode.deepmind.com/
[3]https://storage.googleapis.com/deepmind-media/AlphaCode/competition_level_code_generation_with_alphacode.pdf
[4]https://github.com/deepmind/code_contests