Week 9 Flashcards
What are the different possible types of game?
Deterministic/Stochastic
How many players?
Zero-Sum/Non-zero-sum
Perfect/Imperfect Information
What is a Utility Function?
Defines the final numeric value for a game that ends in terminal state S for a player P.
Best achievable utility is the value of a state.
What is the Minimax value of a node?
Utility of the terminal state to which both players play optimally from that node.
One player maximises their utility, another tries to minimise.
Found in Adversarial search.
What is Alpha-beta pruning?
Let a be the value max can get at least.
When computing min value at n, if we find the value of n will not be greater than a, we stop exploring current nodes children.
What are the properties of Alpha-beta pruning?
Pruning has no effect on minimax value for the root.
Effectiveness improved by good child ordering.
