CSSE 413: Day 2

Outline

• Searching a fundamental tool in AI
• Formalizing a problem
• States
• State Space
• State spaces as graphs
• Avoiding repeated states
• Uninformed search methods
  • Breadth-first algorithm
  • Depth-first search algorithm
  • General graph search algorithm (from Nilson "Principles of AI")
• Introduction to the term project: Pac-Man

Materials

• Search animations.
  • Blue colored nodes: Explored already or repeat state.
  • Yellow colored node: Not explored yet.
  • Green colored node: Not explored yet and next.
  • Left box below state: Number of moves so far.
  • Right box below state: Not used yet.
  • Lowest box: Order of exploration.
• Wikipedia entry on Pac-Man
• Online Pac-Man
• Python Tutorial