unendlich - Home About Archive

Escape From Zurg

Posted on 21.08.2009

Lately I have been reading about searching in game trees. So a friend of mine sent me the “Escape from Zurg” paper, which talks about problem solving by tree searching with Haskell.

In a large class of problems one is given a start state and some predicate for a desired final state. Moreover, the rules that dictate how a successor state is generated from a previous one are also given. Take a board game for instance, like tic-tac-toe. There is the initial state (which is the empty board), the predicate for a desired state (a state in which tree pieces of mine are aligned), and rules to create one state from another (the rules of the game). Another example of such problems is the “Escape from Zurg” one, that is stated as follows:

Buzz, Woody, Rex, and Hamm have to escape from Zurg. They merely have to cross one last bridge before they are free. However, the bridge is fragile and can hold at most two of them at the same time. Moreover, to cross the bridge a flashlight is needed to avoid traps and broken parts. The problem is that our friends have only one flashlight with one battery that lasts for only 60 minutes (this is not a typo: sixty). The toys need different times to cross the bridge (in either direction):

Buzz 5 minutes
Woody 10 minutes
Rex 20 minutes
Hamm 25 minutes

Since there can be only two toys on the bridge at the same time, they cannot cross the bridge all at once. Since they need the flashlight to cross the bridge, whenever two have crossed the bridge, somebody has to go back and bring the flashlight to those toys on the other side that still have to cross the bridge. The problem now is: In which order can the four toys cross the bridge in time (that is, in 60 minutes) to be saved from Zurg?

This class of problems is usually solved by searching. The initial state and all the successors ultimately build a DAG (directed acyclic graph) that is called the search space. Some search spaces are small, like tic-tac-toe playing or even the “Escape from Zurg” puzzle. Others are large, like playing Reversi; even larger, like playing Chess; others are infinite. Needless to say that that are better searching ways than others. This same puzzle, for instance, was solved in Scheme by Ben Simon using the cool amb operator. The amb operator uses first-class continuations to backtrack and take another path in case the first one fails. It was an elegant solution for this puzzle, but it is not adequate for general searching because it backtracks blindly. There are others ways to search blindly, for instance depth-first search and breadth-first search.

In a depth-first search, we analyse the successors of a given state until there are no more successors to analyse, and then backtrack to a previous level of the tree. In a breadth-first search, we analyse the whole fringe of the tree (the horizon nodes) before expanding it one level further using the successor rules. This is good for infinite search spaces, because we will eventually find a solution if there is one. The implementation in Scheme is straightforward:

This is actually all we need for simple searches. Of course we need to supply the initial state, the procedure that generates successors and the goal predicate. These are specific for each kind of problem. Let’s see the Zurg problem procedures:

The previous procedures use some utilities:

Our successors procedure does not take time in account. So it is possible for a branch of the tree to go on indefinitely. To guarantee that we will arrive at a solution, we use a breadth-first search:

With the result:

#<state #14 near: (buzz woody rex hamm) far: () flashlight: near time: 0>
#<state #15 near: (rex hamm) far: (buzz woody) flashlight: far time: 10>
#<state #16 near: (woody rex hamm) far: (buzz) flashlight: near time: 20>

#<state #17 near: (woody) far: (rex hamm buzz) flashlight: far time: 45>
#<state #18 near: (buzz woody) far: (rex hamm) flashlight: near time: 50>
#<state #19 near: () far: (buzz woody rex hamm) flashlight: far time: 60>

If we change our successors procedure a little, we can use depth-first search: