Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Competitive Programming with AlphaCode

deepmind.com

Post reply on HN
Print view View original

161–170 of 415 posts

Re: Competitive Programming with AlphaCode

#161

Post by Groxx »

e4e78a06 wrote: post #134
FemmeAndroid wrote: post #103

This is extremely impressive, but I do think it’s worth noting that these two things were provided: - a very well defined problem. (One of the things I like about competitive programming and the like is just getting to implement a clearly articulated problem, not something I experience on most days.) - existing test data. This is definitely a great accomplishment, but I think those two features of competitive program…

I don't think it's quite as impressive as you make it out to be. Median performance in a Codeforces programming competition is solving the easiest 1-2 problems out of 5-6 problems. Like all things programming the top 1% is much, much better than the median. There's also the open problem of verifying correctness in solutions and providing some sort of flag when the model is not confident in its correctness. I give it…

I do kinda wonder if it'd lead to as good results if you just did a standard "matches the most terms the most times" search against all of github.

I have a suspicion it would - kinda like Stack Overflow, problems/solutions are not that different "in the small". It'd have almost certainly given us the fast square root trick verbatim, like Github's AI is doing routinely.

Re: Competitive Programming with AlphaCode

#162

Post by jakub_g »

ctoth wrote: post #154
jakub_g wrote: post #109

Earlier quoted context omitted.

100% agree. Someone (who?) had to take time and write the detailed requirements. In real jobs you rarely get good tickets with well defined expectations; it's one of most important developer's jobs to transform fuzzy requirement into a good ticket. (Side note: I find that many people skip this step, and go straight from fuzzy-requirement-only-discussed-on-zoom-with-Bob to code; open a pull request without much contex…

So what happens when OpenAI releases TicketFixer 0.8 which synthesizes everything from transcripts of your meetings to the comments to the JIRA ticket to the existing codebase and spits out better tickets to feed into the programming side?

Take my money.

Re: Competitive Programming with AlphaCode

#163

Post by [deleted] »

ogogmad wrote: post #153
jakey_bakey wrote: post #152

At the risk of sounding relentlessly skeptical - surely by training the code on GitHub data you're not actually creating an AI to solve problems, but creating an extremely obfuscated database of coding puzzle solutions?

We validated our performance using competitions hosted on Codeforces, a popular platform which hosts regular competitions that attract tens of thousands of participants from around the world who come to test their coding skills. We selected for evaluation 10 recent contests, each newer than our training data. AlphaCode placed at about the level of the median competitor, marking the first time an AI code generation sy…

[deleted]

Re: Competitive Programming with AlphaCode

#164

Post by BobbyJo »

ctoth wrote: post #148
e4e78a06 wrote: post #134

Earlier quoted context omitted.

I don't think it's quite as impressive as you make it out to be. Median performance in a Codeforces programming competition is solving the easiest 1-2 problems out of 5-6 problems. Like all things programming the top 1% is much, much better than the median. There's also the open problem of verifying correctness in solutions and providing some sort of flag when the model is not confident in its correctness. I give it…

This is technology that simply didn't exist in any form 2 years ago. For no amount of money could you buy a program that did what this one does. Having been watching the growth of Transformer-based models for a couple years now really has hammered home that just as soon as we figure out how an AI can do X, X is no longer AI, or at least no longer impressive. How this happens is with comments like yours, and I'd reall…

I don't think that's what happening. Let's talk about this case: programming. It's not that people are saying "an AI programming" isn't impressive or isn't AI, it's that when people say "an AI programming" they aren't talking about ridiculously controlled environments like in this case.

It's like self-driving cars. A car driving itself for the first time in a controlled environment, I'm sure, was an impressive feat, and it wouldn't be inaccurate to call it a self-driving car. However, that's not what we're all waiting for when we talk about the arrival of self-driving cars.

Re: Competitive Programming with AlphaCode

#166

Post by redsummer »

qualudeheart wrote: post #90

Calling it now: If current language models can solve competitive programming at an average human level, we’re only a decade or less off from competitive programming being as solved as Go or Chess. Deepmind or openAI will do it. If not them, it will be a Chinese research group on par with them. I’ll be considering a new career. It will still be in computer science but it won’t be writing a lot of code. There’ll be sev…

No post body was provided.

Re: Competitive Programming with AlphaCode

#167

Post by ctoth »

BobbyJo wrote: post #164
ctoth wrote: post #148

Earlier quoted context omitted.

This is technology that simply didn't exist in any form 2 years ago. For no amount of money could you buy a program that did what this one does. Having been watching the growth of Transformer-based models for a couple years now really has hammered home that just as soon as we figure out how an AI can do X, X is no longer AI, or at least no longer impressive. How this happens is with comments like yours, and I'd reall…

I don't think that's what happening. Let's talk about this case: programming. It's not that people are saying "an AI programming" isn't impressive or isn't AI, it's that when people say "an AI programming" they aren't talking about ridiculously controlled environments like in this case. It's like self-driving cars. A car driving itself for the first time in a controlled environment, I'm sure, was an impressive feat,…

And if AI programming were limited to completely artificial contexts you would have a point, though I'd still be concerned. We live in a world, however, where programmers routinely call on the powers of an AI to complete their real code and get real value out of it. This is based on the same technology that brought us this particular win, so clearly this technology is useful outside "ridiculously controlled environments."

Re: Competitive Programming with AlphaCode

#168

Post by d0mine »

It reminds me that median reputation on StackOverflow is 1. All AlphaSO would have to do is to register to receive median reputation on SO ;) (kidding aside AlphaCode sounds like magic)

