AI-Evolve-Befunge
view release on metacpan or search on metacpan
AUTHOR
Mark Glines <mark-befunge@glines.org>
CONTACT
You can either email me at the above address, or find me on irc.magnet.net with
the nickname "Infinoid". If you want to tell me how much the module rules or
sucks, or if you have any questions about it, that's a good place to start. If
you have a specific bug or feature you want to tell me about (or better yet, a
patch), you can send it to:
bug-AI-Evolve-Befunge@rt.cpan.org
That will add it to the issue tracker so it won't get lost.
COPYRIGHT AND LICENSE
lib/AI/Evolve/Befunge.pm view on Meta::CPAN
This software project provides all of the necessary tools to grow a
population of AI creatures which are fit to perform a task.
Normally, end users can use the "evolve" script as a frontend. If
that's what you're after, please see the documentation contained
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 -
it will probably take several weeks of solid processing time before you
begin to see any promising results at all. It takes a lot of random
code generation before it starts to generate code that does what you
want it to do.
If you don't know anything about Befunge, I recommend you read up on
that first, before trying to understand how this works.
The individuals of this population (which we call Critters) may be of
various sizes, and may make heavy or light use of threads and stacks.
Each one is issued a certain number of "tokens" (which you can think
of as blood sugar or battery power). Just being born takes a certain
number of tokens, depending on the code size. After that, doing things
(like executing a befunge command, pushing a value to the stack,
spawning a thread) all take a certain number of tokens to accomplish.
When the number of tokens drops to 0, the critter dies. So it had
better accomplish its task before that happens.
After a population fights it out for a while, the winners are chosen
(who continue to live) and everyone else dies. Then a new population
is generated from the winners, some random mutation (random
generation of code, as well as potentially resizing the codebase)
occurs, and the whole process starts over for the next generation.
=head1 PHYSICS
At the other end of all of this is the Physics plugin. The Physics
plugin implements the rules of the universe inhabited by these AI
creatures. It provides a scoring mechanism through which multiple
critters may be weighed against eachother. It provides a set of
commands which may be used by the critters to do useful things within
its universe (such as make a move in a board game, do a spellcheck,
lib/AI/Evolve/Befunge/Critter.pm view on Meta::CPAN
=head1 DESCRIPTION
This module is where the actual execution of Befunge code occurs. It
contains everything necessary to set up and run the code in a safe
(sandboxed) Befunge universe.
This universe contains the Befunge code (obviously), as well as the
current board game state (if any). The Befunge code exists in the
negative vector space (with the origin at 0, Befunge code is below
zero on all axes). Board game info, if any, exists as a square (or
hypercube) which starts at the origin.
The layout of befunge code space looks like this (for a 2d universe):
|----------| |
|1 | |
|09876543210123456789|
---+--------------------+---
-10|CCCCCCCCCC |-10
-9|CCCCCCCCCC| | -9
-8|CCCCCCCCCC | -8
lib/AI/Evolve/Befunge/Critter.pm view on Meta::CPAN
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
but the code exists in more, the board will be represented as a square
starting at (0,0,...) and will only exist on plane 0 of the non-(X,Y)
axes.
Several attributes of the universe are pushed onto the initial stack,
in the hopes that the critter can use this information to its
advantage. The values pushed are (in order from the top of the stack
(most accessible) to the bottom (least accessible)):
* the Physics token (implying the rules of the game/universe)
* the number of dimensions this universe operates in
* The number of tokens the critter has left (see LIMITS, below)
lib/AI/Evolve/Befunge/Critter.pm view on Meta::CPAN
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:
=over 4
lib/AI/Evolve/Befunge/Physics.pm view on Meta::CPAN
my $critter2 = Critter->new(Blueprint => $bp2, Color => 2, @extra_args);
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
my @population;
my ($generation, $host);
$host = $ENV{HOST};
my $file = IO::File->new($savefile);
croak("cannot open file $savefile") unless defined $file;
while(my $line = $file->getline()) {
chomp $line;
if($line =~ /^generation=(\d+)/) {
# the savefile is the *result* of a generation number.
# therefore, we start at the following number.
$generation = $1 + 1;
} elsif($line =~ /^popid=(\d+)/) {
# and this tells us where to start assigning new critter ids from.
set_popid($1);
} elsif($line =~ /^\[/) {
push(@population, AI::Evolve::Befunge::Blueprint->new_from_string($line));
} else {
confess "unknown savefile line: $line\n";
}
}
my $self = bless({
host => $host,
blueprints => [@population],
lib/AI/Evolve/Befunge/Population.pm view on Meta::CPAN
sub cleanup_intermediate_savefiles {
my $self = shift;
my $gen = $self->generation;
my $physics = $self->physics;
my $host = $self->host;
my $results = "results-$host";
mkdir($results);
my $fnbase = "$results/" . join('-', $host, $physics->name);
return unless $gen;
for(my $base = 1; !($gen % ($base*10)); $base *= 10) {
my $start = $gen - ($base*10);
if($base * 10 != $gen) {
for(1..9) {
my $delfn = "$fnbase-" . ($start+($_*$base));
unlink($delfn) if -f $delfn;
}
}
}
}
=head2 migrate_export
$population->migrate_export();
t/10migration.t view on Meta::CPAN
BEGIN { $num_tests += 1 };
my $quit1 = "q";
my $scorer1 = "[ @]02M^]20M^]11M^" . (' 'x605);
my $scorer2 = "[ @]22M^]21M^]20M^" . (' 'x605);
my $scorer3 = "[@ <]02M^]20M^]11M^" . (' 'x605);
# migrate (input overrun)
my $population = AI::Evolve::Befunge::Population->load('t/savefile');
is(scalar @{$population->blueprints}, 3, "3 critters to start with");
$population->host('whee');
$population->popsize(5);
sleep(0.25);
seed(0.85);
alarm(3);
$population->migrate();
is($incoming->getline, '[I-4 D4 F3 Hnot_test1]'.$scorer3."\n", 'migration exported a critter');
alarm(0);
my $ref = $population->blueprints;
is(scalar @$ref, 8, 'there are now 8 blueprints in list');
t/10migration.t view on Meta::CPAN
is($$ref[$id]{host}, $expected_results[$id]{host}, "loaded $id host right");
is($$ref[$id]{code}, $expected_results[$id]{code}, "loaded $id code right");
is($$ref[$id]{fitness}, $expected_results[$id]{fitness}, "loaded $id fitness right");
}
BEGIN { $num_tests += 8*4 };
# migrate (no overrun)
undef $population;
$population = AI::Evolve::Befunge::Population->load('t/savefile');
is(scalar @{$population->blueprints}, 3, "3 critters to start with");
$population->host('whee');
$population->popsize(8);
sleep(0.25);
seed(0.85);
alarm(3);
$population->migrate();
is($incoming->getline, '[I-2 D4 F2 Hnot_test]'.$scorer2."\n", 'migration exported a critter');
$population->migrate();
alarm(0);
$ref = $population->blueprints;
tools/evolve view on Meta::CPAN
=head1 SYNOPSIS
evolve [-q|v|d] [-h host] [savefile]
=head1 DESCRIPTION
This script is a frontend to the AI::Evolve::Befunge genetic
algorithm. It sets up a board game instance, possibly loading
previous genetic data from a savefile (if given on the command line),
and starts running a new generation.
It will run until it is killed.
=head1 COMMAND LINE ARGUMENTS
=head2 -q, --quiet
Enable quiet mode. This will reduce the amount of output.
( run in 0.335 second using v1.01-cache-2.11-cpan-0d8aa00de5b )