Make your own free website on Tripod.com

back to previous section up to contents on to next section

b!Gollem: Evolutionary Framework

Genetic Programming

Simply stated, genetic programming (GP) is the process of "evolving" an algorithm to perform a particular task. GP is inspired by the notion of natural selection. It is similar to, but not quite the same as genetic algorithms (GA), in which the parameters of an algorithm are evolved in order to create a "fit" solution to given problem.

The applicability of GP for a particular domain depends on number of factors:

Assuming these conditions are met, solutions are "evolved" as follows.
  1. A population of "random" programs (sequences of atomic functions) are created. Let us call this the current population.
  2. The fitness of each program in the current population is evaluated, typically yielding a numerical fitness value or a linear ordering of the individuals within the population.
  3. A new population is created from the current by three general techniques:
  4. The new populated then becomes the current population, and we repeat steps 2 through 4 until the desired fitness level is reached.
Statistics tells us that if our functionality is sufficient to solve the problem and our fitness measure is meaningful, the average fitness of the population will increase over time.

Note that in general, GP/GA will not yield the ideal solution to a problem, but often a "good" solution will suffice.

There are many on-line resources for information regarding GA/GP, use your favorite search engine to find them.

Genetic Programming in b!Gollem

Gollem's genetic architecture extends traditional genetic programming in two primary ways.

Data-Types

Gollem's data types can be divided into two categories: "globals" for which exactly one instance exists, and "locals" which collectively form the "closed" function argument.

Global Data-Types

 o Board
Board is a representation of go board. It contains all the "game state" information, as well as the functions necessary for refereeing a game, counting territory and determining the winner. Board also acts as a "publisher" of game data to the "subscribers" ChainMap and Field. It is the primary structure behind the Board Window.
 o ChainMap
The ChainMap is representation of the board as a collection of connected, same color groups or chains. Each location on the board is mapped to a "group structure" which contains information about the size, shape, and neighbors of the connected stones (or empty intersections).
 o Field
Field is an electrical field model representation of the board. Each stone is considered a "point charge" which propagates charge across empty intersections. The field model can be used to measure "influence".

 o Log
The Log is simply a history of the moves made in the game. It is the source for the History Window and is also used to implement the undo/redo stack.

Local Data-Types

 o Bool
A simple Boolean (true/false) value.

 o Coor
A board location, represented as x,y coordinates.

 o Color
A trinary value that represents what stone (if any) might occupy a board location (either Black, White or Empty).

 o Flavor
An 8-value variable that represents all possible combinations of Black, White and Empty.

 o Float
A floating point (real number) value.

 o Int
An integer (whole number) value.

 o List
A "linked list" of coordinates (Coors). This can be used as a set of distinct locations, a bag (multi-set) of not necessarily distinct values or as an ordered list.

 o Rect
A rectangular region of the board. This can be used to specify a "universe of interest" or as a coordinate offset (vector).

These data-types, together with the functions that manipulate them, form the foundation of Gollem's built-in go knowledge.

Back to the top of this page.

Genetic Functions

For each of the above data-types, a large number of "manipulating functions" have been defined. (Currently there are over 1,000 implemented functions and nearly 2,000 planned in total.) Each function takes two collections of local data as an argument and each has access to the global data as well. Some example functions include:

Back to the top of this page.

Genetic Framework

The b!Gollem genetic framework is based on a CPU model. Programs (individuals) take the form of a sequence of atomic functions. These programs are "run" on an engine that might be thought of as a CPU.

The Central Processing Unit

CPU Schematic

the processing engine

The CPU can be divided into two parts that loosely correspond to Read-Only Memory (ROM) and Random Access Memory (RAM). We'll describe each portion in turn.

Read-Only Memory
The ROM portion of the CPU is composed of a function table, an array of the atomic functions, and the global data types like the Board, et al., described above. The "read-only" description is somewhat inaccurate here, since the "internal state" of global data types can be changed, but only indirectly. That is, the programs cannot directly alter the global data types; they can only query them for information. The global data types change, however, for each move made in the game.

Random Access Memory
The RAM portion of the CPU is entirely composed of local data types stored in registers. Three registers, designated alpha, beta and gamma are individual instances of the collection of local data types. A special stack register is an arbitarliy large list of local data instances, stored in a standard "push-down" stack. Only the top-most collection on the stack is available for reading or writing.

There are several "meta" functions within the function table that manipulate the registers, copying or exchanging values and pushing/popping values from the stack.

The Programs

An individual in the population is simply a sequence of integers that correspond to entries in the function table. A program is run by calling each function in turn. In particular, each "atom" in a program is composed of two parts. The first part specifies which registers are to be acted upon. For instance, the same function can have dramatically different results when run upon registers alpha and beta than it would when run with two "copies" of the gamma register. In this way each entry in the function table corresponds to 16 different functions--one for each ordered pair of registers. The remaining part of the atom specifies which entry in the function table to use.

The Genetic Operators

Breeding within the Gollem system is a fairly straight-forward implementation of GP. Since the order of the functions within the table is arbitary, functions are bred as piece. The "operator" (function) and "operand" (register) parts of each atom may be changed indepenedently. A "chromosome" within the Gollem system is the sequence of atoms and it is these sequences that are bred.

The following list describes the genetic operators currently being used. The frequency of use is determined by the breeding parameters dialog box described on a previous page.

Back to the top of this page.


back to previous section up to contents on to next section