AI-Evolve-Befunge

 view release on metacpan or  search on metacpan

lib/AI/Evolve/Befunge.pm  view on Meta::CPAN

within that script.  Otherwise, read on.

This particular file (AI/Evolve/Befunge.pm) does not contain any code;
it exists mainly to provide a version number to keep Build.PL happy.
The rest of this file acts as a quick-start guide to the rest of the
codebase.

The important bits from a user's standpoint are the Population object
(which drives the main process of evolving AI), and the Physics plugin
(which implements the rules of the universe those AI live in).  There
are sections below containing more detail on what these two things
are, and how they work.


=head1 POPULATIONS

The Population object is the main user interface to this project.
Basically you just keep running it over and over, and presumably, the
result gets better and better.

The important thing to remember here is that the results take time -

lib/AI/Evolve/Befunge.pm  view on Meta::CPAN

thing it does is checks the "inbox" directory for any new incoming
critters.  If they are detected, they are imported into the population
(and deleted from the "inbox").

Imported critters will compete in the next generation.  If they win,
they will be involved in the reproduction process and may contribute to
the local gene pool.

On the server end, a script called "migrationd" is provided to accept
connections and distribute critters between nodes.  The config file
specifies which server to connect to.  See the CONFIG FILE section,
below.


=head1 PRACTICAL APPLICATION

So, the purpose is to evolve some nice smart critters, but you're
probably wondering, once you get them, what do you do with them?
Well, once you get some critters that perform well, you can always
write up a production program which creates the Physics and Critter
objects and runs them directly, over and over and over to your heart's

lib/AI/Evolve/Befunge/Critter.pm  view on Meta::CPAN

       |09876543210123456789|
       |1         |         |
       |----------|         |

Where:

    C is befunge code.   This is the code under test.
    B is boardgame data. Each location is binary 0, 1 or 2 (or
                         whatever tokens the game uses to represent
                         unoccupied spaces, and the various player
                         pieces).  The B section only exists for
                         board game applications.

Everything else is free for local use.  Note that none of this is
write protected - a program is free to reorganize and/or overwrite
itself, the game board, results table, or anything else within the
space it was given.

The universe is implemented as a hypercube of 1 or more dimensions.
The universe size is simply the code size times two, or the board size
times two, whichever is larger.  If the board exists in 2 dimensions

lib/AI/Evolve/Befunge/Critter.pm  view on Meta::CPAN

=head1 LIMITS

This execution environment is sandboxed.  Every attempt is made to
keep the code under test from escaping the environment, or consuming
an unacceptable amount of resources.

Escape is prevented by disabling all file operations, I/O operations,
system commands like fork() and system(), and commands which load
(potentially insecure) external Befunge semantics modules.

Resource consumption is limited through the use of a currency system.
The way this works is, each critter starts out with a certain amount
of "Tokens" (the critter form of currency), and every action (like an
executed befunge instruction, a repeated command, a spawned thread,
etc) incurs a cost.  When the number of tokens drops to 0, the critter
dies.  This prevents the critter from getting itself (and the rest of
the system) into trouble.

For reference, the following things are specifically tested for:

lib/AI/Evolve/Befunge/Migrator.pm  view on Meta::CPAN

    $self->spin_writes();
    $self->spin_exceptions();
}


=head2 spin_reads

    $migrator->spin_reads();

Handle read-related events.  This method will delay for up to 2
seconds if no reading is necessary.

=cut

