The Perl Toolchain Summit needs more sponsors. If your company depends on Perl, please support this very important event.

NAME

    AI::Evolve::Befunge::Critter - critter execution environment

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
     -7|CCCCCCCCCC|         | -7
     -6|CCCCCCCCCC          | -6
     -5|CCCCCCCCCC|         | -5
     -4|CCCCCCCCCC          | -4
     -3|CCCCCCCCCC|         | -3
     -2|CCCCCCCCCC          | -2
     -1|CCCCCCCCCC|         | -1
    --0| - - - - -BBBB - - -|0--
      1|          BBBB      |  1
      2|          BBBB      |  2
      3|          BBBB      |  3
      4|                    |  4
      5|          |         |  5
      6|                    |  6
      7|          |         |  7
      8|                    |  8
      9|          |         |  9
    ---+--------------------+---
       |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 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)
    * The   iter cost (see LIMITS, below)
    * The repeat cost (see LIMITS, below)
    * The  stack cost (see LIMITS, below)
    * The thread cost (see LIMITS, below)
    * The code size (a Vector)
    * The maximum storage size (a Vector)
    * The board size (a Vector) if operating in a boardgame universe

If a Critter instance will have it's ->invoke() method called more than once (for board game universes, it is called once per "turn"), the storage model is not re-created. The critter is responsible for preserving enough of itself to handle multiple invocations properly. The Language::Befunge Interpreter and Storage model are preserved, though a new IP is created each time, and (for board game universes) the board data segment is refreshed each time.

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:

Size of stacks
Number of stacks
Storage size (electric fence)
Number of threads
"k" command repeat count
"j" command jump count
"x" command dead IP checks (setting a null vector)

Most of the above things will result in spending some tokens. There are a couple of exceptions to this: a storage write outside the confines of the critter's fence will result in the interpreter crashing and the critter dying with it; similarly, a huge "j" jump count will also kill the critter.

The following commands are removed entirely from the interpreter's Ops hash:

    , (Output Character)
    . (Output Integer)
    ~ (Input Character)
    & (Input Integer)
    i (Input File)
    o (Output File)
    = (Execute)
    ( (Load Semantics)
    ) (Unload Semantics)

CONSTRUCTOR

new

    Critter->new(Blueprint => \$blueprint, Physics => \$physics,
              IterPerTurn => 10000, MaxThreads => 100, Config => \$config,\n"
              MaxStack => 1000,Color => 1, BoardSize => \$vector)";

Create a new Critter object.

The following arguments are required:

Blueprint

The blueprint object, which contains the code for this critter. Also note, we also use the Blueprint object to cache a copy of the storage object, to speed up creation of subsequent Critter objects.

Physics

The physics object controls the semantics of how the universe operates. Mainly it controls the size of the game board (if any).

Config

The config object, see AI::Evolve::Befunge::Util::Config.

Tokens

Tokens are the basic form of life currency in this simulation. Critters have a certain amount of tokens at the beginning of a run (controlled by this value), and they spend tokens to perform tasks. (The amount of tokens required to perform a task depends on the various "Cost" values, below.)

When the number of tokens reaches 0, the critter dies (and the interpreter is killed).

The following arguments are optional:

CodeCost

This is the number of tokens the critter pays (up front, at birth time) for the codespace it inhabits. If the blueprint's CodeSize is (8,8,8), 8*8*8 = 512 spaces are taken up. If the CodeCost is 1, that means the critter pays 512 tokens just to be born. If CodeCost is 2, the critter pays 1024 tokens, and so on.

If not specified, this will be pulled from the variable "codecost" in the config file. If that can't be found, a default value of 1 is used.

IterCost

This is the number of tokens the critter pays for each command it runs. It is a basic operational overhead, decremented for each clock tick for each running thread.

If not specified, this will be pulled from the variable "itercost" in the config file. If that can't be found, a default value of 2 is used.

RepeatCost

This is the number of tokens the critter pays for each time a command is repeated (with the "k" instruction). It makes sense for this value to be lower than the IterCost setting, as it is somewhat more efficient.

If not specified, this will be pulled from the variable "repeatcost" in the config file. If that can't be found, a default value of 1 is used.

StackCost

This is the number of tokens the critter pays for each time a value is pushed onto the stack. It also has an effect when the critter creates a new stack; the number of stack entries to be copied is multiplied by the StackCost to determine the total cost.

If not specified, this will be pulled from the variable "stackcost" in the config file. If that can't be found, a default value of 1 is used.

ThreadCost

This is a fixed number of tokens the critter pays for spawning a new thread. When a new thread is created, this cost is incurred, plus the cost of duplicating all of the thread's stacks (see StackCost, above). The new threads will begin incurring additional costs from the IterCost (also above), when it begins executing commands of its own.

If not specified, this will be pulled from the variable "threadcost" in the config file. If that can't be found, a default value of 10 is used.

Color

This determines the color of the player, which (for board games) indicates which type of piece the current player is able to play. It has no other effect, and thus, it is not necessary for non-boardgame physics models.

If not specified, a default value of 1 is used.

BoardSize

If specified, a board game of the given size (specified as a Vector object) is created.

METHODS

invoke

    my $rv = $critter->invoke($board);
    my $rv = $critter->invoke();

Run through a life cycle. If a board is specified, the board state is copied into the appropriate place before execution begins.

This should be run within an "eval"; if the critter causes an exception, it will kill this function. It is commonly invoked by "move" (see below), which handles exceptions properly.

move

    my $rv = $critter->move($board, $score);

Similar to invoke(), above. This function wraps invoke() in an eval block, updates a scoreboard afterwards, and creates a "dead" return value if the eval failed.

populate

    $critter->populate($board);

Writes the board game state into the Befunge universe.

spend

    return unless $critter->spend($tokens * $cost);

Attempts to spend a certain amount of the critter's tokens. Returns true on success, false on failure.