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

391–400 of 415 posts

Re: Competitive Programming with AlphaCode

#391

Post by thomasahle »

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…

Can't rule it out, but if Alphacode gets to top 1% in five years, that's when it can basically do algorithms research. We can ask it to come up with new algorithms for all the famous problems and then just have to try and understand it's solutions :O

Re: Competitive Programming with AlphaCode

#393

Post by [deleted] »

tannhaeuser wrote: post #384
YeGoblynQueenne wrote: post #378

Earlier quoted context omitted.

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 ;)

[deleted]

Re: Competitive Programming with AlphaCode

#394

Post by YeGoblynQueenne »

tannhaeuser wrote: post #384
YeGoblynQueenne wrote: post #378

Earlier quoted context omitted.

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 ;)

Let's say I'm aware of it :)

Re: Competitive Programming with AlphaCode

#395

Post by gavagai691 »

hnfong wrote: post #369
gavagai691 wrote: post #315

Earlier quoted context omitted.

Apologies, I don't quite follow your reasoning.

I think the GP means that the AlphaStar team stopped working on the project because they felt it was reaching a dead end and unlikely to produce further results, or at least other ventures might have been more promising. I think that's most likely the case too, otherwise why would they give up?

I guess I feel that there is a big discontinuous jump between "not clearly better than humans" and "clearly better than humans," where the latter is much, much more significant than the former. It seems like going on a hike and stopping before the summit.

Re: Competitive Programming with AlphaCode

#396

Post by Veedrac »

rfoo wrote: post #388
Veedrac wrote: post #375

Earlier quoted context omitted.

> 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

Apologies, I thought you meant ‘optimized’ in a different sense, not in terms of how list.pop is implemented, as AlphaCode wasn't involved in that. You are entirely correct that list.pop uses memmove.

> Someone submitted this 1553D code to Codeforces and it passed

Ah, well that shows you have a 2 second time limit, which is quite a lot of time! Not quite enough to empty a 200k element list with list.pop(0)s, but not far off; a 140k element list squeaks in under the time limit for me.

Re: Competitive Programming with AlphaCode

#397

Post by deanmen »

37ef_ced3 wrote: post #225
deanmen wrote: post #215

Earlier quoted context omitted.

You can do it without a subtraction unsigned int swapbits(unsigned int a) { bool bit6 = a & (1

And, to be clear, this is a human solution. Not as efficient as mine, but kudos.

The compiler seems to generate less efficient code than either if you write the most mechanical solution for swapping the bits in C.

gcc and clang give

   swap:                                   # @swap
        mov     ecx, edi
        shr     ecx, 11
        and     ecx, 32
        mov     eax, edi
        and     eax, -65569
        or      eax, ecx
        and     edi, 32
        shl     edi, 11
        or      eax, edi
        ret

   swap:
        mov     eax, edi
        mov     edx, edi
        and     edi, -65569
        sal     eax, 11
        shr     edx, 11
        and     eax, 65536
        and     edx, 32
        or      eax, edx
        or      eax, edi
        ret

   /* only works on little-endian! */
    typedef union
   {
 struct
 {
  unsigned bit1: 1;   unsigned bit2: 1;
  unsigned bit3: 1;   unsigned bit4: 1;
  unsigned bit5: 1;   unsigned bit6: 1;
  unsigned bit7: 1;   unsigned bit8: 1;
  unsigned bit9: 1;   unsigned bit10: 1;
  unsigned bit11: 1;   unsigned bit12: 1;
  unsigned bit13: 1;   unsigned bit14: 1;
  unsigned bit15: 1;   unsigned bit16: 1;
  unsigned bit17: 1;   unsigned bit18: 1;
  unsigned bit19: 1;   unsigned bit20: 1;
  unsigned bit21: 1;   unsigned bit22: 1;
  unsigned bit23: 1;   unsigned bit24: 1;
  unsigned bit25: 1;  unsigned bit26: 1; 
  unsigned bit27: 1;   unsigned bit28: 1;
  unsigned bit29: 1;   unsigned bit30: 1;
  unsigned bit31: 1;   unsigned bit32: 1;
 };
 unsigned int n; } mybits;

   unsigned int swap(unsigned int n)
   {
    mybits foo;
    foo.n = n;
    unsigned tmp = foo.bit6;
    foo.bit6 = foo.bit17;
    foo.bit17 = tmp;
    return foo.n;
   }

Re: Competitive Programming with AlphaCode

#398

Post by parentheses »

noduerme wrote: post #353
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…

>> filter out 99% of incorrect solutions And next year they can filter out 99.99%. And the year after that, 99.9999%. So literally, an exponentially greater number of monkey/typewriting units. (An AI produced Shakespeare play coming soon). >> we have no clue at all what that actually is and how these model learn This is why I'm super cool-to-cold about the AI/deep learning classes being sold to young people who would…

i like that you drew a connection with monkeys on typewriters.

Re: Competitive Programming with AlphaCode

#399

Post by algon33 »

Isinlor wrote: post #281
algon33 wrote: post #3

How suprising did you guys find this? I'd have said there was a 20% chance of this performing at the median+level if I was asked to predict things beforehand.

There is a prediction market called Metaculus. TL;DR In 2020 community of 169 people and the best forecasters were assigning ~15% that it will happen by July 2021. More specifically, on Dec 31, 2016 in partnership with Center for the Study of Existential Risk, Machine Intelligence Research Institute, and The Future of Life Institute they asked: How long until a machine-learning system can take a simple text descripti…

For some reason I forgot to check metaculus for this. Thanks for the reminder.

Re: Competitive Programming with AlphaCode

#400

Post by algon33 »

machiaweliczny wrote: post #156
algon33 wrote: post #3

How suprising did you guys find this? I'd have said there was a 20% chance of this performing at the median+level if I was asked to predict things beforehand.

I am surprised, as recently OpenAI had ~25% of easy problems and ~2% in competitive problems. Seems like DeepMind is ahead in this topic as well. Actually I think Meta AI had some interesting discovery recently that could possibly improve NNs in genral, so probably this as well. I am not in field but wonder if some other approaches like Tsetlin machines would be more useful for programming.

Somehow I have never heard of Tsetlin machines before this. Are you talking about this https://ai.facebook.com/blog/the-first-high-performance-self... result by MetaAI?
Post reply on HN