sub spin_reads {
    my $self = shift;
    $self->try_connect() unless defined $$self{sock};
    my $select = IO::Select->new($$self{loc});
    $select->add($$self{sock}) if defined $$self{sock};
    my @sockets = $select->can_read(2);
    foreach my $socket (@sockets) {

lib/AI/Evolve/Befunge/Physics.pm  view on Meta::CPAN

    my $score = $physics->run_board_game([$critter1,$critter2],$board);

Run the two critters repeatedly, so that they can make moves in a
board game.

A score value is returned.  If a number greater than 0 is returned,
the critter wins.  If a number less than 0 is returned, the critter
loses.

The score value is derived in one of several ways... first priority
is to bias toward a creature which won the game, second is to bias
toward a creature who did not die (when the other did), third,
the physics plugin is asked to score the creatures based on the moves
they made, and finally, a choice is made based on the number of
resources each critter consumed.


=cut

sub run_board_game {
    my ($self, $aref, $board) = @_;

lib/AI/Evolve/Befunge/Physics.pm  view on Meta::CPAN

    return $self->run_board_game([$critter1,$critter2], $board);
}


=head2 double_match

    my $relative_score = $physics->double_match($bp1, $bp2);

Runs two board games; one with bp1 starting first, and again with
bp2 starting first.  The second result is subtracted from the first,
and the result is returned.  This represents a qualitative comparison
between the two creatures.  This can be used as a return value for
mergesort or qsort.

=cut

sub double_match :Export(:DEFAULT) {
    my ($self, $config, $bp1, $bp2) = @_;
    my $usage = '...->double_match($config, $blueprint1, $blueprint2)';
    croak($usage) unless ref($config) eq 'AI::Evolve::Befunge::Util::Config';

lib/AI/Evolve/Befunge/Population.pm  view on Meta::CPAN

=head1 INTERNAL METHODS

The APIs of the following methods may change at any time.


=head2 mutate

    $population->mutate($blueprint);

Overwrite a section of the blueprint's code with trash.  The section
size, location, and the trash are all randomly generated.

=cut

sub mutate {
    my ($self, $blueprint) = @_;
    my $code_size = $blueprint->size;
    my $code_density = $self->config->config('code_density', 70);
    my $base = Language::Befunge::Vector->new(
        map { int(rand($code_size->get_component($_))) } (0..$self->dimensions-1));

lib/AI/Evolve/Befunge/Population.pm  view on Meta::CPAN

    $blueprint->code($code);
    delete($$blueprint{cache});
}


=head2 crossover

    $population->crossover($blueprint1, $blueprint2);

Swaps a random chunk of code in the first blueprint with the same
section of the second blueprint.  Both blueprints are modified.

=cut

sub crossover {
    my ($self, $chr1, $chr2) = @_;
    my $code_size = $chr1->size;
    my $base = Language::Befunge::Vector->new(
        map { int(rand($code_size->get_component($_))) } (0..$self->dimensions-1));
    my $size = Language::Befunge::Vector->new(
        map { my $d = ($code_size->get_component($_)-1) - $base->get_component($_);

lib/AI/Evolve/Befunge/Population.pm  view on Meta::CPAN

    delete($$chr2{cache});
}


=head2 crop

    $population->crop($blueprint);

Possibly (1 in 10 chance) reduce the size of a blueprint.  Each side
of the hypercube shall have its length reduced by 1.  The preserved
section of the original code will be at a random offset (0 or 1 on each
axis).

=cut

sub crop {
    my ($self, $chromosome) = @_;
    return $chromosome if int(rand(10));
    my $nd       = $chromosome->dims;
    my $old_size = $chromosome->size;
    return $chromosome if $old_size->get_component(0) < 4;

lib/AI/Evolve/Befunge/Util.pm  view on Meta::CPAN

interface you should be using in almost all cases.

If you don't specify a particular attribute, overrides by that
attribute will not show up in the resulting config.  This is so you
can (for instance) specify a host-specific override for the physics
engine, and query that successfully before knowing which physics
engine you will be using.

Note that you can recurse these, but if you have two paths to the same
value, you should not rely on which one takes precedence.  In other
words, if you have a "byhost" clause within a "bygen" section, and you
also have a "bygen" clause within a "byhost" section, either one may
eventually be used.  When in doubt, simplify your config file.

=cut

sub custom_config :Export(:DEFAULT) {
    my %args = @_;
    setup_configs();
    # deep copy
    my @configs = Load(Dump(@all_configs));