L9: Monte Carlo Tree Search, Current AI, Timeline Overview

Question 1

How does Monte Carlo Tree Search work?

Answer 1

Use sampling to evaluate game tree. Replace evaluation function with random playouts. Only partially explores game tree (balance exploration and exploitation)

Question 2

Steps of Monte Carlo Tree Search

Answer 2

1. Leaf selection (find promising leaf, balancing exploration and exploitation)
2. Leaf expansion (add new node to selected leaf)
3. Simulation (random playout till game end- note if node already end of play then just skip to 4)
4. Backpropagation (update node values based on simulation result- in examples update with +/-1 for each player if we won and don’t update q() at all if we lose-only n)

Question 3

What is the formula for the Upper Confidence Bound for Trees (UCT)?

Answer 3

From node v select child u such that that
u = argmax per child w (q(w)/n(w) + C*sqrt(ln(n(v))/n(w))
First part is avg. score, second part is penalty for frequently visited nodes. So make c bigger to prioritise exploration and smaller to prioritise exploitation. C often = 2

If n(w) = 0 then just choose that child to prevent division by zero

Question 4

Can you do question on slide 60?

Answer 4

Yes?

Question 5

Describe the two move selection methods

Answer 5

Max child: Select child w of root v that maximises q(w)/n(w)

Robust child: Select child w of root v that maximises n(w)- child explored the most

Question 6

Name some possible MCTS extensions

Answer 6

• Pruning heuristics
• Non-uniform playouts
• Replacing with evaluation function
• Game simplification
• Incorporating deep learning techniques

Question 7

Describe the developments in AI during the 1990s and 2000s

Answer 7

Increased computing power had several consequences:
* “Old” methods were finally getting the power they needed
For example Kasparov vs. Deep Blue
* Approximate expensive methods were becoming “good enough” (Monte Carlo methods in general, Heuristic optimisation methods (genetic algorithms, ant colony optimisation, etc))
* Existing methods were becoming practical enough to embed in applications.- “Expert systems” now just one of many functionalities embedded in MS Excel

Question 8

What s the deep learning revolution?

Answer 8

Took place in 2010s.
* GPU-accelerated neural nets enable practical deep learning
* Specialised neural net topologies successful on certain tasks
* Convolutional neural nets for images and video
* LSTM networks for handwriting, speech, temporal data
* Initially fueled by availability of “big data”
* Combination with reinforcement learning breakthrough in dynamic setting