1. Adversarial Search, Minimax, and Alpha-Beta Pruning

So far we’ve only considered problems where there is a single agent, however there are situations where there are other agents which may be there to help (cooperative agent), hinder (adversarial agent), or just there for its own goals.

Game tree

A game tree is a tree where nodes are game states and edges are moves, there are three types of node:

• max nodes: options for max-player
• min nodes: options for min-player
• terminal nodes: final outcomes

Link to original

Minimax

Minimax

Minimax is a decision rule that dictates that you should minimise the possible loss for a worst case (maximum loss) scenario.

Link to original

Example Minimax

Let’s say we have two agents, agent MAX which tries to do the best thing to benefit itself, and an agent MIN which tries to do the worst thing for themselves which would benefit MAX. As such, we can use this information to find the best of the worst outcomes we can get by going down different paths in a game tree.

Hence, the optimal strategy can be found from the minimax of each node. Take for example a game tree as follows:

We propagate the worst value from the min layer:

We can now take the best value from the utility layer which is $3$. It’s a complete and optimal solution to the problem but it’s not particularly efficient. This problem has a time complexity of $O(b^d)$ where $d$ is number of levels and $b$ is the branching factor. While space complexity is $O(b\cdot d)$.

Alpha-Beta Pruning

Alpha-Beta Pruning

Alpha-Beta Pruning applies two optimisations:

• skip rest of MIN children when $\beta \le \alpha$
• skip rest of MAX children when $\beta \le \alpha$

Which are based on two observations of Minimax:

• when some of the children of a MAX node have been evaluated, there is a lower-bound $\alpha$ on how much MAX can get, even if the other children have not been evaluated yet
• when some of the children of a MIN node have been evaluated , there is an upper bound $\beta$ on how much MAX can get, even if the other children have not been evaluated yet

Link to original

Example Alpha-Beta Pruning

Once we found $2$ in the second subtree, we stop searching the rest of the tree as we know that the best worst outcome will be $\ge 3$.

We continue until we exhaust all options.