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

211–220 of 415 posts

Re: Competitive Programming with AlphaCode

#211

Post by bricemo »

xorcist wrote: post #208
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…

You don't think it's impressive, yet you surmise that a computer program could compete at a level of the top 1% of all humans in five years ? That's wildly overstating the promise of this technology, and I'd be very surprised if the authors of this wouldn't agree.

Agree. If an AI could code within the top 1%, every single person whose career touches code would have their lives completely upended. If that’s only 5 years out…ooof.

Re: Competitive Programming with AlphaCode

#212

Post by raphlinus »

csee wrote: post #171
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…

You're extrapolating across very different types of problems. Go and Chess have unlimited training data. Competitive programming does not.

To me, that's actually one of the more interesting questions. It's possible to grade the output of the AI against objective criteria, like does it run, and resources consumed (RAM, CPU time, and, particularly of interest to me, parallel scaling, as GPU algorithms are too hard for most programmers). To what extent can you keep training by having the AI generate better and better solutions to a relatively smaller input pool of problems? I skimmed the paper to see how much they relied on this but didn't get a clear read.

Re: Competitive Programming with AlphaCode

#213

Post by qualudeheart »

d0mine wrote: post #168

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 (w…

I don’t even think the “will AI replace human programmers” question is that interesting anymore. My prediction is that a full replacement won’t happen until we achieve general artificial intelligence, and have it treat programming as it would any other problem.

Elsewhere ITT I’ve claimed that to fully automate programming you also need a model of the external world that’s on par with a humans.

Otherwise you can’t work a job because you don’t know how to do the many other tasks that aren’t coding.

You need to understand what the business goals are and how your program solves them.

Re: Competitive Programming with AlphaCode

#214

Post by deanmen »

37ef_ced3 wrote: post #36
dskloet wrote: post #32

Earlier quoted context omitted.

There's really no need for an 11 in the code. I'd say that makes the code worse, not better.

This is a toy problem to illustrate that CoPilot cannot write code that requires mathematical reasoning. It regurgitates solutions from the training set, via a mixed internal reresentation.

   unsigned int swapbits(unsigned int a)
   {
       bool bit6 = a & (1

Re: Competitive Programming with AlphaCode

#215

Post by deanmen »

37ef_ced3 wrote: post #5

The example problem (essentially, is T a subsequence of S with deletions of size N) is a classic problem with no doubt dozens of implementations in AlphaCode's training set. And yet, what a garbage solution it produces. To illustrate the difference between intelligence and regurgitation, someone tell me what CoPilot generates for this: // A Go function to swap the sixth bit and seventeenth bit of a 32-bit signed inte…

You can do it without a subtraction

     unsigned int swapbits(unsigned int a) {
     bool bit6 = a & (1

Re: Competitive Programming with AlphaCode

#216

Post by jensensbutton »

jakub_g wrote: post #109
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…

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…

Maybe the problem transformation will be both the beginning _and_ end of the developer's role.

Re: Competitive Programming with AlphaCode

#217

Post by FiberBundle »

It never ceases to amaze me what you can do with these transformer models. They created millions of potential solutions for each problem, used the provided examples for the problems to filter out 99% of incorrect solutions and then applied some more heuristics and the 10 available submissions to try to find a solution.

All these approaches just seem like brute-force approaches: Let's just throw our transformer on this problem and see if we can get anything useful out of this.

Whatever it is, you can't deny that these unsupervised models learn some semantic representations, but we have no clue at all what that actually is and how these model learn that. But I'm also very sceptical that you can actually get anywhere close to human (expert) capability in any sufficiently complex domain by using this approach.

Re: Competitive Programming with AlphaCode

#218

Post by qualudeheart »

EGreg wrote: post #151

To me, coding in imperative languages are one of the hardest things to produce an AI for with current approaches (CNN’s, MCTS and various backpropagation). Something like Cyc would seem to be a lot more promising… And yet, I am starting to see (with GitHub’s Copilot, and now this) a sort of “GPT-4 for code”. I do see many problems with this, including: 1. It doesn’t actually “invent” solutions on its own like AlphaZe…

Can you write more about how Cyc would help? The idea behind Cyc is cool but I don’t think I’ve seen anyone discuss using it for program synthesis.

Re: Competitive Programming with AlphaCode

#220

Post by hackinthebochs »

37ef_ced3 wrote: post #179
Veedrac wrote: post #176

Earlier quoted context omitted.

The first example is almost correct, conditioned off a sentence description. The second example is the right idea, it just bit off more than it could chew when slicing it all together. Using string ops for binary manipulation in Python isn't even stupid; it can be faster in a lot of cases. This feels a lot like screaming at a child for imperfect grammar.

It illustrates that CoPilot is generating maximum likelihood token strings and has no real understanding of the code. That's what is happening here. There is no intelligence, just regurgitation. Randomization and maximum likelihood completion. Just like with the competitive programming example, we're asking it to produce solutions that it has seen in its training set. If you ask for a nontrivial twist on one of those…

>It illustrates that CoPilot is generating maximum likelihood token strings and has no real understanding of the code.

Funny, today I was just thinking of people's tendencies to dismiss AI advances with this very pattern of reasoning: take a reductive description of the system and then dismiss it as obviously insufficient for understanding or whatever the target is. The assumption is that understanding is fundamentally non-reductive, or that there is insufficient complexity contained within the reductive description. But this is a mistake.

The fallacy is that the reductive description is glossing over the source of the complexity, and hence where the capabilities of the model reside. "Generating maximum likelihood token strings" doesn't capture the complexity of the process that generates the token strings, and so an argument that is premised on this reductive description cannot prove the model deficient. For example, the best way to generate maximum likelihood human text is just to simulate a human mind. Genuine understanding is within the solution-space of the problem definition in terms of maximum likelihood strings, thus you cannot dismiss the model based on this reductive description.

Post reply on HN