NAME
AI::Evolve::Befunge - practical evolution of Befunge AI programsSYNOPSIS
use aliased 'AI::Evolve::Befunge::Population' => 'Population';
use AI::Evolve::Befunge::Util qw(v nonquiet);
$pop = Population->new();
while(1) {
my $gen = $pop->generation;
nonquiet("generation $gen\n");
$pop->fight();
$pop->breed();
$pop->migrate();
$pop->save();
$pop->generation($gen+1);
}DESCRIPTION
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.
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.
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, or request a google search).
Physics engines register themselves with the Physics database (which is managed by Physics.pm). The arguments they pass to register_physics() get wrapped up in a hash reference, which is copied for you whenever you call Physics->new("pluginname"). The "commands" argument is particularly important: this is where you add special befunge commands and provide references to callback functions to implement them.
One special attribute, "generations", is set by the Population code and can determine some of the parameters for more complex Physics plugins. For instance, a "Go" game might wish to increase the board size, or enable more complex rules, once a certain amount of evolution has occurred.
Rather than describing the entire API in detail, I suggest you read through the "othello" and "ttt" modules provided along with this distribution. They are small and simple, and should make good examples.
MIGRATION
Further performance may be improved through the use of migration.
Migration is a very simple form of parallel processing. It should scale nearly linearly, and is a very effective means of increasing performance.
The idea is, you run multiple populations on multiple machines (one per machine). The only requirement is that each Population has a different "hostname" setting. And that's not really a requirement, it's just useful for tracking down which host a critter came from.
When a Population object has finished processing a generation, there is a chance that one or more (up to 3) of the surviving critters will be written out to a special directory (which acts as an "outbox").
A separate networking program (implemented by Migrator.pm and spawned automatically when creating a Population object) may pick up these critters and broadcast them to some or all of the other nodes in a cluster (deleting them from the "outbox" folder at the same time). The instances of this networking program on the other nodes will receive them, and write them out to another special directory (which acts as an "inbox").
When a Population object has finished processing a generation, another 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.
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 content. After you have reached your goal, you need not continue to evolve or test new critters.
CONFIG FILE
You can find an example config file ("example.conf") in the source tarball. It contains all of the variables with their default values, and descriptions of each. It lets you configure many important parameters about how the evolutionary process works, so you probably want to copy and edit it.
This file can be copied to ".ai-evolve-befunge" in your home directory, or "/etc/ai-evolve-befunge.conf" for sitewide use. If both files exist, they are both loaded, in such a way that the homedir settings supercede the ones from /etc. If the "AIEVOLVEBEFUNGE" environment variable is set, that too is loaded as a config file, and its settings take priority over the other files (if any).