Pacman Search

CSC460 - Artificial Intelligence ©️

Project Phase 1

Outline 📜

1. Project Outline
2. Project Introduction
3. Question 1: Finding Fixed Food Dot using Depth First Search
4. Question 2: Breadth First Search
5. Question 3: Varying the Cost Function
6. Question 4: A* search
7. Question 5: Finding All the Corners
8. Question 6: Corners Problem: Heuristic
9. Question 7: Eating All The Dots
10. Question 8: Suboptimal Search
11. Contributors

Introduction 📝

This code implements general search algorithms such as depth-first, breadth-first, uniform cost, and A* to optimize Pacman's navigation in a maze world, enabling him to efficiently collect food and reach specific locations.

🚩 Question 1: Finding Fixed Food Dot using Depth First Search

In this problem, pacman should find a path to reach a Food Dot, each step will cost pacman 1. We implemented the Depth First Search algorithm in search.py in the corresponding function.

We create a DFSNode class to store the state | action | parent, of each state in the problem. In addition, we created the function get_path in DFSNode, allowing us to reconstruct the path from root to that node.

Answers to Questions:

1. Is the exploration order what you would have expected?
   

   yes it is

2. Does Pacman actually go to all the explored squares on his way to the goal?
   

   No, there might exists an explored square that is not located on the root-to-goal path

3. Is a 130 a least cost solution for mediumMaze? If not, think about what depth-first search is doing wrong.
   

   No, it is not a least cost solution, DFS returns the first path root-to-goal that it finds without it being an optimal solution

Test Cases

$ python pacman.py -l tinyMaze -p SearchAgent

Path found with total cost of 10 in 0.0 seconds

Search nodes expanded: 15

Pacman emerges victorious! Score: 500

---

$ python pacman.py -l mediumMaze -p SearchAgent

Path found with total cost of 130 in 0.0 seconds

Search nodes expanded: 146

Pacman emerges victorious! Score: 380

---

$ python pacman.py -l bigMaze -p SearchAgent

Path found with total cost of 210 in 0.0 seconds

Search nodes expanded: 390

Pacman emerges victorious! Score: 300

🚩 Question 2: Breadth First Search

In this problem, pacman should find a path to reach a Food Dot, each step will cost pacman 1. We implemented the Breadth First Search algorithm in search.py in the corresponding function.

We create a BFSNode class to store the state | action | parent, of each state in the problem. In addition, we created the function get_path in BFSNode, allowing us to reconstruct the path from root to that node.

Answers to Questions:

1. Does BFS find a least cost solution?
   

   yes it does

Test Cases

$ python pacman.py -l mediumMaze -p SearchAgent -a fn=bfs

Path found with total cost of 68 in 0.0 seconds

Search nodes expanded: 269

Pacman emerges victorious! Score: 442

---

$ python pacman.py -l bigMaze -p SearchAgent -a fn=bfs -z .5

Path found with total cost of 210 in 0.0 seconds

Search nodes expanded: 620

Pacman emerges victorious! Score: 300

Generic BFS works on eightpuzzle.py

$ python eightpuzzle.py

A random puzzle

| 1 | 2 | 5 |

| 3 | 7 | 4 |

| 6 | X | 8 |

BFS found a path of 5 moves: ['up', 'right', 'up', 'left', 'left'] After 1 move: up

---

| 1 | 2 | 5 |

| 3 | X | 4 |

| 6 | 7 | 8 |

Press return for the next state... After 2 moves: right

---

| 1 | 2 | 5 |

| 3 | 4 | X |

| 6 | 7 | 8 |

Press return for the next state... After 3 moves: up

---

| 1 | 2 | X |

| 3 | 4 | 5 |

| 6 | 7 | 8 |

Press return for the next state... After 4 moves: left

---

| 1 | X | 2 |

| 3 | 4 | 5 |

| 6 | 7 | 8 |

Press return for the next state... After 5 moves: left

---

| X | 1 | 2 |

| 3 | 4 | 5 |

| 6 | 7 | 8 |

🚩 Question 3: Varying the Cost Function

In this problem, pacman should find a path to reach a Food Dot, each step will cost pacman some value pre-defined by the costFn function.

We implemented the Uniform Cost Search algorithm in search.py in the corresponding function.

We create a UCSSearchProblemNode class to store the state | action | parent and the cost of the path from the root to that node, of each state in the problem i.e. g(n).

In addition, we created the function get_path in UCSSearchProblemNode, allowing us to reconstruct the path from root to that node.

Test Cases

$ python pacman.py -l mediumMaze -p SearchAgent -a fn=ucs

Path found with total cost of 68 in 0.0 seconds

Search nodes expanded: 269

Pacman emerges victorious! Score: 442

---

$ python pacman.py -l mediumDottedMaze -p StayEastSearchAgent

Path found with total cost of 1 in 0.0 seconds

Search nodes expanded: 186

