Re: DungeonMaker 1.0 released

[Mark Collins <me@thisisnurgle.org.uk>]

On Tuesday 12 June 2001 13:58, you wrote:
> Mark Collins wrote:
> >Not really a chunk of code....
>
> Indeed not, but it's not a genetic algorithm either. Granted, you use
> parameters you call genes, but the essence of the genetic algorithm is that
> it stores parents with high fitness value, and generates new gene-sets from
> two parents using crossover and mutation. You do none of this.

Actually, it's a true "Natural Selection" based genetic algorithm That system 
was originally used by me for a Quake bot. Each bot has a specific number of 
genes (one for sniping, one for camping, one for grouping etc),  and when 
ever a bot is respawned, it inherits genes from the remaining pool.

Of course, if you have too few bots, then the genepool isn't diverse enough, 
and if you have too many, then there's very little chance of them adapting to 
the players style, but it is possible.

Just because it appears it's a non-standard system (mainly due to the 
environment it was designed for), it doesn't mean it's not a genetic 
algorithm.

> Any implementation of the genetic algorithm will have to store a sizeable
> genepool to file, it will have to completely rewrite that file each time a
> new potential parent is added to it, and it will have to allow all possible
> integer ranges for its individual genes. Every time a new set of genes is
> requested from the engine, it must be generated from two parents read from
> file, with crossover and mutation applied to them. In a general
> implementation I would also want the concept of chromosomes, and genes with
> floating point values, though that isn't strictly required. It is also
> neccessary to allow for the tuning of parameters such as mutation rate. In
> the end, this will be a solid chunk of code indeed, at least compared to
> the small benefits it would provide for automatic difficulty balancing
> (which was the context I used the term in).

Maybe you should learn efficient programming? For a dungeon, my algorithm 
from the previous mail could easilly be used. It goes a little something like 
this:

Generate a set of random dungeons.
Play each of the dungeons in order
If a dungeon is fit, don't kill it, otherwise, kill it
Spawn a new dungeon using the remaining genepool.

Each gene could used to specify a certain property of the dungeon, such as 
long corriders, big rooms, treasure rooms etc etc.

> Frankly, Mark, if you don't even know what a genetic algorithm is, I think
> you should reconsider writing a book about that subject. Or at least study
> the existing literature some before you do.

Ok. Here is the genetic algorithm from "Artificial Intelligence: A Modern 
Approach":

function Genetic-Algorithm(population, Fitness-Fn) return as individual
	inputs: population, a set of individuals
	Fitness-Fn: a function that measures the fitness of the individual

	repeat
		parents := Selection(population, Fitness-Fn)
		population := Reproduction(parents)
	until some individual is fit enough
	return best individual in population, according to Fitness-Fn

In my example above, the fitness is defined by whether or not the player can 
kill the bot, and the population information is stored in the genepool (i.e. 
the total number of each type of gene that is still in the game).

Just because your idea of a genetic algorithm may be overly complex, it 
doesn't mean others can't find better ways to use them. My system works on 
those exact principles, accept it's designed to adapt over time, not in one 
tight loop.

(and FYI, I've been offered a place of Oxford Uni to do AI research).

I suggest you read some books on genetics and memetics, maybe The Selfish 
Gene by Richard Dawkins and The Meme Machine by Susan Blackmore (their 
biology/psychology books, but they're a good read about universal darwinism 
none-the-less).

Nurgle

---------------------------------------------------------------------
To unsubscribe, e-mail: linuxgames-unsubscribe@sunsite.dk
For additional commands, e-mail: linuxgames-help@sunsite.dk