One approach is to use the Monte Carlo method. Monte Carlo methods are mainly used in three problem classes: optimization, numerical integration, and generating draws from a probability distribution. This problem falls into the intersection of the first & third class, so Monte Carlo seems like a reasonable thing to try.
The basic idea behind the Monte Carlo method is to simulate a number of random attempts, accumulate information from the results & then use that data to make a decision. So for this particular problem, you would:
- simulate multiple attempts to get from one place to another
- for each attempt keep track of the number of moves (or other resources) required
- when done simulating attempts, use things like the min, max, average, standard deviation to make a decision
As a perk, you can use the collected stats in a variety of ways to simulate different flavors of AI. A risk averse AI might seek to avoid the worst case scenarios. An optimistic AI might favor greedy, unlikely moves that have a big pay off, but are prone to failure.
The number of attempts influences the strength of the conclusions, but is subject to diminishing returns (for an illustration of this, look up a simple coding experiment for using Monte Carlo to estimate Pi). As such it may require some tuning to make sure your not wasting a lot of time while only improving results by a fraction of a percent. In terms of implementation, the number of simulated attempts can be set by time, trial count or some combination of the two; use whichever is a good fit for your game / framework.
Also, for this problem, you might need to add in a simulation 'basement'. That is to say, it seems like it might be possible for a very unlucky attempt to end up cycling infinitely (the pawn always gets moved back to the start). To guard against that, I would add some logic that automatically bins any simulated trial that takes more than X moves. You might also want to keep track of where such cases end up - looking at those groupings might indicate that some map feature is acting like a probabilistic gravity well for luck & skewing your play.
The strengths of the Monte Carlo method are:
- relatively easy to code
- they often run quickly
- if the AI gets some extra processing cycles, you can improve your results
- often times you can change the underlying game play (say by adding teleporters or some other feature) and won't need to make many changes to the simulation
- you can simulate weaker AI by reducing the number of simulations
- they are used in both real world problems & games and thus have a fair body of research to all back on
The weaknesses are:
- determining the cutoffs can take a fair bit of tuning
- the don't guarantee optimal solutions
- if your problem size scales badly, they might not be practical
Some additional notes: if possible, I would first try to calculate a best path that completely avoids the non-deterministic nodes. If you can do so, this sets a lower bound. If a given simulation takes more distance (or time or what ever you're trying to minimize) than the purely non-deterministic path, you already know that there are better options.