Copy the page URI to the clipboard
Flynn, Colin James (2009). Cross-Validation of Fitness Scores During Co-evolution Using the 'Trap-the-Cap' Board Game as a Testbed. Student dissertation for The Open University module M801 MSc in Software Development Research Dissertation.
DOI: https://doi.org/10.21954/ou.ro.000160ac
Abstract
Games have always been used as a convenient way of testing AI techniques, they have well defined rules and well defined outcomes. The reinforcement learning method of co-evolution is investigated using the board game of Trap-the-Cap. Co-evolution is used when no teacher is available for game playing 'agents' to learn from. Essentially, two populations of agents take it in turns to rank each other before mutating and hence evolving. The populations start out as completely naïve Trapthe- Cap players and gradually increase in sophistication over the ensuing generations. A criticism of co-evolution is that each population of agents is used for training and testing the other population. This is normally to be avoided, but this is not easy for co-evolution which was selected because no teacher was available to provide training. This thesis investigates the technique of injecting independent test agents into the coevolution cycle to provide 'Cross-Validation' of the ranking of a population. It asks the question 'does the use of Cross-Validation provide measurable benefits in terms of speed of evolution, network complexity and performance?' Neural networks were used as the agents in the two populations. The particular technique used to evolve and mutate them is called Neuro-Evolution of Augmenting Topologies (NEAT) which is a method that allows neural networks to use the cross-over operation as well as mutation. Cross-Validation was achieved by providing a source of independently evolved neural networks as an additional source of testers during the co-evolution cycle. Results were encouraging and showed that there was indeed an advantage gained in terms of performance, speed of evolution and network complexity. However, these effects were only present for the first one hundred or so generations, after which the advantage disappeared. This may have been related to the game of Trap-the-Cap itself and the parameters used to evolve players.