The Alpha Beta Procedure
Alpha beta pruning is a search algorithm that improves the efficiency of minimax algorithm by reducing the number of nodes to be evaluated a tad in the search tree. The minimax procedure explores all the nodes of the search tree, where as alpha beta pruning (using branch and bound techniques) ignores all those nodes that are worse that the nodes evaluated so far. As a result, lot of searching effort is saved. An important characteristic of alpha beta pruning is that it returns the same solution as minimax algorithm would have returned. Moreover, it ignores (prunes or cuts off) those nodes (branches) that does not influence the final solution
Consider that in a game tree, there exist a node 'i' such that a player has choice to move to 'i'. The alpha beta pruning procedure finds out whether the player has a better choice 'b' either at the parent n or at any other node above this level. If a better choice 'b' exists then alpha beta procedure prunes node of 'i' because we have a better choice than 'i' and therefore 'i' is not expanded or evaluated. This results in faster searching.
The alpha beta pruning algorithm maintains two variables '∝' and 'β' for each node that is being examined. The variable '∝' will store the value of the best possible move we can make that we have found so far. On contrary, the variable 'β' will store the value of the best possible move of our opponent can make, that we have computed so far.
At any node, if the value of '∝' becomes greater than or equal to the of value of (∝ > β), then it implies that our opponent's best move will make our position more worse and hence we will prune this move (i.e., this branch is not at all evaluated further).
Algorithm: Alpha beta (Player, board position, ∝, β).
STEP 1: Check the current board position for game completion state. If game over, return the winner.
STEP 2: Set, SUCCESSOR = All possible (legal) moves (nodes) the player can make in the current board position.
STEP 3: If player is 'max' then,
For each node in SUCCESSOR perform the following,
- Set, Score = Alpha_beta (opponent, SUCCESSOR, ∝, β).
This is a recursive call.
- If Score > ∝ , then ∝ = Score.
This means we have found a better move (node).
Therefore, update the value of ∝ to new value. (i.e., score)
- If ∝ > β then, return ∝
This is the cut off' step. Since ∝ ≥ β, it means if we move to this node, our situation will become worsed. Therefore, we will not expand this node, rather we will prune it.
STEP 4: If player is 'min' then
For each node in SUCCESSOR perform the following,
- Set, Score = Alpha_beta (opponent, SUCCESSOR, ∝, β),
This is recursive call.
- If Score < β then set β = Score.
It means opponent has found a better worse move
- If ∝ > = β then, return β,
This is a cut off step. Since ∝ ≥ β we will return β because this is player min's move.
Example: Consider the game of tic-tac-toe in which two players (max and min) make moves alternately such that 'max' will always try to move to a node (in the game tree) which has high value where as 'min' will try to move to a node with-minimum value. Consider a trivial 2 ply game tree for tic-tac-toe given in Fig.
![An Example Tree for Tic-tac-toe Game alpha beta algorithm in AI,alpha beta procedure in AI,AI alpha beta algorithm,exmples of alpha beta algorithm in AI,how to solve tic tac toe using alpha beta procedure of AI,Estudies4you AI,a trivial two ply game treefor tic toc toe,AI minmax procedure steps,Solving Tic tac toe using Minimax Search in AI,Estudies,AI notes,Artificial Intelligence Lecture notes,Artificial intelligence notes,features of ai,uses ofAI,ai notes jntuh,ai lecture notes jntu,AI notes unitwise,ai lecture notes unitwise](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhd5poSI-pdg5-r0k4_Q2qTbhUN2zhMmu1k1Tu9q6IAZS6CjN3DJqfLrEprrZyhx_yavmCObjtjUk9ACI8kfINot2xnEP_yaS9Yr3jFHnV5m3OSHnJrIvB5FT9gy5n2kUadvIIRDWfVrU0/w412-h322/AI-Alpha+beta+algorithm.png)
Fig: An Example Tree for Tic-tac-toe Game
The alpha beta procedure will search the given game tree as follows,
STEP 1: The initial value of ∝ and β of the root node will be set to -∞ and +∞ respectively. Then, the first leaf node is expanded, that gives value '5'. Since, 'M1' is a 'min' node its 'β' value is set to 5.
![An Example Tree for Tic-tac-toe Game alpha beta algorithm in AI,alpha beta procedure in AI,AI alpha beta algorithm,exmples of alpha beta algorithm in AI,how to solve tic tac toe using alpha beta procedure of AI,Estudies4you AI,a trivial two ply game treefor tic toc toe,AI minmax procedure steps,Solving Tic tac toe using Minimax Search in AI,Estudies,AI notes,Artificial Intelligence Lecture notes,Artificial intelligence notes,features of ai,uses ofAI,ai notes jntuh,ai lecture notes jntu,AI notes unitwise,ai lecture notes unitwise](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj8FecZsOdu0GN_Vewp6L2fj6Ap62bptX9qUsKQQZD4VNNCYiv9EVCkSvlN98BAwZ4qR-4ui8W6ekY_lAkYwF5NNSeKRx_4AqM_u3NKRVXc5GD9K6JHQi1WsbSC6zXAsjrwxbuQzMroVVM/w292-h371/AI-Alpha+beta+algorithm.png)
![An Example Tree for Tic-tac-toe Game alpha beta algorithm in AI,alpha beta procedure in AI,AI alpha beta algorithm,exmples of alpha beta algorithm in AI,how to solve tic tac toe using alpha beta procedure of AI,Estudies4you AI,a trivial two ply game treefor tic toc toe,AI minmax procedure steps,Solving Tic tac toe using Minimax Search in AI,Estudies,AI notes,Artificial Intelligence Lecture notes,Artificial intelligence notes,features of ai,uses ofAI,ai notes jntuh,ai lecture notes jntu,AI notes unitwise,ai lecture notes unitwise](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjjZxrxIIwaiLLY9qyflCIzwWUsFaxV4S3lP6I2mg_g3yyWIYUOiXLdaK0GwSiW6v2MfL_GBFAzRoSWxHvviSandGLUcPWbfnKL2HhwCz6Mb1qeCjTrLLz43V_UMdEHpHFkOIIAv88RDes/w268-h354/AI-Alpha+beta+algorithm.png)
![An Example Tree for Tic-tac-toe Game alpha beta algorithm in AI,alpha beta procedure in AI,AI alpha beta algorithm,exmples of alpha beta algorithm in AI,how to solve tic tac toe using alpha beta procedure of AI,Estudies4you AI,a trivial two ply game treefor tic toc toe,AI minmax procedure steps,Solving Tic tac toe using Minimax Search in AI,Estudies,AI notes,Artificial Intelligence Lecture notes,Artificial intelligence notes,features of ai,uses ofAI,ai notes jntuh,ai lecture notes jntu,AI notes unitwise,ai lecture notes unitwise](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj3Mne_bKDqb4hvC4n-OjWxK5uHQDlwSJtBn8cySY3T5txRZ6PNTT-gVtdYP1KaL0-pYLUvtpKGNqueDbKlzwypIb-GWLaE-wCG5UXar1jrT78QgCHGlNgqTMHN64r6Ya5zkTEk3xEo2DE/w306-h352/AI-Alpha+beta+algorithm.png)
![An Example Tree for Tic-tac-toe Game alpha beta algorithm in AI,alpha beta procedure in AI,AI alpha beta algorithm,exmples of alpha beta algorithm in AI,how to solve tic tac toe using alpha beta procedure of AI,Estudies4you AI,a trivial two ply game treefor tic toc toe,AI minmax procedure steps,Solving Tic tac toe using Minimax Search in AI,Estudies,AI notes,Artificial Intelligence Lecture notes,Artificial intelligence notes,features of ai,uses ofAI,ai notes jntuh,ai lecture notes jntu,AI notes unitwise,ai lecture notes unitwise](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhL7ahcPb-htte4QPjYvsI_YXhusez8pMODcikOkQhDDmWUTD6CZzVJoo8qond97O67SnSJuCPI5DsW8_pm7mlNA1_OM-K7tL5tCFzwcAcWhwLDEuBjjokf3NNGxL2VBkj5NgAJURHOdoI/w320-h243/AI-Alpha+beta+algorithm.png)
![An Example Tree for Tic-tac-toe Game alpha beta algorithm in AI,alpha beta procedure in AI,AI alpha beta algorithm,exmples of alpha beta algorithm in AI,how to solve tic tac toe using alpha beta procedure of AI,Estudies4you AI,a trivial two ply game treefor tic toc toe,AI minmax procedure steps,Solving Tic tac toe using Minimax Search in AI,Estudies,AI notes,Artificial Intelligence Lecture notes,Artificial intelligence notes,features of ai,uses ofAI,ai notes jntuh,ai lecture notes jntu,AI notes unitwise,ai lecture notes unitwise](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi8lx6jVB20q-lDp9oajjMFPhplHVsi_f3hNft8t4a8jleTacU3CAoIflBXK0gfje-4UyT7xqXBMFoWgwgXssyGU68k3t5PEGl8Ro7DtH8rNewazWGM48IQcdPlfFuHOIKBMoE7BGD6UBQ/w513-h298/AI-Alpha+beta+algorithm.png)
The minimax algorithm would have explored the whole game tree to search the best strategy. However, alpha_beta pruning algorithm have reduced the number of nodes to be evaluated. Moreover, it is observed that alpha_beta pruning will reduce the exponential complexity of minimax algorithm to half.