CMPSC 442 Artificial Intelligence: Homework 3: Informed and Adversarial Search
CMPSC 442: Homework 3
Instructions
In this assignment, you will explore a number of games and puzzles from the perspectives of informed and adversarial search.
A skeleton file homework3_cmpsc442.py containing empty definitions for each question has been provided. Since portions of this assignment will be graded automatically, none of the names or function signatures in this file should be modified. However, you are free to introduce additional variables or functions if needed.
You may import definitions from any standard Python library, and are encouraged to do so in case you find yourself reinventing the wheel. If you are unsure where to start, consider taking a look at the data structures and functions defined in the collections, itertools, Queue, and random modules.
You will find that in addition to a problem specification, most programming questions also include a pair of examples from the Python interpreter. These are meant to illustrate typical use cases to clarify the assignment, and are not comprehensive test suites. In addition to performing your own testing, you are strongly encouraged to verify that your code gives the expected output for these examples before submitting.
1. Tile Puzzle [40 points]
Recall from class that the Eight Puzzle consists of a 3 x 3 board of sliding tiles with a single empty space. For each configuration, the only possible moves are to swap the empty tile with one of its neighboring tiles. The goal state for the puzzle consists of tiles 1-3 in the top row, tiles 4-6 in the middle row, and tiles 7 and 8 in the bottom row, with the empty space in the lower-right corner.
In this section, you will develop two solvers for a generalized version of the Eight Puzzle, in which the board can have any number of rows and columns. We have suggested an approach similar to the one used to create a Lights Out solver in Homework 2, and indeed, you may find that this pattern can be abstracted to cover a wide range of puzzles. If you wish to use the provided GUI for testing, described in more detail at the end of the section, then your implementation must adhere to the recommended interface. However, this is not required, and no penalty will imposed for using a different approach.
1. [0 points] In the TilePuzzle class, write an initialization method __init__(self, board) that stores an input board of this form described above for future use. You additionally may wish to store the dimensions of the board as separate internal variables, as well as the location of the empty tile.
2. [0 points] Suggested infrastructure.
In the TilePuzzle class, write a method get_board(self) that returns the internal representation of the board stored during initialization.
>>> p = TilePuzzle([[1, 2], [3, 0]]) >>> p.get_board()
[[1, 2], [3, 0]]
>>> p = TilePuzzle([[0, 1], [3, 2]]) >>> p.get_board()
[[0, 1], [3, 2]]
Write a top-level function create_tile_puzzle(rows, cols) that returns a new TilePuzzle of the specified dimensions, initialized to the starting configuration. Tiles 1 through r · c - 1 should be arranged starting from the top-left corner in row-major order, and tile 0 should be located in the lower-right corner.
>>> p = create_tile_puzzle(3, 3) >>> p.get_board()
[[1, 2, 3], [4, 5, 6], [7, 8, 0]]
>>> p = create_tile_puzzle(2, 4) >>> p.get_board()
[[1, 2, 3, 4], [5, 6, 7, 0]]
In the TilePuzzle class, write a method perform_move(self, direction) that attempts to swap the empty tile with its neighbor in the indicated direction, where valid inputs are limited to the strings "up", "down", "left", and "right". If the given direction is invalid, or if the move scrambles the puzzle by calling perform_move(self, direction) the indicated number of times, each time with a random direction.
In the TilePuzzle class, write a method successors(self) that yields all successors of the puzzle as (direction, new-puzzle) tuples. The second element of each successor should be a new TilePuzzle object whose board is the result of applying the corresponding move to the current board.
create_tile_puzzle(3, 3) move, new_p in p.successors(): print move, new_p.get_board()
>>> b= >>> p= >>> for ...
[[1,2,3], [4,0,5], [6,7,8]] TilePuzzle(b)
move, new_p in p.successors(): print move, new_p.get_board()
up [[1,2,3],[4,5,0],[7,8,6]] up [[1,0,3],[4,2,5],[6,7,8]] left [[1, 2, 3], [4, 5, 6], [7, 0, 8]] down [[1, 2, 3], [4, 7, 5], [6, 0, 8]] left [[1, 2, 3], [0, 4, 5], [6, 7, 8]] right [[1, 2, 3], [4, 5, 0], [6, 7, 8]]
3. [20 points] In the TilePuzzle class, write a method find_solutions_iddfs(self) that yields all optimal solutions to the current board, represented as lists of moves. Valid moves include the four strings "up", "down", "left", and "right", where each move indicates a single swap of the empty tile with its neighbor in the indicated direction. Your solver should be implemented using an iterative deepening depth-first search, consisting of a series of depth-first searches limited at first to 0 moves, then 1 move, then 2 moves, and so on. You may assume that the board is solvable. The order in which the solutions are produced is unimportant, as long as all optimal solutions are present in the output.
>>> p = TilePuzzle(b)
>>> list(p.find_solutions_iddfs()) [['down', 'right', 'up', 'left', 'down', 'right'], ['right', 'down', 'left', 'up', 'right', 'down']]
4. [20 points] In the TilePuzzle class, write a method find_solution_a_star(self) that returns an optimal solution to the current board, represented as a list of direction strings. If multiple optimal solutions exist, any of them may be returned. Your solver should be implemented as an A* search using the Manhattan distance heuristic, which is reviewed below. You may assume that the board is solvable. During your search, you should take care not to add positions to the queue that have already been visited. It is recommended that you use the PriorityQueue class from the Queue module.
Recall that the Manhattan distance between two locations (r_1, c_1) and (r_2, c_2) on a board is defined to be the sum of the componentwise distances: |r_1 - r_2| + |c_1 - c_2|. The Manhattan distance heuristic for an entire puzzle is then the sum of the Manhattan distances between each tile and its solved location.
>>> b = [[4,1,2], [0,5,3], [7,8,6]]
>>> p = TilePuzzle(b)
>>> p.find_solution_a_star()
2. Grid Navigation [15 points]
In this section, you will investigate the problem of navigation on a two-dimensional grid with obstacles. The goal is to produce the shortest path between a provided pair of points, taking care to maneuver around the obstacles as needed. Path length is measured in Euclidean distance. Valid directions of movement include up, down, left, right, up-left, up-right, down-left, and down-right.
Your task is to write a function find_path(start, goal, scene) which returns the shortest path from the start point to the goal point that avoids traveling through the obstacles in the grid. For this problem, points will be represented as two-element tuples of the form (row, column), and scenes will be represented as two-dimensional
>>> scene = [[False, True, False],
... [False, True, False],
... [False, True, False]]
3. Linear Disk Movement, Revisited [15 points]
Recall the Linear Disk Movement section from Homework 2. The starting configuration of this puzzle is a row of L cells, with disks located on cells 0 through n - 1. The goal is to move the disks to the end of the row using a constrained set of actions. At each step, a disk can only be moved to an adjacent empty cell, or to an empty cell two spaces away, provided another disk is located on the intervening square.
Implement an improved version of the solve_distinct_disks(length, n) function from Homework 2 that uses an A* search rather than an uninformed breadth-first search to find an optimal solution. As before, the exact solution produced is not important so long as it is of minimal length. You should devise a heuristic which is admissible but informative enough to yield significant improvements in performance.
4. Dominoes Game [25 points]
In this section, you will develop an AI for a game in which two players take turns placing 1 x 2 dominoes on a rectangular grid. One player must always place his dominoes vertically, and the other must always place his dominoes horizontally. The last player who successfully places a domino on the board wins.
1. [0 points] In the DominoesGame class, write an initialization method __init__(self, board) that stores an input board of the form described above for future use. You additionally may wish to store the dimensions of the board as separate internal variables, though this is not required.
2. [0 points] Suggested infrastructure.
In the DominoesGame class, write a method get_board(self) that returns the internal representation of the board stored during initialization.
>>> b = [[True, False], [True, False]] >>> g = DominoesGame(b)
>>> g.get_board()
In the DominoesGame class, write a method successors(self, vertical) that yields all successors of the puzzle for the current player as (move, new-game) tuples, where moves themselves are (row, column) tuples. The second element of each successor should be a new DominoesGame object whose board is the result of applying the corresponding move to the current board. The successors should be generated in the same order in which moves are produced by the
3. [25 points] In the DominoesGame class, write a method
get_best_move(self, vertical, limit) which returns a 3-element tuple containing the best move for the current player as a (row, column) tuple, its associated value, and the number of leaf nodes visited during the search. Recall that if the vertical parameter is True, then the current player intends to place a domino on squares (row, col) and (row + 1, col), and if the vertical parameter is False, then the current player intends to place a domino on squares (row, col) and (row, col + 1). Moves should be explored row-major order, described in further detail above, to ensure consistency.
Your search should be a faithful implementation of the alpha-beta search given on page 170 of the course textbook, with the restriction that you should look no further than limit moves into the future. To evaluate a board, you should compute the number of moves available to the current player, then subtract the number of moves available to the opponent.
>>> b = [[False] * 3 for i in range(3)] >>> g = DominoesGame(b)
>>> g.get_best_move(True, 1)
((0, 1), 2, 6)
In the GUI, you can click on a square to make a move, press 'r' to perform a random move, or press a number between 1 and 9 to perform the best move found according to an alpha-beta search with that limit. The GUI is merely a wrapper around your implementations of the relevant functions, and may therefore serve as a useful visual tool for debugging.
