The Project

Genetic Programming: an introduction

On 02.24.10, In General, By The Villain

(The following is a synopsis of chapters 5 and 6 of John R. Koza’s “Genetic Programming”)

OVERVIEW:

Genetic Programming is derived from Genetic Algorithms, and in many ways involves the same process of evolutionary natural selection. The core difference between Genetic Algorithms and Genetic Programming is the program structure. Genetic Algorithms (GAs) operate on fixed length binary strings representing a biological chromosome, while Genetic Programming (GP) instead operates on dynamic hierarchical programs. While in GA, the size and shape of a binary string are fixed, GP programs vary in size and shape. This makes GP programs more complex and, in many ways, more powerful.

The more complex and dynamic program structure of GP results in a cascade of other differences which separate it from GA. Because of this, some problems may be better suited to one method or the other. Generally the more complex the problem or the larger the search space for a solution, the more likely the problem should be solved by GP.

GP solves problems by breeding computer programs, then using reproduction and crossover in iterations through generations of programs, until a solution to the problem is found or some other set parameter is satisfied (such as number of generations run).

Koza’s GP, Figure 5.1

Koza references Holland’s (1975) list of key features of all adaptive systems. For GP to operate successfully, the following must be defined:
· Initial Structures
· Fitness Measures
· Genetic Processes
· Program Memory
· Termination Criterion
· Designating a result

INITIAL STRUCTURES:

GP programs are best represented by expression trees, which are hierarchies containing functions and terminals.

The above diagram represents the program string (in pseudocode):

if{x<4}then{t}else{r}}

Any of the functions if, <, then, else or terminals x, 4, t, r will be subject to change as GP progresses through generations.

It is important to select a sufficient set of primitive functions for a problem. For instance, with an ant trying to maneuver through a maze for food, MOVE, RIGHT, and LEFT are sufficient. Anything less is insufficient, while anything more may or may not be useful.

Keep in mind the set of functions and terminals must be sufficient, but extraneous functions and terminals will often degrade performance.

After the sufficient pool of primitive functions has been determined, the initial population (generation 0) is generated with expression trees containing random combinations of these functions and terminals.

A uniform random probability distribution is responsible for arranging the the expression trees within the initial population, using only the sufficient function set determined ahead of time.

There are three types of expression trees (pp. 92-93):
· Full (every branch of the tree is equal length)
· Grow (variably shaped trees bound only by maximum branch length)
· Ramped half-and-half (combination of full and grow)

Koza prefers to use the ramped half-and-half method for all of his GP demonstrations.

FITNESS MEASURES:

Defining fitness is important because fitness directly affects the primary GP operations of reproduction and crossover. There are many ways to accomplish this.

“The most common approach to measuring fitness is to create an explicit fitness measure for each individual in the population… Each individual in a population is assigned a scalar fitness value by means of some well-defined explicit evaluative procedure” (p. 94).

Koza describes four kinds of explicit fitness measures used in GP programs:

1. Raw Fitness (The “measurement of fitness that is stated in the natural terminology of the problem itself” [p. 95].)
2. Standardized Fitness (The lower the number the better. If the raw fitness is also striving for the lowest number, standardized = raw. Otherwise standardized is the inverse of raw.)
3. Adjusted Fitness (Computed from the standard fitness, adjusted fitness is always between 0 and 1. The bigger the adjusted fitness, the more fit the individual.)
4. Normalized Fitness (Computed from adjusted fitness, the sum of normalized fitness values equals 1.)

GENETIC PROCESSES:

The genetic processes in GP consist of two primary operations: Reproduction and Crossover.

Reproduction:
Reproduction in GP is asexual (one parent, one offspring).

“The operation of reproduction consists of two steps. First, a single [program] is selected from the population according to some selection method based on fitness. Second, the selected individual is copied, without alteration, from the current population into the new population (i.e., the new generation)” (p. 99).

Three methods of reproduction include:
· Fitness-proportionate selection (The most popular method–uses the fitness measure to determine how many of which programs are allowed to reproduce)
· Tournament selection
· Rank selection

Crossover:
Crossover in GP is sexual recombination (two parents, two offspring). It is, essentially, a swapping of subtrees.

Which parents are chosen for crossover is determined by the fitness-based selection method.

Random crossover points are chosen (again determined by using a uniform probability distribution) from each parent. Everything in the subtree below the crossover point is swapped with the subtree underneath the crossover point in the other parent.

Swapping of simple terminals (instead of entire subtrees) is common in GP, and this is the same as point mutation in GA–so mutation is inherent in GP crossover.

Another Crossover difference between GA and GP: In GP the two crossover points in the two parents are usually different; in GA the two points are always identical because crossover is operating on a fixed-length character string. This leads to better capacity for variety in GP:

“In genetic programming, when an individual incestuously mates with itself (or copies of itself), the two resulting offspring will, in general, be different (except in the relatively infrequent case when the crossover points are the same). As before, the Darwinian reproduction operation creates a tendency toward convergence; however, in genetic programming, the crossover operation exerts a counterbalancing pressure away from convergence. Thus, convergence of the population is unlikely in genetic programming” (p. 104).

Also important for GP crossover is the maximum permissible size, which is measured by the depth of the tree. Regulating the maximum depth keeps crossover from creating oversized trees and saves computing time.

