An Optimal Fox AI Using State Machines

I’ve really enjoyed thinking about the puzzles at http://gurmeet.net/puzzles/, especially looking for ways to solve them or get hints as to how to solve them using visualization without knowing the answers. Last Time I explored puzzle 11, Treasure Island, and this time I’ll look at puzzle 5, Fox in a Hole.

The Puzzle

Here is the wording from http://gurmeet.net/puzzles/:

Consider five holes in a line. One of them is occupied by a fox. Each night,
the fox moves to a neighboring hole, either to the left or to the right. Each
morning, you get to inspect a hole of your choice. What strategy would ensure
that the fox is eventually caught?

The Challenge

The question I asked was, can we, without knowledge of a working strategy, create a fox that plays optimally against us so we can be sure we’ve come up with a strategy that will work? We could simulate a fox that chooses to move left or right randomly, but we would never be sure that our strategy is fool proof. Can we make sure our fox plays hard to get if we don’t even know how to catch it? Turns out we can. Try out the demo of my solution and see if you can both figure out how to catch the fox and understand why a strategy works. Implementation details are below the demo. Code is at https://gist.github.com/azundo/5941503.

Instructions

Click on a hole to select it for inspection. You win if the fox has nowhere
left to hide. If you give up, click the button and one possible path the fox
could have taken to avoid your inspections will be shown.

A Quantum Fox

Instead of modeling our fox as being in one concrete location, we’ll keep track of all possible holes the fox could be in at any given time without getting caught, depending on which holes we have inspected in the past. We’ll use a finite-state machine to keep track of which holes the fox could be in. If we ever get to the state where the fox couldn’t be in any holes without being caught, we know our strategy is a good one. We don’t require any knowledge of the best path for the fox to choose, or a winning strategy.

Our State Space

Each state in our state space will consist of all of the possible holes the fox could be in at any one time. There are 5 holes and each hole has two states: it is either possible for the fox to be in that hole, or not possible. This gives us a state space of size 2^5 = 32. We could model this as a bit vector with 5 bits, but for clarity I will use a simple array. If it is possible for the fox to be in hole i, then our state array will contain i. We’ll number our holes 0, 1, 2, 3, 4.

For example, before we check any holes, our state would be [0, 1, 2, 3, 4]. The fox could be in any hole. If we check hole 2, then our state would move to [0, 1, 3, 4]. In the case where there is no possible hole for our fox to be in without catching him at some point, our state is an empty array [].

State Transitions

The key implementation detail when using a state machine is our state transitions. How do we decide which state we move to next? In our case our next state is dependent on two things, our previous state (the set of possible holes the fox could have been in yesterday) and our selection of which hole to check.

To start let’s forget about the action of checking a hole. How can we determine what holes the fox can be in based on what holes it could have been in yesterday? If it was possible for the fox to be in hole i yesterday, then it is possible for the fox to be in any hole beside i today. If we iterate over all of the holes that the fox could have been in yesterday then we’ll get the set of holes it could be in today.

We’ll use a very simple adjacency list to make our lives easy. If we access element i of the adjacency list we will get back an array containing all of the holes next to i.

var ADJACENCY_LIST = [
    // hole 0 is next to hole 1
    [1],
    // hole 1 is next to hole 0 and hole 2
    [0, 2],
    // etc.
    [1, 3],
    [2, 4],
    [3]
];

This adjacency list defines a very simple graph where each hole is a node connected by edges to each of its adjacent holes. The first and last holes only have one adjacent hole (and thus one edge) while the others have two.

Accessing element 0 of our ADJACENCY_LIST tells us which holes are next to hole 0. If we want to know the set of possible future holes, we take the set of possible past holes and add all of the adjacent holes. Simple enough.

Lastly we don’t include the hole that we chose to inspect since the fox would get caught if he ended up there. Hence, our transition function looks like this:

  function nextState(pastState, guess) {
    /*
     * Calculates our next state based on the past state and
     * the next hole to be inspected.
     */
    var next = [], i, j, possiblePastHole, possibleNextHoles, possibleNextHole;
    for (i = 0; i < pastState.length; i++) {
      // any value in our pastState represents a hole that
      // the fox was possibly in yesterday
      possiblePastHole = pastState[i];

      // look up holes next to the possiblePastHole in our ADJACENCY_LIST
      possibleNextHoles = ADJACENCY_LIST[possiblePastHole];
      for (j = 0; j < possibleNextHoles.length; j++) {
        // any holes that are ajacent to a possible hole
        // from the pastState are valid holes for the fox in
        // the next state, provided that hole wasn't
        // inspected.  Note that the fox cannot stay in the
        // same hole, it has to move to an adjacent hole.
        possibleNextHole = possibleNextHoles[j]
        // don't add holes that are already in the next
        // state array since our state is the set of
        // possible holes
        if (possibleNextHole !== guess && next.indexOf(possibleNextHole) === -1) {
          next.push(possibleNextHole);
        }
      }
    }
    return next;
  }

If we ever end up with an empty state, the fox has nowhere to go. We must have caught it at some point, no matter where it started and how it decided to move.

Every time we select a hole to inspect, we’ll update our state and push a copy of it onto an array to keep track of what states we’ve been through in the past. We’ll use that later.

  function selectHole(selection) {
      // update state information
      state = nextState(state, selection);
      stateHistory.push(state.slice());
      // if there are no possible holes for the fox to be in, we caught him!
      if (state.length === 0) {
        foxCaught(selection);
      } else {
        advanceOneDay(selection);
      }
  }

Reconstructing the Fox’s Moves

If we save each state we reach, we can reconstruct a possible path the fox could have taken to get to the current state. Let’s choose any arbitrary hole from the current state, and work backwards by looking for adjacent holes in the previous state. We are guaranteed to find a backwards path since every hole in our current state must be possible. Here is the code:

  function getPossibleSequence() {
    // only depends on stateHistory, an array of our past states
    var i, finalState, stateToDetermine, possibleHoles, possibleHole, seq = [];
    if (stateHistory.length === 0) {
      return seq;
    }
    finalState = stateHistory.pop();
    // pick whatever hole happens to be listed first in the
    // final state to end our sequence.
    seq.unshift(finalState[0]);
    // work backwards through the state history, picking a
    // valid state from each entry and unshifting it onto
    // the front of the sequence
    while (stateHistory.length > 0) {
      stateToDetermine = stateHistory.pop();
      // find a hole beside the hole at the front of our
      // sequence since our 'graph' is not directed, we can
      // safely use the same adjacency values to move
      // backwards through the state list
      possibleHoles = ADJACENCY_LIST[seq[0]];
      for (i = 0; i < possibleHoles.length; i++) {
        possibleHole = possibleHoles[i];
        // if the possible hole is in our stateToDetermine, use it.
        if (stateToDetermine.indexOf(possibleHole) !== -1){
          seq.unshift(possibleHole);
          break;
        }
      }
    }
    return seq;
  }

Demo and Further Steps

Throwing this together with some d3.js drawing and we get the demo from above. The full code is in a gist at https://gist.github.com/azundo/5941503 and viewable on bl.ocks.org at http://bl.ocks.org/azundo/5941503.

You could also make solving the puzzle a bit easier if you showed all possible holes the fox could be in as you go along, instead of only showing one possible path at the end. Feel free to fork and implement this as a good exercise in d3 basics.

Now can you catch the fox?

Attributions

Fox designed by Sebastian Blei from The Noun Project

Azundo Design

Musings and Makings