Revision ead1f42777dc71e983cfed0af872555ede7cc4b0 (click the page title to view the current version)


Changes from ead1f42777dc71e983cfed0af872555ede7cc4b0 to current

title: Search
categorie: session

# Reading

R&N Chapter 3.1-3.4. 
If the text is overwhelming, 
please use the briefing keywords below to guide your reading.

# Briefing

+ Problem Solving Agent vs Planning Agent
    - problem solving agent -> atomic representation
    - planning agents out of scope for now
+ Modelling: **State Machine**
    - Steates - Transitions; Intial State - Goal; Actions - Action Cost
    - Goal -> Problem -> Search -> Execution
+ Informed: the solution can be found without action, and then excecute without further 
    -  Best-First Search
    -  Redundant Paths
    -  Performance
+ Uninformed (Tree Searches): the agent has to act to gather enough information to find
  the goal.
    - Breadth First
    - Depth First 
    - Bidirectional Search
+ **Challenge** find a good model of states

# Group Work Exercises

The first two exercises are taken from the
[AIMA Exercises](,
and the third one from CodinGame.
Please discuss them in groups.

## 2.4

For each of the following assertions, say whether it is true or false and 
support your answer with examples or counterexamples where appropriate.

1. An agent that senses only partial information about the state cannot 
be perfectly rational.
2. There exist task environments in which no pure reflex agent can behave 
3. There exists a task environment in which every agent is rational.
4. The input to an agent program is the same as the input to the agent 
5. Every agent function is implementable by some program/machine 
6. Suppose an agent selects its action uniformly at random from the set 
of possible actions. There exists a deterministic task environment in 
which this agent is rational.
7. It is possible for a given agent to be perfectly rational in two 
distinct task environments.
8. Every agent is rational in an unobservable environment.
9. A perfectly rational poker-playing agent never loses.

## 3.2

Give a complete problem formulation for each of the following problems. 
Choose a formulation that is precise enough to be implemented.

1. There are six glass boxes in a row, each with a lock. Each of the 
first five boxes holds a key unlocking the next box in line; the last box 
holds a banana. You have the key to the first box, and you want the 
2. You start with the sequence ABABAECCEC, or in general any sequence 
made from A, B, C, and E. You can transform this sequence using the 
following equalities: AC = E, AB = BC, BB = E, and Ex = x for any x. For 
example, ABBC can be transformed into AEC, and then AC, and then E. Your 
goal is to produce the sequence E.
3. There is an n×n grid of squares, each square initially being either 
unpainted floor or a bottomless pit. You start standing on an unpainted 
floor square, and can either paint the square under you or move onto an 
adjacent unpainted floor square. You want the whole floor painted.
4. A container ship is in port, loaded high with containers. There 13 
rows of containers, each 13 containers wide and 5 containers tall. You 
control a crane that can move to any location above the ship, pick up the 
container under it, and move it onto the dock. You want the ship unloaded.

## Blunder at CodinGame

+ [Blunder Episode 2](

This is rated as **hard**, but given that you study AI and this week,
we discuss **search trees**, it should not be too hard, but **please**
do the modelling before you try coding.

Team up and discuss how this game can be modelled as a state machine,
how the states can be organised as a tree, and finally how you can traverse
the tree, maximising Blunder's loot.

When you have a good model, you can code up the solution.

# CodinGame challenges

There are plenty more relevant problems on CodinGame.

## Medium Problems

1.  [Don't Panic --- Episode 1]('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.
1. [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 
4.  [Death First Search - E1](
    + You need to assess the opponent's possibilities, keeping track
      of multiple possibilities. 
3.  [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]('t-panic-episode-2) (conditions)
    + Hard.  Builds on the previous episode above.
4. [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.
1.  [Shadows of the Knight --- Episode 2]( (binary search, intervals)
    + Very hard.  Builds on the previous episode above.