There are also secondary operations in GP, all of which are optional and are probably best reserved for specific situations:
· Mutation (Asexual changing of an individual terminal, but occurs occasionally through sexual crossover in GP anyway. Useful in moderation in GAs, but really not necessary in most GP applications.)
· Permutation (Asexual inversion–swapping terminals of a function.)
· Editing (Follows editing rules such as shortening “(NOT ( NOT X))” to “X.” This can be used for cosmetic purposes and for simplification or improvement of GP output.)
· Encapsulation (Protection from crossover for ideal offspring subtrees, encapsulation offers “a means for automatically identifying a potentially useful subtree and giving it a name so that it can be referenced and used later” [p. 110].)
· Decimation (Deleting a portion of population, controlled by two parameters [p. 112]: “a percentage and a condition specifying when the operation is to be invoked.”)

MEMORY:

It is only necessary for the current generation to be maintained in memory for GP operations. Although the individuals in a population represent only a small set of possibilities in the realm of all possible programs, the genetic processes ensure the search will keep moving in the right direction–toward a solution.

TERMINATION CRITERION:

This is not nature and the computer will not run the program forever, so a termination criterion must also be set. This may be a set number of generations or a 100% exact solution to a problem, which, when satisfied, ends the program.

DESIGNATING A RESULT:

Results come in different forms. There may be a 100% exact solution, but maybe there is no single best solution. If the program is terminated at a set number of generations, then the best-so-far individual is usually chosen. The fitness parameters are used to determine what is the best-so-far individual, what is the 100% exact solution to the problem, or what percentage of correctness is close enough to suffice.

Tagged with: GP • Koza

Genetic Algorithms: an introduction

On 02.09.10, In General, By The Villain

The following is a synopsis of chapter 3 of John R. Koza’s “Genetic Programming”:

Genetic algorithms provide a way to search a large space of possible solutions in a near-optimal way, using 4 Bio-Darwinian methods:

1. Natural Selection (find the members of the population with the best fitness)
2. Reproduction (replicate those members of the population identified to have the best fitness)
3. Crossover (cross-breed two parent chromosomes at a random point to produce new offspring)
4. Mutation (randomly change bits within a chromosome)

Koza’s Figure 3.1

Natural selection and reproduction result in a definite performance improvement within the population, but just using these two methods limits the potential players in the realm of all possible solutions. Basically the existing best persist and reproduce and the not-so-good go extinct, but if the optimal solution was not in the population to begin with, it could never be found because there is no variation.

“Natural selection does not create variety. It merely selects from whatever variety is already present in the population in order to increase the average fitness of the population as a whole” (pg. 48).

Crossover and mutation are necessary evils in that they slightly degrade the overall optimization, while opening up the possibilities toward discovering better solutions that were not present in the original population.

“The genetic crossover operation serves the necessary function of creating promising new individuals in the search space” (pg. 48).

So, by keeping relatively low levels of crossover and mutation within the GA architecture, new solutions can be discovered while still allowing natural selection and reproduction to keep the balance tilting toward an optimal solution.

“The allocation of future trials is most nearly optimal when [crossover and mutation rates] are both small. A schema with a relatively short defining length and a relatively few defined positions is a building block which will be propagated from generation to generation at close to the near-optimal rate. The genetic algorithm processes such schema most favorably. A problem whose solution can be incrementally built up from schemata of relatively short defining length and relatively few defined positions is handled by genetic algorithms in a near-optimal way” (pg. 49).

The interesting thing about the genetic algorithm is that it is a domain independent process and can find near-optimal solutions without even storing a memory of the solution’s lineage. The only prerequisite is for the problem to be defined in terms the GA can “understand.”

This prerequisite can be fulfilled by applying a simple 4-step process to any problem (pp. 53-54):

1. Select the representation scheme.
This often includes transitioning problem parameters to binary strings. This is an ideal way to present the problem to the GA as a “chromosome” ripe for reproduction, crossover and mutation.
2. Identify the fitness measure.
This step is crucial to defining what the problem is seeking to achieve.
3. Define control parameters and variables.
Here is where the population, bit string length, and generations to be run are defined.
4. Define when / how the run will be terminated and what will be designated as the best result.

Koza proves the point of how domain independent the GA is by giving several different in-depth examples in this chapter: among them a restaurant-burger conundrum, a load-bearing optimizer, and the ever-popular ant-food path optimization problem. All of these problems can be broken down into binary strings allowing solutions to be figured out through the use of genetic algorithms. A good read, for sure.

Tagged with: GA • Koza

Character Collisions

On 02.02.10, In Development, Ideas, Video Games, By The Villain

The binary-bitmap conversion portion of the BBC has already been discussed and is in development. But there are many other aspects of this part of the program that need to be considered, including a physics engine and the motion of the letters. One thing that’s been bugging me is how the letters will react when they run into one another.

Let’s assume that two letters, an ‘A’ and a ‘B’ are floating around in their predetermined environment. They run into each other–what happens?

First of all, we need to clearly define what consitutes a character. There are 256 pixels in the 16×16 square, yes, but most of the border consists of ‘0’s–white space. Is it going to be considered a collision when the outer white pixels of the bitmap collide, or are we going to go with a more literal description of the letters running into each other, i.e. the black pixels (‘1’s)?

