Games
-
Game Trees
-
Minimax: Assumes players play optimally
-
Expectimax: Assume opponent play randomly, value calculated is strictly larger than Minimax
-
Pruning
-
\(\alpha\): MAX’s best option on path to root / minimum value that MAX is assured of
\(\beta\): MIN’s best option on path to root / maximum value that MIN is assured of
-
In the maximizer, any value that's more than \(\beta\) will be disregarded by its parent minimizer
When we see a \(v \geq \beta\) in MAX, we know that MAX's value will be no less than \(\beta\) and
will be ignored, so no further evaluation is needed
-
In the minimizer, any value that's less than \(\alpha\) will be disregarded by its parent maximizer
When we see a \(v \leq \alpha\) in MIN, we know that MIN's value will be no more than \(\alpha\) and
will be ignored, so no further evaluation is needed
-
Utilities
-
Utility of an action = expected value of an action
-
Agent can be risk-neutral, risk-adverse, risk-seeking depending on its preferred action
