Open Article
SQLite_BotPrize.medium

Winning the 2K Bot Prize with a Long-Term Memory Database using SQLite

Jeremy Cothran on November 19, 2009

Note: This article was written by Jeremy Cothran and Alex Champandard (editor) about Jeremy's winning entry to the 2009 edition of the 2K Bot Prize.

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:

  1. Tracking the locations of kill/death events, also called map hotspots.

  2. 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:

  1. Futile behaviors, such as running in an endless loop without progress towards the goal, or

  2. 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.

Discussion 8 Comments

alexjc on November 19th, 2009

Nice work Jeremy! I spent a long time re-writing/editing parts of this article, but I didn't include any of my own opinions... so I'll write them here instead. [B]1)[/B] Overall I think there are a some innovations here that most games can include without much overhead. For instance, the idea of having a recent filter for goal/target selection based on recent failures. I think that was probably one of the biggest improvements, and it doesn't need a database to pull off! All you need is a small list of hashed goals and a quick traversal of that list when selecting a new goal. [B]2)[/B] I think using a database helped you prototype and identify what additions would help with the behavior, but in the end I'm not sure any of these (runtime) behaviors needed a SQLite database. Things like the visibility lookups can be stored in a simple matrix (see William van der Sterren's work and Killzone 1) or [URL="http://aigamedev.com/insider/coverage/waypoint-cover-maps/"]Killzone 2's cover maps[/URL]. The hotstpot list could also be stored in a simple array with a time and 3D position, then filtered. [B]3)[/B] The performance of the database doesn't seem to be quite up to industrial-strength game AI yet, though I'd be interested in hearing how it'd work with some of the performance improvements you mentioned. Also, technically speaking, there are a few things I'd do differently with the database: [LIST] [*]I'd store dates as SQL datetimes and use the built-in datetime comparison operators rather than casting them to strings and doing a string comparison. [*]You'd be better off having one database per level, rather than having an extra WHERE clause in the SELECT statement. [/LIST] ... and of course storing the database in memory only and not on disk. [B]4)[/B] Now looking at the big picture, the Bot Prize seems like it's caught in a bit of a strange place. It's neither showcasing academic research nor is showing off recent techniques used by game developers... In fact, as I speculated [URL="http://forums.aigamedev.com/showthread.php?t=3435"]here in the forums[/URL], using UT 2004 as the basis for this makes the base technology a bit out-dated. However, as Chris replied, the Bot Prize is doing an amazing job at drawing in people to Game AI. It's also encouraging, and what I draw from this article is that it's a fascinating problem to work on and it's still very much accessible to anyone who has the time to dig into the code! . Again, great work Jeremy, and I'm now very keen to prototype some of these longer-term memory tricks (e.g. goal filtering) -- though I'm not entirely convinced by SQLite yet! Alex

jcothran on November 19th, 2009

Hey Alex, Thanks for the post and all the editing help,guiding questions and feedback to get it in place. Feedback on the opinion points below. 1)Agreed! 2)Yes, I'd agree that the behavior lookups could also be implemented in-game. The demonstration of using SQL and SQLite serves more as a bridge to that ubiquitous persistent storage and query domain than what might be optimized for a specific game or industry case. MMO's use SQL databases to manage player and world information as do GIS(Geographic Information Systems) and the synthesis between massive amounts of more static information accumulated over time with dynamic reactive behaviors and goal planning will involve several staged layers of memory caching using various structures and locality. 3)Tied into point #2, I'd agree to use a faster cache or in-game structure if database query performance is too slow for a given task. I'm mainly advocating database usage as a more easily understood and supported long-term data management medium for longer term decisions or analysis which are not as time-critical. These longer term decisions might be tactical or strategic decisions made by the AI's or similar usage of the gameplay data for gameplay analysis or further research and development purposes. Regarding the datetime representation, one of the strength/weaknesses of sqlite is that there are only five basic datatypes(null,integer,float,string,blob) so while there are datetime functions for parsing datetime strings, there is no datetime specific column type. While string comparisons are slower for both the datetime and map_level columns, the query performance was fast enough for my particular case. A search on 'sqlite optimization' will show many ways to further optimize database structures and query performance. 4)I think UT2004 has been mostly an academic candidate because of the Gamebot API and language closeness between Java (a dominant university taught language) and Unrealscript. There's always going to be a tension between research where ideas need to be openly documented, shared and reproducible and development where things tend to get more closed and proprietary. As the games industry continues to encourage and support open and free academic and independent development with their game development tools, hopefully we'll see academic gameplay or AI development with more recent technology.

jefft on November 21st, 2009

Sounds like really nice work, I read some of the judges' comments from the site as well. I've often thought that bots need the ability to give up on goals which for some reason (unknown the the bot) they cannot succeed at. I am curious however about the general competition. Is this something that is run every year? How difficult is it to write a bot for it? For example, do you have access to the geometry of the level, or waypoints, or are you running around madly raycasting trying to figure out where the walls are? If half your job is essentially a computer vision like way of discovering your surroundings, it almost feels like you should be doing robotics instead. ;)

jefft on November 21st, 2009

