COSC 6368 (Dr. Eick) in Spring 2009
Assignment1: Heuristic Search
First Draft
Assigned: 2/9/09
Due: Problems 1-6: Feb. 28, 11p; electronic submission
Problem 7: Feb. 26 in class/March 24, 11p (electronic submission)---this and only this task is a group
task
Problem 1: State-Space Search Representation
In the water-jug puzzle we are given a 3 liter jug, named Three, and a 4 liter jug,
named Four. Initially, Three and Four are empty. A jug can be filled from a tap T, and, we can
discard the water from either jug into a drain, D. Water may also be poured from one jug into another. There
are no other measuring devices. We want to find a set of operations that will leave precisely two liters
of water in Four.
(a) Formulate this problem as a state-space search problem
Give a precise definition of a state, the start state, the goal
state or goal condition, and the operators. Operators should be specified
as "schemas" that indicate for a given state, when the operator
is legal (i.e., a set of constraints on when the operator can be applied
to an arbitrary state) and the description of the successor
state after the operator is applied. In other
words, each operator should be specified in a way that it would easily implemented in a
program to solve this problem.
(b) Show the State Space
Draw the complete state-space graph that includes all nodes (and legal directed arcs
connecting these nodes) for this problem. Inside each node show the state description, and
label each arc with its associated operator. Highlight a path that gives a solution to the
problem.
Problem 2: Using various search techniques
Assume that you have the following search graph, where S is the
start node and G1 and G2 are goal nodes. Arcs are labeled with
the cost of traversing them and the estimated cost to a goal
is reported inside nodes.
(i) For each of the search strategies listed below,
(a) indicate which goal state is
reached if any, (b) list, in order, the states expanded,
and (c) show the final contents of the OPEN and CLOSED lists. (Recall that a
state is expanded when it is removed from the OPEN list.)
When all else is equal, nodes should be expanded in alphabetical order.
- breadth-first
- best-first
(using f = h)
- A*
(using f = g + h)
- Beam Search with k=2 (using f=g+h)
- RBFS(using f=h)
Remark: Only the solutions for the last 3 strategies have to be submitted!
General Pseudocode for Searching
The following is the basic outline of the search strategy
used for breadth-first, depth-first, and best-first
search algorithms.
OPEN = { startNode } // Nodes under consideration.
CLOSED = { } // Nodes we're done with.
while OPEN is not empty
{
remove an item from OPEN based on search strategy used
- call it X
if goalState?(X) return the solution found
otherwise // Expand node X.
{
1) add X to CLOSED
2) generate the immediate neighbors (ie, children of X)
3) eliminate those children already in OPEN or CLOSED
4) add REMAINING children to OPEN
}
}
return FAILURE // Failed if OPEN exhausted without a goal being found.
The following is the basic outline of the search strategy
used for the
search algorithms.
OPEN = { startNode } // Nodes under consideration.
CLOSED = { } // Nodes we're done with.
while OPEN is not empty
{
remove an item from OPEN based on search strategy used
- call it X
if goalState?(X) return the solution found
otherwise // Expand node X.
{
1) add X to CLOSED
2) generate the immediate neighbors (ie, children of X)
3) add all children to OPEN
}
}
return FAILURE // Failed if OPEN exhausted without a goal being found.
Problem 3: h in Bestfirst Search
What are the characteristics of a good state evaluation function h to be
used in conjunction with A*/BestFirst Search?
Problem 4: Backtracking
a) Assume you apply a version of backtracking to the 8-puzzle that does not use a depth bound, but which
checks for loops in the current path. Assuming there are sufficient resouces; will this version backtacking
find a solution, if a solution exists? Give reasons for your answer!
b) Backtracking only memorizes states that are on the currently explored path. What are the advantages of this
approach? What are the disadvantages of this approach? Be specific!!
Problem 5: Find a state Evaluation Function
Propose a state-evaluation function for the King+Rook vs. King endgame. Explain
your state evaluation function!
Remark: You do not need to implement the proposed function!
Problem 6: Game Playing
a) What assumption does the minimax search strategy make about the moves that the opposign player selects?
b) In real world games, such as checkers, it is usually not feasible to generate the entire search space.
What approach is typically chosen by game playing programs to cope with this problem?
c) What is the main difference between minmax search and alpha-beta search?
d) Why does search in game playing programs always proceed forward from
the current position rather than backward from the goal?
Problem Specification (Group Project)