Pacman AI
Basic-Search-Algorithms-with-Pac-Man
(Email for access to project)
Pacman Path finder algorithms
Implemented BFS, DFS, UCS, and A* with multiple heuristics in order to find solutions/paths for pacman to move towards. In addition to path finding algorithms, I also utilized a single layered perceptron inorder to train an AI to play pacman.
Installation
Download and utilize a miniconda or anaconda python 2.* environment to run the application, once files opened in conda use the commands listed for each of the following sections of code.
https://docs.conda.io/en/latest/miniconda.html
Usage
To start and play a game as the clinet run the command below, this does not utilize any of the algorithms. python pacman.py
For bfs, dfs or ucs on a list of maps use the following commands:
python pacman.py -l mediumMaze -p SearchAgent -a fn=bfs
python pacman.py -l bigMaze -p SearchAgent -a fn=bfs -z .5
python eightpuzzle.py
python pacman.py -l mediumMaze -p SearchAgent -a fn=ucs
python pacman.py -l mediumDottedMaze -p StayEastSearchAgent
python pacman.py -l mediumScaryMaze -p StayWestSearchAgent
python pacman.py -l bigMaze -z .5 -p SearchAgent -a fn=astar,heuristic=manhattanHeuristic
python pacman.py -l tinyCorners -p SearchAgent -a fn=bfs,prob=CornersProblem
python pacman.py -l mediumCorners -p SearchAgent -a fn=bfs,prob=CornersProblem
python pacman.py -l mediumCorners -p AStarCornersAgent -z 0.5
python pacman.py -l testSearch -p AStarFoodSearchAgent
python pacman.py -l trickySearch -p AStarFoodSearchAgent
python pacman.py -l bigSearch -p ClosestDotSearchAgent -z .5
python pacman.py -l bigSearch -p ApproximateSearchAgent -z .5 -q
Which will out put the listed map with the path found ex.
Algorithms
def depthFirstSearch(problem):
closed_list = []
target = None
open_list = util.Stack()
open_list.push((problem.getStartState(), [], 0))
while not open_list.isEmpty():
current_state, moves, current_cost = open_list.pop()
closed_list.append(current_state)
if problem.isGoalState(current_state):
target = moves
break
for next_state, action, next_cost in problem.getSuccessors(current_state):
if next_state not in closed_list:
open_list.push((next_state, moves + [action], current_cost + next_cost))
return target
def breadthFirstSearch(problem):
"""Search the shallowest nodes in the search tree first."""
closed_list = []
target = None
open_list = util.Queue()
open_list.push((problem.getStartState(), [], 0))
in_open = [problem.getStartState()]
while not open_list.isEmpty():
current_state, moves, current_cost = open_list.pop()
in_open.remove(current_state)
closed_list.append(current_state)
if problem.isGoalState(current_state):
target = moves
break
successors = problem.getSuccessors(current_state)
for next_state, action, next_cost in successors:
if next_state not in closed_list and next_state not in in_open:
open_list.push((next_state, moves + [action], current_cost + next_cost))
in_open.append(next_state)
return target
def uniformCostSearch(problem):
"""Search the node of least total cost first."""
parent_map = {}
closed_list = []
target = None
open_list = pacmanPriorityQ.AI_Priority_Queue();
open_list.insert((problem.getStartState()), 0)
parent_map[problem.getStartState()] = []
while not len(open_list) == 0:
(current_state), p = open_list.delete_min()
closed_list.append(current_state)
if problem.isGoalState(current_state):
target = current_state
break
successors = problem.getSuccessors(current_state)
for next_state, action, next_cost in successors:
if next_state in open_list and next_state not in closed_list:
if p + next_cost < open_list.__getitem__(next_state):
open_list.__delitem__(next_state)
open_list.insert(next_state, p + next_cost)
parent_map[next_state] = parent_map[current_state] + [action]
elif next_state not in closed_list:
open_list.insert(next_state, p + next_cost)
parent_map[next_state] = parent_map[current_state] + [action]
return parent_map[target]
def aStarSearch(problem, heuristic=nullHeuristic):
"""Search the node that has the lowest combined cost and heuristic first."""
closed_list = []
target = None
open_list = pacmanPriorityQ.AI_Priority_Queue()
open_list.insert((problem.getStartState()), heuristic(problem.getStartState(), problem))
parent_map = {problem.getStartState(): []}
while not len(open_list) == 0:
(current_state), p = open_list.delete_min()
closed_list.append(current_state)
if problem.isGoalState(current_state):
target = current_state
break
successors = problem.getSuccessors(current_state)
for next_state, action, next_cost in successors:
if next_state in open_list and next_state not in closed_list:
if p + next_cost < open_list.__getitem__(next_state):
open_list.__delitem__(next_state)
open_list.insert(next_state, (p - heuristic(current_state, problem))
+ next_cost + heuristic(next_state, problem))
parent_map[next_state] = parent_map[current_state] + [action]
elif next_state not in closed_list:
open_list.insert(next_state, (p - heuristic(current_state, problem))
+ next_cost + heuristic(next_state, problem))
parent_map[next_state] = parent_map[current_state] + [action]
return parent_map[target]
License
Attribution Information: The Pacman AI projects were developed at UC Berkeley. The core projects and autograders were primarily created by John DeNero (denero@cs.berkeley.edu) and Dan Klein (klein@cs.berkeley.edu). Student side autograding was added by Brad Miller, Nick Hay, and Pieter Abbeel (pabbeel@cs.berkeley.edu).