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: • • •
 
0 Comments
Leave A Response

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: •
 
0 Comments
Leave A Response

Welcome to The Project

On 01.04.10, In Beginnings, Video Games, By The Villain

(originally written by Pariahpism, July 10, 2009)

Well it started with a conversation about the recent phenomena of videogame journals.  I tried my hand at it with a couple freeware games that are more based on random level generation and consistently random experiences rather than story.  I find these have a better potential to tell their own story rather than the one already given, if one even existed; which in these it didn’t.

The dark tale about a merchant murdered got The Villain pondering how to make a video game.  This was something he’d never thought of and something I’d never expect him to say.  He will soon be finishing his software engineering degree which taught him to expertly create a mortgage calculator in some common programming languages.

Other than the mortgage calculating game he was so familiar with, he was a total novice to the videogame world.  It’s something that never held his interest.  If he was serious, which he is, it was to be a trial to ease him into our culture.  We videogame folk are a serious and bitter sort.  Angst and resentment go with or morning cereal and mocking humor with tuna are our lunch.  An unlearned couldn’t walk in and understand us any better than the large corporations who make most of our games; basic trends of what sells better over what is actually better.  He would be sniffed out and quickly excommunicated by our purists.  I wouldn’t let my friend walk alone in our prison yard.  His ass would not be sold for pruno.

Basic instructions ensued of the basic types, what’s good, what’s bad, what’s out there now, what’s out there no longer and the trends and history of it all.  In my mind I saw this gaming venture working, but only very basically.  I was hoping to do some artwork while he did the coding and we’d both contribute to the story and while I kept a stalwart presence that we’d break no unwritten covenant.  I foresaw a couple awesome stories made playable with some visceral visuals and maybe we’d win some Indie Game Awards.  Maybe.

Then this brilliant bastard his me with something I didn’t consider: Something new.  Being an avid studier in the origins and designs of evolution, he hits me with Thomas Ray’s virtual evolution project where he created virtual viruses.  In 1989!  The Villain’s idea was to use the engines of evolution to program elements in games.  After mild discussion, I told him that this is something that has never before been done.  It would be singular in design and in competition.  And only knowing that this website is never visited that I feel comfortable posting these ideas freely.

Tagged with: • • •
 
1 Comments
Leave A Response
Go To Top »