===== Lab: Search =====

==== Before the lab ====

  * **Reading:**
    * AIMA: **Chapter 3 - Solving Problems by Searching**. Focus on problem formulation, graph-search concepts, the main uninformed and informed search strategies, and the assumptions behind their completeness and cost optimality.
  * **Technical preparation:**
    * Open today's notebook and run all setup cells and the first code cell in **Segment 1** to verify that the notebook works in your environment. __You should obtain a simplified visualization of the Romania map.__

==== Q&A ====

  - What assumptions does the Romania route-finding problem make about the map, road costs, and the effects of travelling along a road? Which real-world changes would require replanning?
  - Which details should be included in the state, and which should be abstracted away? When would "current city" cease to be a sufficient state representation?
  - Why does BFS permit an early goal test, while UCS normally tests for a goal only when a node is removed from the frontier?
  - What makes a heuristic useful? How can a more aggressive heuristic reduce search effort while weakening theoretical guarantees?

==== Notebook ====

**Notebook:** [[https://colab.research.google.com/drive/1XfX_rELHLTst58bI73dgcysG7RsFLIYk?usp=sharing|HCAI_Lab_Search.ipynb]] (Work in Google Colab or download the .ipynb file to local environment)

Work in groups of 2-4. Every group member must be able to explain the results.

==== Challenge ====

Work in groups of **2–4** to protect a network in [[https://www.codingame.com/training/medium/death-first-search-episode-1|Death First Search - Episode 1]].

An agent is moving through the network towards one of several gateways. In each turn, your program must remove one connection to stop the agent from escaping.

Begin with a simple working strategy. Then make it smarter: Which gateway poses the greatest immediate risk? Which path is the agent likely to follow? Should you cut the final connection to a gateway or intervene earlier? Can a locally sensible decision create a worse situation in the next turn?

Use graph search to guide these decisions, and consider situations in which a simple greedy strategy may fail.

Start the challenge during the lab and continue it as part of the **self-study regarding classes**.
Groups that complete Episode 1 may continue with [[https://www.codingame.com/training/hard/death-first-search-episode-2|Death First Search — Episode 2]].
Selected groups may share their strategies at the next lab, and effective solutions may receive bonus points.

==== Learn more! ====

  * [[https://www.redblobgames.com/pathfinding/a-star/introduction.html|Introduction to the A* Algorithm from Red Blob Games]] -- an interactive comparison of BFS, UCS/Dijkstra, and A*