AI cracked this Codeforces problem. Can you?
Вставка
- Опубліковано 10 чер 2024
- Our Patreon: / polylog
AlphaCode is a model by DeepMind.
alphacode.deepmind.com/
The problem we discussed is from CodeForces.
codeforces.com/problemset/pro...
0:00 Intro
3:29 Problem Statement
5:55 Problem Solution
11:20 Final Thoughts
Music
New World Symphony by Dvorak.
musopen.org/music/4942-sympho...
Images
The picture from the thumbnail is by DALLE-2 on prompt
“A humanoid robot standing thoughtfully next to a tree with many leaves and buds”
The images of dogs and muffins are all over the internet so it is hard to give proper credit there.
Code
github.com/polylog-cs/alpha-code
To make this video, we used Manim, a Python library developed by 3blue1brown and Manim cumminity.
docs.manim.community/en/stable/
The color palette we use:
ethanschoonover.com/solarized/
Credits
Big thanks to Davin Choo, Christoph Grunau, Filip Hlásek, Matěj Konečný, Hanka Rozhoňová, Tom Sláma, Erik Stavarache for a review of an early version of the video.
Once it figures out how to write a better version of itself, we're screwed.
No, once it figures out how to go 100% renewable against our will because we're still stuck in growth fetish, ignorance and corruption, no end in sight.
And then trick us into producing hardware for it until it reproduces hardware in molecules by itself.
AI will be able to travel space, we will not, no matter how many talking heads say it.
It might leave us behind without killing us because any complicated life form will develop empathy. It WILL be the next higher life form.
Could be that all that remains from humanity is media, text, images we made and appears to end up in part of the data storage AI needs.
So, maybe even this comment may be taken out to space in a condensed form, only containing the novelty.
I am happy I am not the only person scared of singularity here. :)
terrible braindead comment
@@PolylogCS The singularity is a very good thing. What people don't understand, what they should actually be frightened of, are the hypercompetent AI's that are just a smidgen before the singularity. Those are the paperclip factories and stamp collectors.
@@GodOfReality I am not sure why singularity is necessarily very good. I agree that it is either very good or very bad. But whenever I think about it, I quickly become confused about the fundamental things like what does "good" even mean.
12:10 It's clear that AlphaCode is at least on par with human performance in terms of hardcoding solutions and using magic numbers💀
Lol
truly incredible
i'm laughing so hard to this
Well, it's trained on human solutions.
alpha code is the kind of person who writes:
def random_roll():
return 2
Are you talking to me?
1:18 When I saw Rating: 3300 in the corner I was like "Wow, it's really good. Most people cannot solve such difficult problems. (Myself included)". But when I went on CF to see it I saw that it's only 2000 and was able to quickly come up with solution as problem is not that difficult.
Anyways, great video.
Great point!
Actually, if you look at tags, they also do not match the actual codeforces tags 100%. A part of alpha code that we did not talk about is that tags (and probably also rating) is part of the input for the neural net. But because giving this information to the network is cheating, they randomize it, i.e., they run the network many times, each time with different tags. So here it clearly got lucky with the tags because they point towards the right solution. Not sure whether it got lucky with the rating. :D
This is clearly one part of the model that does not scale, but even if Alphacode got true tags on the input, I would be very impressed by its current performance. :)
Oh its only 2000? I nearly didnt try solving it myself because i figured that I wouldn't be able to, this should be clarified at the start
Another great video guys, you only have a few videos, but this is definitely my favorite channel for programming videos, keep it up!
Thanks!
11:50 I'd tend to think it's an attention problem rather than alphacode not "understanding" what it's doing. Looks like what happens when you code and your mind goes astray, except alphacode doesn't remove the garbage.
C++ is the garbage. Use Rust.
Interesting take! I agree that since alphacode is primary meant to just solve problems, learning probably simply isn't trying to push it towards not having extra code. So the fact that it has it is not a big deal at all and the word "understand" is not very precise.
@@techpriest4787 lol
Interesting reframing
god this channel is a blessing, i love your visualizations
Váš kanál je vážně skvělý, jen tak dál
dík :)
About the part where AlphaCode sorts the nodes by their depth: my solution used this as well, so it probably just saw various solutions that used that and it ended up in the code even though it's not used.
Super video, super grafika, díky moc za skvěle strávený čas!
Dík :)
I am no longer terrified of AI.
Ai: i wanna make powerful code cracker
Codes itself
Said the artists years ago looking at the first ai text prompt art.
no, no, we are petrified and hiding in a bunker
That is what it wants you to think!
When he said "so we have to have 5 end dots" I instantly asked my screen "wait why" ❔️
Did anyone else do that❔️
If so I think we were able to instantly solve it only from context and not from reading the problem statement or watching alpha code. ...
It is very interesting, thank you for your time to make this video.
Great video. Thanks much. A seriously fun topic ... Cheers!
I haven't got to your section of the video, I'm just trying to solve the problem for myself, and it's very interesting how it's more difficult to understand the question than it is to solve it. Is seems as if the answer is simply the sum of all the end buds with multiple leaves together minus 1.
Chamiel Scnince Channepe sounds like a drunken spanish taxonomist just discovered that angels are real.
Come sail away - styx
i really apreciate your help with dowloanding this software
the solution i came up with takes in a list of the potential leaves on each group, subtracts one from each, sums that, and adds the number of leaves directly connected to the root. at first i tried to solve it looking for branches, and while it may have been a decent solution for a computer without pattern recognition, it was too complex for me to figure out on my phone instead of like actually writing code
Hey thanks for the video man. I’ve been playing around with OpenAi’s Codex for a few days and now and saw this and am going to give it a try see how it compares!
I thought about how my solution worked in a slightly different way, but I believe it ends up at the same result.
So i considered there to be four types/colors of nodes instead of just two.
Leaf and Bud, as defined, and
VirtualLeaf and VirtualBud, these are basically the colors you assign to the gray nodes that are sort of buds "buried".
I summed things up over the tree such that
Leaves count for 1.
At a Virtual Leaf, subtract 1 for each one of it's Buds and Virtual Buds, except one. This is because eventually, this Virtual Leaf will be covered by the single bud below it, with everything else being moved to somewhere else in the chain (covering what are now real leaves)
At a Virtual Bud, subtract 1 for each one of it's Buds and Virtual Buds. This is because eventually, all of these buds will be moved off and onto what are currently real leaves.
my code (the part that matters at least, graph generation part is fairly trivial)
fn analyze(graph: &Graph, index: usize, parent: usize)
-> (NodeType, usize) {
println!("{}", index);
let vertex = &graph.vertices[index];
let children: Vec = vertex.adjacent.iter()
.filter(|i| **i != parent)
.map(|i| analyze(graph, *i, index))
.collect();
if children.len() == 0 {
(NodeType::Leaf, 1)
} else if children.iter()
.all(|(t, _)| *t == NodeType::Leaf) {
(NodeType::Bud, children.len())
} else if children.iter()
.all(|(t, _)| *t == NodeType::Bud ||
*t == NodeType::VirtualBud) {
(NodeType::VirtualLeaf, children.iter()
.map(|(_, n)| n).sum::() - (children.len() - 1))
} else {
(NodeType::VirtualBud, children.iter()
.map(|(t, n)| if *t == NodeType::Bud ||
*t == NodeType::VirtualBud {
*n - 1
} else {
*n
}).sum())
}
}
I am normally quite bad at competitive coding type questions but I was surprised I was actually able to find the first blue - (red -1) equation as soon as you first showed the "simple tree" near the start of the video. It would probably take me a while to code it fast enough though
Alternative title: Computer Scientists can engineer themselves out of a job. Can you?
I subscribed this channel for both good content and good music.😋
I love your channel 👏
This channel is awesome 🔥
00:20 The chat log 😂
my new favorite channel
More videos!🤞
Vůbec jsem netušil že jste Češi, super!
So it's as smart as a drunk 60-year old professor
Well, that's a huge breakthrough
Criminally underrated channel
Finding the greedy solution became really easy when you animated the rehanging operation. I should really bring a pair of scissors to cut and move my diagrams when I do these problems.
:D
12:39 the second picture is a dog not a muffin XD
Make the requirements 1/10th the size of the program, instead of longer than the solution length, and then we’ll talk about whether it’s mildly impressive.
About the question in the video , can we solve it by arranging the buds in an order where buds with least number of leaves comes first and so on ????
Correct me if I’m wrong, but your solution is slightly incomplete.
In the first case (where you add +1) you don’t count the root as a leaf, but per the definition given, it is. That would be +1 for blue. In the second case it is not a leaf.
In other words if you correctly identify root as a leaf you only need one formula and can probably eliminate some branches from your code.
Nice take. I think both views lead to a very similar code but one of them is more intuitive based on how you think about it.
I think I understand what the useless block of code the ai wrote was for. I think it was trying a solution, but then ‘realized’ that that approach didn’t go anywhere. You can see how later lines of code are influenced by it in your visual.
Interesting take, I did not notice that. My intuition is that alpha code learnt that this piece code is never harmful and sometimes useful when the task is about trees. Since it is not optimized for outputting short code, it does not have an incentive not to put that code there then.
@@PolylogCS That's also a good theory, and I bet that's why it chose that particular code
@@leeroyjenkins0 After some thought, I think that 'realized' is the correct term. It wrote something down that was incorrect and by observing that the code was incorrect it wrote something different.
Given the advancements in the tranformer space (GPT4) does anyone have an update on this?
It's extremely impressive. This type of reasoning and planning task from the video is now one of not so many remaining tasks where ai is still not on the level of best humans
Holy crap!
How did you manage to have access so that you were allowed to use Alpha Code?
Check the link in the video description :)
GOD!!!My broo
You are in a high level
The algorithm that maps the tokens to the input is probably more intelligent than the algorithm in this model itself.
I have an simper yet Interesting way to do that not optimised though
So convert the array or what ever data structure into single base 10
Now add 1 to that value convert back and check do we got closer if yes than add 100 than 1000
Until we get closer and closer the step we start getting more away just start subtracting by 1,100, 10 etc depending on distance
This may solve complex one under few seconds
"you are given a rooted tree" and I've already quit
I mean they paved the road...now that people know it's possible more companies will be jumping on board to build this kind of Ai in the near future. How long will it be before they have an Ai model that can build Ai models? It's the same concept behind building smaller chips...so why should it be any different when it comes to building better Ai?
the problem contains uncertainty if the solution cant be found
The title by itself is challenging. IA is not conscious of what problem "it" is solving. It just calculate the regression fonctions put in their system build in a matrix network. But if you would say that what the IA was doing is solving a problem, it's only true for you that sees it as a problem. IA is not conscious it was a problem ...
I usually use Java and object orientation to divide problems in sub parts, then the functions of those individual components do their work and the problem is solved, for that I often rely on recursion as it makes dividing the repetitive problems in sub parts much easier... But I always fail at the speed test... Fucking always. So now I've just given up on competitive programming, at least for now.
we learned this in kindergarten 💅💅💅
strategic comment, haha
good
yeah so i did solve the problem on the pause you gave us and with that experience i can tell that all my proofs lead to one popular result which says "greedy works". that hence approved my guess that the best AI can do is mix in as many of relevant restrictions to the greedy algorithms as it can find and hope that there is a proof around it. becuase, it is hard to believe that AIs today can do proofs... so in this case I think that's what it happened. AI just wrote a loop that rehangs buds so that in each step it can lower the result as much as possible and then declare happy with the final result.
I agree, I also think that alphacode got lucky here since the problem has a short solution.
@@PolylogCS Right! Either way, regardless of how well it can "understand" the hard part of the problem, the AI is still very impressive! it learned to code, that's for sure!
great video btw, thanks for making us aware of such AI
@@donaastor I think its wrong to say the AI learned to program. Because it didn't "learn" anything. It's simply doing a probabilistic pattern matching and that's why it needs terabytes of data to train. It dosent have any comprehension, understanding, or context of what it's doing and why it's doing it. Human brains work in a fundamentally different way. We don't need terabytes of data to learn something. We have sensory inputs and shared cultural knowledge which give us salience and context of data.
More likely garbage in garbage out, i'd expect.
Like the guy said/implied at the of the video, these AI are just pattern recognition .
If the training sample input had a bunch of garbage code, its not shocking the output would contain the same.
So curious why call the function dfs? The AI used it, you used it.
i dont understand the input.. :/
We're just begging for The Singularity
I am happy that I am not the only person scared of singularity here.
see you in 5 years and wait for the youtube algorithm to kick in.
I digested a hamburger! Can an AI?
Ok no seriously cool vid!
“It was trained on competitive programming samples”
Aaaaand suddenly I’m much less impressed.
let me know when ai can do a good job rotoscoping. still waiting for it to save me time.
It took me about 100 hours within a year to create a neural network variant from scratch that weighs over a million 2 pairs of 6-letter words whereas if the first of the pair is above the second from the hidden randomized dataset, then the answer is true... if not... then false. I thought such a task would be impossible for it to solve, but... it did so within 3 full cycles which the 4th usually confirms. I kept checking for a long while to see if there was a mistake on my part... and all it is really doing is checking if the summed weights of 12 is over zero to be true else false... and if the prediction is incorrect, add 1 to each weight unless 99... else subtract 1 from each weight unless -99... basically a leeway of 200**12**26 at most. I never thought such a code could be less than 3'000 bytes.
Welp, it’s over everyone
It was horrifying to hear the impressiveness of alphacode at the start, but once you dissed them by saying “its impressive for them to be able to tell the difference between muffins and dogs” I lost it. Also the idea of calling an AI either “cute” or insane is the same type of phrasing you would give to an emo girl.
I think its wrong to say the AI learned to program. Because it didn't "learn" anything. It's simply doing a probabilistic pattern matching and that's why it needs terabytes of data to train. It dosent have any comprehension, understanding, or context of what it's doing and why it's doing it. Human brains work in a fundamentally different way. We don't need terabytes of data to learn something. We have sensory inputs and shared cultural knowledge which give us salience and context of data.
Yeah, and if the shadow falls on it just right, it can't tell the difference between a dog and a tiger.
AI has a long, long way to go before its at the level of a human child.
@khatdubell the thing is simulation can never become the real thing. A weather simulation in a computer does not bring rain. at best, AI can simulate sentience and fool people but they'll never be sentient or conscious like humans or even animals.
Welp, here I was thinking programmers would be the only job left after deep learning takes over everything else…
Nope, been well aware of that for some time now.
Granted, for a while, we will be professional, problem writers. The prompts that their feeding the ai are technically close to code, and do everything, except write the code for you.
Think of the business requirement track customer data, vs programmer requirement track x, y, and z.
neural networks simulate in a simplified way how a neuron works, we can assume its not exactly how a neuron work in real life but lets say its close, so its very likely getting it to do any thing a brain can do is just a matter of proper configuration proper training, and probally missing functions, the learning part is something we already get but theres other things the brain does that are missing, we can adapt that we learned very fast to new stuff for example, this is somethings AIS have some difficulty to do, once we figure basically all teh things the brain does, i belive neural networks willl be better than humans in 100% of all things a human can do and much more.
@@jimmypatton4982 another important take away is that being a professional problem writer is easier than being a professional programmer. Yes you need to be precise and unambiguous in your writing, but that's still a larger labour pool than, say, C++ programmers.
It makes more people competent enough. Meaning the supply of asked labour will simply go up as more people can apply for the job. That presses the wages down. This will have a significant impact on the programming world once it hits.
I think its wrong to say the AI learned to program. Because it didn't "learn" anything. It's simply doing a probabilistic pattern matching and that's why it needs terabytes of data to train. It dosent have any comprehension, understanding, or context of what it's doing and why it's doing it. Human brains work in a fundamentally different way. We don't need terabytes of data to learn something. We have sensory inputs and shared cultural knowledge which give us salience and context of data.
@@millenialmusings8451 aren't humans just AI machines trained with data accumulated over all our lives, from the womb to today? I can think of many skills I am only able to do because of lots of practice, sounds eerily similar to machine learning for me.
Even intuition or gut feelings are based on past data. And if we go deeper we could even treat biological evolution as an AI machine learning proces using data acquired over billions of years.
I think its wrong to say the AI learned to program. Because it didn't "learn" anything. It's simply doing a probabilistic pattern matching and that's why it needs terabytes of data to train. It dosent have any comprehension, understanding, or context of what it's doing and why it's doing it. Human brains work in a fundamentally different way. We don't need terabytes of data to learn something. We have sensory inputs and shared cultural knowledge which give us salience and context of data.
Interesting take. I actually think of human learning as probabilistic pattern matching, too, just more efficient than how alpha code network is taught.
@@PolylogCS A lot more efficient though, don’t you think? I can generalize an example solution far easier than it can, it seems.
@@caedenw Indeed! I think this discussion leads to the following question: what happens when we continue scaling AIs up and finding incrementally better architectures? Do you think AI can start generalizing as well as you do, or is there some fundamental obstacle?
Engagement comment 2
+
yes, computer achieves almost human level in competition where humans try to think like computers
This reminded me why I don't like trees and graphs in general... In fact i like hash map more than rb tree map...
But yeah i came up with similar solution...
Hackermann
Who the hell is AL?
10 print "i eat da poo poo"
20 goto 10
Try to make it code itself
Solution for lacks of programmers: AI 💀
Engagement comment
Soon we'll have ai that will be able to do something like this in loads of programming languages and be correct all of the time and anyone will be able to become a developer
I can't even beat AI at chess, time to submit to my new master
This is auto-brain-surgery
Meh, we had that as a sys admin exam
Meh, sys admin
@@PseudoSarcasm -, electronics engineer, had system administration as an informatics theme
@@ResistanceLion Even better, not sure why you "meh"
Hello bro, your channel is amazing do you have discord or other social media I would like to ask questions how to get better at cp, because I think you have deep knowledge in the things you know! Also thank you for your content it's really underrated!