I think the second idea makes more sense, even though in computer logic the bitmap touches the other bitmap when the 16×16 squares meet, which causes a kind of predicament for us. The crazy thing about going with option 2 is that it will cause a morphing in the bitmap of at least one of the letters, even before the actual collision takes place. In other words, the ‘A’ bitmap will already change before the genetic code is activated.

Purple shows changed pixels:
0000000000000000
0000000000000000
0001111111000000
0001111111100000
0001000000110000
0001000000010000
0001000000010000
0001000000110000
0001111111100000
0001111111110000
0001000000010000 ‘A’ bitmap becomes:
00000000000001000000010000 0000000000000100
00000001000001000000110000 0000000100000100
00000011100001111111100000 0000001110000111
00000010100001111111000000 0000001010000111
00000110110000000000000000 0000011011000000
0000010001000000 0000010001000000
0000110001100000 0000110001100000
0000100000100000 0000100000100000
0000100000100000 0000100000100000
0001111111110000 0001111111110000
0001111111110000 0001111111110000
0001000000010000 0001000000010000
0011000000011000 0011000000011000
0010000000001000 0010000000001000
0110000000001100 0110000000001100
0000000000000000 0000000000000000

One way around this is to make the border ‘0’s (white pixels) invisible, or transparent to the other letters. Also, we could somehow use them so that when the outer pixels of two letters collide, they activate some sort of “signal” (probably a specific function in the code) that a collision is imminent and that the decision-making procedure needs to occur. Maybe this could even change the white pixels to a different color as an extra visual aid to show that a collision is about to take place somewhere within the soup–a way to highlight the action. Just a thought.

Before: Collision Imminent!
0000000000000000 0000000000000100
0000000100000000 0000000100000100
0000001110000000 0000001110000111
0000001010000000 0000001010000111
0000011011000000 0000011011000000
0000010001000000 0000010001000000
0000110001100000 0000110001100000
0000100000100000 0000100000100000
0000100000100000 0000100000100000
0001111111110000 0001111111110000
0001111111110000 0001111111110000
0001000000010000 0001000000010000
0011000000011000 0011000000011000
0010000000001000 0010000000001000
0110000000001100 0110000000001100
0000000000000000 0000000000000000

The fight-or-flight function, another good chance for GP to help with decision-making, will then determine: Do I, as an ‘A’…
1. continue toward the ‘B’ (attack),
2. change direction to avoid ‘B’ (retreat),
3. breed with ‘B’ (perform GA/GP)?

The thing is, both letters will be running this function to determine the best course of action. It would be interesting in this scenario to see what would happen if ‘A’ tried attacking while ‘B’ decided to activate the genetic algorithm. What would happen? Who would win? Maybe the program would crash and we’d need to tweak it, but whatever–this is just a brainstorming session.

All this can be figured out. I think the main problem with the white borders in a bitmap will be aesthetics: the collision wouldn’t really look like a collision if just the outer empty sections of the letter boxes are running into each other. We can go with the highlighting/color-changing idea, or maybe we can implement some sort of overlap in the outer white pixels on the bitmaps to show more precise-looking collisions. The speed of the letter movement could also be enough to distract the user’s eye from the extra white space. Then again, as small as a 16×16 bitmap is, the difference is probably subtle enough that it won’t even be noticeable.

Tagged with: Alphabet Soup • Binary-Bitmap Converter • GA • GP

Bitmap-Binary Basics

On 02.01.10, In Code, Development, Video Games, By The Villain

The Bitmap-Binary Converter will likely be the core engine for at least the early versions of Alphabet Soup. To create it, there are a few things we need to consider. The two most glaring questions are how will we read individual pixels, and how will the actual conversion between pixel color and binary code take place? An even more basic consideration is which programming language we will use. I am leaning heavily toward C#, as it seems fully capable of tackling both problems.

There are a couple of ways we could do this. Let’s start with the assumption we begin with the bitmap and define all the colors for a given letter (“A”, for example). This website explains how to access each pixel individually–exactly what we are trying to do.

This is the core of the code allowing the color definition for each pixel based on location within the bitmap:

public void SetPixel(int x, int y, PixelData color)
{
PixelData* pixel = PixelAt(x, y);
*pixel = color;
}

However this is using ‘unsafe’ code to access each individual pixel. To use ’safe’ code the actual program execution would take forever. So there may be a third alternative worth looking into. And here are more thoughts about this. This is something we are going to have to experiment with to find the best method, or we might have to figure out our own.

To save the bitmap code for future use, we will have to set the black pixels to 1 and white pixels to 0. This will produce 256 characters, ranging from charA[0] to charA[255]. We might have the program write this data to a separate file, or just store it within its own memory.

For visual reference, here is the bitmap in actual size:

Here is the ‘A’ bitmap represented in binary:

0000000000000000
0000000100000000
0000001110000000
0000001010000000
0000011011000000
0000010001000000
0000110001100000
0000100000100000
0000100000100000
0001111111110000
0001111111110000
0001000000010000
0011000000011000
0010000000001000
0110000000001100
0000000000000000

Here is the above bitmap referenced in pixel notation (shortened to describe the four corners):

