Maybe Auto-Research Will Work This Time?

[00:00:00]So, in this video, I'll be giving Auto Research another spin. Now, the idea behind Auto Research is that we have some sort of a script locally that an LM is allowed to change and iterate over.

[00:00:10]Every time that we iterate, we are able to also score the performance of a script. We have some sort of number that tells us how good we are doing. The LM can read this, and this can inform the next iteration of the script, and so forth, and so forth, and the whole point is that the LM might be able to improve its own work. Now, this isn't the first time that I gave this Auto Research a spin. A month or two ago, I tried to run it against traveling salesman problems, and the results were pretty mixed, actually. A big reason for this is that traveling salesman kinds of problems need algorithms that also need to run for a pretty long time. And this whole idea behind Auto Research works best if the script itself only takes a minute or two, and then the LM can make very quick iterations. So, for this video, we're going to be trying out a very different use case, and we're going to do something that is related to this guy.

[00:00:57]This device is known as an Anbernic, and a really cool thing that you could do is you can actually put your own Pico-8 game on this. A Pico-8 is a standard that lets you put an entire game on a PNG image, and I've actually got an instance running on my machine over here. Uh the way this game works is you've got a couple of green dots, that'll be you, and as you can see, I can move this green guy around. I can make a jump in this case, and you can see if you move your guy next to the opponent, the color just flips. And you can make a short jump, and when you do that, you make a clone. When you make a long jump, you leave a hole. So, this is a game that can actually get surprisingly deep, and it's a lot of fun, but only if the AI that you're playing against is pretty good. If the AI is really bad, it's pretty lame.

[00:01:36]Playing against a random player really is too easy. So, what I wanted to do is come up with some sort of system that I could play against. And again, a really big constraint of these kinds of games is that Pico-8 really forces you to have a small, constrained game. It's also partially why game developers like it.

[00:01:53]It's a great system for rapid prototyping because there are so many constraints. There's a maximum number of tokens that your code can have. There's also a maximum size. We're talking kilobytes here, by the way, not megabytes, if I recall correctly. So, I'm not going to be able to do anything with deep learning and reinforcement learning and AlphaGo or anything like that. That would simply not fit. So, what I could do instead is I could try to come up with some sort of a function that's going to take a look at this board state. You know, it's a 7 by 7 grid, some green blobs, some orange blobs, right? And given that input, the function has to figure out what the value of every possible move is, and then we're going to see if we can take the best move. That is something that you could encode in a Python function, and therefore, you could assume that if you have a good simulator, that maybe outer research would actually work for this problem. And that's something I actually tried. I'm happy to report that at the end of the entire experience, I actually have a really good AI that I can play against.

[00:02:46]But there are also a couple of caveats and a couple of things that I got to warn you for if you try this out yourself. So, the whole point of this video is to explain all the lessons that I learned, but a good place to start is maybe to also give a high overview of the setup in general because if you think about it, there are lots of ways you could go about this outer research thing. Now, the way that I chose to go about it is I have my 7 by 7 board, right? With my green guys and my orange guys. And the goal of the game is to have a final state where more green than orange guys exist. If so, then you, the green player, won. The way I'm going to go about it is this board has a state, and that's going to be the input of a score move function. And you can imagine this might be a NumPy array or a Python list of sorts, right? There's lots of ways to represent this, but conceptually, it's a 7 by 7 board, and there's either nothing, green, or orange there. So, it's a three-state 7 by 7 situation. So, you know, the board is not small, but it's not huge, either. But for all the possible moves, we're going to return some scores, just trying to keep it simple. This is the function that the LM is allowed to change. So, that is also in a separate file. And the LLM system prompt makes it very clear that this is the only file that you could go ahead and change. I wasn't that formal about it. You could also add a linter if you wanted to, but once the edit has been made, then there's a separate file with a separate function that has this evaluator that's going to take this score move function, and then it's going to do a bunch of simulations against some known heuristics. Now, one thing that's pretty important here is that the LLM is actually not aware of the heuristics that I'm using here. I want my heuristics to function as a signal. I don't want them to function like a target. Having an LLM do a for loop, that's maybe the easy bit. The hard bit, even without a research, is the methodology. So, the way that I went about it is I have a couple of heuristics. One of them is greedy in terms of oh, the orange player is going to optimize for making a move that's going to be able to capture the most green blobs, and if not, it's going to try to something random. There's heuristics like that that I tried out.

