Explain alpha-beta pruning.

·         The problem with minimax search algorithm is that the no. of game states it has to examine, is exponential in the no. of moves.

·         α- β proposes to compute the correct minimax algorithm decision, without looking at every node in the game tree.

Steps in α- β pruning:

·         MAX player cuts off search when he knows MIN player can force a provably bad outcome.

·         MIN player cuts off search when he knows MAX player can force a provably good outcome.

·         Applying an alpha cutoff means we stop search of a particular branch, because we see that we already have a better opportunity elsewhere.

·         Applying a beta cutoff means we stop search of a particular branch, because we see that the opponent already has a better opportunity elsewhere.

    ·         Applying both forms is called α- β pruning.