scribble

Influence Game and Multi Column Swiss Tournament

Individual players in a sport team behave according to their own 5 senses. Through them, they acquire information about their surroundings and play accordingly. There is no central hive mind that micromanages their movements. Regardless, patterns and strategies emerge from those player's actions. We take this observation of human intelligence for granted, but there is something fascinating when the same phenomenon can be observed from a few lines of computer code. Even more so when the computer learns the strategies without human guidance.

These pages are my personal research project on artificial neural networks (ANNs), evolutionary algorithms and self-organizing systems which I worked on during the summer and fall of 2012. I have been interested in ANNs ever since I saw Etaanaru's video on AI pathfinding back in 2009 but only recently got motivated to carry out my own project after reading Fehérvári and Elmenreich's "Evolving Neural Network Controllers for a Team of Self-Organizing Robots"1. I've decided to use a similar approach for training, involving the use of Swiss tournaments for evaluating the relative performance of ANNs efficiently and evolutionary algorithms.

My project is based around a simple game called "Influence Game", in which different "teams" are represented and controlled by an ANN to compete in a tournament. The best performing teams (elites) are selected and a new generation is derived by using a variety of evolutionary methods. The particular methods uses MacLeod's "An Introduction to Practical Neural Networks and Genetic Algorithms For Engineers and Scientists"2 as guidance. I then measure the increase or decrease in performance of teams across generations and observe strategies they adopt.

This particular project focuses on the tournament system - a crucial component as it is responsible for differentiating the best "teams" of each generation. To increase the learning capability of teams, I develop an approach which I call "multi column Swiss tournament" and demonstrate its advantages over a traditional Swiss tournament.

Note that beyond this introduction, I will adopt the use of we for formalism. However, this project report is still intended to be easy for an educated public, so I'm playing around with styles a little here. Finally, for those who are curious, the program I use is written from scratch, using C++ for artificial neural network simulation, C# for rendering teams playing Influence Game and encoding it into a video, Scheme/Racket for analyzing data points and plotting graphs.

  1. ‎Case description
    1. Rules of the Influence Game
    2. ANN controller structure
    3. Input/Output interface
  2. Fitness evaluation and evolution
    1. Single column Swiss tournament (SCST)
    2. Evolutionary algorithms
    3. Issues with the methodology
    4. Multi column Swiss tournament (MCST)
    5. Observations and discussion
  3. Observations and discussion
    1. Sample MCST case study
    2. Analysis of MCST
    3. Conclusion
    4. Further studies
  4. Bibliography

I hope you will enjoy reading about this project!