Chris McCormick

Today I finished reading A field guide to genetic programming, a free, self published, creative commons licensed computer science book written by practitioners in the art of evolving computer programs. I say art because as the book makes clear this science is still quite young and experimental, mostly based on heuristics and rules of thumb. This is exactly what makes the book so valuable a resource. Outside the basic evolutionary algorithm the number of different ways of representing candidates, eliminating the unfit, reproducing new candidates, choosing population size, choosing mutation rate, etc. etc. make it incredibly complex to form a systematic analysis of the different aspects of the technique. The book gives experienced advice about all of these aspects and also suggests areas that need further study.

The book is ideal for people who want to get up to speed with the front line of current developments in the field. By the end of the book one is armed with enough knowledge to dive right in and start creating and using programs that evolve programs. A basic understanding of computer science concepts are all that is needed to grasp the concepts in the book, so anyone with a first year level of a computer science degree, or a few years of programming experience, should have no problem.

I purchased a hardcopy version of the book for easy reading and it came as a paper-back the size of a sheet of A5. The illustrations on the outside of the cover and througout the book lend it a lighthearted and easily comprehensible air and the writing itself is more enthusiastic than you would expect from a scientific text, making it an easy read. The examples provided are consice, easy to understand, and directly to the point, and the book is incredibly well referenced providing numerous texts to follow up some concepts in more detail.

Perhaps the most compelling feature of the book is the multitude of successful, practical applications of GP to real world problems which are found throughout it's pages. Before I read it, I was already convinced that the only way that we will evolve human equivalent intelligence will be through some type of artificial evolutionary process. Now I am even more convinced of that. Here are some choice quotes from the late Alan Turing, as always, far ahead of his time:

"There is the genetical or evolutionary search by which a combination of genes is looked for, the criterion being the survival value."

("Intelligent Machinery", Turing, 1948)

"We cannot expect to find a good child-machine at the first attempt. One must experiment with teaching one such machine and see how well it learns. One can then try another and see if it is better or worse. There is an obvious connection between this process and evolution.

'Structure of the child machine' = Hereditary material

'Changes of the child machine' = Mutation

'Natural selection' = Judgement of the experimenter"

("Computing Machinery and Intelligence", Turing, 1950)

What higher computer science accolade is there than Alan Turing's posthumous recommendation? In short, great book. Find out more at the official website and purchase it online at lulu.com.

Wow, I am super-excited to report that I have started doing work for RjDj.

I am now 99% certain that the way in which we all listen to music in the future won't always be the same as the way in which we listen to it now. This review, by someone completely who is not associated with RjDj, sums the idea up quite nicely.

I'm excited.

In order to test out a generic Python multiplayer game library that I'm working on, I had to come up with a game design for the simplest possible multiplayer game. I'll post the library's code here another time when it's stable and tested, but in the meantime here's the game design that I came up with:

It's a two player turn-based strategy game with the simple objective of destroying all of the other player's ships. There are two phases; the input phase, and the simulation phase. Each player runs the client on their own computer and they input their next moves simultaneously during the input phase. The moves are hidden from the other player until the simulation phase, which happens once both players are finished inputting their moves. Control of the ships is simple; click the blue circle and then click the playing field in order to define the path of each of your ships for that turn; click the red circle and click in the direction which you'd like the ship to shoot for that turn. When ships are hit with enemy fire their health bar will show up with it's value diminishing, and when it gets to zero the ship will disappear. You can also see the health bar of ships by hovering the mouse over them.

There were a couple of truckstops I couldn't find in Google Maps, but I think that this is most of them

I've been re-visiting some code I wrote quite a while ago which generates a virtually infinite number of generic 2D RPG maps, with grass, sand, road, trees, and water, like this:

Here's the algorithm I have used, implemented in Python, using a Perlin Noise generator:

detail = abs(perlin.Noise2D(x / 300.0, y / 300.0))
desert1 = -perlin.Noise2D(x / 100.0, y / 100.0)
desert2 = perlin.Noise2D(x / 10.0, y / 10.0)
desertp = desert1 * detail + desert2 * (1.0 - detail)
waterp = perlin.Noise2D(x / 150.0, y / 150.0)
roadsp = (abs(perlin.Noise2D(x / 50.0, y / 50.0)))
treep = max(0, perlin.Noise2D(x / 300.0, y / 300.0)) + perlin.Noise2D(x / 3.0, y / 3.0)

oasis = desertp > 0.95
lake = desertp < -0.6
river = desert1 < 0.6 and abs(waterp) < 0.075
desert = desertp > 0.6 and desertp < 1.0 or desert1 > 0.8
roads = abs(roadsp) < 0.05
riversideRoads = desertp < 0.6 and abs(waterp) < 0.11 and abs(waterp > 0.08)
trees = treep > 1.15

if lake or river or oasis:
    DrawWater(x, y)
elif roads or riversideRoads:
    DrawRoad(x, y)
elif desert:
    DrawDesert(x, y)
elif trees:
    DrawGrass(x, y)
    DrawTrees(x, y)
else:
    DrawGrass(x, y)

One problem is that I couldn't find a decent perlin noise generator for Python that was easy to install, so I had to roll my own, and it's dog slow (apologies to any dogs who are reading this). I even tried re-implementing it as a Python extension in C but it was still only twice as fast. Psyco also did nothing to help the situation, which basically means it isn't slow because of bad optimisation but because the algorithm is very CPU intensive. The good news is that a few nights ago, while I couldn't sleep, I think I came up with a really quick way of generating random fractal based landscapes by caching the results of previous, higher order position lookups. If I'm right, it kind of turns the Perlin algorithm inside out to prevent redundant calculations. Of course, it will trade off speed for higher memory usage, but that's ok in this situation. I haven't tested my idea out yet, but hopefully I will get around to it and make my map algorithm much faster.

Another problem is that my existing maps won't wrap onto a torus without discontinuities, which means you have to have infinitely large maps for people to explore, which go on and on forever. I'd rather the maps wrapped so I could wrap them around planets and stuff. Fortunately, I think that with the judicious use of modulus operators my new algorithm should wrap pretty nicely.

Characters

I came up with these vector art characters which I think would be suitable for a 2D RPG style game.

They're SVGs made in Inkscape, which is highly scriptable, so I am thinking about prototyping a character creator screen which will allow you to deck them out in different colours, clothes, accessories, etcetera, and then use Inkscape to render variations in the background.