| Next revision | Previous revision |
| courses:hcai:lab_search [2026/09/29 08:24] – created kkt | courses:hcai:lab_search [2026/09/29 21:27] (current) – [Challenge] kkt |
|---|
| * 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. | * 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:** | * **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. | * 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 ==== | ==== Q&A ==== |
| |
| - What assumptions make a fixed sequence of actions an adequate solution? What would change if the environment were nondeterministic or partially observable? | - 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? |
| - Consider route finding. 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? | - 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? | - 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? | - What makes a heuristic useful? How can a more aggressive heuristic reduce search effort while weakening theoretical guarantees? |
| ==== Notebook ==== | ==== Notebook ==== |
| |
| **Notebook:** [[https://colab.research.google.com/drive/1XfX_rELHLTst58bI73dgcysG7RsFLIYk?usp=sharing|HCAI_Lab_Search.ipynb]] (Open in Google Colab or download the .ipynb file to local environment) | **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. Running the cells alone is not sufficient for checkpoint credit. | Work in groups of 2-4. Every group member must be able to explain the results. |
| |
| ==== Challenge ==== | ==== Challenge ==== |
| |
| Work in groups of **2–4** on [[https://www.codingame.com/training/medium/death-first-search-episode-1|Death First Search - Episode 1]]. | 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]]. |
| |
| Your program must represent a changing network as a graph and remove one edge in each turn to prevent the moving agent from reaching a gateway. | 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. |
| |
| Start by implementing a valid baseline strategy. Then improve it using BFS or another suitable graph-search algorithm. Pay particular attention to: | 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? |
| - representing and updating the graph; | |
| - selecting a gateway or path to defend; | |
| - choosing which edge to remove; | |
| - identifying situations in which a locally reasonable strategy may fail. | |
| |
| The challenge is intended to be started during the lab and completed as part of the **self-study regarding classes**. | Use graph search to guide these decisions, and consider situations in which a simple greedy strategy may fail. |
| |
| 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 briefly present their strategies and results at the beginning of the next lab. Particularly effective solutions may receive bonus points. | 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! ==== | ==== Learn more! ==== |