Testbeds for Artificial intelligence (AI) Research

Introduction

Computer games and simulations have provided effective platforms and test-beds for AI research. They provide cost-effective tools and environments that replicate real-world situations to test and implement new ideas and fix drawbacks. These testbeds can help AI researchers to develop and test intelligent systems. AI techniques can also be used in games to create a more sophisticated behaviour for Non-Player Characters (NPCs), personify inherent NPC behaviour, and improve decision-making processes [18]. This results in games that are more interactive and create an ever-increasing fun experience for players. 

AI research in games started with perfect-information games, including classical board games where players have knowledge of all possible moves. With the advancement of computer processing power and graphics generation, AI research on games moved toward imperfect-information and highly stochastic games including Third-Person Shooter (TPS) and Real-Time Strategy (RTS) categories, where many factors influence the state of the environment and create dynamic and unknown situations similar to real-world situations. Modern computer games provide a better venue for testing many AI research problems including learning, reasoning, pathfinding, and decision making under uncertainty [34] Game-design companies stringently protect their intellectual property, which restricts universal access to any advances achieved. Most companies have been unwilling to release documentation on how to interface with their games [206]. These issues make it consistently difficult for MAS researchers to test or implement their theories in sophisticated games. Meanwhile, older versions of some commercial games have been released as open-source projects under the GNU Public License (GPL) agreement to be used for teaching and researching tools. Some games have been created purely as a test-bed for AI theories. Examples of these testbeds include ORTS [33] and NERO [212]. 

Many of the AI techniques that have been developed and tested using these games can be used in real-world applications. Also, some robotic games and competitions have been formed to encourage researchers from different engineering and computing fields to create sophisticated robots competing against each other in a number of areas. Some of these challenges include Robocup Soccer and Rescue League, which are held every year. 

In the following sections, some examples of these games along with some AI research conducted using them are discussed. Based on the genre of the games discussed, they are categorised into classical, shooter, strategy, and robotic games in the following sections. 

Classical Games 

Much AI research has been conducted on classical board games including Check ers [63, 191, 193], Chess [37, 103], Tic-Tac-Toe [61, 70, 154, 218], Othello [32, 160, 246], Go [162, 185], and Backgammon [177, 219]. 

Early AI research using games were conducted on perfect-information games, where all possible moves can be determined throughout the game. In perfect information games, the state of the game is fully known to players [143]. Only sequential games can be considered perfect-information games. Some examples of these games include the classical board games of Checkers, Chess, and Othello. Imperfect-information games are not fully observable and some elements of the game are hidden to the players [223]. Examples of these games include Poker and Backgammon. Some of the new challenges introduced by these types of games include hidden states, probabilistic knowledge, and multiple opponents. Figure 2.3 displays the board layout and setup of two popular classical board games (Chess and Checkers). In the following sections, some of the research conducted on the classical games Checkers and Chess, and the card game Poker are briefly mentioned. 

