## State Space Searching in Tcl

This page explores the use of Tcl for searching a state space from a problem. I define a GeneralSearch algorithm in Tcl, and then go on to define BreadthFirst and DepthFirst searches. Later, I might add heuristic search methods such as A*, iterative deepening etc. Finally, I demonstrate a simple example. - NEM

Note - see Searching A Star in Space for much better code by RS - NEM

```################################################################################
# Some general search strategies in Tcl.
#
################################################################################
catch {console show}
# Let's first implement our node:

proc createNode {name operator state pathCost} {
puts "Creating node at \$state as a result of \$operator -> \$pathCost"
set name2 [split \$name |]; # use | as a path seperator.
set parent [string range \$name 0 [expr {[string last "|" \$name] - 1}]]
if {\$operator == "starting"} {
set parent "Dummy"
} else {
set parent [\${parent}::getState]
}

namespace eval \$name [subst {
variable parent \$parent
variable this \$name
variable operator \$operator
variable pathCost \$pathCost
variable depth [llength \$name2]
variable state \$state
}]
proc \${name}::getState {} {
variable state
return \$state
}
proc \${name}::getPathCost {} {
variable pathCost
return \$pathCost
}
proc \${name}::getParent {} {
variable parent
return \$parent
}
return \$name
}

# We will implement the queue as a list.
proc MakeQueue {initState} {
set queue [list [createNode "rootNode" "starting" \$initState 0]]
return \$queue
}

proc RemoveFront {n} {
upvar 1 \$n nodes
set front [lindex \$nodes 0]
set nodes [lreplace \$nodes 0 0]
return \$front
}

# The problem will be an array of the form:
#  problem(initState) - initial state
#  problem(goalTest) - the ideal state (i.e. the goal)
#  problem(operators) - the operators of the problem

proc Expand {node operators} {
# Apply all operators to node and return a list
# of new nodes.
set returnNodes {}
set uniqueName 1
foreach operator \$operators {
set name \$node
append name "|node\$uniqueName"
set res [eval \$operator \$node]
if {![string equal \$res "Error"]} {
foreach item \$res {
lappend returnNodes [eval createNode \$name \$operator \$item]
incr uniqueName
set name \$node
append name "|node\$uniqueName"
}
}
}
return \$returnNodes
}

# All other functions are defined by the particular search.
proc GeneralSearch {p QueuingFunc} {
upvar 1 \$p problem
set nodes [MakeQueue \$problem(initState)]
while {[llength \$nodes] > 0} {
puts "Continue?"
if {[string equal [gets stdin] "n"]} {
exit
}
set currentNode [RemoveFront nodes]
puts "\$nodes"
set result [eval \$problem(goalTest) [\${currentNode}::getState]]
if {\$result == 1} {
return \$currentNode
} else {
puts "->Expanding [\${currentNode}::getState]"
set res [Expand \$currentNode \$problem(operators)]
if {[string length \$res] == 0} {
puts "No nodes expanded."
continue
}
\$QueuingFunc \$res nodes
}
}
}

################################################################################
# To define a new search, you can use the building blocks above.
# For instance, let's define breadth-first and depth-first:
#
################################################################################

# First, define our queuing function.
upvar 1 \$p problem
proc EnqueueAtEnd {newNodes q} {
upvar 1 \$q queue
set queue [concat \$queue \$newNodes]
return
}
return [GeneralSearch problem EnqueueAtEnd]
}

proc DepthFirstSearch {p} {
upvar 1 \$p problem
proc EnqueueAtFront {newNodes q} {
upvar 1 \$q queue
set queue [concat \$newNodes \$queue]
return
}
return [GeneralSearch problem EnqueueAtFront]
}
################################################################################
# To define a search problem you simply do the following:
#     * Define your problem with an initial state of some sort (a string in this case)
#     * Define the goal test as a procedure in the following form:
#         proc goalTest {state} {
#             # Work out if goal here
#             return 1 for success
#             return 0 for failure
#         }
#     * A list of operators in the form:
#         proc operator1 {node} {
#             return [list newState pathCost]
#         }
#     * The operators are resposible for deciding new states and calculating the pathCost
#     to this new state.
#
#
# A simple example:
#  Search a maze for the quickest route.
#  This was a coursework assignment I had a while back.
################################################################################
# The problem:
#  Find your way from A to U in the following maze.
#  |   ============\
#  | A  B  C  D  E |
#  |   |==|==   |  |
#  | F |G |H  I |J |
#  |   |  |==   |  |
#  | K  L  M  N |O |
#  |   |==|==|  |  |
#  | P |Q |R |S |T |
#  |===|  |  |==|  |
#  | U  V  W  X  Y |
#  |   |===========/
# We apply the restrictions that no move can go back to the start state, and no
# move can go back to the state it was _just_ at (i.e. the direct parent state).
################################################################################

# First, define our stateSpace. For this search, the stateSpace is known
# but the procs would still work if your operators can get information from other
# sources. It is easier though, if we just give them the info in the first place :-)

# The state-space here consists of nodes followed by a list stating which
# directions are possible and what the path cost is and what the destination is.

array set map {
A        {e 1 B s 1 F}
B        {w 1 A e 1 C}
C        {w 1 B e 1 D}
D        {w 1 C e 1 E s 1 I}
E        {w 1 D s 1 J}
F        {n 1 A s 1 K}
G        {s 1 L}
H        {e 1 I}
I        {n 1 D w 1 H s 1 N}
J        {n 1 E s 1 O}
K        {n 1 F e 1 L s 1 P}
L        {n 1 G w 1 K e 1 M}
M        {w 1 L e 1 N}
N        {n 1 I w 1 M s 1 S}
O        {n 1 J s 1 T}
P        {n 1 K}
Q        {s 1 V}
R        {s 1 W}
S        {n 1 N}
T        {n 1 O s 1 Y}
U        {e 1 V}
V        {n 1 Q w 1 U e 1 W}
W        {n 1 R w 1 V e 1 X}
X        {w 1 W e 1 Y}
Y        {n 1 T w 1 X}
}

set stateSpace(initState) "A"
proc GoalTest {state} {
if {[string equal \$state "U"]} {
return 1
} else  {
return 0
}
}
set stateSpace(goalTest) GoalTest
proc moveNorth {node} {
# Check if node can move north, if it can
# return the list, else return ""
set moves \$::map([\${node}::getState])
set result "Error"
set parent [\${node}::getParent]
foreach {dir cost newState} \$moves {
if {[string equal \$dir "n"] && ![string equal \$newState \$parent]} {
# We have a winner!
set pathCost [expr {[\${node}::getPathCost] + \$cost}]
set result [list \$newState \$pathCost]
}
}
return \$result
}

proc moveEast {node} {
# Check if node can move north, if it can
# return the list, else return ""
set moves \$::map([\${node}::getState])
set result "Error"
set parent [\${node}::getParent]
foreach {dir cost newState} \$moves {
if {[string equal \$dir "e"] && ![string equal \$newState \$parent]} {
# We have a winner!
set pathCost [expr {[\${node}::getPathCost] + \$cost}]
set result [list \$newState \$pathCost]
}
}
return \$result
}

proc moveWest {node} {
# Check if node can move north, if it can
# return the list, else return ""
set moves \$::map([\${node}::getState])
set result "Error"
set parent [\${node}::getParent]
foreach {dir cost newState} \$moves {
if {[string equal \$dir "w"] && ![string equal \$newState \$parent]} {
# We have a winner!
set pathCost [expr {[\${node}::getPathCost] + \$cost}]
set result [list \$newState \$pathCost]
}
}
return \$result
}

proc moveSouth {node} {
# Check if node can move north, if it can
# return the list, else return ""
set moves \$::map([\${node}::getState])
set result "Error"
set parent [\${node}::getParent]
foreach {dir cost newState} \$moves {
if {[string equal \$dir "s"] && ![string equal \$newState \$parent]} {
# We have a winner!
set pathCost [expr {[\${node}::getPathCost] + \$cost}]
set result [list \$newState \$pathCost]
}
}
return \$result
}

# These operators are all basically the same, but they could be wildly different in real life.

set stateSpace(operators) [list moveNorth moveEast moveWest moveSouth]
# you could change the order to see if it makes a difference. On uninformed strategies it will
# change the order of search, but the outcome should still be the same, if the search is optimal &
# complete.

# Now we search:
puts "Depth First Search:\n==================="
catch {DepthFirstSearch stateSpace} result
set result [split \$result "|"]
puts "\$result"
set route [lindex \$result 0]
puts -nonewline "[\${route}::getState] -> "
set result [lrange \$result 1 end]
foreach item \$result {
append route "|\$item"
puts -nonewline "[\${route}::getState] -> "
}

puts "End!"
puts "Total cost: [\${route}::getPathCost]"

catch {DepthFirstSearch stateSpace} result
set result [split \$result "|"]
puts "\$result"
set route [lindex \$result 0]
puts -nonewline "[\${route}::getState] -> "
set result [lrange \$result 1 end]
foreach item \$result {
append route "|\$item"
puts -nonewline "[\${route}::getState] -> "
}

puts "End!"
puts "Total cost: [\${route}::getPathCost]"```

And that should do it! Just copy and paste into tclsh or wish console and watch it whirl!

Heuristic Searches

 Category Concept