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

381–390 of 415 posts

Re: Competitive Programming with AlphaCode

#381

Post by qayxc »

thomasahle wrote: post #57
prideout wrote: post #46

It is obvious to me that computer programming is an interesting AI goal, but at the same time I wonder if I'm biased, because I'm a programmer. The authors of AlphaCode might be biased in this same way. I guess this makes sense though, from a practical point of view. Verifying correctness would be difficult in other intellectual disciplines like physics and higher mathematics.

Just make it output a proof together with the program.

That won't work because the systems aren't trained on proofs and proper theorem provers don't work that way either.

Re: Competitive Programming with AlphaCode

#382

Post by hnfong »

qayxc wrote: post #380
blt wrote: post #52

I am always surprised by the amount of skepticism towards deep learning on HN. When I joined the field around 10 years ago, image classification was considered a grand challenge problem (e.g. https://xkcd.com/1425/ ). 5 years ago, only singularity enthusiast types were envisioning things like GPT-3 and Copilot in the short term. I think many people are uncomfortable with the idea that their own "intelligent" behavior…

This scepticism shouldn't surprise you. Not being sceptical is just an indicator that you've not been in the field for long enough. 30 years ago, the end of programming was prophesised, because 5th generation languages (5GL) and visual programming would enable everybody to design and build software. 20 years ago, low-code and application builders were said to revolutionise the industry and allow people in business ro…

I think you and GP are talking about different things.

You're saying a lot of so-called technological breakthrough is more hype than substance. The GP is saying that people tend to dismiss actual breakthroughs as mundane stuff. Once $method is published that solves $hardproblem, people comment as if $hardproblem was never hard in the first place, and moves the goalposts a bit saying "if $harderproblem can be solved, then that would be profound".

I think the truth is (obviously) somewhere in between. Btw, I dare you go back to a 1980s programming environment and tell me that the programming paradigm shifts are just hype :D My one-liner python scripts can probably do much more than an average coder writing assembly... and given modern hardware my code runs faster too!

Re: Competitive Programming with AlphaCode

#383

Post by hnfong »

evouga wrote: post #290
xibalba wrote: post #288

Between developments like this (and Copilot [Is there a general accepted word for this class of things e.g. "AI Coders"?) and the move toward fully remote, I predict the mean software engineering salary in the United States will be lower in 10 years (in real dollars) than it is today.

I think this is a safe bet, but I would make it with or without the presence of AI Coders. We're clearly in the middle of Tech Bubble 2.0 and it's sure to pop in the next 10 years (and probably much sooner, given the recent crypto and NASDAQ rumblings).

People have been talking about tech bubbles for years, there might be a small financial bubble due to the money printing in recent years but I'm not seeing a big bust coming like dot-com. Tech compensation is probably more influenced by the discrepancy between locations. Once people figure out how to properly handle remote workers and remote teams (which is happening due to Covid), global compensations level will probably level out.

Re: Competitive Programming with AlphaCode

#384

Post by tannhaeuser »

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

Possibly interesting trivium: automated debugging was first described in 1982, in Ehud Shapiro's PhD thesis titled "Algorithmic Program Debugging" (it's what it sounds like and it can also generate programs by "correcting" an empty program): https://en.wikipedia.org/wiki/Algorithmic_program_debugging Of course all this targeted only Prolog programs so it's not well-known at all.

It's also the starting point for Inductive Logic Programming (as in Shapiro's "Model Inference System"), as I'm sure you know ;)

Re: Competitive Programming with AlphaCode

#385

Post by __MatrixMan__ »

hnfong wrote: post #364
noduerme wrote: post #354

Earlier quoted context omitted.

>> While lots of commenters seem concerned about jobs, I look forward to having the dataset oliphaunt and ship computer from Fire Upon Deep someday soon. I think this is more worthy of debate than anything about DSL models or current limits to problem spaces. I'm not concerned about my job, but I am concerned about a world where corporate money starts shifting toward managing AIs as beasts rather than coding clever s…

"Understanding the code" might not be that big of a deal as you might think -- we have this problem today already. A talented coder might leave the company and the employer may not be able to hire a replacement who's as good. Now they have to deal with some magic in the codebase. I don't hear people giving advice not to hire smart people. At least with AI, you can (presumably) replicate the results if you re-run ever…

> Now they have to deal with some magic in the codebase. I don't hear people giving advice not to hire smart people.

People do advise against hiring people who write incomprehensible code.

Yeah every now and then you run across some genius with sloppy code style and you have to confine them to a module that you'll mark "you're not expected to understand this" when they leave because they're really that much of a genius, but usually the smart people are smart enough to write readable code.

Re: Competitive Programming with AlphaCode

#386

Post by qayxc »

hnfong wrote: post #382
qayxc wrote: post #380

Earlier quoted context omitted.

This scepticism shouldn't surprise you. Not being sceptical is just an indicator that you've not been in the field for long enough. 30 years ago, the end of programming was prophesised, because 5th generation languages (5GL) and visual programming would enable everybody to design and build software. 20 years ago, low-code and application builders were said to revolutionise the industry and allow people in business ro…

I think you and GP are talking about different things. You're saying a lot of so-called technological breakthrough is more hype than substance. The GP is saying that people tend to dismiss actual breakthroughs as mundane stuff. Once $method is published that solves $hardproblem, people comment as if $hardproblem was never hard in the first place, and moves the goalposts a bit saying "if $harderproblem can be solved,…

> Btw, I dare you go back to a 1980s programming environment and tell me that the programming paradigm shifts are just hype