Pacman emerges victorious! Score: 646

---

$ python pacman.py -l mediumScaryMaze -p StayWestSearchAgent

Path found with total cost of 68719479864 in 0.0 seconds

Search nodes expanded: 108

Pacman emerges victorious! Score: 418

🚩 Question 4: A* search

We implemented the A* search algorithm in search.py in the corresponding function.

We create a AStarNode class to store the state | action | parent and the cost of the path from the root to that node, of each state in the problem + the heuristic value of that state i.e. g(n) + h(n).

Test Cases

$ python pacman.py -l bigMaze -z .5 -p SearchAgent -a fn=astar,heuristic=manhattanHeuristic

Path found with total cost of 210 in 0.0 seconds

Search nodes expanded: 549

Pacman emerges victorious! Score: 300

Answers to Questions:

1. What happens on openMaze for the various search strategies?
   • DFS:
     DFS is not optimal, it will not find the shortest path to the goal, it will find the first path to the goal.
     
     • Path found with total cost of 298 in 0.0 seconds
     • Search nodes expanded: 576
     • Pacman emerges victorious! Score: 212
   • BFS:
     BFS is optimal, it will find the shortest path to the goal.
     
     • Path found with total cost of 54 in 0.0 seconds
     • Search nodes expanded: 682
     • Pacman emerges victorious! Score: 456
   • UCS:
     UCS is optimal, it will find the shortest path to the goal.
     
     • Path found with total cost of 54 in 0.0 seconds
     • Search nodes expanded: 682
     • Pacman emerges victorious! Score: 456
   • A*
     A* is optimal, it will find the shortest path to the goal.
     
     • Path found with total cost of 54 in 0.0 seconds
     • Search nodes expanded: 550
     • Pacman emerges victorious! Score: 456

🚩 Question 5: Finding All the Corners

In this problem, pacman should find a path to reach all the Corners in the maze, each step will cost pacman some value pre-defined by the costFn function.

We used

self.startState = self.CornersState(self.startingPosition, [False, False, False, False])

as a representation of the start state, where the boolean values represent if the corner is visited or not.

We implemented the CornersProblem class in searchAgents.py to represent the problem. Inside that class we created a CornersState class to represent the state of the problem, which is a tuple of the current position and boolean values representing if the corner is visited or not.

We implemented the getSuccessors function to return the successors of the current state, the isGoalState function to check if the current state is the goal state and the getStartState function to return the start state of the problem.

Test Cases

$ python pacman.py -l tinyCorners -p SearchAgent -a fn=bfs,prob=CornersProblem

Path found with total cost of 28 in 0.0 seconds

Search nodes expanded: 252

Pacman emerges victorious! Score: 512

---

$ python pacman.py -l mediumCorners -p SearchAgent -a fn=bfs,prob=CornersProblem

Path found with total cost of 106 in 0.0 seconds

Search nodes expanded: 1966

Pacman emerges victorious! Score: 434

---

🚩 Question 6: Corners Problem: Heuristic

In this problem, we implemented the cornersHeuristic function in searchAgents.py to return the heuristic value of the current state.

We created a Admissible and Consistent heuristic function heuristic_found_by_ga_for_corners_problem found in searchAgents.py

1. How we created it:

   Genetic Algorithm

   We used a genetic algorithm to find the best heuristic function.

   Try it yourself:

   In genetic_algorithm.py you can modify on which maze you want to train ("tinyCorners", "mediumCorners", "bigCorners")
   To run:

   python install -r requirements.txt

   python genetic_algorithm.py -p CornersProblem -l mediumCorners

   How it works:

   1. Encoding
   A chromosome is a set of 0 and 1 (i.e. 010011) where each digit, represent whether its corresponding heuristic is used.
   The full list of heuristic functions is:

       HEURISTICS_LIST = [
           manhattan_distance,
           euclidean_distance,
           diagonal_distance,
           max_heuristic,
           min_heuristic,
           null_heuristic
       ]
   

   How? look at the below example:

   010011

   means that

   euclidean_distance,  min_heuristic,  null_heuristic

   are being used
   
   
   
   2. Fitness Function
   To evaluate the fitness of a chromosome, we ran aStarSrarch on the problem where the heuristic used is new_heuristic and we returned:
   

   (1/nodes_expanded)*(10**c)

   Where c is a small integer just to make even small changes in nodes_expanded a more valuable thing to the algorithm
   new_heuristic is defined as follow (pseudo code):

   def new_heuristic(start, goal):
       set_of_heuristic_allowed = extract_allowed_heuristics(chromosome)
       values = [h(start, goal) for h in set_of_heuristic_allowed]
       return method_of_joining_heuristics(values)
   

   where method_of_joining_heuristics is one of:

       method_of_joining_heuristics = {
           'max' : max,
           'min' : min,
           'mean' : lambda x: sum(x)/len(x),
           'mode' : lambda x: max(set(x), key=x.count),
           'median' : lambda x: median(x),
           'range': lambda x: max(x) - min(x),
       }
   

   3. Selection
   We used ranking selection to select the best heuristic functions.
   4. Crossover
   We used single point crossover to create new heuristic functions. Crossover probability is 0.8.
   5. Mutation
   We used bitstring mutation to mutate the heuristic functions allowed. Mutation probability is 0.2.
   6. Stopping Criteria
   We used number of generations as a stopping criteria. We ran the genetic algorithm for 30 generations.
   7. Results
   We ran the genetic algorithm for 30 generations and the best heuristic function we found is:

   Best solution:   (1, 1, 1, 1, 1, 1)
   

   Best Fitness:    1
   

   Best Cost (number of nodes expanded):    741
   

   Best solution is made of:       RANGE( manhattan_distance,  euclidean_distance,  diagonal_distance,  max_heuristic,  min_heuristic,  null_heuristic,  )
   

   Where

   RANGE = lambda x: max(x) - min(x)
   

   thus the best heuristic combination is RANGE( manhattan_distance, euclidean_distance, diagonal_distance, max_heuristic, min_heuristic, null_heuristic, )