Inventing relational DBs hasn't replaced programmers, we just write custom DB engines less often. Inventing electronic spreadsheets hasn't deprecated programmers, it just means that we don't need programmers for corresponding tasks (where spreadsheets work well).

AI won't replace programmers until it grows to replace the humanity as a whole.

Re: Competitive Programming with AlphaCode

#169

Post by wittycardio »

chroem- wrote: post #51
wittycardio wrote: post #6

Earlier quoted context omitted.

Solving competitive programming problems is essentially solving hard combinatorial optimization problems. Throwing a massive amount of compute and gradient descent at the problem has always been possible. If I'm not mistaken what this does is reduce the representation of the problem to a state where it can run gradient descent and then tune parameters. The real magic is in finding structurally new approaches. If anyt…

> Solving competitive programming problems is essentially solving hard combinatorial optimization problems. True, but if you relax your hard requirements of optimality to admit "good enough" solutions, you can use heuristic approaches that are much more tractable. High quality heuristic solutions to NP-hard problems, enabled by ML, are going to be a big topic over the next decade, I think.

I should correct myself, this isn't even that. This is just text analysis on codeforces solutions, which makes it even worse than I thought. Very pessimistic about it's generalizability.

Re: Competitive Programming with AlphaCode

#170

Post by johndough »

gfd wrote: post #95
baobabKoodaa wrote: post #76

Earlier quoted context omitted.

The median rating is not descriptive of median ability, because a large number of Codeforces competitors only do one or a few competitions. A very small number of competitors hone their skills over multiple competitions. If we were to restrict our sample to competitors with more than 20 competitions, the median rating would be much higher than 1300. It's amazing that Alphacode achieved a 1300 rating, but compared to…

You can find the rating distribution filtered for >5 contests here: https://codeforces.com/blog/entry/71260 I am rated at 2100+ so I do agree that 1300 rating is low. But at the same time it solved https://codeforces.com/contest/1553/problem/D which is rated at 1500 which was actually non-trivial for me already. I had one wrong submit before getting that problem correct and I do estimate that 50% of the regular compe…

The proposed O(N²) solution contains many unnecessary operations, e.g. the creation of list c or reversal of the input strings. Maybe it has been copied from a related problem? You can easily solve the task with half as many lines in O(N).

    for _ in range(int(input())):
        a = list(input())
        b = list(input())
        while a and b:
            if a[-1] == b[-1]:
                a.pop()
                b.pop()
            else:
                a.pop()
                if a: a.pop()
        print("NO" if b else "YES")
Post reply on HN