(a) Chess (Image source: http://chess.com) (b) Checkers (Image source: http://checkers.ws) 

Figure: Board layouts of two popular classical board games. 

Checkers 

Checkers is the name of a category of board games that share a set of common rules. The most dominant rule is that a player’s pieces can be taken by being jumped over. Figure (b) shows a typical example of a Checkers game where each player is given 12 pieces on the 3 rows closest to their side of an 8 × 8 board. Many computer programs have been developed to play games against human. 

Samuel’s Checkers program is one of the earliest works created to bring machine learning into games [191, 192]. He wrote the first Checkers program in 1952 and added a self-learning mechanism to it in 1954. The program was able to play against itself and improve its skills using a method similar to an early version of RL [215]. This lead to the development of a Checkers program called Chinook that defeated the world champion of the time, Dr Marion Tinsley in 1994. Dr Marion Tinsley is the best Checkers player that ever lived. He won the world championship nine times and lost only seven games over the last 45 years of his life [193] Chinook was developed by a research team led by Jonathan Schaeffer at the University of Alberta [193, 194]. In 2007, Chinook developers proved that the program was invincible and able to consistently beat the best human players [195]. 

Chess 

One of the most popular board games that have drawn significant attention from the AI research community is Chess. It has a higher complexity than the Checkers game as the number of possible moves and situations are much higher. In 1997, a Chess program called Deep Blue developed by the IBM corporate defeated the world champion, Garry Kasparov, in a six-game match by two wins to one with three draws [37, 103]. Some of its features included: a single-chip search engine with multi-level parallelism, a complex evaluation function, and an expert game database. 

Poker 

In a category of card games called poker, multiple players are dealt a limited sample of a much larger population (imperfect-information). Poker players need to “deal with probabilistic knowledge, risk assessment, and possible deception” [17]. Poker is a good test-bed for AI theories when dealing with situations where perfect information is not available to competing agents including economics, online auctions, and negotiating. It is one of the examples where static mathematical models do not give good results and dynamic and adaptive algorithms are required to play successfully [56]. 

A number of Poker computer programs have been developed using AI techniques to play against humans. One of these programs is called Loki, which uses methods for hand evaluation and betting strategies as well as learning techniques to create statistical models of opponents [17]. Although it can challenge human opponents at an intermediate level, more work is required before it will be ready for a championship [143]. 

Shooter Games 

Modern computer games provide a good venue to implement and test many AI techniques where the environment is often large and dynamic. These games con tain many elements and factors that can change the state of the game environment. This can result in the creation of many different, unpredictable situations. These games are considered as imperfect-information games because players play si multaneously and also do not know all actions of all the other players. 

The main categories of modern computer games are commonly considered to be action and shooter games. In such games, multiple players and NPCs are involved in a battle simulation. First-Person Shooter (FPS) and Third-Person Shooter (TPS) are the main subcategories of these kinds of games. Various testbeds and competitive simulation environments have also been developed in the context of a TPS or FPS game. They provide a very useful tool for teaching and investigating AI techniques and cognitive modelling. Examples of such testbeds include Robocode [99], dTank[129], and NERO [212].  Robocode was originally developed by Matthew Nelson in 2001. dTank is developed at the Applied Cognitive Science Lab of the Pennsylvania State University.

Much research has also been conducted on designing NPCs playing against humans in commercial First-Person Shooter (FPS) and Third-Person Shooter (TPS) games, including Quake [23, 127, 167], Unreal Tournament (UT) series [116, 174], Counter Strike [44], and Soldier of Fortune [22, 66, 71]. The following sections discuss some examples of AI research conducted using Quake and UT. 

Quake 

Quake was developed in 1996 by ID Software. The initial releases of the game featured single-player, mission-based scenarios where players followed a storyline and completed tasks in order to win. Later releases started a new type of multiplayer mode of play called ‘DeathMatch’ where players search for weapons and health items to compete against each other to score points. The release of Quake II and Quake III Arena under GPL created an opportunity to use these platforms as a test-bed for AI research. 

A research team at the University of Rochester developed Quagents as an extension for Quake II to be used for research and teaching purposes [23]. It implements the JESS agent platform. JESS stands for Java Expert System Shell, which is a Java-based rule engine and scripting environment developed by Friedman-Hill [68] at the Sandia National Laboratories in Livermore. JESS is a powerful tool for developing systems with intelligent reasoning abilities and creating expert systems. 

The Java API of Quagents provides abstractions including sensors and behaviours that allow developers to focus on an agent’s cognitive design rather than its low-level system or network programming. Brown et al. [24] implemented Quagents to investigate distributed cooperation and coordination of a team of heterogeneous agents with different physical and computational abilities. They researched ‘Joint Intention’ theory [41] to describe shared goals, and used voting and auction mechanisms for role assignment, role swapping, and resource allocation. 

Thurau et al. [224] developed a game agent for Quake II that can learn reactive behaviours and game strategies through imitating the human players. In their research, the Artificial Potential Fields (APF) [5] was used for pathfinding and a learning APF approach was implemented to train the game agent. The APF was initially used as a real-time spatial navigation and obstacle avoidance approach for mobile robots [5]. The training data was acquired by observation of the actions of human players. Thurau et al. applied the Neural Gas Network [149] to find an optimal representation of the game environment by learning a grid-based waypoint map from the observation of movements of a human player. They demonstrated that game agents were able to pick up specific items and navigate certain paths imitating the actions of a human player without any prior knowledge of the terrain structure. They also showed that reactive behaviours could be learned by means of a combination of Self-Organising Map (SOM) [122] and MLP [225] learning paradigms. A research team lead by Laird [136] developed Quakebot, which is another interface to the Quake II game agent. Quakebot is based on the State, Operator And Result (SOAR) architecture. SOAR is a cognitive architecture created by Laird’s research group [130, 231] to develop systems that behave intelligently. It has evolved as AI architecture and also is the basis for the unified theory of cognition. 

Laird et al. [126–128] used Quakebot to simulate various human reasoning characteristics and behaviours. Some outcomes of their research included equipping the Quakebot with the ability to anticipate the opponent’s actions, build its own map as it explores a level, and organises its knowledge and actions using dynamical hierarchical task decomposition. 

Unreal Tournament 

The first release of Unreal Tournament (UT) series games was developed in 1999 by Epic Games, Inc. and its features upgraded as newer versions were released. This game includes a physics engine and features a customisable 3D map with modifiable landmarks, terrains, and environmental factors. For example, by changing the gravity force, environmental effects in space or underwater are simulated [196]. An interesting feature of UT is the ability to modify different aspects of the game including types of weapons, character profile, and modes of play. UT provides several predefined modes of play which include ‘DeathMatch’, ‘Capture the Flag’, and ‘Domination’. In the ‘Capture the Flag’ mode, teams compete to capture the opponent team’s flag and take it to their own base. In the ‘Domination’ mode, teams compete to dominate the majority of control points and retain possession until the end of the game. 

A project called Gamebots was started at the University of Southern California’s Information Sciences Institute to modify the UT game and use it as a test-bed for AI research [3]. Gamebots interface takes the sensory information from the game environment and allows software agents to use that data to control the UT characters. It takes advantage of the UT game engine and its built-in scripting language ‘Unreal-Script’, which has great flexibility for development or customisation [230]. It comes with a wide variety of extendable environments and provides a flexible test-bed for MAS research including learning, spatial navigation, resource allocation, multi-agent planning, and human-machine teamwork [115]. Much research has been conducted using Gamebots. 

Kaminka et al. [116] built a team of Gamebots agents and implemented a mechanism for collaborative goal maintenance in two teamwork architecture of DIESEL, which is a teamwork and task-work architecture built on top of SOAR [116], and BITE, which is behaviour-based, teamwork-architecture for robots. 

Petrakis et al. [174] implemented a feed-forward ANN, trained with backpropagation for weapon selection of agents in UT 2004 using the GameBots libraries. They demonstrated that their method improved the performance of agents significantly. 

The JavaBot project extended the GameBots protocol to provide a higher-level interface and remove the hassle of network programming, message passing and other pragmatic issues. The figure above shows different components of a Java-based agent player in UT. The components coloured blue are the GameBots infrastructure. The JavaBot components are coloured green and the red components indicate what is built on top of JavaBots platform. 

Sioutis [206] used the JavaBot API and JACK Intelligent Agents development platform to investigate reasoning and learning for intelligent agents within the context of UT. He developed an agent that could navigate, teleport and find re sources within the UT environment. 

Strategy Games 

Strategy games initially emerged from the classical strategy board games such as Chess, Go and miniatures WarGames [186], which required thinking and cog nitive skills to play. Computers enabled researchers to embed Subject Matter Expert (SME) knowledge rules and strategy into applications capable of beating humans. 

In modern strategy games, players need to explore the virtual world, create and control units and structures, and compete with other teams for resources, which can include gold, wood, weapons, and food. Victory is achieved through reaching a more powerful state or defeating the other teams by capturing their bases while protecting the home base and mission-critical assets from enemy attacks. A powerful state can also be reached by collecting enough resources and building an unassailable number of units in a given time period. 

The two main subcategories of strategy video games include of Turn-Based Strategy (TBS) and Real-Time Strategy (RTS). Each differs in the way the game is played. In TBS games, players take turns to make their moves, whereas in RTS games there is no need to wait for a turn as everything happens simultaneously in real-time. Some of the research conducted on TBS games includes Battleground [146, 147], Settlers of Catan [175], and Legion [26, 27]. 

RTS games provide a practical venue to test many MAS research problems including “real-time planning and decision making under uncertainty, learning, reasoning, resource management, collaboration, and pathfinding” [34]. Despite the popularity of RTS games, less research has been conducted on these genres of games compared to other genres. One reason for this might be the complexity of their dynamic environment and the large number of components that influence the state of the game simultaneously. Examples of open-source RTS games used as test-beds for AI research include Spring [155], ORTS [33, 40, 137], Wargus [179], and Battle of Survival [178]. 

In the following sections some AI research conducted using the Legion and ORTS games are described briefly. 

Legion 

The 2D TBS game of Legion was developed by Bryant and Miikkulainen at the University of Texas as a test-bed for MAS research [25]. The aim of the game was to train a group of agents acting as ‘legions’ to protect an area of a map from the attack of pre-programmed opponent agents (‘barbarians’). The game consists of a map divided into hexagonal cells as shown in the Figure below. Each game unit can make one atomic move at its turn to move to one of the six adjacent cells. It may also remain stationary. 

(a) The sensor fields. (b) Objects within the game. 

Figure : Snapshot of Legion II, an AI research testbed [25]. 

Bryant and Miikkulainen used these games to investigate different machine learning techniques for training agents. They implemented the backpropagation learning technique with the MLP network and introduced a multi-agent architecture called Adaptive Team of Agents (ATA) [26, 27]. ATA is a group of homogeneous agents that have identical control policies and are able to adapt and switch roles appropriate to their environment to optimise team performance. 

These authors also implemented the Enforced Sub-Populations (ESP) algorithm to optimise and enhance behaviours of an ANN-based agent within these games [26, 28, 29]. The ESP algorithm [74] is an alternative co-evolutionary method and an extension to the Symbiotic Adaptive Neuro-Evolution (SANE) RL method [160, 161]. It was employed for the evolution of connection weights in an MLP network representation of agents within the ATA controller. The authors demonstrated improvement in the overall performance and generation of more believable behaviour in an agent playing these strategy games. 

ORTS 

The game of ORTS stands for Open Real-Time Strategy. This project was started by a research team led by Buro [33] at the University of Alberta in Canada. ORTS is an open-source 3D RTS game engine (developed in C++), which was released under GPL. Users can customise the game and define unit types, structures, and their interactions using a home-brewed scripting language. It is a programming environment developed with the purpose of allowing researchers to investigate AI concepts including pathfinding, reasoning, learning, and real-time planning [34]. 

Most commercial RTS games are based on peer-to-peer technology that basically duplicates the whole game environment on each peer machine and hides only part of the game state from players. Such games are prone to hacking and cheating in online tournaments by unveiling the entire game state. ORTS is a networked multi-player game that uses client/server architecture to send user commands to units in the game and update the players view. Only selected data is sent to players to reveal the game state. Figure below displays a screenshot of the ORTS environment, showing 3D models, terrains and game characters. 

Screenshot of the Open Real-Time Strategy game [34]. 

Lichocki et al. [137] applied the Gene Expression Programming (GEP) [54], as a tool to evolve strategies for teams of cooperating resource-gathering agents within the ORTS game. Hagelback and Johansson [81, 82] used the Multi-Agent Potential Fields to create agents for a resource gathering and tank-battle scenario in ORTS environment. Their agent team won the three ORTS competitions of Collaborative Path Finding, Tank Battle, and Complete RTS in the 2008 ORTS tournament. 

Robotic Games 

Robotic games provide a great opportunity for researchers and students in various fields of computing and engineering to bring their ideas into action and implement AI theories in real-world applications. A number of robotic competitions are conducted annually to achieve great results and accelerate research in the fields of AI and robotics [213]. These competitions include soccer and racing matches. Participants are required to create robots that interact with each other and achieve common goals. These competitions add fun and motivation to encourage researchers in the implementation of advanced AI theories while making increasingly more intelligent robots.

Robotic Racing 

Computer-controlled Car Racing is a robotic racing competition associated with IEEE Congress on Evolutionary Computation (CEC) [143]. It has introduced many technological challenges, including the design of electronic components for remote-controlled cars, image capture and processing, and modelling the physics of a car. The use of a simulated racing application has allowed researchers to spend more time and effort on improving AI behaviour of agents-controlled cars. Tanev et al. [217] designed an agent with evolving behaviour, via GA, to remotely control a toy car running at the fastest possible speed while still avoiding obstacles. Their technique was tested both on a simulator and on a radio-controlled toy car under racing conditions. 

Togelius and Lucas [226] produced a high-performance ANN-controlled agent for simulated car racing. They used MLP networks with the EA as the learning technique and were able to optimise the behaviour of the agent that raced a car around a simulated track. Lucas and Togelius [144] implemented and compared the performance of different machine-learning techniques for controlling simulated racing cars and visiting as many waypoints as possible within defined periods of time. Single and multi-layer perception networks were used with the different learning techniques including ES, Sarsa and Temporal Difference (TD) [214]. The authors demonstrated that EA worked more reliably than RL techniques, and outperformed human players and programmed controllers. On the other hand, those embedded with RL techniques learned faster when they were successful, which is a trait similar to human behaviour. 

RoboCup Soccer 

RoboCup Soccer is an international research project that stems from an education initiative. It provides a suitable environment to hold a series of robotic tournaments involving a group of international participants every year. The long-term goal of RoboCup Soccer challenge is to develop a team of robots that play against and beat the soccer world cup champions in 2050. Researchers from around the world are invited to participate in these challenges and attempt to win the Robotic Soccer World Cup. 

The soccer games are divided into robot leagues of humanoid, four-legged, middle and small-sized and simulation leagues of 2D, 3D, and mixed reality. Figure below shows humanoid robots in the RoboCup Soccer standard platform league. These robotic tournaments provide a challenging and entertaining opportunity to exchange technical information among researchers and add to the body of knowledge in various computer, robotic and AI fields. 

RoboCup Soccer, standard platform league robots 

Since the tasks of developing and debugging the electronics and mechanics of robots are both time consuming and costly, soccer simulation environments have been created to allow researchers to focus on the development of AI aspects of soccer-playing agents. Examples of the use of these simulated environments include JavaSoccer and SoccerBots. 

JavaSoccer is a RoboCup Soccer league emulator for the small-sized robot. Balch [8] developed JavaSoccer to facilitate research in the RoboCup Soccer domain. Using JavaSoccer, Oudeyer and Koning [170] modelled soccer-playing agents’ strategies and behaviours through Conversation Policies [207]. They implemented an approach called Protocol Operational Semantics (POS), which allows for the description of conversation policies imposing a number of constraints over agents’ behaviour. 

SoccerBots is a Java-based soccer simulation package of the TeamBots software developed at the Carnegie Mellon University. Leng et al. [133] used Soccer Bots as a viable test-bed to investigate individual and cooperative learning abilities of goal-based, soccer-playing agents through the adoption of Reinforcement Learning (RL) algorithms. 

Conclusion

Computer games and simulations have contributed much to the research and development of AI techniques in a variety of applications. These tools have provided testing environments for the implementation and testing of AI theories and the creation of intelligent systems. AI research using games began with classical board games, which are perfect-information games where all possible moves are fully known to players. As computing technology progressed, research moved toward imperfect information and highly stochastic games with hidden states. In such games, many factors influence the state of the environment and create dynamic and unknown situations, which simulate real-world situations to a large extent.

References and Credits

Checkout the Bibliography and Acronyms pages for details of the references, and acronyms.

Photo by Tamara Gak on Unsplash