[00:04:44]Those were in a separate file. The LLM was not allowed to read them. The only thing the LLM was allowed to do was this. And effectively from there, you could let it rip. But if you're doing this in practice, there's still this one other thing you do want to have, and that is that you do want to log your results. So, what I ended up doing is I ended up making this big JSONL file, and that contains for every iteration the code that was generated, the score, and also just a little line that says this is the thought or the idea that I was exploring in this one iteration. And when that's done, a new line gets added, a new line gets added. And the nice thing about doing this is that you can watch for changes. So, what I ended up doing is I made a Marimo notebook.

[00:05:21]Basically, it serves as a dashboard for this entire setup, and it just every 2 seconds or so checks, "Hey, did this file update?" If so, then update the view, and that way I had a little dashboard. And that dashboard looked a little bit like this. So, you can see there's this blue line. There's a couple of moments when it ticks up, and there's also a couple of moments when we are trying to iterate, and it tries to improve, it tries to improve, but we're doing worse. And sometimes you see these nudges go up, and after a while, and you know, one thing that you can see is we end up at a pretty good spot, and eventually we do get a little bit better, but there it flattens off at some point as well. Just under 0.8 chance of winning against all these heuristics that I had. Now, while running this, I stumbled across two problems. The first of which is that an LLM can get stuck in trying to repeat the same trick with only a very small variation. So, one thing that I did notice upon inspection is that the LLM was really just trying minor differences, not really getting much better. So, it does help to keep an eye on the whole process, hit stop at some point, and then to also tell the LLM, "Oh, maybe you should consider this other direction altogether." That's something that definitely helped. But even with this setup, there's a very big mistake that I made, and now might be a really good time to also take a step back yourself, watch the animation, and to figure out if you can spot the mistake that I made. Because you see, we had this dashboard, and it was live updating, and I could see improvements happen, and I could also see moments when we didn't make much improvements.

[00:06:43]This was the point in time when I also figured, "Hey, maybe I should kick it, maybe give it some suggestions." But what you're going to notice is that as time moves forward is that the improvements actually get quite small.

[00:06:53]And we're calling an outcome better based off of barely a percentage point in score difference. Now, this is where we might want to do a just a little bit of math. So, let's say over here, right?

[00:07:04]This best candidate, that has a score of 0.77 roughly, let's say. Okay, how many simulations did you do? Because if you only did, let's say, 100 simulations, then the difference between this and the previous best candidate might be because of two outcomes of the entire simulation. And therefore, it might be the case that you're calling this candidate better, not because it's actually better in the long run, but simply because it kind of got lucky. And this is where there's an awkward balance. If you want your score to be more accurate, the more simulations you're going to have to run. But at the same time, the more simulations that you run, the slower the iteration loop is going to be for this auto research. For me personally, I figured I might care a bit more about accuracy than I care about iteration speed for this particular problem. So, when I noticed that we're calling something better based off of a small jump, my first reaction was to say, well, that's great, but we're going to just redo the whole thing. Luckily, I had my JSON L file, so I could replay the entire history to get the score. And when I redid it, I also noticed that this chart just looked different. There's this big jump in the beginning, and that jump is definitely still there when you redo this exercise, but definitely the stuff at the back here where, oh, we called this guy better, but it was just a small jump, that did start to change. So, just as a small reminder, auto research works really well if there's a good score that you can attach to your script, but if there's any sort of noise attached to that score, the main risk is that you're going to pick a file based off of a score that's lucky and not based off of a file that's actually actually better.

[00:08:38]That said, after doing all of this, what tactic was actually best? That was pretty interesting actually to see. The agent on its own came up with a couple of heuristics, and I also injected a few that I thought might be interesting. And these were things like, okay, suppose that I make this move, how much space do I still have for my other guys to move?

[00:08:55]If they get stuck, that would be a bad thing. I also noticed that the outer ring has a lot of value in this game, so how many of the outer ring nodes do I capture? So, things like that eventually went in. But in the end, the approach that really won was the approach where we were weighing all of these other scores and finding the right weighing scheme that ended up being the thing that won. So, it wasn't necessarily one heuristic, it was basically figuring out what heuristics matter and weighing them against each other in the right way. So, there you go. I did end up with a AI that's really hard to beat, so I'm super happy with that. So, in a lot of ways, mission accomplished. I was also very happy that I thought about methodology a lot and that I also prepared such that I had a good dashboard inside of Marimo.

[00:09:37]As you can see, I've got my auto refresh UI over here. I can also uh tune that. But, hopefully this was useful. If you're keen to do things with auto research, it definitely does feel like there's a couple of these instances where it could work really well. But, it doesn't mean that it's a silver bullet that will work for everything. And as always, LLMs are great, but the methodology behind it, that's usually still uh the hard part.