Expectimax Search
Minimax assumes an optimal (adversarial) opponent. However, most of the time, an opponent will not play optimally. In that case, we can use Expectimax search (also known as Expectiminimax).
We replace MIN nodes with CHANCE nodes that compute an expected value over outcomes weighted by probability .
Mixed Layer Types
Different node types (MIN, MAX, CHANCE) can be mixed in a flexible way to represent different game scenarios.
For example, a game tree for Backgammon would look like this:
Monte Carlo Tree Search
Monte Carlo Tree Search (MCTS) is an anytime algorithm used to approximate the true expected utility of a state. It is used when a game tree is too large to fully evaluate. It is especially useful as it is not vulnerable to a poor evaluation function.
Given a leaf on the game tree, we might want to evaluate the expected score to know if its worth proceeding down that path, without having to fully calculate all possible proceeding positions.
MCTS finds an empirical estimate for the state, by simulating many potential games from that position to the terminal state. It runs a repeated loop in the allocated time with four distinct phases.
| Phase | Process |
|---|---|
| Selection | Descend the tree picking children that balance being promising and being under-explored. |
| Expansion | Extend tree by adding a new child node. |
| Simulation | Play out randomly (or with a cheap policy) to a terminal state. |
| Back-propagation | Propagate the win/loss result up the path, updating wins/visits for every ancestor. |
UCB1 Formula
The UCB1 formula balances exploitation and exploration to select which child node to visit next.
- wins
- # of simulations, # of simulations of parent
- balancing factor/exploration constant
The final chosen action is the action whose node has the highest number of rollouts (not win rate). Win-rate, as a selection criteria, can be fluked from a few runs, and its observed that more rollouts naturally leads to a higher win rate from the UCB1 formula.
Recap of Probability
Agents need to be prepared for a level of uncertainty in their environment. Probabilistic reasoning is used as a framework for managing our beliefs and knowledge of the environment, given uncertainty.
- Evidence — what agent knows about the world
- e.g. sensor readings or symptoms
- Unknown variables — hidden aspects agent must reason about
- e.g. where an object is or what disease is present
- Model — mathematical rules linking evidence to unknown variables
- e.g. how likely is an object’s position given some sensor readings
Summary of Core Probability Concepts
Random Variables — something we are uncertain about
Probability Distributions — table of probabilities of values for a random variable
Joint Distributions — tracks combinations of multiple variables simulatenously
Event — a set of outcomes
Marginalisation — combine collapsed rows by adding
Conditional Distribution — probability distributions over some variables given fixed values for others
Inference by Enumeration
Inference by enumeration is a brute-force mathematical method used to answer probabilistic queries about a system by systematically calculating and summing terms from a full joint distribution table.
All random variables are categorised into three groups:
- Query Variable () — value you want to find probability distribution for
- Evidence Variables () — observed variables you already know
- Hidden Variables () — other unknown variables