home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / ai / 4381 < prev    next >
Encoding:
Internet Message Format  |  1992-11-23  |  3.7 KB
  1. Xref: sparky comp.ai:4381 rec.games.programmer:4802
  2. Newsgroups: comp.ai,comp.ai.genetic,rec.games.programmer
  3. Path: sparky!uunet!elroy.jpl.nasa.gov!swrinde!zaphod.mps.ohio-state.edu!cis.ohio-state.edu!neuron.cis.ohio-state.edu!pja
  4. From: pja@neuron.cis.ohio-state.edu (Peter J Angeline)
  5. Subject: Re: Games and genetic algorithms
  6. In-Reply-To: PAULSON3@Applelink.apple.com's message of Sat, 21 Nov 1992 00: 51:52 GMT
  7. Message-ID: <PJA.92Nov23154818@neuron.cis.ohio-state.edu>
  8. Followup-To: comp.ai,comp.ai.genetic,rec.games.programmer
  9. Originator: pja@neuron.cis.ohio-state.edu
  10. Sender: news@cis.ohio-state.edu (NETnews        )
  11. Reply-To: pja@cis.ohio-state.edu
  12. Organization: Ohio State Computer Science
  13. References: <1992Nov11.001553.12600@samba.oit.unc.edu>
  14.     <1992Nov11.131739.19137@athena.mit.edu>
  15.     <1992Nov16.175215.29411@versyss.com>
  16.     <1992Nov18.210045.19530@Princeton.EDU>
  17.     <PAULSON3-201192153909@kip2-11.apple.com>
  18. Date: Mon, 23 Nov 1992 20:48:18 GMT
  19. Lines: 56
  20.  
  21.  
  22. Finding good (let alone optimal) gaming strategies with GAs is pretty darn
  23. hard. The problem being how do you test the proposed strategy without biasing
  24. its play.  You can't really test every possible situation so you need to set up
  25. a situation where reasonable generalization can happen.  Good generalization is
  26. hard for most problems, includeing any non-trival game, as those who read about
  27. PAC learning results will atest. Its basically you playing "Guess which
  28. strategy I'm thinking" with the computer. So most of the time you have to be
  29. happy finding a reasonable strategy in an interesting way.  I have looked at
  30. these problems in the context of learning overall and especially GAs in my
  31. paper "Learning in a Competetive Population" submitted to IJCAI-93.
  32. Instructions for getting this paper are below.
  33.  
  34. One interesting approach to finding gaming strategies with GAs, other than
  35. using classifier systems, is to pattern after Hillis' 2 population GA where one
  36. population evolves strategies and the other evolves counter strategies.
  37. Actually, Hillis was learning sorting networks, but the ideas the same.  So one
  38. population plays everyone in the other and the strategies increase their
  39. abilities only through self-competition. My paper looks at why this won't
  40. always work and describes a system which evolves modular computer programs to
  41. play Tic Tac Toe using a variant method which is better for theoretical
  42. reasons. Turns out that learning with GA using a predesigned "expert" isn't as
  43. good as having the population train itself, at least in the task I'm doing.
  44. This of course assumes each member of the population is judged on a small
  45. sample of the possible games against the "expert" or each other.  Se the paper
  46. for details.
  47.  
  48. "Learning with a Competetive Population" is available via anonymous ftp by do
  49. the following: 
  50.  
  51.     unix> ftp nervous.cis.ohio-state.edu
  52.     Name: anonymous
  53.     Password: <your user id>
  54.     ftp> cd pub/papers
  55.     ftp> get 92-pa-compete.ps.Z
  56.     ftp> quit
  57.     unix> uncompress 92-pa-compete.ps.Z
  58.  
  59. This creates a postscript file called 92-pa-compete.ps which can be printed on
  60. any postscript printer.   If you have a problem mail tooo me and I'll try to
  61. help. 
  62.  
  63. -pete angeline
  64.  
  65. -------------------------------------------------------------------------------
  66. Peter J. Angeline            ! Laboratory for AI Research (LAIR)
  67. Graduate Research Assistant  ! THE Ohio State University, Columbus, Ohio 43210
  68. ARPA: pja@cis.ohio-state.edu ! "Nature is more ingenious than we are."
  69.  
  70.  
  71.  
  72. -- 
  73. -------------------------------------------------------------------------------
  74. Peter J. Angeline            ! Laboratory for AI Research (LAIR)
  75. Graduate Research Assistant  ! THE Ohio State University, Columbus, Ohio 43210
  76. ARPA: pja@cis.ohio-state.edu ! "Nature is more ingenious than we are."
  77.