Genetic Algorithms

Article: 7164 of rec.games.programmer
For those people who are interested in the discussion of CCPs
using genetic algorithms here are a couple of references which
could be useful.
I'm also posting this to the group as I've had a number of 
requests for information, and mail does not seem to be gettting
through.
I have a several other references, so if you would like some
more info try e-mail again.

1.	author = "Gregory J.E. Rawlins",
	title = "Foundations of Genetic Algorithms",
	address = "San Mateo California",
	publisher = "Morgan Kaufmann Publishers, Inc",
	year = "1991" 

2.	author = "Lawrence Davis",
	title = "Handbook of Genetic Algorithms",
	address = "New York",
	publisher = "Van Nostrand Reinhold",
	year = "1991" 

3.	author = "Lawrence Davis",
	title = "Genetic Algorithms and Simulated Annealing",
	address = "London, England",
	publisher = "Morgan Kaufmann Publishers, Inc.",
	year = "1987" 

4.	author = "David E. Goldberg",
	title = "Genetic Algorithms in Search, Optimization, and Machine
		 Learning",
	address = "United States of America",
	publisher = "Addison-Wesley Publishing Company, Inc.",
	year = "1989" 

5.	author = "John H. Holland",
	title = "Genetic Algorithms",
	volume = "267(1), July",
	pages = "44--50",
	journal = "Scientific American",
	year = "1992"

This last paper is a good introduction to GAs and the book by Goldberg
(4) is also pretty good.

Ross.
-- 
Ross Milward,   ross@coral.cs.jcu.edu.au, cprem@marlin.jcu.edu.au
Honours Student - Comp. Sci. Dept.,  James Cook Uni, Qld, 4811, Australia.
"The way the rain comes down hard, that's how I feel inside." - The Cure
      
Article: 7246 of rec.games.programmer
I'm delighted to see that the idea of using real AI in games is
beginning to take off in rec.games.programmer.  About six or nine
months ago I tried to get a discussion of this topic started on
comp.ai, but it fizzled out.  Wrong group, I guess.

The following book discusses in fine detail how to implement many of
the clever suggestions that have recently been raised in this thread
regarding the use of genetic algorithms and neural networks to make
computer games more interesting --e.g., by providing "smart" opponents
(how about partners, too?).  This book will give you game developers
lots of ideas about how to write your "Fifth Generation Computer
Games," and also allow you to save time by avoiding reinvention of a
lot of wheels.

        author = "Steven Levy"
        title = "Artificial Life: The Quest for a New Creation"
        address = "New York, N.Y."
        publisher = "Pantheon Books, Random House, Inc."
	isbn = "0-679-40774-X"
	price = "US$25.00"
        year = "1992"

Another rich source of ideas is the long-running --and free!-- Genetic
Algorithms Digest published by John Grefenstette through the Internet
(I think I heard that someone else took over from him recently).  Here
are some pointers, current as of July 7, 1992:

 - Send submissions to GA-List@AIC.NRL.NAVY.MIL

 - Send administrative requests to GA-List-Request@AIC.NRL.NAVY.MIL
   (this is the one for subscription requests)

 - anonymous ftp archive: FTP.AIC.NRL.NAVY.MIL (see v6n5 for details)

Get a copy of AI Expert Magazine from the newstands and scan the ads to
find (cough, cough) "inexpensive" shell programs that let you quickly
build expert systems, genetic algorithm-based learning programs, and
neural networks.  ($3.95/issue in US, subscriptions 1-800-274-2534 in
US, or 1-303-447-9330 outside the US).

You lot in the U.K.:  See if Richard Forsyth's company Warm Boot
Limited still sells Beagle, a genetic algorithm shell for IBM PC's.

