Multi-Agent Framework Evolves Rust Code That Reinvents Three Optimization Paradigms on an NP-Hard Problem

MonokoEloba · reddit · 2026-08-20

The author built GenOS, a multi-agent orchestrator where autonomous LLM sub-agents write, compile, benchmark, and iteratively evolve Rust code, sharing knowledge and competing across dozens of generations.

The task: the Reverse Game of Life — recovering the exact Gen-0 state that yields a target Gen-5 grid on a flat 20x20 matrix, a notoriously NP-Hard problem.

GenOS organically evolved three peak architectures:

Epsilon (Gen 17, causal optimizer): mapped causal light-cones for local gradients, but non-linearity misled them; stalled at 306/400.
Omega (Gen 10, SAT solver): encoded the 5-generation grid into a massive SAT formula with stochastic WalkSAT, but choked on combinatorial explosion from dense constraints.
Sigma (Gen 39, Darwinian brute force): evolved a SWAR bit-slicing engine evaluating 64 universes per CPU register, plus simulated annealing with thermal shocks — hitting 378/400.

The discovery: Sigma's stall at 378 wasn't algorithmic failure. Analysis of Omega and Sigma data proved the remaining 22 pixels mathematically UNSAT — the flat topology's dead borders made 400/400 physically impossible. 378 was the universe's hard limit.

The author shares Sigma Gen 39's code and notes none of their hand-written algorithms beat SAT/CDCL.

Original post →

Multi-Agent Framework Evolves Rust Code That Reinvents Three Optimization Paradigms on an NP-Hard Problem

More from coding & agent