This week in Occupy Math, we proudly announce a book published by Dr. Eun-Youn Kim, On the Design of Game-Playing Agents. This book gathers, summarizes, and extends work on how much the way you choose to represent software agents in your code changes their behavior. This is a research project that has lasted a decade and is still going strong. The original publication suggested there are problems with thousands of published papers (they did not control for the factor “how were the agents coded?”) and, in the intervening decade, Dr. Kim, Occupy Math, and a dozen collaborators have drilled deeper into this discovery, finding many more factors that need control. Frankly, while this is high-impact work, its also a wonderful illustration of the way mathematicians end up cleaning up after other researchers and putting their work on a firmer foundation. To be clear — this is a huge clean-up and it addresses some serious problems.
Occupy Math will set some context by explaining the big story that Dr. Kim’s work covers. The original discovery was that experiments that were modeling cooperation completely changed their outcome when we changed the type of code learning to cooperate. One encoding, called a finite state machine, learned to cooperate quickly. Another, called an artificial neural net, almost never cooperated. A large number of published papers did not consider the choice of agent encoding at all — they just picked an encoding. Initial reaction to the work was somewhat extreme — denial and some attempts to ignore the work. After that the good researchers took Dr. Kim’s result on board and the smart ones noticed that it meant they got to publish their work again in a new, improved form. In the rest of the post, an interview with Dr. Kim and a few thoughts on the impact of the work.
Dr. Kim, can you tell us why you wrote this book?
It is of particular importance to note that evolutionary algorithms do not just optimize for high scores. The use of evolution also imposes secondary implicit fitness criteria related to the ability of a strategy to survive the reproduction process. In our first research about the subjects of this book, we found that different representations both encoded somewhat different sets of strategies and imposed different patterns of inheritance on evolving populations so there was the potential for behavior of the system to depend on representation. This was the starting motivation that led us to write the book.
We found there were a number of other issues that also arise as examples of insufficient control. These include the amount of computational or informational resources granted to the agents as well as some fairly basic details of the training algorithms themselves. These details appear in a series of published articles, so we decided to draw together and organize what we figured out through our research and experiments. This is intended to help readers address questions about their design of simulations and analysis of resulting behaviors of their evolved game agents. A major goal of the book is to help researchers choose a proper design for their research.
In addition to reporting the pitfalls in agent-based modeling technology, we wanted to introduce the process of designing a representation for agents to be used in a simulation as well as examine the issue of the simulated environment in which the agents are trained. This means that the book can help readers have confident ideas about their own modeling, simulations, and results.
What sort of people would benefit from reading your book?
The first sort of person that can benefit is computer scientists or students who are simulating evolutionary game agents. In this book we present numerous experiments with setting experimental parameters in detail so that they can follow or replicate our experiments and then go on to obtain their own results. The book gives a context to learn what each experiment discovers and how they can set experimental and algorithmic parameters or choose simulation variables including representations, resources, and other environment changes for their own research.
Mathematicians or students who are interested in game theory and math are the second group that can benefit from the book. We introduced and developed mathematical methods to analyze game-playing agents’ behaviors such as fingerprints, non-local adaptation, use of the diffusion character matrix, and several others. Actually, mathematical ideas are needed everywhere and even more in dealing with big data sets. However, it is not common enough for mathematicians to get involved in other fields — including evolutionary computation and evolutionary game theory research. We will be pleased if this book can help our mathematical colleagues get ideas about how to apply their strong mathematical knowledge in the real world.
The third group is a catch-all: anyone who is interested in evolutionary game-playing behaviors. Agent-based simulation is used in ecology, economics, psychology, sociology, and other fields. Even more than computer scientists, these groups find algorithms and the encoding of algorithms somewhat opaque. The book is a collection of critical warning labels for researchers in these areas that use agent-based models.
Does this book tell a complete story about designing game-playing agents, or is there more work to be done?
No, the story has more chapters. The book reports serious flaws in the methodology used to train game-playing agents with evolution and tries to alert researchers to how important the design of game-playing agent simulations is, and the degree to which details of design affect outcomes. This is not a finished work on how to design agent-based game-playing agents; we are simply not there yet. Rather, it is a progress report to the research community with two goals. The authors hope to help others avoid traps that they have detected (or fallen into) and they also hope to encourage others to join us in the enterprise of refining the technique of agent-based modeling to make them more useful and reliable.
Evolution, when implemented as an algorithm, is a type of discrete dynamical system. A term that sometimes appears in the popular press is “non-linear dynamical system”. The standard example of such a system is the weather. The famous butterfly effect shows how hard such systems are to control and understand. The agent-training algorithms studied in the book have the same sort of predictability as weather. This means they are capable of a remarkable degree of discovery — many new strategies for games have been identified in this research. It also means that careful design is critical to having confidence in your results. If you used these techniques, we invite you to participate in the effort to learn to use these systems effectively.
While we examine a few other games briefly, most of the work was done on Prisoner’s Dilemma. The other games were examined to make sure the effects we discovered were not uniquely things that happened in Prisoner’s Dilemma. Chapter 4 of the book is entitled “Does all of this happen outside of Prisoner’s Dilemma?”, but there is plenty of opportunity to extend the work to other games.
What are you working on now?
The next step is trying to devise an agent-training protocol. The first purpose of this is to come up with a common core of things that should be reported such as the details of the agent representation, the experimental parameters, and a clear description of (and possibly a standardization of) core analytic methods. Chapter 6, “Describing and Designing Representations”, makes a start on this and analytical tools invented during the research are scattered throughout the book.
The long-term goal of the research is being able to train humaniform agents or more complex game agents — in other words, agents that plausibly model human behavior. Predictive modeling of human behavior has incredible potential, but this book demonstrates that the road is much longer than most researchers had hoped.
Thank you for answering Occupy Math’s Questions!
Dr. Kim’s book is available from Morgan and Claypool publishers. Here is a direct link to the book. It is available as an e-book or dead-tree edition. Morgan and Claypool sell their books in large blocks (as e-books with unlimited use) to universities and other institutions. This means that if you assign Dr. Kims book — and your institution has subscribed to Morgan and Claypool’s synthesis series — then there is unlimited use of the e-book without an additional charge for your students and institutional colleagues. Occupy Math is the series editor, in part to support this strategy for reducing textbook prices to students. Particularly for our colleagues and brothers and sisters in the non-rich world, controlling the price of textbooks is a critical issue.
Occupy Math is very happy to see this book published. The first paper — joint work with Dr. Kim and Dr. Nichole Leahy — piled up four rejections of the approximate form “Dear God, you must be wrong, spurious objections!” before we placed it in the Transactions on Systems, Man, and Cybernetics. This paper is of a type we call a bomb-throwing anarchy paper. It suggests that there may be serious problems with a large number of other published papers. Having run into replicability issues that arise from lacking details of the agent representations in published papers, Occupy Math thinks this work may be part of the explanation for the replicability crisis in some research domains. In any case the book summarizes a dozen papers that work toward reliable, replicable results with evolved game-playing agents.
Occupy Math hopes you have enjoyed this brief summary of the saga of Dr. Kim’s book. If you have a book that might fit in the computational intelligence in games area, please drop Occupy Math a note at firstname.lastname@example.org. If you think cheaper textbooks might be a good idea (or not?), please comment or tweet!
I hope to see you here again,
University of Guelph,
Department of Mathematics and Statistics