Introduction to Artificial Intelligence - Homework Assignment (10pts.)¶
- NETID:
- Name:
This assignment covers the following topics:
- Search and Agents
- A* Search
- Adversarial Search
Complete all sections. Some questions will require written answers, while others will involve coding. Be sure to run your code cells to verify your solutions.
Section 1: Search and Agents (7pts.)¶
Search and agents are fundamental concepts in AI, where agents interact with environments to achieve goals. Understanding different search strategies and the implementation of algorithms like A* is critical for developing intelligent systems. If an agent has many different possible actions they could take an agent can perform a search across the space of possible actions and their outcomes to determine the next move they should make.
Which of the following is an informed type of search strategy? (0.5pts.)
- [ ] Breadth-First Search
- [ ] Depth-First Search
- [ ] A* Search
- [ ] Linear Search
Short Answer Question:
Explain the primary difference between informed and uninformed search strategies (0.5pts.).
Section 2: Search (The 8-Puzzle Problem)(6pts.)¶
In the 8-Puzzle problem we are given a 3x3 grid. 8 out of the 9 squares are filled with tiles containing a number (1-8). Our goal in this puzzle is to arrange the numbers in sorted order, left to right, top to bottom as illustrated in the above figure. As mentioned in class, A* is an "informed" search strategy which means we will need some kind of heuristic to solve our problem. In this solution we will use something called the "Manhattan Distance".
The Manhattan Distance will allow us to calculate how are we are from a given location using a grid-based layout. In the 8-Puzzle problem we can use the Manhattan of EACH tile from its current location to the location that we want the tile to end up in.
In this manner we can visualize the possible configurations of our 8-Puzzle as a branching tree on which we can perform an A* search.
Potentially Useful Links:
Fill out the given code below to solve the 8puzzle problem using A* and the Manhattan Distace Heuristic:
import random
# Goal state for the 8-puzzle problem
_goal_state = [[1, 2, 3],
[4, 5, 6],
[7, 8, 0]] # 0 represents the empty space
def index(item, seq):
"""Helper function to find the index of an item in a sequence.
Returns -1 if the item is not found."""
try:
return seq.index(item)
except ValueError:
return -1
class EightPuzzle:
def __init__(self):
# Initialize puzzle with default configuration
self._hval = 0 # Heuristic value (used in A* search)
self._depth = 0 # Depth in the search tree
self._parent = None # Reference to parent node in search path
# Initial state of the puzzle
self.adj_matrix = [[1, 2, 3],
[7, 0, 6],
[5, 4, 8]]
def __eq__(self, other):
# Check if two puzzles are identical
return self.adj_matrix == other.adj_matrix
def __str__(self):
# String representation of the puzzle for easy printing
res = ''
for row in self.adj_matrix:
res += ' '.join(map(str, row)) + '\n'
return res
def _clone(self):
# Create a deep copy of the puzzle
clone = EightPuzzle()
clone.adj_matrix = [row[:] for row in self.adj_matrix]
return clone
def _get_legal_moves(self):
"""Return a list of positions where the empty space (0) can move."""
row, col = self.find(0) # Locate the empty space
moves = []
# Check for possible moves and add them to the list
if row > 0: moves.append((row - 1, col)) # Move up
if col > 0: moves.append((row, col - 1)) # Move left
if row < 2: moves.append((row + 1, col)) # Move down
if col < 2: moves.append((row, col + 1)) # Move right
return moves
def _generate_moves(self):
"""Generate new puzzle states by moving the empty space."""
legal_moves = self._get_legal_moves()
zero_pos = self.find(0)
def swap_and_clone(a, b):
p = self._clone()
p.swap(a, b)
p._depth = self._depth + 1 # Increase depth for the new state
p._parent = self # Set current state as parent
return p
return [swap_and_clone(zero_pos, move) for move in legal_moves]
def solve(self, h):
"""Solve the puzzle using A* search with the given heuristic function."""
def is_solved(puzzle):
return puzzle.adj_matrix == _goal_state
open_list = [self] # Nodes to be explored
closed_list = [] # Explored nodes
move_count = 0 # Number of states explored
while open_list:
# TODO: Implement the A* algorithm here
# 1. Select the node from open_list with the lowest f = g + h
# 2. If this node is the goal state, generate the solution path
# 3. Generate successors (new states from legal moves)
# 4. For each successor:
# - If it has not been explored, calculate its heuristic value h
# - If it's already in open_list or closed_list, update it if this path is better
pass
return [], move_count # Return failure if no solution found
def shuffle(self, step_count):
"""Randomly shuffle the puzzle by making valid moves."""
for _ in range(step_count):
row, col = self.find(0)
free = self._get_legal_moves()
target = random.choice(free)
self.swap((row, col), target)
def find(self, value):
"""Find the position of a value in the puzzle."""
for row in range(3):
for col in range(3):
if self.adj_matrix[row][col] == value:
return row, col
def peek(self, row, col):
"""Get the value at a specific position."""
return self.adj_matrix[row][col]
def poke(self, row, col, value):
"""Set a value at a specific position."""
self.adj_matrix[row][col] = value
def swap(self, pos_a, pos_b):
"""Swap two values in the puzzle."""
temp = self.peek(*pos_a)
self.poke(pos_a[0], pos_a[1], self.peek(*pos_b))
self.poke(pos_b[0], pos_b[1], temp)
def heur(puzzle, item_total_calc, total_calc):
"""Heuristic template for calculating the puzzle's cost."""
t = 0
for row in range(3):
for col in range(3):
val = puzzle.peek(row, col) - 1
target_col = val % 3
target_row = val // 3
if val == -1: # Special case for empty space (0)
continue
t += item_total_calc(row, target_row, col, target_col)
return total_calc(t)
def h_manhattan(puzzle):
"""Manhattan distance heuristic function."""
# TODO: Implement the Manhattan distance heuristic here
# The Manhattan distance is the sum of the absolute differences
# between the current positions and the target positions of each tile.
pass
def main():
p = EightPuzzle()
print("Initial State:")
print(p)
# Solve the puzzle using A* search with the Manhattan distance heuristic
path, count = p.solve(h_manhattan)
path.reverse()
for state in path:
print(state)
print("Solved with Manhattan distance exploring", count, "states")
if __name__ == "__main__":
main()
Your job is to read over the code and then fill out the missing parts of two functions. In the function named solve you will need to implement the A* algorithm based on the example shown in class. However unlike the example shown in class the heuristic used will not be the Euclidian distance but instead the Manhattan Distance as shown above. This means you will also need to fill out the function manhattan with the calculations necessary to find the heuristic cost.
1 2 3 1 2 3
7 0 6 -> 4 5 6
5 4 8 7 8 0
Solved with Manhattan distance exploring 10 statesFor example, going from the above grid to the end state should take you 10 explorations.
Adversarial Search (3 pts.)¶
Question: Which of the following best describes the minimax algorithm? (1 pt.)
[ ] An algorithm that seeks to maximize the player's score while minimizing the opponent's score.
[ ] An algorithm that only maximizes the player's score.
[ ] An algorithm that uses randomness to determine the next move.
[ ] An algorithm that minimizes the total score of both players.
Question: Why is alpha-beta pruning used in conjunction with the minimax algorithm? (2 pts.)
Your answer:
Submission Instructions¶
Complete all assigned questions and then submit your finished notebook to a branch called "homework01" on your github repo. Then create a merge request from the homework branch to your main branch and assign your TA.