Game Playing

Types of games

Game Playing Algorithms

Mini-Max Algorithm

The simplest method, just get the minimum value in the minimizer and maximizer in the max node.

Alpha-beta pruning

Alpha-beta pruning is used to reduce the search space, since we don’t need to search all nodes. If there is a node that will prioritize some path, then no need to evaluate other paths.

The way to think for this is that $α$ is the value of the best path for the maximizer along the path to the root, and $β$ is the same thing but for the minimizer.

Example for intuition on pruning

If we have $α$ set to 7 and we get to a minimizer node that has 3 children and we found a value of 3, then there is no need to continue and we should prune because the minimizer here will only give a value that is less than or equal 3, and the maximizer will prefer the path with 7 anyway.

Optimizing alpha-beta for more pruning

To optimize just sort the nodes making the small values on the left of the minimizer and and the large values on the left side of the maximizer. This will help in pruning.