HiveBrain v1.2.0
Get Started
← Back to all entries
patterncppMinor

Genetic C++ programming with Brainfuck

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
codereviewcppstackoverflowc++genericsbrainfuck
withgeneticprogrammingbrainfuck

Problem

This was a project I worked on for fun that basically uses a genetic algorithm to produce simple Brainfuck programs that output whatever the user specifies.

I was just was hoping for criticism of the code, mainly if I'm doing anything blatantly wrong. I'm not too familiar with the STL, so there may have been algorithms I could've used from there but I'm not sure. I realize this is a somewhat decent amount of code, so if you just want to focus on a single function or section, that's fine.

```
/
Brainfuck Evolved
Written by Kurtis Dinelle (http://kurtisdinelle.com)

This program attemps to write programs of its own in the brainfuck language, using a genetic algorithm.
The fitness function will take into account how close the output matches, and how concise the program is.
Shorter programs receive a slight bonus.
/

#include
#include
#include
#include
#include
#include
#include "interpreter.h"

// Don't modify this group of constants.
const unsigned CHAR_SIZE = 255; // The max value of a 'cell' in the memory tape.
const unsigned NUM_MUTATIONS = 3; // The number of types of mutations: (ADD, DELETE, CHANGE).
const char INSTRUCTIONS[] = {'+', '-', '>', '(rand()) / static_cast(static_cast(RAND_MAX) / (high - low));
}

unsigned get_random_int(unsigned low, unsigned high)
{
return (rand() % (high - low + 1)) + low;
}

char get_random_instruction()
{
return INSTRUCTIONS[get_random_int(0, NUM_INSTRUC

Solution

There's quite a bit of code here, so I'm not going to get through all of it, but I'll do as much as possible. Also, since I don't have access to your interpreter.h, I can't guarantee everything I've written will compile; there may be syntax errors and a few bugs lurking around, so consider yourself forewarned.

I think in general this is a fun idea, so kudos for that. However, the way it is written is very much C-style with std::string thrown in. I'm going to endeavour to give you a reasonable chunk of it rewritten in modern-style C++, explaining as much as I can along the way. I'll start by separating out a few things that I think can be encapsulated nicely in separate classes.

The first class will be responsible for random number generation and random selection. I'm going to give it the (not fantastic, admittedly) name of random_generator. Further, this is going to replace rand() (which is, without mincing words, pretty much crap), with the pseudo-random generation supplied by C++11:

#include 

class random_generator
{
private:

    std::random_device rand_dev;
    std::mt19937       generator;

public:

    random_generator()
      : generator(rand_dev())
    { }

    double next(double low, double high)
    {
        std::uniform_real_distribution<> dist(low, high);
        return dist(generator);
    }

    std::size_t next(std::size_t low, std::size_t high)
    {
        std::uniform_int_distribution dist(low, high);
        return dist(generator);
    }

    template 
    typename Sequence::value_type select(const Sequence& seq)
    {
        std::size_t index = next(0, seq.size() - 1);
        return seq[index];
    }
};


The parts that make up this class may be unfamiliar (and a fair bit more complex than simply calling rand()), but will produce much "better" random numbers. std::mt19937 is simply a source of pseudo-randomness to draw from. From this, we can use uniform_real_distribution and uniform_int_distribution. These generate uniformly distributed numbers that lie between (and including) the 2 parameters passed in.

The final function utilises templates to pick random values from any container satisfying operator[]: so things like std::vector and std::array.

Let's move on to the actual brainfuck program itself. We'll again make a class (named, inventively, brainfuck_program) that encapsulates a single program:

#include 

class brainfuck_program
{
private:

    static const std::vector instructions;
    static constexpr unsigned num_children = 2;
    static constexpr unsigned char_size = 255; 
    static constexpr unsigned num_mutations = 3;

    random_generator rand_gen;
    std::string      current_program;

public:

    const std::size_t max_program_size;
    const std::size_t min_program_size; 

    brainfuck_program(std::size_t max_size, std::size_t min_size)
      : max_program_size(max_size),
        min_program_size(min_size)
    { }

    char random_instruction()
    {
        return rand_gen.select(instructions);
    }

    bool add_instruction(std::size_t index)
    {
        if(index = min_program_size) {
            program.erase(index, 1);
            return true;
        }
        return false;
    }

    void mutate_instruction(std::size_t index)
    {
        current_program[index] = random_instruction();
    }

    double fitness(Interpreter& bf)
    {
        ...
    }

private:

    void create_random_program()
    {
        std::size_t program_size = rand_gen.next(min_program_size, max_program_size);
        for(std::size_t i = 0; i  brainfuck_program::instructions = {'+', '-', '>', '<', '[', ']', '.'};  

bool operator==(const brainfuck_program& b1, const brainfuck_program& b2)
{
    return b1.current_program == b2.current_program;
}


Here, I've moved a lot of the global variables to do with brainfuck programs into static class variables (since they shouldn't be changed by the user, they should be the same for all generated brainfuck programs).

Many of the functions that simply operated on a passed in std::string before are now member functions. They now modify a (class private) string instead. The code itself hasn't changed all that much, although we're now using the random_generator class that we defined before to select our random instructions for us. Also, the string that encapsulates the program is initiated when the constructor is called.

Finally, we'll look at a class that is designed to deal with populations of brainfuck programs. Let's call it population_manager:

```
#include
#include
#include
#include
#include

