Parallel evolution of game evaluation functions in ada

ABSTRACT

This is an Ada experience report, where we conclude that Ada tasking and distributed processing facilities make it a good research tool for experimentation with algorithms that might eventually need multiple processors. We implemented a genetic algorithm in Ada to create effective computer players for Connect4. Key to our success was employing Ada tasking and ALRM Annex E Distributed computing to harness a symmetric multiproces-sor and a distributed machine with very few code changes. Easy extension of an original single-task code to multi-tasking and distributed variants-even though extension was not planned in advance-was essential to timely completion. Using either the parallel or distributed implementation, about 150 processor hours were sufficient to evolve players that neither the GNU "Four-in-a-Row" Expert player nor the author could defeat. This algorithm relies on human expertise to restrict the genetic search space. Work is in progress on a new algorithm with near-zero encoded knowledge, which will run on 220 distributed nodes within the same distributed computing framework.

REFERENCES

• 1: Fogel, David B. New Results on Evolving Strategies in Chess. Applications and Science of Neural, Fuzzy Systems, and Evolutionary Computation VI 5200 (2003): 56--63.
• 2: Wikipedia contributors, "Connect Four," Wikipedia, The Free Encyclopedia, http://en.wikipedia.org/w/index.php?title=Connect_Four&oldid=131063397 (accessed May 19, 2007).
• 3: Wikipedia contributors, "Connect Four," Wikipedia, The Free Encyclopedia, http://en.wikipedia.org/w/index.php?title=Connect_Four&oldid=131063397 (accessed May 8, 2007).
• 4: Stuart J. Russell , Peter Norvig, Artificial intelligence: a modern approach, Prentice-Hall, Inc., Upper Saddle River, NJ, 1995
• 5: Allis, Victor. A Knowledge-Based Approach to Connect Four. Masters Thesis, Vrije University, Amsterdam, Netherlands, 1988.
• 6: Stuart J. Russell , Peter Norvig, Artificial intelligence: a modern approach, Prentice-Hall, Inc., Upper Saddle River, NJ, 1995
• 7: Author Unknown, "Four-in-a-Row," http://live.gnome.org/Four-in-a-row (accessed May 17, 2007).
• 8: Krischik, Martin, Welcome to Annex E for GNAT, http://gnat-glade.sourceforge.net/pmwiki.php/Main/HomePage.
• 9: Wrigley, Adrian, "Re: Help with Glade (Annex E) on Windows", USENET comp.lang.ada, Jan 29, 2007, 11:29:46 GMT.
• 10: Wikipedia contributors, "Parallel Virtual Machine," Wikipedia, The Free Encyclopedia, http://en.wikipedia.org/wiki/Parallel_Virtual_Machine, (accessed May 8, 2007).

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Concurrent programming structures

General Terms:
Algorithms, Design, Experimentation, Languages, Performance