(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.
(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.
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.
Our version
of the game is deterministic in the sence that black's move
is completely determined for a given position. The black king's first
priority is to capture an unprotected rook. If this is not possible,
it is assumed that the black king moves to a safe field (a field
is safe, if it is neither in the reach of the
white rook nor in the reach of the white king) for which
the following value is minimal
Test your system for a tranining benchmark that consists of 12 example problems; the training testcases are ordered by degree of difficulty --- do not get too disappointed, if your program does not too well for some test cases with high numbers. Moreover, submit a 2 (-3) page report that describes your overall approach to solve the problem and the history of the project.
Provide an interface to your program that it can read a set of example problems from a file, and then tries to solve all problems of the set in a file. In general, your program should be able to read input-files of the following format (example: file for tranining benchmark):
number of games to play(integer) newline name of starting position(4 asci character) newline starting position (8 lines --- see example) empty_line newline name of starting position(4 asci character) newline starting position (8 lines --- see example) empty_line ...
Problem 6: Paper Walk Through
Download Tom Mitchell's white paper on "The Discipline of Machine Learning"
from: http://www.cs.cmu.edu/~tom/pubs/MachineLearning.pdf. Lead the walkthrough
of the paper sections that are assigned to you. Detailed instructions on what to do
will be given in the Feb. 12 class. The walkthrough itself will take place during the
February 19 class.