Revision 5a4afd2971e09569cebb28722eeb722b25a50f1b (click the page title to view the current version)

Search

Reading

R&N Chapter 3.1-3.4.

Briefing

  • Problem Solving Agent vs Planning Agent
    • problem solving agent -> atomic representation
  • Goal -> Problem -> Search -> Execution
  • Modelling: State Machine
    • Steates - Transitions; Intial State - Goal; Actions - Action Cost
  • Informed:
    • Best-First Search
    • Redundant Paths
    • Performance
  • Uninformed: Tree Searchs
    • Breadth First
    • Depth First
    • Bidirectional Search

CodinGame challenges

Group work

This is rated as hard, but given that you study AI and this week, we discuss search trees, it should not be too hard.

Team up and discuss how this game can be modelled as a tree and how you can traverse it to maximise Blunder’s loot.

Medium Problems

  1. Don’t Panic — Episode 1 (conditions)
    • You need to help Marvin and his clones (or is it the other way round?) reach the exit in order to help them escape the inside of the Infinite Improbability Drive.
  2. Shadows of the Knight Episode 1 (medium): intervals, binary search
    • Also given in Week 2
    • Batman will look for the hostages on a given building by jumping from one window to another using his grapnel gun. Batman’s goal is to jump to the window where the hostages are located in order to disarm the bombs. Unfortunately he has a limited number of jumps before the bombs go off …
  3. Death First Search - E1
    • You need to assess the opponent’s possibilities, keeping track of multiple possibilities.
  4. Mars Lander — Episode 2 (distances, trigonometry)
    • The goal for your program is to safely land the Mars Lander shuttle, the landing ship which contains the Opportunity rover. Mars Lander is guided by a program, and right now the failure rate for landing on the NASA simulator is unacceptable. This puzzle is the second level of the Mars Lander trilogy. The controls are the same as the previous level but you must now control the angle in order to succeed.

Harder Problems

  1. Don’t Panic — Episode 2 (conditions)
    • Hard. Builds on the previous episode above.
  2. Death First Search - E2
    • Hard. Builds on the previous episode above.
  3. Mars Lander — Episode 3 (distances, trigonometry)
    • Very hard. Builds on the previous episode above.
  4. Shadows of the Knight — Episode 2 (binary search, intervals)
    • Very hard. Builds on the previous episode above.