(0,0) through (0,15)
…
(15,0) through (15,15)

And here is the character equivalent to the above pixels:
charA[0] = (0,0) = value of ‘0′
charA[15] = (0, 15) = value of ‘0′
charA[240] = (15,0) = value of ‘0′
charA[255] = (15,15) = value of ‘0′

Or, we do it the other way: Start with 62 ‘.txt’ files (52 letters and numbers 0-9, or whatever amount we end up with for the base set of characters), each with 256 “0″ and “1″ characters representing the 16×16 bitmap.

Read the text from the file and use the code “if charA[0]=’0′…” / “if charA[0]=’1′…” and the earlier bitmap code to convert each corresponding pixel to black or white by referencing the corresponding pixel within the bitmap. Whenever crossover occurs in the program, it creates a new binary (or .txt) file to represent that organism. I think a thorough understanding of the C# StringBuilder Class is going to come in handy for this, in splicing strings of binary characters and performing other modifications. Again, this will be closely intertwined with the GP or GA code, which will be the determining factor for where the splicing will occur each time.

Basically we’re accomplishing the same thing but from two different directions: bitmap-to-binary or binary-to-bitmap. It will probably be valuable to know how to do this in both directions for purposes of the program anyway. Basic C# data type conversions (string-to-binary-to-decimal-to-chars-to-string and so on) will be instrumental in making this work properly. This should actually be pretty simple; it will just take some time to sort out the details.

What I described above should accomplish the basic functionality of the BBC; once we get this working we can move onto the engine’s more complex functions, such as attributing higher “sensitivity values” to certain pixels and recognizing “contact” with other letters.

Tagged with: Alphabet Soup • Binary-Bitmap Converter

Alphabet Soup by Genetic Algorithms: a sample run

On 01.27.10, In Development, Video Games, By The Villain

*Define Initial Population*

The initial population in the final version of Alphabet Soup may likely contain one of each keyboard character available. For now, for simplicity’s sake, let’s begin with 4 characters: A,B,a,b. In our game, all 4 characters decide to run into each other at once.

First we will convert the 16×16 characters into binary, 0 for gray and 1 for yellow:

A:
0000000000000000
0000000100000000
0000001110000000
0000001010000000
0000011011000000
0000010001000000
0000110001100000
0000100000100000
0000100000100000
0001111111110000
0001111111110000
0001000000010000
0011000000011000
0010000000001000
0110000000001100
0000000000000000

A, Binary String: 0000000000000000000000010000000000000011100000000000001010000000000001101100000000000100010000000000110001100000000010000010000000001000001000000001111111110000000111111111000000010000000100000011000000011000001000000000100001100000000011000000000000000000
A, Binary-Decimal conversion: 95786086615602871731981918389383308042547593781186608

B:
0000000000000000
0000000000000000
0001111111000000
0001111111100000
0001000000110000
0001000000010000
0001000000010000
0001000000110000
0001111111100000
0001111111110000
0001000000010000
0001000000010000
0001000000110000
0001111111100000
0001111111000000
0000000000000000

B, Binary String: 0000000000000000000000000000000000011111110000000001111111100000000100000011000000010000000100000001000000010000000100000011000000011111111000000001111111110000000100000001000000010000000100000001000000110000000111111110000000011111110000000000000000000000
B, Binary-Decimal conversion: 46403387827017775033653233413204161160929512263696

a:
0000000000000000
0000000000000000
0000000000000000
0000001111100000
0000011111110000
0000110000110000
0000000000010000
0000000111110000
0000011111010000
0000110000010000
0000110000110000
0000111001110000
0000011111011000
0000000000000000
0000000000000000
0000000000000000

a, Binary String: 0000000000000000000000000000000000000000000000000000001111100000000001111111000000001100001100000000000000010000000000011111000000000111110100000000110000010000000011000011000000001110011100000000011111011000000000000000000000000000000000000000000000000000
a, Binary-Decimal conversion: 86418088698874722540000455600782178239016967

b:
0000000000000000
0000100000000000
0000100000000000
0000100000000000
0000101111000000
0000111111100000
0000110000110000
0000100000010000
0000100000010000
0000100000010000
0000100000010000
0000110000110000
0000111011100000
0000101111000000
0000000000000000
0000000000000000

b, Binary String: 0000000000000000000010000000000000001000000000000000100000000000000010111100000000001111111000000000110000110000000010000001000000001000000100000000100000010000000010000001000000001100001100000000111011100000000010111100000000000000000000000000000000000000
b, Binary-Decimal conversion: 766259462624453036391004127445265907255673543052767246

So, our Initial Population (POPinit) consists of the following four characters and their decimal representation:
1. (A) 95786086615602871731981918389383308042547593781186608
2. (B) 46403387827017775033653233413204161160929512263696
3. (a) 86418088698874722540000455600782178239016967
4. (b) 766259462624453036391004127445265907255673543052767246

*Define fitness of POPinit*

First, we establish the Total, the Best, the Worst and the Average based on their decimal representations:
Total: (A+B+a+b) 862091952714301014596894421608062875060164244585234517
Best: (b) 766259462624453036391004127445265907255673543052767246
Worst: (a) 86418088698874722540000455600782178239016967
Average: 23958122541618481117083899450474345137254323064508656.25

