Calculating probabilities in a random maze walk with cycles

Question

I'm working on this programming challenge where a Frog takes a random walk through a maze, with various obstacles and bombs along the way to potential exits.

The challenge is to calculate the probability of the frog reaching an exit.

My issue is that I don't know what to do with cycles - cases where the frog can walk back and forth between two or more spaces.

Imagine you have:

     BOMB    BOMB
EXIT SPACE 1 SPACE 2 BOMB
     BOMB    BOMB

For Space 1, the probability of making it to the exit is the probability of Walking Directly to the Exit (1/4), or going back and forth until eventually reaching the exit (1/4^3 + 1/4^6 + 1/4^9...). For Space 2 its (1/4^2 + 1/4^5...)

This gets even more confusing if you have multiple free spaces to go between, e.g.

     BOMB    BOMB    BOMB
EXIT SPACE 1 SPACE 2 SPACE 3 BOMB
     BOMB    BOMB    BOMB

What's a solid algorithmic way to deal with the complexity introduced by these cycles?

Answer 1

I would solve this in two phases.

The first phase is to identify from which squares you CAN possibly exit in any way. This will let you find and identify as "You're stuck" any closed loops with no possible exits.

Once that analysis is done, you can assign 0 to all dead ends and bombs, and 1 to all exits. The probabilities of exiting for all other squares will be the unique solution to a set of linear equations where p(i, j) = average(p(i', j') over all places you can move in one turn. That will be a set of n x m equations in n x m variables. Solve that with your favorite linear algebra technique (I recommend row reduction).

Now for each square you know the exact probability of being able to exit. And now your answer is straightforward.

Note that if you just try the linear algebra piece of the second approach, the solution to the system of linear equations will not be unique. The first phase solves that to be sure that you're coming up with the right solution.

Answer 2

For a maze:

+----+----+----+----+----+
|    |BOMB|BOMB|BOMB|    |
+----+----+----+----+----+
|EXIT| S1 | S2 | S3 |BOMB|
+----+----+----+----+----+
|    |BOMB|BOMB|BOMB|    |
+----+----+----+----+----+

You can map this to a matrix of the probabilities of what happens after each move:

//    DEAD, ESC,  S1,   S2,   S3
p = [
    [ 1.00, 0.00, 0.00, 0.00, 0.00 ], // DEAD 
    [ 0.00, 1.00, 0.00, 0.00, 0.00 ], // ESCAPED
    [ 0.50, 0.25, 0.00, 0.25, 0.00 ], // S1 
    [ 0.50, 0.00, 0.25, 0.00, 0.25 ], // S2 
    [ 0.75, 0.00, 0.00, 0.25, 0.00 ]  // S3
];

So, reading along the middle row, if the frog starts in the S1 square then, after one hop, there is:

• a 0.5 probability it will be dead;
• 0.25 probability it will have escaped; and
• 0.25 probability it will be in S2.

And reading along the top two rows - there is a probability of 1 that if it has died/escaped then it will stay dead/escaped (respectively).

To work out the probabilities after n hops then you just raise the probability matrix to the power n.

//    DEAD, ESC,  S1,   S2,   S3
p = [
    [ 1.00, 0.00, 0.00, 0.00, 0.00 ], // DEAD 
    [ 0.00, 1.00, 0.00, 0.00, 0.00 ], // ESCAPED
    [ 0.50, 0.25, 0.00, 0.25, 0.00 ], // S1 
    [ 0.50, 0.00, 0.25, 0.00, 0.25 ], // S2 
    [ 0.75, 0.00, 0.00, 0.25, 0.00 ]  // S3
    ];

function multiply( a, b )
{
  if ( a[0].length !== b.length )
  {
    throw "Matrices must have same a.x/b.y dimensions!";
  }
  let r = [];
  for ( let y = 0; y < a.length; y++ )
  {
    r[y] = [];
    for ( let x = 0; x < b[0].length; x++ )
    {
      r[y][x] = 0;
      for ( let i = 0; i < a[0].length; i++ )
      {
        r[y][x] += a[y][i] * b[i][x];
      }
    }
  }
  return r;
}

// Start at S1
r = [ [ 0, 0, 1, 0, 0 ] ];
// Output probabilities up to 10 decimal places.
dp = 10;

console.log(
  "i"
  + " " + "DEAD".padEnd(" ",dp+2)
  + " " + "ESCAPED".padEnd(" ",dp+2)
  + " " + "S1".padEnd(" ",dp+2)
  + " " + "S2".padEnd(" ",dp+2)
  + " " + "S3".padEnd(" ",dp+2)
);
for ( let i = 1; i <= 50; i++ ){
  r = multiply( r, p );
  if ( i < 10 || i % 10 === 0 )
  {
    console.log(
      i
      + " " + Number(r[0][0]).toFixed(dp)
      + " " + Number(r[0][1]).toFixed(dp)
      + " " + Number(r[0][2]).toFixed(dp)
      + " " + Number(r[0][3]).toFixed(dp)
      + " " + Number(r[0][4]).toFixed(dp)
    );
  }
}

This simple example shows that it quickly converges to a state where it is very unlikely for the frog to be still moving and there is a probability of 0.7321428571 that it is dead and 0.2678571429 that it is alive.

The challenge would be to take the input map and output the matrix and then to look at methods of optimising raising a matrix to a power to quickly find this convergence point (either through repeatedly squaring the matrix - p = multiply(p, p); - or other methods).

Answer 3

The answer that suggests solving a set of linear equations is correct, but here is another approach.

Imagine a very large number of frog's are all placed on the starting square and begin moving at random around the maze. The frogs all step at the same time. At each time step, we can use a number between 0.0 and 1.0 to represent the proportion of frogs on each square. So:

• At time 0, all the frogs are at the start, so that square has weight 1.0 and the rest have weight 0.0
• At each time step:
  • Any frogs on a bomb are destroyed (set weight to 0.0)
  • Any frogs that have reached an exit stay there
  • Frogs on any other square are distributed evenly among its neighbours
  • All frogs move at the same time, so these updates need to be performed all at once

After running this for many steps, nearly all the frogs will be in one of three states:

1. Destroyed by a bomb
2. Waiting at an exit
3. Stuck in the maze in an infinite cycle

The tricky part is deciding when to stop the simulation, in light of the possibility of cycles. It is tempting to think we can stop when none of the weights changes by more than some small value. However, if there were some repetitive cycle this would never happen, e.g. in a 2x1 maze with no exits the frogs will hop endlessly back and forth and the weights will never converge. For this specific task, given that the size of the maze is limited, you might get away with fixing the number of steps to some "large enough" value. Alternatively you could first find all the squares from which exit is impossible and exclude these from your convergence test (as suggested in another answer).