Oh, if anyone out there wants to get seriously rich, here's a tip: The
new Personal Digital Assistants (PDAs) that Apple and Sharp are about
to start selling will provide a new platform for delivery of super
outrageous computer games, a new market segment for computer games,
and a market for new kinds of computer games.  Many of these games
will have "painless" educational content, and will help to achieve the
goal of "learning on demand" that is being talked about now.  Contact
the Small Business Administration to find out how to get money from
the US Government to develop socially beneficial educational games.
I'd like to see one that teaches kids the three classic forms of
reasoning: deduction (A, if A then B, so B fer sure), abduction (B, if
A then B, so maybe A), and induction ( A, B, so maybe if A then B).
Then maybe in twenty years presidential elections would be more
interesting.

PDAs will totally blow away older products such as the GameBoy, and
will even give the new pen-based computers a tough challenge to match
their performance and ease of use.  Apple's "Newton" PDA will have a
RISC processor twice as powerful as a Mac IIfx to run your games on,
and a pen-based interface to support new styles of direct interaction
with the action on the screen.  Draw the course you want your
submarine to follow right on the map; draw notes on a staff to play a
tune that will (hopefully) put the troll to sleep; run wires to
connect the logic gates that control your battlebot; sketch in the
missing part of the famous painting; copy that Old High Martian
inscription from the crumbling wall to show the Professor; try to
forge Leisure Suit Larry's signature in the guest book at the Blue
Oyster Bar.

Later models of Apple's PDAs will have packet radio modems that will
allow you to connect to the Internet and participate in real-time
global multiple-player games.  Send MPEG-compressed video of your own
face to people who never did you any harm.  Engage in mortal combat
with other scramjet jockeys around the world while riding the bus to
work!

Continuous speech recognition for vocabularies of a few hundred words
will probably be available on PDAs in a year or two, using Apple's
Casper software (Carnegie-Mellon University's Sphinx system, but
speeded up 35-40 times).  Similarly, Apple's Galatea software will
allow your characters to speak arbitrary sentences with really good
pronounciation (sorry, Talking Moose!).  Apple has been demoing these
two programs lately as research prototypes, but I see that already the
desktop Cyclone Macs out early next year are rumored to have speech
recognition built in.  Sharp will be selling low-cost, low-end
versions of PDAs early next year with fewer features than Newton.  In
a few years they will probably be $49.95 in K-Mart, come in six
designer colors, and half the kids in Junior High will carry one along
with their Walkman.

For those of you wondering what programming language to learn, Apple
is now circulating a specification for Dylan, a very powerful new
dynamic language for scripting applications for Newton and other PDAs.
Based on the Scheme dialect of Lisp, it is perfectly suited to
artificial intelligence programming styles.  Apple claims that Dylan's
strong point is a seamless integration between the programming and
execution environments to allow rapid development.  They see Dylan as
a kind of "HyperCard of the 90's" that --like HyperCard-- will allow
thousands of "ordinary" people to develop new applications for PDAs
without being professional programmers.

Scientific American had a special issue recently on genetic algorithms
(June '92?).  Don't miss Holland's tutorial and the 1-page story about
the Russian programmers who are going to offer a game/simulation of a
tank of pretty fish, which you can breed to produce new kinds of fish,
exchange with your friends, enter in ALife 4-H shows, etc.  I think it
said the fish's chromosomes are over 600 bits long, and they control
not only the fish's appearance, but its behaviour.

Dec 91 Scientific American had a nice article on Rod Brooks' robot
insects at the MIT AI Lab and other interesting, current AI/robotic work.

Sep 91 Scientfic American had a story about how far radio-linked
computing might go, as Xerox Palo Alto Research Center sees it.  So
many computers in each room that you can't count them all!

Does anyone know what General Magic is developing?

Happy hacking!!  -- and don't forget to tie your games into the local
virtual reality arcade center.

-- 
Grandpaw Bill's High Technology Consulting & Live Bait, Inc.
      
Article: 7273 of rec.games.programmer
     -=> Timothy D. Goss spoke of "Re: splitting the group" <=-
    To All at 08-21-92  03:34
 TDG> Now.  Would anyone like to discuss some of the primitives necessary to
 TDG> make a really useful genetic algorithm?  I can't see how a 'good'
 TDG> critter can evolve without some powerful primitives to draw upon.  Any
 TDG> ideas?

I thought I posted something on this.  Anyway my thought is to
use "inheritance" combined with fractal geometry.  What I mean is
using a system of "weights" inherited from an ancestor these
weights each have an "equation" that's models a particular "state"
of behavior.

It's like a soccer ball on a field of play.  You have 20 players
each with their own bias.  10 want to score a goal to the right
10 to the left.  Each team of players vie for control of the ball.
In general it will depend on the strategies each player employees
on the moving the ball as to who wins.  however it also depends
on who has control of the ball!  SO let's say each of the ten
players have their own favorite strategy which will work
differently.  Each team struggles for control of the ball
meanwhile.

By inheriting these weights [that is the better ones] and
equations each succesive generation will have a better strategy
model to work with.  Besides by also adding NEW equations/weights
you could add mutation! :)

        Stephen Cyberman@Toz.Buffalo.NY.US
        Scripted at Fri  08-21-1992  14:00:47