Based on these findings, we can calculate the chance of Reproduction / Survival for each character.
A: 0.1111088977388315456010566688830799217993208329796695901253… = 11% chance of reproducing
B: 0.0000538264945878643991068686448919016779835612586246604953… = <1% chance of reproducing
a: 0.0000000001002423099146058828565205588056220034311729841463397... = MUCH <1% chance of reproducing
b: 0.8888372756663382800852305796155076177170736023305327652329... = 88% chance of reproducing

*Perform Reproduction Function*

As you can tell from the fitness of each character, the character “b” has by far the best chance at survival, while character “A” is the only other letter with much of a chance at all. In the actual game, the reproduction function will decide who actually survives reproduction so it is impossible to say for sure, but based on these percentages we will go with three b’s and one A surviving to population generation 0.

So, the result of the reproduction function should look something like:

1. (b) 766259462624453036391004127445265907255673543052767246
2. (b) 766259462624453036391004127445265907255673543052767246
3. (b) 766259462624453036391004127445265907255673543052767246
4. (A) 95786086615602871731981918389383308042547593781186608

*Define fitness of gen0″

Again, we determine the total, best, worst and average fitness of the new population, gen0:

Total, better: (b+b+b+A) 2394564474488961980904994300725181029809568222939488346
Best, same: (b) 766259462624453036391004127445265907255673543052767246
Worst, better: (A) 95786086615602871731981918389383308042547593781186608
Average, better: 598641118622240495226248575181295257452392055734872086.5

Note that the Total, Worst, and Average fitness of the population all improved as an expected result of natural selection. The Best fitness, meanwhile stays the same–and it has no chance for improvement until running the next stage of the GA…

*Perform genetic crossover operation on gen0*

Start with 2 parents. Let’s use 3 & 4 as an example with an arbitrary crossover point (we’ll say 170 digits in–though this would actually be determined by the randomly generated genetic operation):

3. (b) 766259462624453036391004127445265907255673543052767246 =
00000000000000000000100000000000000010000000000000001000000000000000101111000000000011111110000000001100001100000000100000010000000010000001000000001000000100000000100000 | (crossover point) 01000000001100001100000000111011100000000010111100000000000000000000000000000000000000

4. (A) 957860866156028717319819183893833080425475937811868 =
00000000000000000000000100000000000000111000000000000010100000000000011011000000000001000100000000001100011000000000100000100000000010000010000000011111111100000001111111 | (crossover point) 11000000010000000100000011000000011000001000000000100001100000000011000000000000000000

From this crossover, we get 2 new offspring characters:

offspring1 (o1):
0000000000000000
0000100000000000
0000100000000000
0000100000000000
0000101111000000
0000111111100000
0000110000110000
0000100000010000
0000100000010000
0000100000010000
0000100000110000
0001000000010000
0011000000011000
0010000000001000
0110000000001100
0000000000000000

o1, Binary String: 0000000000000000000010000000000000001000000000000000100000000000000010111100000000001111111000000000110000110000000010000001000000001000000100000000100000010000000010000011000000010000000100000011000000011000001000000000100001100000000011000000000000000000
o1, Binary-Decimal conversion: 766259462624453036391004127445265907255673543589892144

offspring2 (o2):
0000000000000000
0000000100000000
0000001110000000
0000001010000000
0000011011000000
0000010001000000
0000110001100000
0000100000100000
0000100000100000
0001111111110000
0001111111010000
0000110000110000
0000111011100000
0000101111000000
0000000000000000
0000000000000000

o2, Binary String: 0000000000000000000000010000000000000011100000000000001010000000000001101100000000000100010000000000110001100000000010000010000000001000001000000001111111110000000111111101000000001100001100000000111011100000000010111100000000000000000000000000000000000000
o2, Binary-Decimal conversion: 95786086615602871731981918389383308042547593244061710

So gen1 looks like:
1,2 are the same as before; 3,4 are the offspring of crossover:
1. (b) 766259462624453036391004127445265907255673543052767246
2. (b) 766259462624453036391004127445265907255673543052767246
3. (o1) 766259462624453036391004127445265907255673543589892144
4. (o2) 95786086615602871731981918389383308042547593244061710

*Convert gen1 offspring to valid characters*

Now, 3 and 4 are new shapes that do not correspond with any of our 4 letters. The BBC (Bitmap-to-Binary Converter) will be used to “read” these bitmaps and find the closest letter in the space of possible letters which we will define. So, the offspring will turn into something like “h” and “8″, because those are the closest possibilities within the alphabet.

I was going to include a range in decimal numbers and apply that to the nearest alphabet character within that range, but I don’t think that will work because more often than not the offspring will just end up reverting to one of the two characters from which it was created. From this perspective, the BBC may be a very useful portion of the AS program.

So, o1 become “h” and o2 becomes “8″, converting gen1 characters to:

o1=h:
0000000000000000
0000110000000000
0000110000000000
0000110000000000
0000110111000000
0000111111100000
0000111000110000
0000110000110000
0000110000110000
0000110000110000
0000110000110000
0000110000110000
0000110000110000
0000110000110000
0000000000000000
0000000000000000

