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