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

231–240 of 415 posts

Re: Competitive Programming with AlphaCode

#231

Post by keewee7 »

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…

AI is being aggressively applied to areas where AI practitioners are domain experts. Think programming, data analysis etc.

Programmers and data scientists might find ourselves among the first half of knowledge workers to be replaced and not among the last as we previously thought.

Re: Competitive Programming with AlphaCode

#232

Post by diehunde »

ctoth wrote: post #136
diehunde wrote: post #39

Earlier quoted context omitted.

My bet would be that it will never happen in a reasonable time frame. And also by that logic, writing that "documentation/spec" would just mean learning a new programming language the AI engine can parse making it as useful as a compiler. Anyone who has been writing and designing software for a while knows the cycle is way more complex than take some input and write code. Let me know when the AI engine is able to do…

You ever notice how the "let me know when" part of this keeps changing? Let me know when computers can ... play Go/understand a sentence/compose music/write a program/ ... But surely they'll never be able to do this new reference class you have just now come up with, right?

Not really? I mean I would never say "let me know when computer can do X" when X is something that doesn't require too much creativity and imagination. Like, a computer composing music, doesn't impress me too much because music itself has structure. A computer creating music that would wow a professional composer? That would be impressive. Same with this topic. A computer that solves some (because it failed several) short programming challenges and OP says it will kill programming entirely? Not even close. Pretty cool though.

Re: Competitive Programming with AlphaCode

#233

Post by 37ef_ced3 »

hackinthebochs wrote: post #220
37ef_ced3 wrote: post #179

Earlier quoted context omitted.

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

The difference between me and you is that I implement neural nets professionally. Here is one of my (non-professional) open source projects: https://NN-512.com

I'm sure if you understood what the transformer was doing, you would be less impressed.

Re: Competitive Programming with AlphaCode

#234

Post by Veedrac »

omnicognate wrote: post #195
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.

You're misunderstanding my point. Nobody's screaming at anything. Whether this thing is impressive isn't at issue. It's utterly astonishing. I'm trying to figure out whether copilot in its current form is a tool that will be useful to me in my job. (I'd be able to do this evaluation properly if they'd just let me on the damned beta.) Nearly right isn't good enough for this afaics. In fact, I expect there to be a slig…

> The second one is definitely not "the right idea". It tries to do it with string manipulations, which (regardless of the fact that it does so incorrectly) is completely the wrong approach. This one is actually "better" than the other in the paradoxical sense I mentioned above, because I could reject it the moment I saw it convert the number to a string.

In this case string ops are a worse idea, but as I said before, this is not generally true of Python, at least when using CPython. Eg. the string method is significantly the faster in this example:

    # https://stackoverflow.com/a/20918545/1763356
    def reverse_mask(x):
        x = ((x & 0x55555555) > 1)
        x = ((x & 0x33333333) > 2)
        x = ((x & 0x0F0F0F0F) > 4)
        x = ((x & 0x00FF00FF) > 8)
        x = ((x & 0x0000FFFF) > 16)
        return x

    # My ver
    def reverse_format(x):
        return int(f"{x:032b}"[::-1], 2)
Python's dynamic object overhead (and to a lesser extent, interpreter overhead) makes a lot of seemingly-expensive operations not matter very much.

Re: Competitive Programming with AlphaCode

#235

Post by the-smug-one »

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…

I'm trying to solve this for fun, but I'm stuck! I've got a recursive definition that solves the problem by building a result string. I think it's a dynamic programming problem, but right now I can't see the shared sub-problems so :). Some real sour cherries being experienced from not getting this one!

Re: Competitive Programming with AlphaCode

#236

Post by bmh100 »

hackinthebochs wrote: post #20
Inufu wrote: post #18

Earlier quoted context omitted.

I agree, I expect programmers will just move up the levels of abstraction. I enjoyed this recent blog post on the topic: https://eli.thegreenplace.net/2022/asimov-programming-and-th...

The "problem" is that as you move up the levels of abstraction, you need fewer people to do the same amount of work. Unless the complexity of the work scales as well. I've always felt that programmers would be the first class of knowledge workers to be put out of work by automation. This may be the beginning of the end for the programming gravy train.

On the other hand, as the value of an hour of programming increases, the quantity demanded may also increase.

Re: Competitive Programming with AlphaCode

#237

Post by jdlshore »

wittycardio wrote: post #159
jdlshore wrote: post #122

Earlier quoted context omitted.

> If anything I'd say algorithms and math continue to be the core of programming. I disagree; I think the core of programming is analyzing things people want and expressing solutions to those wants clearly, unambiguously, and in a way that is easy to change in the future. I'd say algorithms and math are a very small part of this work.

That's not programming, that's called being a good employee. Any person in any role should be doing that. Programming is about algorithms and math. Now a good employee who's in a technical role should have both.

> Programming is about algorithms and math.

You've simply restated your opinion without providing any supporting arguments, and as I already said, I disagree. The vast majority of programming I see (and as a consultant, I see a fairly wide variety) is not about algorithms and math, but instead gluing together systems and expressing domain logic.

Now, I suppose you could argue that domain logic is "algorithms and math," but in my experience, it's less about the specific algorithms and more about precisely describing fuzzy human behavior.

It's that "precisely describing" and "easy to change in the future" parts that makes what programmers do different than what any good employee does.

(I do agree that there is some programming that is focused on algorithms and math, but it's in the minority, in my experience. Perhaps the type of work you do is focused on algorithms and math, but I believe that's a relatively small part of the software development ecosystem.)

Re: Competitive Programming with AlphaCode

#238

Post by hackinthebochs »

37ef_ced3 wrote: post #233
hackinthebochs wrote: post #220

Earlier quoted context omitted.

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

The difference between me and you is that I implement neural nets professionally. Here is one of my (non-professional) open source projects: https://NN-512.com I'm sure if you understood what the transformer was doing, you would be less impressed.

This is the wrong context to go with an appeal to authority. I know what the transformer is doing, I've also developed neural networks before (though not professionally). Your experience is working against you in developing your intuition. There's another common fallacy that because we're somehow "inside" the system, that we understand exactly what is going on, or in this case what isn't going on. Language models are composed of variations of matrix multiplications, but that isn't a complete description of their behavior. It's like saying because we've looked inside the brain and there's just electrical and chemical signals, the mind must reside somewhere else. It's just a specious argument.

Re: Competitive Programming with AlphaCode

#239

Post by ahgamut »

pedrosorio wrote: post #227
ahgamut wrote: post #206

I find almost every new advance in deep learning is accompanied by contrasting comments: it's either "AI will soon automate programming/ ", or "let me know when AI can actually do ". There are many views on this spectrum, but these two are sure to be present in every comment section. IIUC, AlphaCode was trained on Github code to solve competitive programming challenges on Codeforces, some of which are "difficult for…

> 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 humans who participate in these contests are unable to do so (although I guess the issue here is that Github is not properly indexed and searchable for humans?).

Indeed, so we don't know what "difficult" means for , and hence we cannot compare it to .

My point is, whenever I see a new achievement of deep learning, I have no frame of reference (apart from my personal biases) of how "trivial" or "awesome" it is. I would like to have a quantity that measures this - I call it generalization difficulty.

Otherwise the datasets and models just keep getting larger, and we have no idea of the full capability of these models.

Post reply on HN