[GuB-42]

Using evolution in the context of Core War is not a new idea by far, it is even referenced in the paper.

Examples here: https://corewar.co.uk/evolving.htm

The difference here is that instead of using a typical genetic algorithm written in a programming language, it uses LLM prompts to do the same thing.

I wonder if the authors tried some of the existing "evolvers" to compare to what the LLM gave out.

[dgacmu]

Oh man, that's funny to see one of my grad school class projects in that list. Takes me back. :-)

From that experience: The LLM is likely to do drastically better. Most of the prior work, mine included, took a genetic algorithm approach, but an LLM is more likely to make coherent multi-instruction modifications.

It's a shame they didn't compare against some of the standard core wars benchmarks as a way to facilitate comparisons to prior work, though. Makes it hard to say that they're better for sure. https://corewar.co.uk/bench.htm

[throw_paper]

For anybody who stumbles over this thread and is curious:

Ring Warrior Enhanced v9 has a Wilkies score of 34, and

Spiral Bomber Optimized v22 has a Wilkies score of 85.

At least that's what my quick and dirty check with exMars says :-)

34 is not that great. 85 is better, but I think some Core War evolvers can match it. For instance, the MEVO example at https://newton.freehostia.com/net/corewar/evol/ describes an evolved warrior with a score of 93.

[jacquesm]

I'm not sure if that will hold up. The LLM is not going to do anything random and that is actually a powerful component that makes original output possible.

[kyralis]

I wonder if a combination would be useful. Use an actual GA to do the mutation, and then let an LLM "fix" each mutated child.

[jacquesm]

Could be. But the interesting thing is that all you can do here is optimize. Random chance is - like attention ;) - all you need.

[Ieghaehia9]

That in turn makes me wonder:

Given fixed opposition, finding a warrior that performs the best is an optimization problem. Maybe, for very small core sizes like a nano core, it would be possible to find the optimum directly by SAT or SMT instead of using evolution? Or would it be impractical even for those core sizes?

[slickytail]

I think it would, for all practical purposes, be impossible to determine an optimal warrior, even at very small core sizes. Not only is the search space huge but the evaluation function can take unbounded time to resolve. We should consider the halting problem embedded inside the optimization target as a clue to the problem's difficulty.

[Ieghaehia9]

That's the thing: Core War matches last a finite time (after which the match is judged a tie). So you have a finite memory space, finite time, and a finite number of match combinations. And for predetermined constant N, the bounded halting problem ("does the program halt within N steps") is in NP.

For the nano hill[1], the constants are: each warrior has a max of five lines of code, core size is 80 instructions, and a match lasts a maximum of 800 cycles.

If N = 1, it's clear that the best you can do is drop a bomb at a fixed location and hope you hit. So that is mostly a tie. For N=2, it's probably still not possible to do anything useful. With N = 10, perhaps a quickscan is possible. N = 800 -- who knows?

[1] https://corewar.co.uk/nano.htm

[api]

See also:

https://en.wikipedia.org/wiki/Tierra_(computer_simulation)

https://avida-ed.msu.edu

https://github.com/adamierymenko/nanopond

Lots of evolving bug corewar-style systems around.

I think the interesting thing with this one is they're having LLMs create evolving agents instead of blind evolution or some similar ML system.