Title page for ETD etd-12072004-074439

Document Type Master's Dissertation
Author Franken, Cornelis J
Email nfranken@cs.up.ac.za
URN etd-12072004-074439
Document Title PSO-based coevolutionary Game Learning
Degree MSc (Computer Science)
Department Computer Science
Advisor Name Title
Prof A P Engelbrecht Committee Chair
  • games
  • machine learning
  • neural networks
  • particle swarm optimisation
  • Iterated prisoner’s dilemma
  • evolutionary computation
  • coevolution
  • Checkers
  • computational intelligence
Date 2004-05-08
Availability unrestricted
Games have been investigated as computationally complex problems since the inception of

artificial intelligence in the 1950’s. Originally, search-based techniques were applied to create

a competent (and sometimes even expert) game player. The search-based techniques, such

as game trees, made use of human-defined knowledge to evaluate the current game state and

recommend the best move to make next. Recent research has shown that neural networks

can be evolved as game state evaluators, thereby removing the human intelligence factor completely.

This study builds on the initial research that made use of evolutionary programming

to evolve neural networks in the game learning domain. Particle Swarm Optimisation (PSO)

is applied inside a coevolutionary training environment to evolve the weights of the neural

network. The training technique is applied to both the zero sum and non-zero sum game domains,

with specific application to Tic-Tac-Toe, Checkers and the Iterated Prisoners Dilemma

(IPD). The influence of the various PSO parameters on playing performance are experimentally

examined, and the overall performance of three different neighbourhood information sharing

structures compared. A new coevolutionary scoring scheme and particle dispersement operator

are defined, inspired by Formula One Grand Prix racing. Finally, the PSO is applied in three

novel ways to evolve strategies for the IPD – the first application of its kind in the PSO field.

The PSO-based coevolutionary learning technique described and examined in this study shows

promise in evolving intelligent evaluators for the aforementioned games, and further study will

be conducted to analyse its scalability to larger search spaces and games of varying complexity.

  Filename       Size       Approximate Download Time (Hours:Minutes:Seconds) 
 28.8 Modem   56K Modem   ISDN (64 Kb)   ISDN (128 Kb)   Higher-speed Access 
  00dissertation.pdf 2.79 Mb 00:12:55 00:06:39 00:05:49 00:02:54 00:00:14

Browse All Available ETDs by ( Author | Department )

If you have more questions or technical problems, please Contact UPeTD.