AI DIY – Managing State Spaces

Note: The solution to the tutorial is found in the above video.  If you want to try your hand at this first, then we would advise watching the video later.

Introduction

In the first tutorial, you spent some time looking at existing games (or creating simple games of your own) and understanding how the properties of the world can impact upon any AI decision making.  In this tutorial, we want to discuss the challenge of modelling states: a concise snapshot of the world at a given point in time.

States are useful for us to understand the work succinctly.  If we can model the world as a state, we can write systems that will enumerate all possible states that can happen in the world.  Provided these systems are in place, we can then search through the sea of all potential states.  This is the crux of how AI works, given we can search from an initial state, to a defined goal state and devise plans of action.

AI 101 - Chapter 6 If this is all new to you, I would advise checking out AI 101 – Part 6, which starts looking at the principles of state management and search.

So let’s begin, working on a couple of exercises designed to make you think about state modelling.

River Crossing Puzzles

You may have stumbled upon these brain teasers as a child, given they were designed to keep you thinking as early as the 9th century (Pressman and Singmaster, 1989).  One of the oldest and most recognised of these is the three object problem: where each constraints dictate how we can move objects from one location to another.  There are a number of cosmetic variations of this problem, but my favourite is the ‘Chicken, Fox & Grain’.

A farmer finds himself stuck on one side of a river.   He needs to get himself, along with a chicken, a fox and a sack of grain to the other side.

While he has a rowboat, it’s not very large and can only carry him and one other item at any given time.  As a result, he will need to make multiple trips to get everything across.

However, he cannot leave the fox and the chicken alone unsupervised.  Otherwise, the fox will eat the chicken.  Similarly, if the chicken and the grain are left together, the chicken will eat the grain.

How does the farmer get everything across safely?

Image by Ian Li.

Solving The Problem (The AI Way)

For this exercise, your task is to explore the state space that would emerge from this problem.  Bear in mind that states often give consideration to locations and objects used in the problem.  Furthermore, the actions of the problem space link states together by transforming the current configuration of values into a different one. Some key questions to consider are as follows:

  • What information is important?
    • In this case, it is the three items we wish to carry and where they are relative to the river.
  • What actions are permitted?
    • Bear in mind that there are constraints, meaning you cannot commit certain actions. For example, the boat cannot cross the river without the farmer being in it.
  • What states are terminal?
    • Which states would result in failing to solve the problem?  What states are valid and would result in you completing the task?

Once you have an idea of how the state should be modelled, draw all potential states that can exist for this problem.  It is best if you start with the initial configuration based on the problem description, then expand out across each state by linking states based upon actions that you can take.  You will note that sometimes this causes loops in your diagram, since you can make an action that reverses the previous one.  A simple example of the search space, not including actions that revert us back to prior states, is shown below.

A (restricted) enumeration of the state-space for the chicken-fox-grain problem. Immediately identifying terminal states.

Finally, once you have enumerated all potential states (and there is a fair number of them), you can then find a solution, by selecting the states and actions that will get you from the initial state to the goal.

A discussion of the solution can be found in the accompanying video. However, please refrain from watching this segment until you have completed this task.

Discussion

There are a number of issues that can emerge when enumerating this state space down to where a solution can be found.   We summarise some of the key issues when trying to enumerate our state space:

  • Backtracking and Loops: When you model all the actions that can be occurred at a given state, one of the most obvious issues is that it can result in a transition back to a state you have already visited. This could prove an issue for a search algorithm (notably depth-first search), given that the state space now contains loops (or rather, the search tree is now becoming a graph).
  • Number of Solutions: There are at least two optimal solutions at the same depth of the search tree.  If you consider the state-space diagram above, we must take the chicken first, but two different paths can emerge afterwards by taking either the fox or the grain next.  There are potentially an infinite number of solutions to the problem, provided that you inject redundant actions that delay the final state arising.
  • State Space Is Surprisingly Large But Relatively Small: While the solution can be found only a few layers down, the overall size of the state space is larger than that, given the ability to effectively undo good work you have already achieved.  However, the state space is still finite and relatively small compared to other problem spaces, even something as simple as Tic-Tac-Toe.

An Added Challenge

For those of you who find the ‘Chicken and Fox’ problem too easy, try looking at a more difficult river crossing challenge, such as the ‘Missionaries & Cannibals’ problem:

Three missionaries and three cannibals must cross a river to the other side.  A boat is available, but can only carry two people at any given time.  There are two further constraints: firstly, the boat cannot cross the river by itself with nobody on board. Secondly, should at any point in time of there be more cannibals than missionaries present , the cannibals will eat the missionaries

References

Pressman, Ian; David Singmaster (June 1989). “The Jealous Husbands” and “The Missionaries and Cannibals”. The Mathematical Gazette (The Mathematical Association) 73 (464): 73–81.

Enjoying AI and Games? Please support us 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.