search

kurtjd / brainfuck-evolved

A program which generates its own simple brainfuck programs using a genetic algorithm.
MIT License
5 stars 1 forks source link

Quine Search #1

Open void4 opened 4 years ago

void4 commented 4 years ago

I wonder how fast this approach would find a Quine...

Edit: I added these two lines to the top of calculate_fitness(), let's see what happens:

    GOAL_OUTPUT = program;
    GOAL_OUTPUT_SIZE = GOAL_OUTPUT.length();

Edit: I've put my fork here: https://github.com/void4/Brainfuck-Evolved

kurtjd commented 4 years ago

I wonder how fast this approach would find a Quine...

Edit: I added these two lines to the top of calculate_fitness(), let's see what happens:

    GOAL_OUTPUT = program;
    GOAL_OUTPUT_SIZE = GOAL_OUTPUT.length();

Edit: I've put my fork here: https://github.com/void4/Brainfuck-Evolved

This is awesome, never would have thought to use genetic algorithms for this!

void4 commented 4 years ago

Thanks!

Intuitively, this seems to be a valid method of finding one, since existing Brainfuck quines are not too long (~400-1000 instructions for the shorter ones) and the kind of selection/crossover mechanism your code implements seems to be suited for this.

However, after trying many different parameters, code generation and -mutation tweaks, I still haven't found anything that comes close to being a quine. With the most 'successful' programs only outputting long strings of characters that reduce the averaged distance to the code...

Manually constructed Quines, especially the shorter ones seem to use very involved mechanisms, lookup tables and such, data structures that are unlikely to be generated with this precision by genetic evolution, at least not in a short timeframe. They are fragile constructions, if a single instruction changes their output is drastically changed.

I compiled the manually constructed ones I found here: https://github.com/void4/notes/issues/42

Switching to another brainfuck dialect (e.g. https://esolangs.org/wiki/Symbolic_Brainfuck) may yield more success, but also simultaneously defeats the purpose of finding a pure BF quine (unless the dialects can be translated into each other).

It would be great to have a language of similar low complexity that is also antifragile, perhaps through memory isolation and some sort of composability. This way, a genetic crossover event may break some components, but still preserve the functionality of both parent programs.

I built this recently: https://esolangs.org/wiki/RarVM which may interesting :)