Complexity Theory is the study of complex systems such as flocking birds, chaos theory and other complex phenomena in the universe. In this paper, Professor Wareham and Watson, apply complexity analysis on game-playing agents.
Todd Wareham and Scott Watson
Automatic generation of game content is an important challenge in computer game design. Such generation requires efficient methods for automatically evaluating the playability of generated game content. Research to date has focused on the evaluation of levels within games. However, the increasing importance of gameplay involving complex non-player agents (for example, agents capable of exchanging items and facts with each other and human players) suggests that methods for automatically evaluating the playability of groups of such agents should also be investigated. In this paper, we propose an augmented finite-state machine model for agents with item and fact exchange capabilities and use computational complexity analysis to explore under what restrictions efficient playability evaluation of groups of such agents is and is not possible.
To understand this paper probably, I had first to get an overview of what complexity theory is, and this video was beneficial. The game that the paper analyzes is a social game of trading facts and items. Facts are defined as objects that can be owned by multiple game agents in the world, e.g., scientists at NASA knows that the earth is round. Items are objects that can be owned by one agent at a time.
The game is modeled using an Augmented Finite State Machine (AFSM). A transition between agent M and X is defined as follows: (Q1, ax, Ix, Fx, Q2, am, Im, Fm). So, if an agent M is in state Q1, and an agent X takes action ax while having an item set Ix and a fact set Fx, then M will go to state Q2 and responds with an action am, as well as giving fact set Fm and item set Am.
The primary result of the paper is that using the above mentioned model, doing an Agent Playability Evaluation (APE) is NP-hard. In other words, APE cannot be done in polynomial time. Even if it was between two agents only. Later in the paper, it is clarified that it is possible to do APE if certain constraints are applied.
In general, the paper included a research area that is entirely new to me, and I may have not fully understood its subjects. Yet, I am impressed by the formalization of the problem and the broad applicability of complexity theory.
The paper can be accessed at: http://www.cs.mun.ca/~harold/Courses/Old/CS690B.W16/Diary/CCAI15submit.pdf