Learning to play Pac-Man: An evolutionary, rule-based approach

Pac-Man is a well-known, real-time computer game that provides an interesting platform for research. We describe an initial approach to developing an artificial agent that replaces the human to play a simplified version of Pac-Man. The agent is specified as a simple finite state machine and ruleset. with parameters that control the probability of movement by the agent given the constraints of the maze at some instant of time. In contrast to previous approaches, the agent represents a dynamic strategy for playing Pac-Man, rather than a pre-programmed maze-solving method. The agent adaptively "learns" through the application of population-based incremental learning (PBIL) to adjust the agents' parameters. Experimental results are presented that give insight into some of the complexities of the game, as well as highlighting the limitations and difficulties of the representation of the agent.

A framework and tool support for the systematic testing of model-based specifications

Formal specifications can precisely and unambiguously define the required behavior of a software system or component. However, formal specifications are complex artifacts that need to be verified to ensure that they are consistent, complete, and validated against the requirements. Specification testing or animation tools exist to assist with this by allowing the specifier to interpret or execute the specification. However, currently little is known about how to do this effectively. This article presents a framework and tool support for the systematic testing of formal, model-based specifications. Several important generic properties that should be satisfied by model-based specifications are first identified. Following the idea of mutation analysis, we then use variants or mutants of the specification to check that these properties are satisfied. The framework also allows the specifier to test application-specific properties. All properties are tested for a range of states that are defined by the tester in the form of a testgraph, which is a directed graph that partially models the states and transitions of the specification being tested. Tool support is provided for the generation of the mutants, for automatically traversing the testgraph and executing the test cases, and for reporting any errors. The framework is demonstrated on a small specification and its application to three larger specifications is discussed. Experience indicates that the framework can be used effectively to test small to medium-sized specifications and that it can reveal a significant number of problems in these specifications.

Theoretical frameworks for analysing turn-based computer strategy games

This paper argues for a more specific formal methodology for the textual analysis of individual game genres. In doing so, it advances a set of formal analytical tools and a theoretical framework for the analysis of turn-based computer strategy games. The analytical tools extend the useful work of Steven Poole, who suggests a Peircian semiotic approach to the study of games as formal systems. The theoretical framework draws upon postmodern cultural theory to analyse and explain the representation of space and the organisation of knowledge in these games. The methodology and theoretical framework is supported by a textual analysis of Civilization II, a significant and influential turn-based computer strategy game. Finally, this paper suggests possibilities for future extensions of this work.

Viewpoint-based testing of concurrent components

The use of multiple partial viewpoints is recommended for specification. We believe they also can be useful for devising strategies for testing. In this paper, we use Object-Z to formally specify concurrent Java components from viewpoints based on the separation of application and synchronisation concerns inherent in Java monitors. We then use the Test-Template Framework on the Object-Z viewpoints to devise a strategy for testing the components. When combining the test templates for the different viewpoints we focus on the observable behaviour of the application to systematically derive a practical testing strategy. The Producer-Consumer and Readers-Writers problems are considered as case studies.

A case study in specification and implementation testing

Achieving consistency between a specification and its implementation is an important part of software development In previous work, we have presented a method and tool support for testing a formal specification using animation and then verifying an implementation of that specification. The method is based on a testgraph, which provides a partial model of the application under test. The testgraph is used in combination with an animator to generate test sequences for testing the formal specification. The same testgraph is used during testing to execute those same sequences on the implementation and to ensure that the implementation conforms to the specification. So far, the method and its tool support have been applied to software components that can be accessed through an application programmer interface (API). In this paper, we use an industrially-based case study to discuss the problems associated with applying the method to a software system with a graphical user interface (GUI). In particular, the lack of a standardised interface, as well as controllability and observability problems, make it difficult to automate the testing of the implementation. The method can still be applied, but the amount of testing that can be carried on the implementation is limited by the manual effort involved.

Testing java interrupts and timed waits

Testing concurrent software is difficult due to problems with inherent nondeterminism. In previous work, we have presented a method and tool support for the testing of concurrent Java components. In this paper, we extend that work by presenting and discussing techniques for testing Java thread interrupts and timed waits. Testing thread interrupts is important because every Java component that calls wait must have code dealing with these interrupts. For a component that uses interrupts and timed waits to provide its basic functionality, the ability to test these features is clearly even more important. We discuss the application of the techniques and tool support to one such component, which is a nontrivial implementation of the readers-writers problem.

Engaging game characters: Informing design with player perspectives

The behavior of characters in current computer games is generally scripted and predictable. This paper discusses some issues related to creating game characters that enhance player engagement and identifies the need for a more player-centered approach to game character design. This paper reports the results of a focus group that was carried out with experienced game players to determine what game character behaviors would enhance their engagement in a game. The four general areas of concern that came out of this discussion were consistency with context, player expectations, social interactions and consistency with the environment. This paper discusses these issues and their implication for game character design with a view to creating engaging game characters. © Springer

It's all in the game: Teaching software process concepts

A major challenge in teaching software engineering to undergraduates is that most students have limited industry experience, so the problems addressed are unknown and hence unappreciated. Issues of scope prevent a realistic software engineering experience, and students often graduate with a simplistic view of software engineering’s challenges. Problems and Programmers (PnP) is a competitive, physical card game that simulates the software engineering process from requirements specification to product delivery. Deliverables are abstracted, allowing a focus on process issues and for lessons to be learned in a relatively short time. The rules are easy to understand and the game’s physical nature allows for face-to-face interaction between players. The game’s developers have described PnP in previous publications, but this paper reports the game’s use within a larger educational scheme. Students learn and play PnP, and then are required to create a software requirements specification based on the game. Finally, students reflect on the game’s strengths and weaknesses and their experiences in an individual essay. The paper discusses this approach, students’ experiences and overall outcomes, and offers an independent, critical look at the game, its use, and potential improvements.

Combining influence maps and cellular automata for reactive game agents

Agents make up an important part of game worlds, ranging from the characters and monsters that live in the world to the armies that the player controls. Despite their importance, agents in current games rarely display an awareness of their environment or react appropriately, which severely detracts from the believability of the game. Some games have included agents with a basic awareness of other agents, but they are still unaware of important game events or environmental conditions. This paper presents an agent design we have developed, which combines cellular automata for environmental modeling with influence maps for agent decision-making. The agents were implemented into a 3D game environment we have developed, the EmerGEnT system, and tuned through three experiments. The result is simple, flexible game agents that are able to respond to natural phenomena (e.g. rain or fire), while pursuing a goal.