%0 Thesis %1 decaux:2001:masters %A De Caux, Robert %D 2001 %K Coevolution, Pareto algorithms, genetic gpsys, ipd, java, programming, scoring, strongly typed %T Using Genetic Programming to Evolve Strategies for the Iterated Prisoner's Dilemma %U http://www.cs.ucl.ac.uk/staff/W.Langdon/ftp/papers/decaux.masters.pdf %X The technique of Genetic Programming (GP) uses Darwinian principles of natural selection to evolve simple programs with the aim of finding better or fitter solutions to a problem. Based on the technique of Genetic Algorithms (GA), a population of potential solutions stored in tree form are evaluated against a fitness function. The fittest ones are then modified by a genetic operation, and used to form the next generation. This process is repeated until certain criteria have been met. This could be an ultimate solution, or a certain number of generations having been evolved. Genetic Programming is a fast developing field with potential uses in medicine, finance and artificial intelligence. This project attempts to use the technique to evolve strategies for the game of Prisoner's Dilemma. Although a simple game, the range of possible strategies when the game is iterated is vast, but what makes it particularly interesting is the absence of an ultimate strategy and the possibility of mutual benefit by cooperation. A system was created to allow strategies to be evolved by either playing against fixed opponents or against each other (coevolution). The strategies are stored as trees, with GP used to form the next generation. The main advantage of GP over GA is that the trees do not need to be of a fixed size, so strategies can be developed which use the entire game history as opposed to just the last few moves. This implementation has advantages over previous investigations, as information about which go is being played can be used, thus allowing cleverer strategies. Work has also been conducted into a hunting phase, where strategies roam a two dimensional grid to find a suitable opponent. By studying the history of potential opponents and using GA, evidence emerged of an increase in cooperative behaviour as strategies sought out suitable opponents, demonstrating parallels with biological models of population dynamics. The system has been developed to allow a user to alter important parameters, select the evolution method and seed the population with pre-defined strategies by means of a graphical user interface.

@mastersthesis{decaux:2001:masters, abstract = {The technique of Genetic Programming (GP) uses Darwinian principles of natural selection to evolve simple programs with the aim of finding better or fitter solutions to a problem. Based on the technique of Genetic Algorithms (GA), a population of potential solutions stored in tree form are evaluated against a fitness function. The fittest ones are then modified by a genetic operation, and used to form the next generation. This process is repeated until certain criteria have been met. This could be an ultimate solution, or a certain number of generations having been evolved. Genetic Programming is a fast developing field with potential uses in medicine, finance and artificial intelligence. This project attempts to use the technique to evolve strategies for the game of Prisoner's Dilemma. Although a simple game, the range of possible strategies when the game is iterated is vast, but what makes it particularly interesting is the absence of an ultimate strategy and the possibility of mutual benefit by cooperation. A system was created to allow strategies to be evolved by either playing against fixed opponents or against each other (coevolution). The strategies are stored as trees, with GP used to form the next generation. The main advantage of GP over GA is that the trees do not need to be of a fixed size, so strategies can be developed which use the entire game history as opposed to just the last few moves. This implementation has advantages over previous investigations, as information about which go is being played can be used, thus allowing cleverer strategies. Work has also been conducted into a hunting phase, where strategies roam a two dimensional grid to find a suitable opponent. By studying the history of potential opponents and using GA, evidence emerged of an increase in cooperative behaviour as strategies sought out suitable opponents, demonstrating parallels with biological models of population dynamics. The system has been developed to allow a user to alter important parameters, select the evolution method and seed the population with pre-defined strategies by means of a graphical user interface.}, added-at = {2008-06-19T17:35:00.000+0200}, author = {{De Caux}, Robert}, biburl = {https://www.bibsonomy.org/bibtex/257ec7bf3e2461a1d553d576e085aac3a/brazovayeye}, interhash = {0a26d5d5351f91ac3ba314bad942d8b1}, intrahash = {57ec7bf3e2461a1d553d576e085aac3a}, keywords = {Coevolution, Pareto algorithms, genetic gpsys, ipd, java, programming, scoring, strongly typed}, month = {September}, notes = {Awarded a distinction. Supervised by Robin Hirsch. Zip archive contains msword document}, school = {University College, London}, size = {97 pages}, timestamp = {2008-06-19T17:38:29.000+0200}, title = {Using Genetic Programming to Evolve Strategies for the Iterated Prisoner's Dilemma}, url = {http://www.cs.ucl.ac.uk/staff/W.Langdon/ftp/papers/decaux.masters.pdf}, year = 2001 }