Depth First Game Trees

Having spent too much time writing search trees for solving puzzles I will now put an end to it by describing a template for the purpose. Any puzzle consists of a start state and a goal state and a set of rules to change state. The aim is to list the sequence of state changing actions that arrives at the goal state from a start state. Hence the general algorithm can be written as:

let seen-states = {start-state}

let Solve(current-state) =
  if current-state = goal-state
    return true
    for-each action in possible-actions
        next-state = Do-Action(action, current-state)
        if NOT next-state in seen-states
          add-state(next-state, seen-states)
          if Solve(next-state)
             print-output action
             return true
    return false


Notice that this is just the solution to the Water-Buckets problem with a few name changes. Simple as it is the devil is in details. In some problems like the Water-Buckets problem, the set of all possible states may small so that ‘seen-states’ can potentially store all of them in memory. In other cases the set of all states be may be too large. Think Rubik’s cube. In other cases the set of all possible states can be linearly ordered (we denote the relation as ‘<‘) and the state traversal never moves from  a state X to a state Y unless X < Y.  This is the case with BrianVita which is why the seen-states are not stored. This is easy to prove if you have a basic understanding of sets and relations.


About The Sunday Programmer

Joe is an experienced C++/C# developer on Windows. Currently looking out for an opening in C/C++ on Windows or Linux.
This entry was posted in Algorithm. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s