h, Binary String: 0000000000000000000011000000000000001100000000000000110000000000000011011100000000001111111000000000111000110000000011000011000000001100001100000000110000110000000011000011000000001100001100000000110000110000000011000011000000000000000000000000000000000000
h, Binary-Decimal conversion: 1149389193936678235951120191876555791760811195370319884

o2=8:
0000001111000000
0000011111100000
0000110000110000
0000100000010000
0000100000010000
0000110000110000
0000011111000000
0000011111100000
0000110000110000
0000100000010000
0000100000010000
0000100000010000
0000110000110000
0000011111100000
0000001111000000
0000000000000000

8, Binary String: 0000001111000000000001111110000000001100001100000000100000010000000010000001000000001100001100000000011111000000000001111110000000001100001100000000100000010000000010000001000000001000000100000000110000110000000001111110000000000011110000000000000000000000
8, Binary-Decimal conversion: 23539885800661303801528815919744719668529798326595472592908

So the gen1 now looks like:
1. (b) 766259462624453036391004127445265907255673543052767246
2. (b) 766259462624453036391004127445265907255673543052767246
3. (h) 1149389193936678235951120191876555791760811195370319884
4. (8) 23539885800661303801528815919744719668529798326595472592908

From which we evaluate the fitness again (“8″ clearly will be the new dominate gene) and so on, generation after generation…

*Conclusion*

This is the basic gist of Alphabet Soup by GA. The final aspect of using GA is to incorporate mutations: the random changing of various pixels within the letters, which will obviously introduce the same effect of crossover in adding to the population of letters. Mutations will only be applied to a small portion of the entire population in each generation, just like in nature. With only 4 characters to choose from, let’s say there are no mutations in this particular generation. That gives us the current pool of characters, including the initial population, gen0 and the current generation (gen1):

[POPinit][gen0] [gen1]
[A,B,a,b][b,b,b,A][b,b,h,8]

So, we have 6 “b”s, 2 “A”s, 1 “a”, 1 “h”, 1 “B” and 1 “8″ floating around. Granted this is an example run, but it plays out pretty realistically: note that the dominate gene (b) is taking up quite a bit of the population, while a and B have not grown at all in population. “h” and “8″ are the new kids on the block, and they will have a direct impact on the future generations, again based on their fitness for reproduction and crossover–with a little bit of mutation thrown in here and there.

One of the core questions remains: How do we make the shapes of the characters matter? In other words, how do we specify the importance of various pixels? This, I believe, can also be accomplished through the BBC, and I have some ideas for that. But more on that later.

Tagged with: Alphabet Soup • Binary-Bitmap Converter • GA • Video Games

Alphabet Character Binaries

On 01.27.10, In Development, Video Games, By Pariahpism

So we have a situation where we have 256 bits that represent the location of pixels in a 16×16 grid. I’m getting the feeling this is going to surprisingly like IP addresses with their subnet masks only eight times larger.

Each pixel will have a one or a zero in the 256 bits. In most of my examples I’ll be using 8 bits because it demonstrative of the same information, only legible to the hu-mons.

The first eight pixels when blank are [0000000]. This is pretty simple. But it would improve most of the processes to build a little encoder to make these characters to binary conversions simpler rather than to hard code all the charters once and everytime there needs to be a change. Plus it would add in the functionality to allow the user to make their own shapes in a free form mode.

Now if a letter with the [00000011] code breeded with one that had a [11000000], it would produced the Base Subnet of [11000011]. The child could contain any shape within the range and possibly none of them. If we choose to add dominant and recessive traits—which we should—than we’ll need to add another tag to show which pixels will retain dominance. Simply enough this can be accomplished with another two subnets.

Back up and let’s look at the parent classes again. [00000011] now needs another three addresses to properly pass down its heritage. [00000011] has a Base Subnet of [00000011] because he’s never once breeded. And he has a Dominant Subnet of [00000011] because we want him to retain his shape as a letter. His Recessive Subnet should be [00000000] just to allow the option to change without the likelyhood. And [11000000] will have similar characteristics. (BS-[11000000] DS-[11000000] RS-[00000000])

When these two parents meet and attempt to breed the BS will become [11000011] with the DS of [XX0000XX] (the ‘X’s are random numbers) and RS [????????]. I don’t quite know how the RS will be generated. Maybe the opposite of the BS that isn’t changed from the RS? Like if the DS becomes [10000010] than we have the unchanged bits [1X00001X]. And make them the opposite of the BS would be [10000010]. I’d have to see this done a few more times further down the line to make sure the DS and the RS don’t always stay the same. I wouldn’t really see the point in just randomizing the RS, so it has to be derived from so other stat.

The child would be made from these ranges. At this point other than the Dominant and Recessive context I’ve been using, there’s nothing GP about this. Fitness hasn’t become a factor in these combinations. It’s just a baseline for breeding and how it affects the appearance of the alphabet. And from appearance, it’s reactions to the environments.

I think I’ll drop some pictures of a character ‘A’ in a 16×16 bit map expounded by its traits.

The black is what it is. The red is the BS traits. The blue is DS traits. And the block that looks blank is actuality the RS traits.

Same here.

The child needs a lot of explaining. The cells are one through seven from left to right.

Ignore the first cell on the left. That comes last.

The second is the BS which is the potential, all the things the child could be.

The third is an overlay showing in green where the ‘A’ in light-blue and the ‘B’ in dark-blue overlay.

The fourth is just the bits that are overlayed. This represents the bits that are common to both and are to be forced dominate.

The fifth is the bits that are the ones possible to become dominant depending on randomness.

The sixth is if the bottom half was somehow all flipped-on making them dominant.

The seventh is the top half that was not flipped on and became recessive.

And now the first is the product. The dark-red and green are manifested because of the dominance and the plum color is now the recessive and does not show itself.

A problem with this system I can already foresee is that everything will soon become either recessive or dominant after only a couple generations of crossover and soon everything will manifest making every character a big black block.

Maybe taking only one side of the family’s gene in step five’s dominance check and make the other un-flipped bits for the opposite family recessive.

Now this is something. Here are all the same things but with the families jumbled between all the four possibles I made by cutting them in half (if it were random like I was hoping there would be hundreds of possibilities). The problem is they make some cool looking half-breed letters. But they wouldn’t look like that with only the dominant side (dark-red) and green manifested. Maybe the whole dominant/recessive thing needs to be reevaluated? Maybe when the dominant bits are chosen it’ll be different. I don’t know. But it also makes the BS pointless. Maybe I should scrap it and start over.

Tagged with: Alphabet Soup • Video Games

The Project. Six months in.

On 01.24.10, In Beginnings, General, Site Updates, Video Games, By The Villain

Over six months have passed since The Project began, and it was long before that the ideas were seeded. Pariahpism published his version of The Project origins right away. While this was an accurate description, I feel it is time to post my view on where it all started, what the past six months have involved, and where we might be going with The Project.

It began with an article published in 2007 by Alan Bellows on DamnInteresting.com about hardware evolution, “On the Origin of Circuits”. A comment in this article led me to Kevin Kelly’s book, Out of Control which is fully readable online. Now normally in my internet browsing I am not going to follow a link to a book and end up reading it in its entirety, but that is exactly what happened with Out of Control. The book starts out in Biosphere 2 in Arizona, and I thought, “Hey, I’ve been there!” And it only got more interesting as it went. Who would have thought ecology, philosophy, technology, economies and evolution had so many things in common.

Turns out Kevin Kelly is no scientist or engineer, but he is a hub of information, finding new meaning and understanding in many subjects, especially technology, with direct access to the top thinkers of our time. His blog The Technium continues to amaze and inspire me, while helping me think outside the box.

Out of Control covered a broad range of subjects, but some information seemed to stick out from the rest. I distinctly recall being impressed by the following, from Chapter 2:

In the film Batman Returns a horde of large black bats swarmed through flooded tunnels into downtown Gotham. The bats were computer generated. A single bat was created and given leeway to automatically flap its wings. The one bat was copied by the dozens until the animators had a mob. Then each bat was instructed to move about on its own on the screen following only a few simple rules encoded into an algorithm: don’t bump into another bat, keep up with your neighbors, and don’t stray too far away. When the algorithmic bats were run, they flocked like real bats.

It all came down to simple mathematical algorithms. Throw enough math into the software and, TADA! Biology plays out on your computer screen! Then, Chapter 15 dealt specifically with Artificial Evolution, while Chapter 17 “An Open Universe” expounded on that. Tom Ray and his game Tierra were highlighted, as was the GP master John R. Koza. These would soon become household names to The Project.

Fast-forward to July 2009. Pariahpism had taken to game journaling, and while not being interested in gaming I was surprisingly enthralled by his stories. My experience with software engineering combined with the memories of Origin of the Circuits and Out of Control prompted a sudden want to try to develop something of the same substance, but on a different scale. Imagine gaming journals about a self-evolving, unpredictable game! Immediately ideas started to take hold. We could provide the goals and the necessary environments, but let the games do the work!

After brief but furious discussions on the matter, Pariahpism proceeded to write about a number of game ideas brewing in our heads:

Alphabet Soup
The Field of Blobs
The Arti-Field of Blobs – The Field of Blobs Side-Quest
Game Untitled

And then the serious research began to see how to go about bringing such ideas to fruition. Little did we know everything that was already out there. Computational Intelligence is a huge realm under AI which includes, among others, Genetic Programming, Genetic Algorithms, A-life, Neural Networks, and so on. Books, websites and whole development environments are relegated to these subjects, prompting us to back up a step and begin collecting information at a rapid pace.

And here we are—still collecting. I have decided to completely overhaul the old website and devote it to The Project, and video gaming in general. Why dailyvillain.com? It started in 2004 as an inside joke, turned nickname, turned URL. It even stood as an acronym on the website for a while—something like Vagabond Interpreting Life’s Lessons and Idiosyncratic Nuances—but that was way too long. Anyway, the web space was already there and now it exists and persists as The Project’s home.

So where is The Project headed? Our original goals still stand. Early versions of Alphabet Soup and various programming languages are the focus of most of our attention for the moment, but concerning the future, anything is fair game at this point. The nice thing is that the interwebs allows the unprecedented vast sharing of information, letting us build on what others have already created. The beauty of Open Source is that it is more than just convenient, it also allows for the acceleration of information sharing, and of course, innovation. That’s what The Project is all about.

