AI 101 – Part 6: Start Searching!

Previously we introduced a terms used as part of knowledge representation. These allow us to understand more about the types of problems we are trying to solve. Now in this chapter, we will start looking at how we try to solve problems, by establishing the principles of search and the idea of a search space.

The State of Things

Towards the end of Part 5, we asked you to think about a particular game you like to play and namely:

What are the important pieces of information that define what I am doing in each frame of the game?

This is a fairly critical thing to manage, given there are often a number of key things we need to think about in the world.  Let’s work through a couple of examples to give you an idea of how this works in practice.

Assassin’s Creed

If we were to use a modern example, such as Assassin’s Creed, what am I interested in as I navigate the world?  There are a number of fundamental things that are crucial to the gameplay:

  • Where am I in the world?
  • What characters are nearby?
    • Are there any enemy guards?
    • Are any assisting NPCs visible? Such as mercenaries or courtesans.
  • What is my current threat level?
  • What weapons am I carrying?
  • What is my current objective?
  • Are there any side objectives that might be worth exploring?

This is a rather extreme example, given that Assassin’s Creed is an expansive and rich game world to explore.  As a result, we are often trying to manage what we wish to achieve in the game at any given time.  This can range from acquiring resources in order to upgrade our equipment, to attaining collectables, completing side-missions or working through the main storyline of the game.  We can typically go about achieving any of these points by looking at the current state of the game and then making a decision based upon what we wish to achieve.

Super Mario Bros.

Let’s consider a simpler example: the original Super Mario Bros. on the Nintendo Entertainment System.  In Mario Bros., we focus on moving from the left of the screen to the right.  The level expands the further right we progress.  Our goal is to reach the flag pole which is at the far right of the level.

If I were to consider a simple (i.e. flat) area of land, with no power ups and no enemies we would only consider the following:

  • Mario’s location – as a two-dimensional vector (i.e. (x,y))

After all, the goal is to reach the end location.  So we can determine that by ensuring Mario reaches the appropriate location.  In the case of traditional Mario Bros., this would be driven by the x value, since reaching the flagpole at the end denotes we have travelled a certain distance across the map.  It is in the players interest to score more points by reaching the top of the flag (i.e. attain a certain value) but it does not impact whether Mario completes the level or not.

We can then say that at any given point in the game, we only model the location of Mario.  This would be the state of the world for an AI system.  For a simple Mario, we only model his location, though as our Mario becomes more complex, we could look to build richer data in our state model so we can make other decisions.

Understanding Transitions

 With a simple state model in place, we need to understand how states transition.  It is important to realise that states move from one to another because an agent executed an action.  This is of course assuming that the problem is deterministic as discussed in Part 5 (i.e.. we know that committing an action will always create a particular outcome).

State transitions allow us to understand how the world works.  If we press right on the gamepad, Mario will walk to the right a certain number of units on the axis  If we press left, Mario walks left along the x-axis.  If we jump, Mario will move up or down the y-axis based upon where he is in the jump phase.  We achieve these this my understanding that underneath these relationships lies a state transition system.

As shown in the diagram, if we have a given state s and we execute a particular action a, we expect a specific successor state – s’ – to occur. By creating this system, we can understand a deterministic environment.  This is often referred to as a state space: a world of all potential states and their interconnectivity which is caused by actions.

The Ability to Search

Given our ability to model a state and the notion of a transition system that tells me what future states I can reach based upon actions, I can now contemplate the notion of searching for particular states in the world.  This is the principle of how many ‘classic’ AI systems work, typically relying on two particular states:

  • The Initial State: the  starting point of our search.  This is typically where we are right now, given I am interested in figuring out how to proceed from this point.
  • The Goal State: the goal can be either be one particular state, or a set of potential states that satisfy a given constraint.

Returning to my Mario example, if I am sitting at the start location my initial state may be somewhere where both the x and y co-ordinate are very small.  Given I am usually in the bottom right corner of the screen (e.g. [5,2]).  Meanwhile my goal is any state that is where the x value is the location of the flagpole.  The value does needs to be somewhere in the range of the flagpoles height.

If I were to assume that the x value of the flagpole is 2000 and the flag can be 150 units high (starting at y coordinate 10) then all states of [200, 10 <= y <= 160] are valid goal states of the search.

Given time, we could explore all the possible states that Mario can reach and plot a path of actions that gets us from that initial state, all the way to the goal state.

Searching in Part 7

In Part 7, we will start looking at the types of search algorithm we can write that will traverse the state transition system.  To get us started, we will look at uninformed search, which does not  make any intelligent decisions as it navigates.  However, it is crucial to understand how these systems work before we look at more intelligent methods of state space traversal.

Enjoying AI and Games? Please support me on Patreon!
Tommy Thompson Written by:

Tommy is the writer and producer of AI and Games. He's a senior lecturer in computer science and researcher in artificial intelligence with applications in video games. He's also an indie video game developer with Table Flip Games. Because y'know... fella's gotta keep himself busy.