Week 2 - Search with A* & MCTS

Question 1

Intelligent agents

Answer 1

Perceive environments and act.

Fully/partial observable
Deterministic/Stochastic
Episodic/Sequential
Static/dynamic
Discrete/continuous

Question 2

Static agents vs Learning

Answer 2

Static have all info at start.
Learning learn.

Question 3

Breadth First

Answer 3

Expand all nodes before moving on to next layer

Question 4

Uniform cost search

Answer 4

Expand node with lowest path cost.

Question 5

Depth first search

Answer 5

Always expand the deepest node.

Could lower exploration though.

Question 6

Bidirectional Search

Answer 6

Search from both the initial and goal state, hoping that they meet in the middle.

Question 7

Informed (Heuristic) Search

Answer 7

Use an estimate for the cost of current state to the goal.

Eg a navigation heuristic from Loughborough to Edinburgh might be going north.

Question 8

A* Search

Answer 8

Combines the cost to get to a node with estimated cost to goal.

f(n) = g(n) + h(n)
(g is cost from initial to current)
(h is estimate to goal)

Question 9

A* Search Conditions for optimality

Answer 9

h(n) must be an admissible heuristic (never overstimate)
Consistency: estimated cost cannot increase

Question 10

When is each (tree/graph) version of A* optimal?

Answer 10

Tree - if h(n) admissible
Graph - if h(n) is consistent

Question 11

A* search always expand the… (cost)

Answer 11

lowest overall cost

Question 12

MIN MAX

Answer 12

MAX step tries to maximise score
MIN tries to minimise max’s score.

DOUBLE CHECK UNDERSTANDING
Max tries to maximise the worst case outcome

Question 13

Alpha beta pruning

Answer 13

Pruning (avoiding) branches that will not be explored.

Faster

Question 14

MCTS

Answer 14

Monte Carlo Tree Search

Question 15

MCTS:

Answer 15

Explores the tree using a stochastic process (Monte Carlo - casinos) when the tree is too large to explore - even with pruning.

Question 16

MCTS: Four main phases

Answer 16

Selection
Expansion
Simulation
Backpropagation

Question 17

MCTS: Selection Phase

Answer 17

Algorithm chooses a node to expand.

Upper Confidence Bound is used to balance exploration and exploitation
see slides for expression

Question 18

MCTS: Expansion Phase

Answer 18

Node is expanded by adding child nodes.

Can be guided by heuristic or random.

Question 19

MCTS: Simulation Phase

Answer 19

SImulate random game outcomes until terminal condition.

Allows to quickly reach the end of the game

Question 20

MCTS: Backpropagation

Answer 20

Result is used to update statistics for the tree “backwards”.

Question 21

Supervised Learning

Answer 21

Examples of correct behaviour provided.

Question 22

Unsupervised Learning

Answer 22

Data is analysed to extract properties

Question 23

Self-supervised Learning

Answer 23

Model learns to reconstruct part of the data so that correlations and strcutures are learnt.

Question 24

Reinforcement Learning

Answer 24

System learns by rewards

Question 25

Best first search

Answer 25

f(n) = h(n)