2. How we used it:

   In searchAgents.py in the function cornerHeuristic, we generated all the permutations of the cornerns i.e. ((c1, c2, c3, c4), (c2, c4, c1, c3) . . .)
   Then for each of those permutations we used our heuristic_found_by_ga_for_corners_problem to calculate the total path cost of that permutation. Then we return the minimum path cost of a permutation.
   Pseudo Code:

   min_cost = infinity
   for permutation in permutations_of_corners:
       cost = 0
       for i in range(len(permutations_of_corners)-1):
           cost += heuristic_found_by_ga_for_corners_problem(perm[i], perm[i+1])
       if cost < min_cost:
           min_cost = cost
   

Test Cases

$ python pacman.py -l mediumCorners -p AStarCornersAgent -z 0.5

Path found with total cost of 106 in 0.1 seconds

Search nodes expanded: 741

Pacman emerges victorious! Score: 434.0

---

$ python pacman.py -l bigCorners -p AStarCornersAgent -z 0.5

Path found with total cost of 162 in 0.2 seconds

Search nodes expanded: 1725

Pacman emerges victorious! Score: 378.0

---

🚩 Question 7: Eating All The Dots

In this problem, we implemented the foodHeuristic function in searchAgents.py to return the heuristic value of the current state.

We created a Admissible and Consistent heuristic function.

How it Works:

We also used the genetic algorithm to find the best heuristic function for this problem.
The function is heuristic_found_by_ga_for_food_problem
We created a exactDistanceUsingAStar(start, goal) function that returns the actual cost of the path from the start to the goal using the AStarSearch algorithm and heuristic_found_by_ga_for_food_problem
Then we found closest_food and furthest_food using heuristic_found_by_ga_for_food_problem
Then we returned the heuristic value as:

    return exactDistanceUsingAStar(start, closest_food) + heuristic_found_by_ga_for_food_problem(closest_food, furthest_food)

Genetic Algorithm Results:

We ran the genetic algorithm for 30 generations using

python install -r requirements.txt

python genetic_algorithm.py -p FoodSearchProblem -l trickySearch

and the best heuristic function we found is:

Best solution:   (0, 0, 1, 1, 1, 0)
Best Fitness:    24
Best Cost (number of nodes expanded):    4089
Best solution is made of:       MAX( diagonal_distance,  max_heuristic,  min_heuristic,  )

Test Cases

$ python pacman.py -l trickySearch -p AStarFoodSearchAgent

Path found with total cost of 60 in 1.4 seconds

Search nodes expanded: 4089

Pacman emerges victorious! Score: 570

---

$ python pacman.py -l mediumSearch -p AStarFoodSearchAgent

Was not able to solve it in 30 seconds (i.e. timeout . . .)

---

🚩 Question 8: Suboptimal Search

In this section, we created an agent that always greedily eats the closest dot. Using ClosestDotSearchAgent in searchAgents.py, we implemented a function that finds a path to the closest dot findPathToClosestDot

We used BFS to find the path to the closest dot using AnyFoodSearchProblem as gameState for BFS.

We modified in AnyFoodSearchProblem the function isGoalState to return true if the current state is a food.

Test Cases

$ python pacman.py -l bigSearch -p ClosestDotSearchAgent

Path found with total cost of 350.

Pacman emerges victorious! Score: 2360

---

$ python pacman.py -l mediumSearch -p ClosestDotSearchAgent

Path found with total cost of 171.

Pacman emerges victorious! Score: 1409

---

Contributors 📖

• Charbel Fayad - charbel.fayad01@lau.edu - 202102394
• Manel Roumaissa Benabid - manelroumaissa.benabid@lau.edu - 201906232

License 📄

This project is licensed under the MIT License - see the LICENSE.md file for details