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

241–250 of 415 posts

Re: Competitive Programming with AlphaCode

#241

Post by bricemo »

FiberBundle wrote: post #217

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 thi…

What do you think then is the difference between going from 50th to 99.9th percentile in their other domains? Is there something materially different between ago, protein folding, or coding? (I don’t know the answer, just curious if anyone else does)

Re: Competitive Programming with AlphaCode

#242

Post by FiberBundle »

bricemo wrote: post #241
FiberBundle wrote: post #217

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 thi…

What do you think then is the difference between going from 50th to 99.9th percentile in their other domains? Is there something materially different between ago, protein folding, or coding? (I don’t know the answer, just curious if anyone else does)

Well with respect to Go the fundamental difference afaict is that you can apply self-supervised learning, which is an incredibly powerful approach (But note e.g. that even this approach wasn't successful in "solving" Starcraft). Unfortunately it's extremely difficult to frame real-world problems in that setting. I don't know anything about protein-folding and don't know what Deepmind uses to try to solve that problem, so I cannot comment on that.

Re: Competitive Programming with AlphaCode

#243

Post by qualudeheart »

YeGoblynQueenne wrote: post #221
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…

>> This is technology that simply didn't exist in any form 2 years ago. A few examples of neural program synthesis from at least 2 years ago: https://sunblaze-ucb.github.io/program-synthesis/index.html Another example from June 2020: DreamCoder: Growing generalizable, interpretable knowledge with wake-sleep Bayesian program learning https://arxiv.org/abs/2006.08381 RobustFill, from 2017: RobustFill: Neural Program Le…

Has someone tried classical program synthesis techniques on competitive programming problems? I wonder what would have been possible with tech from more than 2 years ago.

Re: Competitive Programming with AlphaCode

#244

Post by woadwarrior01 »

alasdair_ wrote: post #80
thomasahle wrote: post #56

Earlier quoted context omitted.

If you make developers 50x more efficient, won't you need 50x fewer developers?

>If you make developers 50x more efficient, won't you need 50x fewer developers? Developers today are 50X more efficient than when they had to input machine code on punched tape, yet the number of developers needed today is far larger than it was in those times.

https://en.m.wikipedia.org/wiki/Jevons_paradox

Re: Competitive Programming with AlphaCode

#245

Post by pedrosorio »

ahgamut wrote: post #239
pedrosorio wrote: post #227

Earlier quoted context omitted.

> Suppose AlphaCode was trained on Github code that contains the entire set of solutions on Codeforces, is it actually doing anything "difficult"? They tested it on problems from recent contests. The implication being: the statements and solutions to these problems were not available when the Github training set was collected. From the paper [0]: "Our pre-training dataset is based on a snapshot of selected public Git…

> They tested it on problems from recent contests. The implication being: the statements and solutions to these problems were not available when the Github training set was collected. Yes, and I would like to know how similar the dataset(s) were. Suppose the models were trained only on greedy algorithms and then I provided a dynamic programming problem in the test set, (how) would the model solve it? > And yet, many…

> Suppose the models were trained only on greedy algorithms and then I provided a dynamic programming problem in the test set, (how) would the model solve it?

How many human beings do you personally know who were able to solve a dynamic programming problem at first sight without ever having seen anything but greedy algorithms?

Deepmind is not claiming they have a machine capable of performing original research here.

Many human programmers are unable to solve DP problems even after having them explained several times. If you could get a machine that takes in all of Github and can solve "any" DP problem you describe in natural language with a couple of examples, that is AI above and beyond what many humans can do, which is "awesome" no matter how you put it.

Re: Competitive Programming with AlphaCode

#246

Post by solarmist »

stupidcar wrote: post #79
msoad wrote: post #19

This seems to have a narrower scope than GitHub Copilot. It generates more lines of code to a more holistic problem vs. GitHub Copilot that works as a "more advanced autocomplete" in code editors. Sure Copilot can synthesize full functions and classes but for me, it's the most useful when it suggests another test case's title or writes repetitive code like this.foo = foo; this.bar = bar etc... Having used Copilot I c…

Having used Copilot for a while, I am quite certain it will replace me as a programmer. It appears to me that when it comes to language models, intelligence = experience * context. Where experience is the amount what's encoded in the model, and context is the prompt. And the biggest limitation on Copilot currently is context. It behaves as an "advanced autocomplete" because it all is has to go on is what regular auto…

I'm skeptical it'll replace programmers, as in no more human programmers, but agree in the sense 100% human programmers -> 50%, 25%, 10% human programmers + computers doing most of the writing of actual code.

I see it continuing to evolve and becoming a far superior auto-complete with full context, but, short of actual general AI, there will always be a step that takes a high-level description of a problem and turns it into something a computer can implement.

So while it will make the remaining programmers MUCH more productive, thereby reducing the needed number of programmers, I can't see it driving that number to zero.

Re: Competitive Programming with AlphaCode

#247

Post by simpleguitar »

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…

It doesn't even have to be average human.

Let's say AI only gets to 10% (or 20% or 30% or whatever, it doesn't really matter), that's a huge number of jobs being lost.

