At the forefront of Artificial Intelligence

What was Columbus' mother's maiden name? – Memory in Games

By Bruno Sousa

Introduction

After seeing Half-Life brilliant AI, I started brainstorming in my little dark room about its AI system. The advanced logic behind the grunts, the primitive but effective alien intelligence, all. It blowned me away completely. After thinking a lot I came to the conclusion that one of AI models was simulating memory. Each entity having different memory status, would create a logistic and adaptable system for the species. The cooperation of members of the same specie can also result of the use of memory, exchanging information between each others so they can create some evading/offensive plan. It was great, probably one of the best AI system I have seen, and since I’m not the only one that also thinks the same way, I decided to write about it in this tutorial.

And for the ones that don’t know me (I bet each and everyone of you) my name is Bruno Sousa, also known as Akura in the internet. You can probably find me in Afternet #gamedev, so if you want a quick chat just drop in. I currently work for Staggan Ltd. as a programmer (what else?) but my long time objective is to take over the world.

As said before, memory can make your players go though: “hey, he kind knows what is happening” to “WOAH, how the hell did he do that ?”, and believe it or not, it’s a really easy programming process. It’s well worth it.

I’ll use the pseudocode during the course of this tutorial so the principle behind it can be applied to any language. If you feel uncomfortable with any of the pseudocode here supplied don’t hesitate on mailing me with your doubts.

Our fist attempt at memory – Tic Tac Toe

Tic Tac Toe (TTT) is a relatively simple game to develop and with some serious hardcore logic it can be programmed to never lose, but instead of covering each move combination or pattern (and have about 20 page of code), we could use an algorithm that would use memory of previous game so it wouldn’t make the same mistakes over and over again (and use about 20 lines of code).

The memory in TTT is one of the easiest to simulate. Let’s analyse TTT briefly before memory in TTT. TTT is played in a 3x3 matrix (Figure 1.0) and there is a winner when someone can make three equal symbols in a row (Figure 2.0). A simple model of a playfield can be:

BYTE Board [3][3];

Figure 1 Figure 2

And each player has a number:

define PLAYER1 1
define PLAYER2 2

Simple as that, now the main logic of the game is up to you. For the memory part we will use a structure recording every movement, something like this:

TTTRecord
{
  BYTE Moves[9]
  BOOLEAN Forced[9]
  BYTE Winner
}

This will be our record for each game, each move the player or computer makes will be stored here, if it’s a forced move (this is, blocking a win, or even making a win) the boolean is set to true. The Winner will be set in the end of the game. Using this approach and saving each game, the TTT AI go to its memory and check for combination games that resemble the current one.

BYTE CheckMove ()
{
  while (Not end of memory)
  {
    load memory record
    check to see if the pattern/combination is the same as current board
    if not 
      return random value
    if so
    {
      check forced move
      prevent forcing move making a move different from record
    }
  }
}

And if the given game (in memory) is being played, then the AI will get a different random move. Playing against TTT various times will make it impossible to beat.

Advanced memory – First Person Shooter

I had already had this idea to implement memory for a while now in a FPS. Advanced games like Unreal Tournament and/or Half-Life probably use a much better approach and advanced then this one to achieve, but I believe they derive from a small model similar to this one.

Lets imagine a deathmatch game ala Quake. We have a map, a player and many bots (single player deathmatch). Lets also imagine that the map resembles Map 1.0 that is divided in 4 sectors, now each bot has an array of a structure similar to the following.

FPSRoomRecord
{
  STRING Name
  BYTE Kills
  BYTE Enemies
  BYTE Ammo
  BYTE Energy
  BYTE Damage
  BYTE Time
  BYTE Items
  BYTE Health
} For MAX_NUMBER_OF_ROOMS

Map 1.0

And each time the bot enter the section it will start logging the information and when he leaves the room saves the record. Now each time a bot need ammo (or anything else) he will search his memory bank, ponder the options (number of ammo vs. damage inflicted vs. health, there can be various combinations here, its up to you to decide the behaviour of the bot) and search for the room chosen.

Since human memory isn’t 100% certain, all info without lapses of forgetting would make the computer a ‘cheater’, a good solution to this problem is to sometimes don’t memorise the info completely correctly and/or forget some record once in a while. Other suggestion can also be player position and/or direction, same for team mates, etc. Also bots (same team) could exchange information between them. There are various interesting options using this kind of model.

From where now

With the memory model explained here you can create any kind of memory needed for games, like in real time strategy games, this model can be used to find bases, record resources and best attack spots, etc.

This model can even be used in racing games. I’m currently designing an AI model for a racings game using memory (a little different and more advanced but based on this system) to make the adversaries more real.

Bottom line is, if you have imagination and know how to program, memory can do wonders for your game.

Conclusion

That’s it, as always I wait for the last day to do my things and the result is a tutorial with no complete source code example, so, as soon as I can I’ll post a link to a couple examples using this model.

Any correction, suggestion, rant, please forward to bruno@staggan.co.uk.

Download Word Format (55Kb)

Submitted: 31/05/2000

Article Toolbar

BibTeX entry