Coevolving a computer player for resource allocation games : using the game of Tempo as a test space.

Decision-making in resource allocation can be a complex and daunting task. Often there exist circumstances where there is no clear optimal path to choose, and instead the decision maker must predict future need and allocate accordingly. The application of resource allocation can be seen in many organizations, from military, to high end commercial and political, and even individuals living their daily life. We define resource allocation as follows: the allocation of owner’s assets to further the particular cause of the owner. We propose two ways that computers can assist with the task of resource allocation. Firstly they can provide decision support mechanisms, with alternate strategies for the allocations that might not have been previously considered. Secondly, they can provide training mechanisms to challenge human decision makers in learning better resource allocation strategies. In this research we focus on the latter, and provide the following general hypothesis: Coevolutionary algorithms are an effective mechanism for the creation of a computer player for strategic decision-making games. To address this hypothesis, we present a system that uses coevolution to learn new strategies for the resource allocation game of TEMPO. The game of TEMPO provides a perfect test bed for this research, as it abstracts real-world military resource allocation, and was developed for training Department of Defence personnel. The environment created allows players to practice their strategic decision-making skills, providing an opportunity to analyse and improve their technique. To be truly effective in this task, the computer player the human plays against must be continuously challenging, so the human can steadily improve. In our research the computer player is represented as a fuzzy logic rule base, which allows us investigation into the strategies being created. This provides insight into the ways the coevolution addresses strategic decision-making. Importantly, TEMPO also gives us an abstraction of another component of strategic decision-making that is not directly available in other games – that of intelligence (INTEL) and counter intelligence (CI). When resource allocation is occurring in a competitive circumstance, it is often beneficial to gain insight into what your opponent is doing through intelligence. In turn, an opponent may seek to halt or skew the information being gained. The use of INTEL and CI in TEMPO allows research into the effects this has on the resource allocation process and the coevolved computer player. The development of a computer player for the game of TEMPO gives us endless possibilities of research. In this research, we have focused on the creation a computer player that can provide a fun and challenging environment for humans learning resource allocation strategies. We investigate the addition of memory to a coevolutionary algorithm for strategy creation. This includes mechanisms to select memory individuals for evaluation of coevolutionary individuals. We describe a successful strategy of selection, based on the way a human’s short and long term memory works. We then investigate the use of INTEL and CI in the game of TEMPO, and the way it is used by the coevolved computer players. Through this work, we present a new version of the TEMPO game that more realistically represents INTEL and CI. Finally, we describe a process that uses coevolution to adapt to a human player real-time, to create a tailored game-play experience. This process was tested in a user study, and showed a distinct advantage through the adaptive mechanism. Overall, we have made some important discoveries, and described some limitations that leave future research open. Ultimately, we have shown that our hypothesis is an achievable goal, with an exciting future.Thesis (Ph.D.) - University of Adelaide, School of Computer Science, 200