Imagine having a machine write all the "simple/boring" code for you. Your productivity will go through the roof. The smartest programmer who can most effectively leverage the machine could replace many hundreds of programmers.

I should brush up on my plumbing and apply for a plumbing license soon. (I think plumbing is safer than electricians, because many CS people have good EE foundations).

Re: Competitive Programming with AlphaCode

#248

Post by solarmist »

Veedrac wrote: post #100
TSiege wrote: post #93

Earlier quoted context omitted.

I have a feeling this is the correct read in terms of progression. But I'm skeptical if it'll ever be able to synthesize a program entirely. I imagine that in the future we'll have some sort of computer language more like written language that will be used by some sort of AI to generate software to meet certain demands, but might need some manual connections when requirements are hazy or needs a more human touch in t…

> But I'm skeptical if it'll ever be able to synthesize a program entirely. Emotional skepticism carries a lot more weight in worlds where AI isn't constantly doing things that are meant to be infeasible, like coming 54th percentile in a competitive programming competition. People need to remember that AlexNet is 10 years old. At no point in this span have neural networks stopped solving things they weren't meant to…

I feel like you're taking that sentence a bit too literally. I read it as "I'm skeptical that AI will ever be able to take a vague human description from a product manager/etc. and solve it without an engineer-type person in the loop." The issue is humans don't know what they want and realistically programs require a lot of iteration to get right, no amount of AI can solve that.

I agree with you; it seems obvious to me that once you get to a well-specified solution a computer will be able to create entire programs that solve user requirements. And that they'll start small, but expand to larger and more complex solutions over time in the same way that no-code tools have done.

Re: Competitive Programming with AlphaCode

#249

Post by sibeshk96 »

pedrosorio wrote: post #245
ahgamut wrote: post #239

Earlier quoted context omitted.

> They tested it on problems from recent contests. The implication being: the statements and solutions to these problems were not available when the Github training set was collected. Yes, and I would like to know how similar the dataset(s) were. Suppose the models were trained only on greedy algorithms and then I provided a dynamic programming problem in the test set, (how) would the model solve it? > And yet, many…

> Suppose the models were trained only on greedy algorithms and then I provided a dynamic programming problem in the test set, (how) would the model solve it? How many human beings do you personally know who were able to solve a dynamic programming problem at first sight without ever having seen anything but greedy algorithms? Deepmind is not claiming they have a machine capable of performing original research here.…

> that is AI above and beyond what many humans can do, which is "awesome" no matter how you put it.

That's not the point being made. The point OP is making is that it is not possible to understand how impressive at "generalizing" to uncertainty a model is if you don't know how different the training set is from the test set. If they are extremely similar to each other, then the model generalizes weakly (this is also why the world's smartest chess bot needs to play a million games to beat the average grandmaster, who has played less than 10,000 games in her lifetime). Weak generalization vs strong generalization.

Perhaps all such published results should contain info about this "difference" so it becomes easier to judge the model's true learning capabilities.

Re: Competitive Programming with AlphaCode

#250

Post by ahgamut »

pedrosorio wrote: post #245
ahgamut wrote: post #239

Earlier quoted context omitted.

> They tested it on problems from recent contests. The implication being: the statements and solutions to these problems were not available when the Github training set was collected. Yes, and I would like to know how similar the dataset(s) were. Suppose the models were trained only on greedy algorithms and then I provided a dynamic programming problem in the test set, (how) would the model solve it? > And yet, many…

> Suppose the models were trained only on greedy algorithms and then I provided a dynamic programming problem in the test set, (how) would the model solve it? How many human beings do you personally know who were able to solve a dynamic programming problem at first sight without ever having seen anything but greedy algorithms? Deepmind is not claiming they have a machine capable of performing original research here.…

> How many human beings do you personally know who were able to solve a dynamic programming problem at first sight without ever having seen anything but greedy algorithms?

Zero, which is why if a trained network could do it, that would be "impressive" to me, given my personal biases.

>. If you could get a machine that takes in all of Github and can solve "any" DP problem you describe in natural language with a couple of examples, that is AI above and beyond what many humans can do, which is "awesome" no matter how you put it.

I agree with you that such a machine would be awesome, and AlphaCode is certainly a great step closer towards that ideal. However, I would like to have a number measures the "awesomeness" of the machine (not elo rating because that depends on a human reference), so I will have something as a benchmark to refer to when the next improvement arrives.

Post reply on HN