For a tad more organization… This blog will help to track our thoughts and progress, while this blog has become the home for the aforementioned gaming journals, other game reviews and pretty much anything game-related.

Tagged with: Background • CI • evolution • GA • GP • Kevin Kelly • On the Origin of Circuits • Out of Control

Introducing: The Computational Intelligence Hierarchy

On 01.24.10, In Site Updates, By The Villain

(Originally published January 17, 2010)

As we attempt to become the premier resource for everything relating to computational intelligence, The Project website continues to expand. The Grand Link Library continues to be updated, and now we have a growing Computational Intelligence Hierarchy to help organize all facets of The Project into something legible. Thanks to Pariahpism for putting together the hierarchy; now I am integrating it into the website and soon will be tying it together with the Grand Link Library. These will simply form the backbone of our work for The Project. The ultimate goals will be realized later, through the details.

Here’s V 1.0:

Tagged with: CI • hierarchy • links

Starting with Subclasses for Alphabet Soup, 0.01

On 01.24.10, In Code, Development, Ideas, Video Games, By The Villain

(Originally published January 10, 2010)

Time to get some thoughts down on digital paper concerning the actual code for Alphabet Soup. For simplicity’s sake, here are some more specific ideas:

To stay close to the code in MSDN’s ant program, we can start with a similar “ant” grid, allowing only up/down and left/right movements. This is not our “floating letters” environment yet, just think of it as a first step toward that.

We also have to redefine what the classes are and where they belong. The “ant” class becomes our “alphabet” class. “Food” in our case should be redefined to individual letter “species.” Let’s start with Alpha, Beta and Charlie to keep it simple. So, while an ant in MSDN’s program will encounter food along its path, any alphabet character will be encountering alphabet subclasses (formerly food) along its path. What the code decides to do results in whether the encountered character is devoured (or eaten, as in the original program), morphed, defended against or something else. So, the individual letters must obey the general rules of the alphabet class, but what they do individually depends on the evolutionary code that is run every time a collision occurs–and what happens should depend upon which letters are involved. I call this the ContactReaction() function.

Here is a general framework:

Alphabet class, stay with MSDN example, with adjustments:
public Void Init(Cell[,] grid, int StepLimit, int SurvivalGoal)

Move() function includes basic movements and the results of contact between letters, to call on evolution code:
public void Move()
{
if(NotFinished())
{
GetFacingCellCoord(outxLocation, outyLocation);
mTrail.Add(newTrailSpace(xLocation, yLocation));
mTotalSteps++;
if(mGrid[xLocation, yLocation].HasAlpha())
{
ContactReaction(Alpha) // calls function for what happens
when character encounters Alpha
// This will be where the evolutionary choice takes place,
well, part of it (see below)
}
if(mGrid[xLocation, yLocation].HasBeta())
{
ContactReaction(Beta)
}
if(mGrid[xLocation, yLocation].HasCharlie())
{
ContactReaction(Charlie)
}
}
}

Here we will place the evolution stuff–to include within ContactReaction() function:
{
// (Define basic function here with evolutionary aspect,
including specifics for each letter (see below))
if(result=Devour)
{
mGrid[xLocation,yLocation].SetEmpty(); // this is as if the
letter eats the other character
}
else
{
(OTHER OPTIONS/TRANSFORMATIONS/EVOLUTION) // Run Generator code
}
}

The ContactReaction() function will involve a lot of tweaking in combination with MSDN’s Generator class. It will call on the Generator class and expression tree constructors to perform the genetic crossover algorithms after every collision. The code for these can be found at http://msdn.microsoft.com/en-us/magazine/cc163934.aspx#S5

An important question…

Generator and Expression Tree from MSDN look great for our purposes, but should we include separate generator/expression tree specs for each of the different letters? More specifically, how will the letter’s shape have an effect on what happens in a collision? Should we define this aspect of it within the generator/expression tree? I think the best solution is to define those specs in our ContactReaction() function, meaning that function would have to be tailored to each individual character–but that way the generator/expression tree class can remain one and just be referenced by the ContactReaction() function–as I have shown above. So the evolutionary choice will still take place in the MSDN-defined classes, but each of the collisions will involve a “lean” toward reaction based on letter shape, as we define in ContactReaction(). This may or may not be the best solution, but it is a start.

Tagged with: Alphabet Soup • expression trees • MSDN • source code

The Master Link List

On 01.24.10, In Site Updates, By The Villain

(Originally published December 30, 2009)

Today’s project: categorizing, alphabetizing and updating the master link list for The Project. Based on the links we have collected so far, the best categories I could divide everything into included:
Blogs
Books Online
Games / Examples / Source Code
Potentially useful link dumps
Tutorials / Articles

Check it out.

Tagged with: links

« Previous Entries

The Project

Computational Intelligence, Genetic Programming, A-life, to name a few…

Genetic Programming: an introduction

Genetic Algorithms: an introduction

Character Collisions

Bitmap-Binary Basics

Alphabet Soup by Genetic Algorithms: a sample run

Alphabet Character Binaries

The Project. Six months in.

Introducing: The Computational Intelligence Hierarchy

Starting with Subclasses for Alphabet Soup, 0.01

The Master Link List

Welcome to The Project.

Categories

Tags

Articles

Links

Meta