NetNews Usenet Archive 1992 #27/NN_1992_27.iso/spool/comp/ai/4316

Internet Message Format | 1992-11-17 | 3.4 KB

Xref: sparky comp.ai:4316 rec.games.programmer:4718
Newsgroups: comp.ai,comp.ai.genetic,rec.games.programmer
Path: sparky!uunet!cis.ohio-state.edu!sample.eng.ohio-state.edu!purdue!ames!kronos.arc.nasa.gov!iscnvx!netcomsv!versyss.versyss.com!keithd
From: [e-mail] (Keith Doyle)
Subject: Re: Games and genetic algorithms
Reply-To: [e-mail] (Keith Doyle)
Organization: VERSYSS Incorporated, Torrance, California
Date: Mon, 16 Nov 1992 17:52:15 GMT
Message-ID: <[e-mail]>
Keywords: genetic algorithms
References: <[e-mail]> <[e-mail]>
Lines: 51

In article <[e-mail]> [e-mail] (Andrew C Goldish) writes:
>I have written several computer games using the Borland Pascal compiler and
>would like to teach the computer to learn from its own mistakes when it plays
>against a human opponent (a la War Games).  I am going to try to insert a
>genetic algorithm into the board evaluation subroutine so that the game
>strategies whose parameters produce the most successful games survive to

One problem you may have with this approach, is that it could take a fairly
long time for it to learn, and in the meantime it could be pretty boring
for the human opponent.

One problem is, if you mutate an "offspring" of the parent evaluation
DNA, it may play worse than it's parent.  Normally, you would compare
the success of the two "organisms" until you determine which one should
be preserved and which one should die out, giving way to new organisms.
This could mean it might play several lousy games before it decides a
particular organism should be edited out.  Not a lot of fun I expect.

However, you may have more success if you create an entire population
of organisms, all of which "vote" with regards to a given move, and
you cast the computer's move based on the majority.  Once the outcome
is decided (and you could even have intermediate goals which can be
used during the game as well), you can "weigh" each of the organisms
performances.  In time, even an organism who consistently votes
wrong (or votes wrong most of the time) will have a weight adjusted
to take this into account, which in effect will turn his vote around
(the program can ultimately consider his vote as a "don't make this
move").  This approach is probably better than a single organism
because the population will evolve a little more slowly and once it
is trained to a reasonable level will tend not to all of a sudden
play a really goofy game due to a single mutation that sends it off
the map.

Another problem may be that if the game is being played by a variety
of human opponents, the program may adapt to one persons playing
style, and then begin to forget some of that training if subsequently
played by another opponent for awhile, as it begins to adapt to the
new opponent.  There may be steps you can take to avoid this, but
I'm not sure what they are.  One approach would be to keep a record
of past game moves, and recheck the organism's voting records to see
that they're still basically on track.  Problem is, as soon as the
population changes enough to vary a strategy in an old game, you
can't play out the rest of the game (the remainder of the opponents
moves no longer apply) to determine if it is a beneficial or
detrimental modification.

At any rate, good luck.  I expect you'll learn some interesting
things re: genetic algorithms in the process.

Keith