class population_manager
{
private:

using prog_score_pair = std::pair;

struct score_sorter
{
bool operator()(const prog_score_pair& p, const prog_score_pair& t) const
{
return s.second > t.second;
}
};

std::vector populations;
std::set population_scores;

public:

const std::size_t population_size;

population(s

Code Snippets

#include <random>

class random_generator
{
private:

    std::random_device rand_dev;
    std::mt19937       generator;

public:

    random_generator()
      : generator(rand_dev())
    { }

    double next(double low, double high)
    {
        std::uniform_real_distribution<> dist(low, high);
        return dist(generator);
    }

    std::size_t next(std::size_t low, std::size_t high)
    {
        std::uniform_int_distribution<std::size_t> dist(low, high);
        return dist(generator);
    }

    template <typename Sequence>
    typename Sequence::value_type select(const Sequence& seq)
    {
        std::size_t index = next(0, seq.size() - 1);
        return seq[index];
    }
};
#include <vector>

class brainfuck_program
{
private:

    static const std::vector<char> instructions;
    static constexpr unsigned num_children = 2;
    static constexpr unsigned char_size = 255; 
    static constexpr unsigned num_mutations = 3;

    random_generator rand_gen;
    std::string      current_program;

public:

    const std::size_t max_program_size;
    const std::size_t min_program_size; 

    brainfuck_program(std::size_t max_size, std::size_t min_size)
      : max_program_size(max_size),
        min_program_size(min_size)
    { }

    char random_instruction()
    {
        return rand_gen.select(instructions);
    }

    bool add_instruction(std::size_t index)
    {
        if(index < max_program_size) {
            current_program.insert(index, 1, random_instruction());
            return true;
        }
        return false;
    }

    bool remove_instruction(std::size_t index)
    {
        if(current_program.size() - 2 >= min_program_size) {
            program.erase(index, 1);
            return true;
        }
        return false;
    }

    void mutate_instruction(std::size_t index)
    {
        current_program[index] = random_instruction();
    }

    double fitness(Interpreter& bf)
    {
        ...
    }

private:

    void create_random_program()
    {
        std::size_t program_size = rand_gen.next(min_program_size, max_program_size);
        for(std::size_t i = 0; i < program_size; ++i) {
            program += random_instruction();
        }
    } 
};

const std::vector<char> brainfuck_program::instructions = {'+', '-', '>', '<', '[', ']', '.'};  

bool operator==(const brainfuck_program& b1, const brainfuck_program& b2)
{
    return b1.current_program == b2.current_program;
}
#include <vector>
#include <numeric>
#include <set>
#include <iterator>
#include <utility>

class population_manager
{
private:

    using prog_score_pair = std::pair<double, brainfuck_program>;

    struct score_sorter
    {
        bool operator()(const prog_score_pair& p, const prog_score_pair& t) const
        {
            return s.second > t.second;
        }
    };

    std::vector<brainfuck_program>          populations;
    std::set<prog_score_pair, score_sorter> population_scores;

public:

    const std::size_t population_size;

    population(std::size_t pop_size)
      : population_size(pop_size),
        populations(population_size)
    { }

    std::pair<brainfuck_program, std::size_t> 
    score_population(Interpreter& bf)
    {
        using prog_inserter = std::insert_iterator<std::set<prog_score_pair, score_sorter>>;
        std::transform(populations.begin(), populations.end(), std::prog_inserter,
                       [&](const brainfuck_program& p) 
                       {
                            auto score = p.fitness(bf); 
                            return std::make_pair(score, p); 
                       });

        return *population_scores.begin();
    }

    double score_total() const
    {
        return std::accumulate(population_scores.begin(), population_scores.end(),
                               0.0, [](const prog_score_pair& p1, const prog_score_pair& p2)
                                    { return p1.first + p2.first; });
    }

 // Other methods...

};

Context

StackExchange Code Review Q#38974, answer score: 4

Revisions (0)

No revisions yet.