Most AI systems in the games industry focus on short-term reactive memory and combat behaviors applying techniques such as behavior trees. However, there seems to be little support for long-term memory, for example remembering locations in space that mark events that occurred. In our daily lives, we internally map, model and remember our surroundings and experiences. This begs the question, how can we similarly organize and leverage longer-term memory within modern AI?
This article looks into the concepts and implementation that went into creating the winning Bot Prize entry this year. In particular, it shows how a SQL database was used for long term memories of hotspots which were analyzed to improve the AI. It also discusses the performance and benefits of such an approach and possible future improvements.
Screenshot 1: The BotPrize winning entry in Unreal Tournament 2004.
Long-Term Memory using SQLite
One experimental approach towards providing long-term memory for AI is to use a relational database (RDB). The database would be responsible for managing lists of information recently acquired within a set of tables. In particular, an ideal candidate implementation is SQLite: a lightweight, portable, file-based relational database which can help in this regard.
SQLite provides persistent file-based records in an easily query-able format which can be accessed via a Structured Query Language (SQL). One important benefit of this approach is that it provides a shared data model for either the game representation (e.g. map, waypoints, etc.) or arbitrary events (consisting of type, location of combat, outcomes). Maintaining such data enables both in-game or offline analysis using a variety of techniques/tools such as R — an increasingly popular statistical language.
(Note: Such techniques are already gaining popularity for gameplay analysis and data-mining, for example Valve's so-called Death Maps in Team Fortress 2.)
Runtime Database Usage & the Bot Prize
For the 2009 Bot Prize contest, the winning entry was my sqlitebot (see video, powerpoint, code) which utilized a sqlite database. The RDB was used for two things:
Tracking the locations of kill/death events, also called map hotspots.
Storing the cross-visibility of waypoints for use in evasive behavior.
The bot started from the example 'advanced' bot from the Pogamut website with a circle-strafing function added from the previous year's winning AMIS bot (both documented and credited within the code). Pogamut is a collection of Java based projects primarily providing a Java NetBeans developer/debug interface and Java object API to control Unreal Tournament 2004 bots. Pogamut uses the Gamebot message API as an intermediary between itself and the game. Screenshot 2 shows the IDE with sample bot state/log messages in the lower right corner and controls for sending game commands such as gameplay speed, changing maps or adding bots in the upper left.
During development of the bot, I noticed that the previous years winners had some memory processes in regards to weapon selection and effectiveness, but not in regards to map events. The example bot included a 'pursue' function, but this only tracked the last known enemy location. An easy initial long-term behavior to add would be knowledge of the map level hotspots: areas where the bot had scored a kill or been killed.
Screenshot 2: Pogamut IDE. (Click to enlarge.)
Hotspot Behavior
To enable a long-term memory of recently active locations, whenever the bot kills another player or is killed by another player, a row is inserted to the observations table with the location of the event, a timestamp, and a weight set to 1.0. When the bot is respawned or looking for a destination, it randomly picks from the most recent n recentRow locations that have been created in the past t recentTime seconds. In practice, n is set to 3 recent rows which are queried from within the past 45 seconds.
In terms of performance, reading and writing to the database are currently millisecond operations — and these insertions and selections should scale to table sizes in the millions of records. This is acceptable for performance since the decision is used for strategic/tactical pathfinding decisions, and any lag in the write or read would not effect more immediately noticeable combat reactive decisions.
Database tables and search indexes are created once initially before the game begins. The database can be file saved and copied for reuse among other games in its initial unpopulated state or a later populated state. In this experiment, while the database is only accessed by a single agent, the database could be concurrently accessed by several agents across multiple games.
The rows added to the tables are timestamped with real-world time and game time for reference. Here's how the table is specified:
CREATE TABLE observations ( row_id integer PRIMARY KEY, row_entry_date TEXT, map_level TEXT, navpoint_id INT, unreal_id TEXT, event_location TEXT, event_time REAL, event_weight REAL);
When the bot is later looking for a target destination the following table query is issued:
String statement = "SELECT * FROM observations
WHERE row_entry_date > strftime('%Y-%m-%d %H:%M:%S','now','-2 minute')
AND event_time > "+gameTime-recentTime+"
AND event_weight = 1
AND map_level = '"+map_level+"'
ORDER BY row_entry_date DESC LIMIT "+recentRows+";";
Here's the query's result representing the most recent 3 locations of a map kill/death:
1333|2009-08-15 15:54:41|DM-Test1|1|DM-Test1.PathNode16|5663.6,-1403.66,-86.15|290.35|1.0 1332|2009-08-15 15:54:29|DM-Test1|0|DM-Test1.InventorySpot5|6739.6,-344.48,-86.15|277.33|1.0 1331|2009-08-15 15:54:16|DM-Test1|1|DM-Test1.PathNode16|6503.56,-1667.54,-86.15|262.97|1.0
One of these rows is randomly chosen as the hotspot, and the bot heads towards that location.
Screenshot 3: Areas around weapons and items quickly become hotspots for the bot.
Evasive Behavior
Another human-like behavioral feature that's noticeably absent in most bots is retreating or evading an enemy after combat initially begins. In the case of sqlitebot, this happens when the health reaches a minimum target threshold (less than half).
Diagram 3 demonstrates how an evasive behavior works; the bot's target destination navpoint is selected outside of the enemy's current visibility set. The from/to navpoint visibility table was populated in an initial pre-game bot map survey step that logs all this information and stores it for runtime use.
Diagram 4: Green locations are navpoints not in player to_navpoint_id visible set, and red locations are from_navpoint_id closest to player.
The table that stores this visibility lookup table is the following:
CREATE TABLE navpoint ( row_id integer PRIMARY KEY, row_entry_date text, map_level text, from_navpoint_id int, to_navpoint_id int, visibility int);
A unique index is also added to prevent possible duplication of the same rows during the initial map survey process:
CREATE UNIQUE INDEX i_navpoint on navpoint (map_level,from_navpoint_id,to_navpoint_id);
When the bot has low health and is looking to evade, the AI selects visible navpoints from this table based on the nearest enemy navpoint, which should obviously not be pathed to:
String statement = "SELECT to_navpoint_id FROM navpoint
WHERE map_level = '"+map_level+"'
AND from_navpoint_id = "+memory.getKnownNavPoints().get(hideFromNav).ID+";";
ResultSet rs = stat.executeQuery(statement);
ArrayList<Integer> ArrayToGet = new ArrayList<Integer> ();
while (rs.next()) {
ArrayToGet.add(rs.getInt(1));
}
The code then selects a random hidden navigation point as the destination, assuming it's not in the player visible arrayset that was determined using the previous query.
boolean hideNavFound = false;
int thisNavpoint = 0;
if (!ArrayToGet.isEmpty()) {
while (!hideNavFound) {
int myRandHide = random.nextInt(memory.getKnownNavPoints().size());
thisNavpoint = memory.getKnownNavPoints().get(myRandHide).ID;
if (ArrayToGet.contains(thisNavpoint)) {
log.info("Navpoint is visible:"+memory.getKnownNavPoints().get(myRandHide).UnrealID.toString());
}
else {
log.info("navpoint not visible:"+memory.getKnownNavPoints().get(myRandHide).UnrealID.toString());
hideNavFound = true;
}
}
}
Screenshot 5: Unreal 2004 is still used by academia as the primary research platform for FPS AI.
Other Additions
In addition to the hotspot and evasive behaviors, further tweaks were made to the original bot's AI based on the following observations. The two most obvious giveaways that an agent is a bot are:
Futile behaviors, such as running in an endless loop without progress towards the goal, or
Predictable behaviors, for example repeatedly jumping, dodging or employing the same move or tactic.
I added a simple associative array which instructed the bot to ignore a goal (e.g. weapon, health, pickup) for a period of time if it was unable to currently path to or complete that goal. To achieve this, I used a hash reference between a goal and a failed attempt time. The goal associative array allowed the bot to temporarily dismiss goals which might produce futile behaviors.
Furthermore, to avoid predictable behaviors, some random fuzziness was added to the bots most common combat reactive decisions, for instance using simple random choices between acceptable alternatives such as ignore, dodge or jump direction on an incoming projectile.
Finally, the bots reaction times to incoming projectiles and weapon switching was also slowed by around 200 milliseconds (implemented as simple delay loop) to give a more human reaction time appearance.
Screenshot 6: UT 2004 features a collection of both indoor and outdoor levels, though vehicles were not part of the Bot Prize.
Further Work
It would be useful to have a common database schema abstraction of such game data for analysis by multiple tools or agents. For instance for a map representations, the following waypoint attributes and associations would be useful to have for many 3D environments:
Waypoint positions and their connectivity with each other,
The initial association between waypoints with tactical attributes such as cover or open area, and
The changing association over time with gameplay events and shifting tactics in the game.
As for performance, a faster intermediate caching layer for the data could avoid the slower latencies handling database connection via a socket, or supporting disk I/O. If multiple parallel agents are using the same database resource, then there can be concurrency latencies related to read state or write access. Performance for reading and writing from the database also depends on the number of rows in the table, so effective search indexes are important for scaling up to millions of records or larger.
SQLite also has the option of running the database in-memory and not to disk, which would most likely offer performance benefits. Spatialite is a 'spatially enabled' sqlite database including common geometry datatypes and related indexes/functions which may offer some further ease of implementation and performance gains.
Finally, it would be interesting to explore how multiple agents might synthesize and share their combined knowledge via such database information, over the course of several games. Further, these ideas could be applied to squads to help with strategic reasoning also.
Conclusions
Many human-like behaviors such as evasion or a "volley"-type dynamic between players in combat are particularly suited to competitive multiplayer games. The ability to model, cache, analyze and recall individual events strategies across multiple games opens up opportunities opportunities for stronger and richer AI to develop in a more open-ended competitive environment.
