Alpha Beta Pruning Algorithm Assignment Help
Alpha beta pruning is a search algorithm which seeks to decrease the number of nodes which are examined through the minimax algorithm in within it's search tree.
The minimax algorithm is a method of finding an optimal move inside a two player game. Alpha-beta pruning is a method of locating the optimal minimax solution while avoiding searching subtrees associated with moves which won't be selected. Within the search tree for a two-player game, there are two types of nodes, nodes symbolizing your moves as well as nodes symbolizing your opponent's moves. Nodes symbolizing your moves are usually drawn as squares (or even possibly upward pointing triangles):
They are also known as MAX nodes. The objective in a MAX node would be to maximize the value of the subtree rooted from which node. To do this, a MAX node selects the child with the greatest value, and that becomes the value of the MAX node
Nodes symbolizing your opponent's moves are usually drawn as circles (or even possibly as downward pointing triangles):
They are also known as MIN nodes. The objective in a MIN node would be to minimize the value of the subtree rooted from which node. To do this, a MIN node selects the child using the least (smallest) value, and that becomes the value from the MIN node.
Alpha-beta pruning gets its name from two bounds which are passed together throughout the calculation, which restrict the set associated with possible solutions in line with the portion from the search tree. Specifically,
β- Beta is the minimum upper bound of possible solutions
α- Alpha is the maximum lower bound of possible solutions
Therefore, whenever any kind of new node has been regarded as a possible path towards the solution, it can only work if: α ≤ Ν ≤ β
Where N is the current estimate of the value from the node.