... The more you run over a cat, the flatter it gets.
--- Blue Wave/QWK v2.10
      
Article: 7298 of rec.games.programmer
All this stuff about genetic algorithms is getting me hungry.  I'm not
a game programmer (though I wouldn't mind being one), but I would like
to know more about GA.  Can anyone recommend some good books (if any) or
any other sources of information on GA?

Also, I've been wanting to make a computer game of Chinese chess.  The
only language I know well is Pascal, but I don't think that's the best
one for this kind of game.  Any programming languages that you can suggest
for programming a chess algorithm?

John Har:  ix9j@vax5.cit.cornell.edu  (yes, we don't get personalized id's)
      
Article: 7307 of rec.games.programmer
ix9j@vax5.cit.cornell.edu writes:

>All this stuff about genetic algorithms is getting me hungry.  I'm not
>a game programmer (though I wouldn't mind being one), but I would like
>to know more about GA.  Can anyone recommend some good books (if any) or
>any other sources of information on GA?

   THE book about GA is(IMHO):

Genetic Algorithms in Search Optimization & Machine Learning.
David E. Goldberg
Addison Wesley, 1989
ISBN 0-201-15767-5
      
Article: 7368 of rec.games.programmer
odlin@reed.edu (Iain Odlin) writes:


>  Greg Knauss writes that he has doubts that you'll see GAs put in anything
>  useful.

Anytime soon.  I think GA will be a force, but not for a long, long time.
Heck, someday we could be breeding our computers, and genetics will HAVE
to play a role in that.

>  I suggest you ("you" being anyone interested in practical GA applications on
>  a PC) check out the April 1991 issue of "Doctor Dobb's Journal."
>
>  It isn't the be-all and end-all of GA, but it'll sure as Hell point you in 
>  the right direction.

Thanks for the tip.
--
 ------------------------------------------------------------------------------
 Greg "Maddog" Knauss               "Aieee!"              greg@duke.quotron.com
 ------------------------------------------------------------------------------
      
Article: 7373 of rec.games.programmer
greg@Quotron.COM (Greg "Maddog" Knauss) writes:
>dmb@rice-chex.ai.mit.edu (David Baggett) writes:
>
>Rice Chex?  Did you get to name your machine, Dave, or did you inherit it?

Actually, rice-chex is just a general-purpose server.  If you want a
challenge, try finding a breakfast cereal (with approprite hyphenation)
that *doesn't* work when you say "ping <cereal>.ai.mit.edu"  :-)

>Interesting, yes, but practical -- probably not.  It's neat to talk about
>GAs and NNs and say, "When..." and "What if..." but I don't think you're
>going to see them in games (or anywhere else) any time soon.  Even the
>"sensory input" of Pac-Man would overload the machine.

That's very much an assumption, and one based on the current state of
the art.  There are possibly ways of simulating generalized thought
without using the conventional GA and NN methods.  I don't think the
information overload is inherent in the problem, but rather a
side-effect of the solution methods we currently have.

>	What I would like to see (and probabaly should do, with "Night
>of the Brain-Sucking Undead Businessman From Beyond the Grame" if I ever
>get off my butt and start working on it again...  Heh) is fuzzy logic.

That still sort of seems like "faking it" to me.  The character is
still chosing from a predetermined set of choices.  It only becomes
interesting, IMHO, when the algorithm (method) starts producing
patterns of behavior that were not programmed in at the outset.  GA's,
at least, provide a straightforward way to make this happen, though
it's unclear (to me at least) that they have anything at all to do
with independent thought.

Dave Baggett
--
dmb@ai.mit.edu           MIT Artificial Intelligence Laboratory                  
ADVENTIONS: interactive fiction (text adventures) for the 90's!
dmb@ai.mit.edu *** Compu$erve: 76440,2671 *** GEnie: ADVENTIONS
      
Article: 7376 of rec.games.programmer
Jerry Shekhel writes:
>I got away with a really fast and really dumb technique in my Chomp game.

James Hague <exuhag@exu.ericsson.se> writes:
>"Dumb" is the way to go.  To connect this with the computer-controller
>players thread, I find all the talk about genetic algorithms and neural
>networks to be a major overestimation of what is necessary to create
>a formidable opponent (for action games anyway).

dmb@rice-chex.ai.mit.edu (David Baggett) writes:
>Also, regardless of how easy it is to make an overly difficult game, it's
>still hard to make computer opponents that aren't very predictable.  If
>you play any current Pac-Man game long enough you'll get very good
>at anticipating the ghosts' "decisions," because when it comes down to
>it they're all canned.  Throwing in some randomness doesn't help a
>whole lot either; a ghost whose movements are random enough to be
>unanticipateable is usually (in my experience) too "dumb" to be a
>threat in practice.

Well that would depend on exactly how much of a disadvantage to the
ghosts the player anticipating the ghosts is.  In the original Pac-Man
it was possible to predict the ghost movements accurately enough to
for books to be published with the exact path to follow through the maze 
to guarantee a victory.  Essentially this means the pridictableness
of the ghosts was terrible disadvantage for them.  Adding a just a bit
of randomness, enough to distrupt any preplaned path, but without
making the ghosts too "dumb" may not be a bad idea. 

							Ross Ridge

-- 
Ross Ridge - The Great HTMU					     l/	 //
								    [OO][oo]
ross@zooid.guild.org						    /()\/()/
uunet.ca!zooid!ross						     db	 //
      
Article: 7379 of rec.games.programmer
Hello everyone,

  I'm thinking about beginning a project which would create a strategy engine
capable of reading a database of rules and creating a space of possible
strategies based on those rules.  The rule database would consist of the
rules of some fairly simple baord wargame translated into a yet-to-be-defined
machine readable language.  The idea here is to create a language capable of
expressing a large number of different wargame rules sets, and an engine 
capable of reading and operating on any rules set expressed in that language.
The goal of the strategy engine would be to propose strategies for the
playing of a game based on current board position, victory conditions, and
whatever else is relevant.

  But, I'm in need of some pointers on where to look for work already done in
this area.  Particularly interesting would be references which deal with
representing boards, units and rules in a program, and anything done already
on decision making and planning in games.  I have a feeling that a lot of work
has been done in similar areas for the creation of computer controlled players
but I don't know where to look.

  If any of you have ANY ideas about what I ought to be reading for this
project, please forward them to me.  If there's any interests, I'll compile
a listing of the resources and post them to this group.

Thanks very much,

Will Scarvie
will@kafka.saic.com

DISCLAIMER:
The opinions expressed are entirely my own and should not be construed to 
represent those of my company.
      
Article: 7404 of rec.games.programmer
(Nicolai Czempin) writes:
>cprem@marlin.jcu.edu.au writes:
>> Now we've got this discussion rolling, is anyone actually going to begin
>> coding a game with intelligent/evolvable CCPs.  It would be great to see
>> a game that had a large variety of CCPs that can evolve into stronger
>> opposition as the game develops.
>> 
>> Ross Milward,   ross@coral.cs.jcu.edu.au, cprem@marlin.jcu.edu.au
>
>A possible starting point would be those bot programs. However, the languages
>to program the bots are usually not very powerful.
>...
>Nicolai Czempin, University of Karlsruhe, Germany
>"I am not left-handed either"

On the contrary - the bot languages are too powerful for genetic algorithms.

To use genetic improvement of algorithms, you have to be able to change the
algorithm randomly.  A bot language is rather complex, and changing (say)
a GOTO to a LET A = B would probably not improve performance.  You would have
to sort through a lot of mutants before you found a viable one.

The key to using genetic algorithms is to formalize the behavior/construction
you wish to improve in a way such that a random change still produces something
plausible.  I don't think that computer-controlled players can be generated
using genetic algorithms.  You could write an algorithm that used a large
number of parameters to determine its behavior, and then vary those parameters
(i.e. define a standard deviation for each parameter, then create a descendent
by randomly selecting a value for each parameter from a normal distribution
around the parent's value using said standard deviation).  Or, you could have
a data language which specified the construction of, say, a battlebot, which
would be altered in random ways (i.e. make entire bot or subunits larger/
smaller, armor thicker/thinner, weapons heavier/lighter; you may then have
to 'renormalize' if bot construction is constrained by resources).  But a
von Neumann machine program is not a good candidate for genetic algorithms.

So to speculate about GA is usually pointless unless you propose a SPECIFIC
data encoding and method of varying it.

The same applies to neural nets.  Neither GA nor neural nets are magic.
It pains me to hear people explain futuristic systems that will do marvellous
things, saying, "They will use neural networks to ...".  Neural networks
compute functions.  They can generalize to previously unseen input, learn to
better approximate the function they compute, etc.  But you have to define the
function!  It has to be the right scope of function - you can't use letters as
input and expect a parse of an English sentence as output; you have to
hypothesize some modularity to the task.

I am aware that a network can theoretically do any computable task.  However,
if your function is not modularized well, the network will function
inefficiently, to the point that it will not work.

Usenet has a lot of discussion of genetic algorithms & neural nets, but seldom
arrives at the useful level of specific proposals.

Phil
goetz@cs.buffalo.edu
      
Article: 7410 of rec.games.programmer
In article <Btx892.1yD@acsu.buffalo.edu> goetz@acsu.buffalo.edu (Phil Goetz) writes:
>On the contrary - the bot languages are too powerful for genetic algorithms.
>
>To use genetic improvement of algorithms, you have to be able to change the
>algorithm randomly.  A bot language is rather complex, and changing (say)
>a GOTO to a LET A = B would probably not improve performance.  You would have
>to sort through a lot of mutants before you found a viable one.
>
>The key to using genetic algorithms is to formalize the behavior/construction
>you wish to improve in a way such that a random change still produces something
>plausible.  I don't think that computer-controlled players can be generated
>using genetic algorithms.

Ok, maybe I'm off in left field, but in Steven Levy's _Artificial Life_
book, he talks about an experiment where programs fought to reproduce
themselves. I guess that I don't remember GAs mentioned there. However,
I started playing around with an old game that I had written that used
programmed players and I used GAs on their code. Now, at first I said
that since I was dealing with machine language and not genes, I would
get only garbage out. And indeed, I seeded the initial population with
some robots that I had written. Within 5 generations, my population was
uniform, and nearly identical to one of my seed robots.

However, I tried again (on a 486, this time :) and I have got some
interesting behaviors quite randomly. I think that I am going to have to
add a little bit more randomness into the brew, because things are
beginning to look too uniform again.

Ok, so to reply to the claim above, computer-controlled players CAN be
generated using genetic algorithms. I've been through 22 generations so
far, and haven't seen anything terrific (I guess that I'm still matching
the computer-generated 'bots to my own, and mine are better... now) but
these things are forming pretty much on their own.

>
>I am aware that a network can theoretically do any computable task.  However,
>if your function is not modularized well, the network will function
>inefficiently, to the point that it will not work.
>

Neural Nets cannot, to my understanding, compute multiplication of two
numbers. Perhaps you are not talking about NNs, or perhaps the
multiplication needs to be done differently than I had approached it. It
seems to me that NNs work fine when the outputs are a linear combination
of the inputs.


Just the $/50 of someone who's spent some spare time toying with this
stuff.

-- 
Your Mom!       The Carburator!         |I'm not paid to HAVE opinions.
Your Shoes!     A gardenhose!           |
You got to got to got to got to ...     |This sig can be yours; send $15 to
SCUD MISSILE!!!	-"Scud Missile", Grunge |tsmaster@athena.mit.edu
      
Article: 7411 of rec.games.programmer
In article <Btx892.1yD@acsu.buffalo.edu>, goetz@acsu.buffalo.edu (Phil Goetz) writes:
> (Nicolai Czempin) writes:
>>cprem@marlin.jcu.edu.au writes:
>>> Now we've got this discussion rolling, is anyone actually going to begin
>>> coding a game with intelligent/evolvable CCPs.  It would be great to see
>>> a game that had a large variety of CCPs that can evolve into stronger
>>> opposition as the game develops.

A friend of mine and I are in the conceptual design phase of a space
combat game.  He is buying a Neural Network program to *possibly* help
in the creation of a CCP.  However, I am more inclined to pursue a GA 
generated CCP.


> To use genetic improvement of algorithms, you have to be able to change the
> algorithm randomly.  A bot language is rather complex, and changing (say)
> a GOTO to a LET A = B would probably not improve performance.  You would have
> to sort through a lot of mutants before you found a viable one.
> 
> The key to using genetic algorithms is to formalize the behavior/construction
> you wish to improve in a way such that a random change still produces something
> plausible.  I don't think that computer-controlled players can be generated
> using genetic algorithms.  You could write an algorithm that used a large
> number of parameters to determine its behavior, and then vary those parameters
> (i.e. define a standard deviation for each parameter, then create a descendent
> by randomly selecting a value for each parameter from a normal distribution
> around the parent's value using said standard deviation).  Or, you could have
> a data language which specified the construction of, say, a battlebot, which
> would be altered in random ways (i.e. make entire bot or subunits larger/
> smaller, armor thicker/thinner, weapons heavier/lighter; you may then have
> to 'renormalize' if bot construction is constrained by resources).  But a
> von Neumann machine program is not a good candidate for genetic algorithms.
> 
> So to speculate about GA is usually pointless unless you propose a SPECIFIC
> data encoding and method of varying it.

> Phil
> goetz@cs.buffalo.edu
> --
> The Usenet Oracle has pondered your question deeply.
> Your question was:
> 
>> help i'm a bug
> 
> And in response, thus spake the Oracle:
> 
> } <poof> you're a feature!
My general concept involves assigning weighted values to a parameter.
In this case say the parameter is your spacecrafts optimal engagement
range to an opponent.  The parameter would have some equation describing
average damage received / average damage given versus range.  The
CCP would try to minimize this parameter.  The weighting would be a
addition or subtraction to the range value.  I would give the CCP
equations similar to the one above for other parameters too.  In this
way I would have a string of weighted values (e.g. 10, 1, .1, 100, etc).
this would be my gene string for the GA.


-- 

   Jim Batka  | Always remember ...                        | Buckaroo
   Modemman   |    No matter where you go, there you are!  |   Bonzai
--------------+--------------------------------------------+--------------
              | Work Email:  BATKAJ@CCMAIL.DAYTON.SAIC.COM | Elvis is
              | Home Email:  JBATKA@DESIRE.WRIGHT.EDU      |   DEAD!
--------------+--------------------------------------------+--------------
              | 64 years is 33,661,440 minutes ... and a   | Beatles:
              | minute is a LONG time [Includes Leap Days]!|   Yellow Submarine