Part I. Written Answers (15 points).
This part of the assignment is concerned with the sizes of state spaces
for search problems. The so-called "combinatorial explosion" can manifest
itself in a variety of ways. Understanding how some states may be double counted
by simple enumeration techniques can be important in applying state-space search.
For example, if a large proportion of states get double counted, it may be worth
implementing functionality to eliminate the double counting.
- "Tic-Tac-Toe" (5 points)
How many distinct states are possible in a game of Tic-Tac-Toe after 5 moves
have been made (3 Xs and 2 Os)? Consider two states to be distinct even if
rotating the board by 90 degrees or 180 degrees, or flipping the board
vertically or horizontally, turns one state into the other.
However if the same arrangement of the board can be reached by multiple
move sequences, still consider that to be just one state.
- "Tri-Tac-Toe" (10 points)
Let us define the game of Tri-Tac-Toe as a game for 3 players, X, Y, and Z.
The object is to get 3 in a row. However, they play on a 3D board that is 3 by 3 by 3.
They take turns in a round-robin protocol.
Give an expression for the number of distinct states that can be achieved after 6 moves
and evaluate it to a number.
Such a state should have 2 X's, 2 Y's, and 2 Z's on the board, filling six of the
27 available voxels.
You may assume that 2 states are distinct even if one can be matched to another by some
rotation of the cube.
- Purple Paperweights (Optional, for 5 points of extra credit)
The Purple Paperweight Company sells a line of paperweights that come in the following
sizes: 2 cm by 2 cm, 4 cm by 4 cm, 6 cm by 6 cm, etc. Thus a typical paperweight is of
size n by n, measured in centimeters. Its design is an array of purple and gold squares
each of size 1 centimeter on a size. The underside is just black felt, with no pattern.
The company promotes the paperweights by explaining how great a variety of patterns they
come in, because the arrangements of purple vs. gold in the grid positions are more or
less random. Give a formula for the number of distinct paperweights having size n by n.
This formula should consider the possibility of various symmetries and double-counting
situations, and it should not do any double counting.
Hints: (1) patterns with 4-way (90-degree) rotational symmetry are not double counted;
patterns with 2-way (180-degree) rotational symmetry, but not 4-way symmetry,
are double counted; other patterns are quadruple counted.
(2) try working out all the patterns for n=2 and use that as a check on your formulas.
|
Part II. 85 Points.
The Python code for a program that performs iterative depth-first search to solve
a Towers of Hanoi puzzle is given in the two files
ItrDFS.py
and
TowerOfHanoi.py
Implement the following
-
Breadth-First Search (10 points).
Using ItrDFS.py as a guide, and starting from the skeleton code
ItrBreadthFS.py that uses
breadth-first search rather than depth-first search to solve the Tower of Hanoi puzzle.
Show the states on a shortest solution path for the Towers of Hanoi puzzle with 4 disks.
Hint: the path should have length 15.
-
Basic 8 Puzzle Formulation (25 points).
Create a file BasicEightPuzzle.py
that provides the same kinds of problem elements that the TowerOfHanoi.py file provides:
metadata, initial state, operators, and a few utility functions for states, including
__hash__() and __eq__(s) , as well as __copy__()
and the __str()__ function.
The first two of these will allow your state objects to be used as keys in dictionaries,
and the third gives a way to construct deep copies. The last one controls how your
states will appear when the print function is called on them.
# goal:
CREATE_GOAL_STATE = lambda x: [0, 1, 2, 3, 4, 5, 6, 7, 8]
Show that it can solve some easy instances of the puzzle, such as instances requiring only
three or four moves.
Here are four instances to try. Note that puzzle0 is the most trivial version possible.
# puzzle0:
CREATE_INITIAL_STATE = lambda x: [0, 1, 2, 3, 4, 5, 6, 7, 8]
# puzzle1a:
CREATE_INITIAL_STATE = lambda x: [1, 0, 2, 3, 4, 5, 6, 7, 8]
# puzzle2a:
CREATE_INITIAL_STATE = lambda x: [3, 1, 2, 4, 0, 5, 6, 7, 8]
# puzzle4a:
CREATE_INITIAL_STATE = lambda x: [1, 4, 2, 3, 7, 0, 6, 8, 5]
-
A-Star Implementation (20 points).
Implement an A* search program using the skeleton code in
AStar.py
that, like ItrDFS.py, will accept as a command-line
argument the name of a problem template such as EightPuzzle but also accepts (a) the name
of a heuristic evaluation function to use in the AStar search
and (b) the name of a puzzle instance file that contains a particular initial state.
For example
python3 AStar.py EightPuzzleWithHeuristics h_euclidean puzzle2a.py
The contents of puzzle2a.py would have this form:
CREATE_INITIAL_STATE = lambda x: [3, 1, 2, 4, 0, 5, 6, 7, 8]
-
Implementing and Comparing Heuristics (30 points).
Implement four heuristic evaluation functions for the 8 Puzzle: h_euclidean(s),
h_hamming(s), h_manhattan(s), and h_custom(s).
The first should compute the euclidean distance for each tile from its location in
state s to its location in the goal state. Then it should add up these distances
and return that sum. The second function should determine the number of tiles that,
in state s, are not where they should end up in the goal state.
The third function should find, for each tile, how many rows it is away from its goal state row
plus how many columns it is away from its goal state column, and it should add those
distances for each of the tiles. When computing these distances, include the empty square
as if it were a virtual tile (tile number 0). The fourth heuristic is one that you should
design yourself. You should design it to be admissible. Ideally, it will outperform
the others. However, it might simply offer a variation or combination of the others.
Include these in a new version of your 8 puzzle formulation: EightPuzzleWithHeuristics.py.
Define the actual functions at the end of the COMMON-CODE section, but create new couple of
lines of code
at the end of the file as follows.
HEURISTICS = {'h_euclidean': h_euclidean, 'h_hamming':h_hamming,
'h_manhattan':h_manhattan, 'h_custom':h_custom}
Compare the performance of these heuristics on each of the example puzzles (given below).
For each puzzle-heuristic pair,
report whether the puzzle was successfully solved and also
report the count of states processed (taken off of OPEN and put on CLOSED).
Put this information into a table.
If it takes more than 30 seconds to solve a particular problem with a particular
heuristic then note that; you may abort such runs.
Example puzzles:
puzzle10a.py:
CREATE_INITIAL_STATE = lambda: [4, 5, 0, 1, 2, 3, 6, 7, 8]
puzzle12a.py:
CREATE_INITIAL_STATE = lambda: [3, 1, 2, 6, 8, 7, 5, 4, 0]
puzzle14a.py:
CREATE_INITIAL_STATE = lambda: [4, 5, 0, 1, 2, 8, 3, 7, 6]
puzzle16a.py:
CREATE_INITIAL_STATE = lambda: [0, 8, 2, 1, 7, 4, 3, 6, 5]
Please put your results for these comparisons (as mentioned, in the form of a table) in
a file results.txt.
|