Been there, done that. I did consulting for a huge company a few years back. They ran their entire business on IBM mainframes running an ancient VSE-based OS.

I had the pleasure of maintaining IBM HLASM (high level assembly) programs with change logs dating back to 1982.

Working with those programs (they were excellently documented) using ICCF wasn't much different from using vim really and the language itself is by far the best assembly dialect I've ever worked with (especially the powerful macro system).

Sure, productivity is much higher in higher level languages if only because you need to write less code. Your Python one-liner, however, can still be as wrong as 100-lines of assembly or 20 lines of C if you make the wrong assumptions.

That's the part that just doesn't change, no matter the underlying technology: garbage in - garbage out. Someone has to write the problem specification and more often than not, that's the part where things start to go sideways.

It's also one of the reasons model-driven development didn't really catch on: MDD only works of you know your problem domain to a T beforehand, because iterating models is a pain; that's rarely the case, though as usually code and understanding of the problem evolve side-by-side.

Explaining a problem precisely, concisely, and correctly so that an AI can synthesise software that hopefully implements it correctly is not as great as a leap forward as you might think.

I'd really suggest taking a look a Rational Rose and similar platforms to get a glimpse at what automated code generation looked like 25 years ago - even back then you rarely had to write actual code (provided the problem domain was well-known and well-specified), even without AI.

Re: Competitive Programming with AlphaCode

#387

Post by atleta »

HeavyStorm wrote: post #366
GuB-42 wrote: post #304

Earlier quoted context omitted.

I think programmers are relatively "safe" from AI for the simple reason they are the ones who talk to AI. The job of programmers is to have machines do stuff so that humans don't have to, and of course, they do it for themselves too. Scripts, libraries, compilers, they are just tools to avoid flipping bits by hand. If something like copilot is not embraced by all programmers, it is that it is often less than helpful,…

Problem is, to "talk with AI", most developers would need to 'retrain' (to use GP's word). Writing and training a neural network is very different from writing a common program.

But it's not that. We're not talking about training narrowly intelligent ML systems for specific problems. You're right, that's a distinct skill. We're talking about a ML system that can write code based on some higher-than-now level of human input. What that level will/could be is what we're arguing about. Whether it has to be done by some kind of programmer-like person or whether it can be a more generic user/product-owner/product manager. I.e. someone who understands the problem domain but doesn't know too much about the solution domain/technology.

Those ML/AI systems will also have to be built, coded and trained but that's a job for a very small set of people compared to the total number of end users (and the total number of developers on the market today). And, as the ML/AI field stands, it always seem to turn out that specialized algorithms that do what the ML layer cannot do, get pretty quickly eliminated by the ML layer. So most solutions always gets closer and closer to end-to-end.

Re: Competitive Programming with AlphaCode

#388

Post by rfoo »

Veedrac wrote: post #375
rfoo wrote: post #346

Earlier quoted context omitted.

2e5 is enough for making a naive O(n^2) solution to get TLE. This is likely due to the fact that in AlphaCode's solution the "inner O(n) loop" is actually a memmove(), which is optimized to be insanely fast.

> AlphaCode's solution the "inner O(n) loop" is actually a memmove(), which is optimized to be insanely fast. Again, it is not. CPython does not do these things. The web page says, and this is corroborated in the paper, > Solutions were selected randomly, keeping at most one correct (passes all test cases in our dataset) and one incorrect sample per problem and language. Note that since our dataset only has a limited…

> CPython does not do these things.

Again, it is.

https://github.com/python/cpython/blob/2d080347d74078a55c477...

This is the memmove() I mentioned above. Like, I actually perf-d the code and confirmed this is in the hot loop.

> but 1553D was not part of that.

Someone submitted this 1553D code to Codeforces and it passed: https://codeforces.com/contest/1553/submission/144971343

Re: Competitive Programming with AlphaCode

#389

Post by Tanjreeve »

faizshah wrote: post #338
briga wrote: post #280

Earlier quoted context omitted.

Another way to frame it is that these models still perform very poorly at the task they're designed to do. Imagine if real programmer needed to write a solution a hundred times before they were able to achieve (average) performance. You'd probably wonder if it was just blind luck that got them to the solution. You'd also fire them. What these models are very good at doing is plagiarizing content, so part of me wonder…

I was really impressed with a lot of the GPT3 stuff I had seen people showing so I gave it a spin myself. I was surprised by how repetitive it seemed to be, it would write new sentences but it would repeat the same concepts among similar prompts. I wish I saved the examples, it was like when a chat bot gets in a loop but GPT3 varied the sentence structure. I think that if you look closely at transformer models output…

Id be shocked if people pitching startups and research grants etc all started saying "yeah this stuff isn't going to work for a couple of decades in any kind of sustainable manner" even if these types of unknowable unknowns were known.

Re: Competitive Programming with AlphaCode

#390

Post by thorwwaskeas »

the-smug-one wrote: post #235
gfd wrote: post #95

Earlier quoted context omitted.

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!

  from collections import defaultdict
  def backspace(s1,s2):
      h = defaultdict(lambda:0)
      for x in s1:
          h[x] = h[x] + 1
      for x in s2:
        h[x] = h[x] - 1
      j = 0
      maxj = len(s2) - 1
      for x in s1:
        if x != s2[j]:
            h[x] -= 1
        elif j = 0 for y in h.values())

  def random_backspace(s1):
    res = []
    for x in s1:
        if randint(0,1) == 0:
            res.append(x)
    return "".join(res)

  def backspaceTest(s1):
    return all(backspace(s1,random_backspace(s1)) for _ in  range(100))
Post reply on HN