[QUOTE=jcothran;34882]Regarding the datetime representation, one of the strength/weaknesses of sqlite is that there are only five basic datatypes(null,integer,float,string,blob) so while there are datetime functions for parsing datetime strings, there is no datetime specific column type. While string comparisons are slower for both the datetime and map_level columns, the query performance was fast enough for my particular case. A search on 'sqlite optimization' will show many ways to further optimize database structures and query performance.[/QUOTE] You could just go old-school and represent dates as integers, say the number of ticks since the match started.

alexjc on November 21st, 2009

Jeff, I agree that the goal filtering is a big part of the winning recipe. I think it was probably the biggest contribution of Jeremy's entry. And it's amazingly simple too! In GameBots, you'd have access to the waypoint-based representation that Unreal provides, but I don't believe you get much more information beyond that except some raytest queries. It'd be hard to build an accurate navigation mesh for example. That said, I do think the Bot Prize is in an odd place; it's not quite robotics level, but not based on what industry is doing either. See my [URL="http://forums.aigamedev.com/showthread.php?t=3435"]other thread[/URL] in the forums here about that. Alex

jefft on November 21st, 2009

[QUOTE=alexjc;34909]I agree that the goal filtering is a big part of the winning recipe. I think it was probably the biggest contribution of Jeremy's entry. And it's amazingly simple too![/QUOTE] Exactly. I think there are two points to consider. The first is whether when you attempt the goal you actually make progress, e.g. you get stuck on geometry, or conflicting priorities, or get ambushed every time you attempt that goal. The second point is whether attempting the goal has a negative outcome, e.g. you spend more ammo trying to pick up the ammo than if you hadn't attempted at all, you get killed every time, etc. After that you can concentrate on how to work with that data. For example, the AI might theorise why the failure occurs (e.g. ambush, transient lack of pathing due to elevator, etc) and make that a precondition or subgoal of the original goal and adjust costs accordingly. Or if no theory or workaround can be found, adjust the probabilities of aiming for certain goals based on the historic odds of success. Another factor to consider is patterns. The order of actions may determine success. For example picking up a powerful weapon may be more successful straight after killing the player. The players habits may determine when certain actions are safe. [QUOTE=alexjc;34909]In GameBots, you'd have access to the waypoint-based representation that Unreal provides, but I don't believe you get much more information beyond that except some raytest queries. It'd be hard to build an accurate navigation mesh for example. That said, I do think the Bot Prize is in an odd place; it's not quite robotics level, but not based on what industry is doing either. See my [URL="http://forums.aigamedev.com/showthread.php?t=3435"]other thread[/URL] in the forums here about that.[/QUOTE] The problem with waypoints as I see it is that you only have info about direct connections between nodes. You don't know what will happen in other areas surrounded by the waypoints. If you have four waypoints in a square formation, all connected together, does this mean the whole square is traversable, or may there be small obstacles within the area? There is fundamentally nothing to stop the competition organisers from generating and providing a navmesh as an optional extra to bots. Okay, sure, it would be information from outside the protocol, but so what? Still an even playing field. Just stick the navmeshes for all levels in a directory the bots can access, named the same as the levels. And it will (largely) prevent one of the major bot flaws of bumping into stuff and getting stuck.

jcothran on November 23rd, 2009

Thanks for the additional comments and ideas. I've been moving in the same direction in regards to ignoring the Gamebot functionality in regards to waypoints and engine-dependent pathing and just modeling the geometry aspects independently outside of the UT2004 engine as the older engine does not seemed designed to support automated navmeshes efficiently. I think in general it would be interesting if game engines supported a common rudimentary game API in regards to character and event representation or dynamic changes in map geometry as effecting the initial mesh. That would allow a level of independence between academic or commercially developed AI controllers and the final application be it game engine/asset rendering or robotics-based. In regards to the contest-specific Turing test goal of having AI's that can pass for human, the two developments that I'd like to demonstrate or see more evidence of are: 1)the ability to better datamine,model and mirror player behaviors - AI's being able to dynamically learn and adapt from experience - there are countless hours of human player data/intelligence running on multiplayer servers now that are essentially untapped by analysis that AI's could learn from - maybe the same AI analysis could help inform actual players of strengths or weaknesses in their existing multiplayer game or simulate their usual human teammates based on their past behavior? 2)as mentioned above with the independent navmesh and pathing approach, the ability to better separate,reproduce and recombine common components of AI such as perception, pathing and goals/planning - in a game or application independent context Jeremy

jefft on November 23rd, 2009

[QUOTE=jcothran;34936]1)the ability to better datamine,model and mirror player behaviors - AI's being able to dynamically learn and adapt from experience - there are countless hours of human player data/intelligence running on multiplayer servers now that are essentially untapped by analysis that AI's could learn from - maybe the same AI analysis could help inform actual players of strengths or weaknesses in their existing multiplayer game or simulate their usual human teammates based on their past behavior?[/QUOTE] The question is how to best mine this data. The problem with the competition (I gather) is that your bot is running on an unknown map, so you can't mine any data for players playing that map except for the judge and the confederate players. I mean perhaps there are some general things you can glean, but I think the map determines play style a lot. Some maps are close combat, some are sniping, and the critical areas of each map vary.

If you'd like to add a comment or question on this page, simply log-in to the site. You can create an account from the sign-up page if necessary... It takes less than a minute!