Table of Contents
The BrainFuck Evolver. Experiments in Genetic Programming using Brainfuck.
Genetic Programming (GP) has already been shown to produce novel solutions to problems 1). Problems with existing GP methods include very specific setup and simulation requirements. For example, a novel antenna was designed using GP 2), but to test the design, an RF simulator had to be designed as well. BFE attempts to eschew this complication.
BFE uses Brainfuck as its “genes.” Brainfuck (BF) is a Turing-complete programming language, meaning it can simulate any other Turing-complete language. Any function or algorithm that takes data, does some calculations and produces output can also be performed with BF.
BF is a software implementation of the theoretical Turing machine consisting of a read/write head and an infinite sheet of memory cells. BF has eight commands, each a single character. The commands '<' and '>' move the read/write head to the left and right, respectively. The commands '+' and '-' increment and decrement the value of the cell at the read/write head. The '[' command jumps to the corresponding ']' command if the cell value under the read/write head is 0. The ']' command returns program control to its corresponding '['. The brackets function exactly like a while() loop in a more traditional programming language. Lastly, the '.' and ',' commands read and write to the sheet to standard input/output. That is to say, the '.' prints the cell value (character) under the read/write head and ',' reads in a value and writes it to the cell under the read/write head.
Programmatically, the read/write head is equivalent to a pointer and the sheet is simply a contiguous block of RAM.
In many ways, BF is ideal to use as programmatic genes. Aside from being Turing-complete, which allows it to do anything that can be accomplished with any other programming language, strings of non-functional code can exist and be bypassed. With a single character (command) mutation that bypassed code path can become active, just like actual genetic code consisting of codons.
Specific Design Needs
There are 4 key design needs to make BFE functional: the framework itself, which needed to be, not just multi-thread, but multi-node capable; a function to mutate BF strands; a BF interpreter; and a means (pun intended) of scoring strands.
BFE is the framework in it's entirety. Previous versions of BFE relied on a master script with a slave running for each core in a cluster.
The latest incarnation consists a single Tcl script using an interpreter with OpenMPI bindings. A stand-alone executable is used for running the bf code and a C-based Tcl extension provides the 'nmc' command used to score output.
BFE tracks all mutations it generates, but when considering the next generation, it groups by score and picks randomly from the top 2% of this population. In this way, different 'species' are picked rather than the same species of strand overfilling the top ranks.
BFE uses a stripped down version of UBI as its BF interpreter. Ubi is an in-house developed BF interpreter, originally designed with the primary goal of being feature-complete and compatible with any language that could loosely be called Brainfuck. It achieved this through togglable options and adjustable cell and sheet sizes. For BFE, ubi3 was stripped down to render ubi4. All togglable options were stripped out, the sheet size was fixed at around 62 MB, bounds checking was removed, a few optimizations were put in.
Without bounds checking, programs can and do segfault the interpreter–this is accepted and by design. Crashing from trying to use too much memory is the desired behavior and comes at no cost to speed or increased code size. The interpreter is also setup to kill it self (via an alarm(2) call) after 30 seconds of running. Both the memory sheet size and kill time are dependent on what the desired outcome is. More complicated and more computationally intense algorithms will of course need more memory and more time to execute.
Ubi's secondary design goal was speed of execution. Like ubi3, ubi4 achieves its speed by reading in the BF instructions and converting them to a linked list of structs and performing a few optimizations long the way. Repeated commands that increment the pointer or cell are condensed into a single operation. Known command patterns are are optimized into single operations (currently only
[+], which are optimized to
*ptr = 0 ).
For larger, longer running BF programs, it may prove faster to actually generate native machine code from the BF code and execute that, but at the current sizes BFE is working with, this quick, in-memory linked list approach seems to work best.
n-Depth Mean Compare
Perhaps the greatest challenge in putting BFE together was determining how to score strands. n-Depth Mean Compare (NMC) compares one ordered set of bytes to another of potentially differing length. NMC returns a floating point greater than or equal to 0. The closer to zero, the more similar the sets are. A score of zero means the sets are identical.
In function and practice, NMC is similar to calculating Jaccard distance, but also takes into account how far removed the set of bytes are from one another, not just how many bytes are common between the two. To clarify, NMC does not just calculate how similar one set is to another. The lower the n-Depth Mean Compare score, the fewer steps are needed to transform one set to the other.
If working with a BF interpreter (such as ubi4) that has cell wrapping (I.E. 255 + 1 = 0) NMC must account for this, as no pair of bytes ever has a difference greater than 128. This done simply by subtracting any difference greater than 128 from 256.
In BFE, BF programs are known as strands (ala DNA). Strands are initially randomly generated then evaluated and scored against reference output using NMC. Other optimizations are possible (for program speed or program size).