Admissible Heuristic for Chutes and Ladders

Question

You are a player of Chutes and Ladders. You are going from cell 1 to cell 100, using standard 6 faced dice. There are “chutes” and “ladders” that hurt and help, respectively.
Explain an algorithm to calculate an admissible heuristic starting square i.

Answer 1

An admissible heuristic can be built simply by ignoring chutes and keeping ladders. 

Let h(i) be the minimum number of dice throws needed to reach square 100 from square i in this relaxed game. Since removing chutes makes the game easier, the true cost in the real game is never smaller than this value, so h(i) is admissible.

Steps:

1. States 1...100

2. For each square s, for each die result d (1...6):

     - move to t = s + d if t <= 100

    - if t is the foot of a ladder, replace it by the ladder top,

     - do not apply chutes

3. This gives a directed graph where every edge has cost 1 throw.

4. Run BFS backward from square 100 or BFS forward from each node in order to get the shortest path length to 100.

5. Set that distance as h(s)

------------------------------

Why admissible? The relaxed game has all real moves except the harmful effect of chutes, therefore, its shortest path cost is a lower bound on the true shortest path cost.