1 Introduction in this assignment, you will implement uninformed search algorithms. 2 Multi-Agent Pac-Man In this assignment, we referred to Multi-Agent Pac-Man project(http://stanford.edu/-cpiech/cs221/ homework/prog/pacman/pacman.html) from Stanford University. We will use the file attached in KUMS Don't forget to use Python 3.6 when scripting your code. 3 Project Instruction 3.1 Breadth-first-search Breadth first search is an search algorithm that traverses tree like data structure exploring the neighbor nodes first. Sequence of exploring tree is explained in picture below. 6 8 10 11 12 Figure 1: Sequence of exploring tree with BFS Breadth-first-search can be implemented with a queue. By putting neighbor nodes of current mode into a queue and exploring next node with queue sequence, we can explore the neighbor nodes first. 3.2 Depth-first Search(DFS) 12 10 11 Figure 1: Sequence of exploring tree with DFS. Depth first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking. 3.3 What to do You should implement BFS and DFS algorithm in order to get Pac-man to the goal. Pac-man can move in four directions which are "North", "South', 'East', and 'West (Stop is not considered). Legal actions that Pac-man can take depends on Pac-man's situation. For example, if East and South side of Pac-man is blocked by will, legal-actions are "North' and 'west'. So, considering legal-action as a node, visit unexplored area in BFS and DFS order and reach to the goal. Figure 2: Example Tree of legal actions of Pac-man While exploring tree, please visit neighbor node in East, West, South, North order and print the sequence of x,y coordinate that Pac-man first visit in result bet file. Starting location of Pac-man is considered to be (0,0) 3.4 What to Submit Please submit searchAgents.py file only. Any late submissions will not be accepted. 3.5 How to Run the Code To try out the Pac-man, run pacman.py from the command line. This agent will just stop at every action If you implement search agent, the agent will move appropriately to search food. python pacman.py To activate the BFSAgent, use-p BFSAgent: python pacman.py -p BFSAgent To activate the DFSAgent, use-p DFSAgent: python pacman py-pDFSAgent 2 To run Pac-man with no graphic, use -q python pacman.py -p DFSAgent -q Note: If you use Macbook and the above codes do not work for you, try these ones: python3 pacman.py To activate the BFSAgent, use -p BFSAgent: python3 pacman.py -p BFSAgent To activate the DFSAgent, use -p DFSAgent: python3 pacman.py -p DFSAgent To run Pac-man with no graphic, use -q python3 pacman.py -p DFSAgent -q