Alpha Beta Pruning in Minimax Algorithm
Sign up for FREE 1 month of Kindle and read all our books for free.
Reading time:
Like we discussed in earlier article, a hard coded AI can be used to create an intelligent opponent which you can challenge to a game of classical tictactoe!
But, that algorithm could still be optimised further. But how do we achieve that? The Alpha Beta Pruning is a search algorithm that tries to diminish the quantity of hubs that are assessed by the minimax algorithm in its search tree. It is an antagonistic search algorithm utilized usually for machine playing of twoplayer recreations (Tictactoe, Chess, Go, and so forth.).
It stops totally assessing a move when no less than one probability has been observed that ends up being more regrettable than a formerly analyzed move. Such moves require not be assessed further. At the point when connected to a standard minimax tree, it restores an indistinguishable move from minimax would, however prunes away branches that can't in any way, shape or form impact an official conclusion!
You must be thinking what does this figure really signifies. Well, it shows how the alogorithm ignores the sub trees which are not really desireable in our game moves. The algorithm keeps up two qualities, alpha and beta, which speak to the base score that the expanding player is guaranteed of and the greatest score that the limiting player is guaranteed of separately. At first alpha is negative infinity and beta is sure infinity, i.e. the two players begin with their most exceedingly terrible conceivable score. At whatever point the most extreme score that the limiting player(beta) is guaranteed of turns out to be not as much as the base score that the expanding player(alpha) is guaranteed of (i.e. beta <= alpha), the augmenting player require not consider the relatives of this hub as they will never be come to in genuine play.
Algorithm
Note :

Alpha Beta Pruning is not a new algorithm but actually an optimization!

Alpha is the best value that the maximizer currently can guarantee at that level or above.

Beta is the best value that the minimizer currently can guarantee at that level or above.
And ofcourse, we are using Tic Tac Toe as our reference example!
def minimax(depth, player, alpha, beta)
if gameover or depth == 0
return calculated_score
end
children = all legal moves for player
if player is AI (maximizing player)
for each child
score = minimax(depth  1, opponent, alpha, beta)
if (score > alpha)
alpha = score
end
if alpha >= beta
break
end
return alpha
end
else #player is minimizing player
best_score = +infinity
for each child
score = minimax(depth  1, player, alpha, beta)
if (score < beta)
beta = score
end
if alpha >= beta
break
end
return beta
end
end
end
#then you would call it like
minimax(2, computer, inf, +inf)
Complexity
 Worst case Performance :
O(E) = O(b^(d/2))
 Worst case space complexity :
O(V) = O(b * d)
Implementations
 Next Best Move Guesser Python
Interactive console game Python
import numpy as np import sys from copy import copy rows = 3 cols = 3 board = np.zeros((rows,cols)) inf = float("inf") neg_inf = float("inf") def printBoard(): for i in range(rows): for j in range(cols): if board[i, j] == 0: sys.stdout.write(' _ ') elif board[i, j] == 1: sys.stdout.write(' X ') else: sys.stdout.write(' O ') print '' # The heuristic function which will be evaluating board's position for each of the winning POS heuristicTable = np.zeros((rows+1, cols+1)) numberOfWinningPositions = rows + cols + 2 for index in range(rows+1): heuristicTable[index, 0] = 10**index heuristicTable[0, index] =10**index winningArray = np.array([[0, 1, 2], [3, 4, 5], [6, 7, 8], [0, 3, 6], [1, 4, 7], [2, 5, 8], [0, 4, 8], [2, 4, 6]]) def utilityOfState(state): stateCopy = copy(state.ravel()) heuristic = 0 for i in range(numberOfWinningPositions): maxp = 0 minp = 0 for j in range(rows): if stateCopy[winningArray[i,j]] == 2: maxp += 1 elif stateCopy[winningArray[i,j]] == 1: minp += 1 heuristic += heuristicTable[maxp][minp] return heuristic def minimax(state,alpha,beta,maximizing,depth,maxp,minp): if depth==0: return utilityOfState(state),state rowsLeft,columnsLeft=np.where(state==0) returnState=copy(state) if rowsLeft.shape[0]==0: return utilityOfState(state),returnState if maximizing==True: utility=neg_inf for i in range(0,rowsLeft.shape[0]): nextState=copy(state) nextState[rowsLeft[i],columnsLeft[i]]=maxp #print 'in max currently the Nextstate is ',nextState,'\n\n' Nutility,Nstate=minimax(nextState,alpha,beta,False,depth1,maxp,minp) if Nutility > utility: utility=Nutility returnState=copy(nextState) if utility>alpha: alpha=utility if alpha >=beta : #print 'pruned' break; #print 'for max the best move is with utility ',utility,' n state ',returnState return utility,returnState else: utility=inf for i in range(0,rowsLeft.shape[0]): nextState=copy(state) nextState[rowsLeft[i],columnsLeft[i]]=minp #print 'in min currently the Nextstate is ',nextState,'\n\n' Nutility,Nstate=minimax(nextState,alpha,beta,True,depth1,maxp,minp) if Nutility < utility: utility=Nutility returnState=copy(nextState) if utility< beta: beta=utility if alpha >=beta : #print 'pruned' break; return utility,returnState def checkGameOver(state): stateCopy=copy(state) value=utilityOfState(stateCopy) if value >=1000: return 1 return 1 def main(): num=input('enter player num (1st or 2nd) ') value=0 global board for turn in range(0,rows*cols): if (turn+num)%2==1: #make the player go first, and make the user player as 'X' r,c=[int(x) for x in raw_input('Enter your move ').split(' ')] board[r1,c1]=1 printBoard() value=checkGameOver(board) if value==1: print 'U win.Game Over' sys.exit() print '\n' else: #its the computer's turn make the PC always put a circle' #right now we know the state if the board was filled by the other player state=copy(board) value,nextState=minimax(state,neg_inf,inf,True,2,2,1) board=copy(nextState) printBoard() print '\n' value=checkGameOver(board) if value==1: print 'PC wins.Game Over' sys.exit() print 'Its a draw' if __name__ == "__main__": main()
Applications
Its major applications are in game of chess. Stockfish (chess) is a C++ open source chess program that implements the Alpha Beta pruning algorithm. Stockfish is a mature implementation that is rated as one of the strongest chess engines available today as evidenced by it winning the Top Chess Engine Championship in 2016 and 2017.
One more interesting thing to notice is that implementations of alphabeta pruning can often be delineated by whether they are "failsoft," or "failhard." The pseudocode illustrates the failsoft variation. With failsoft alphabeta, the alphabeta function may return values (v) that exceed (v < Î± or v > Î²) the Î± and Î² bounds set by its function call arguments. In comparison, failhard alphabeta limits its function return value into the inclusive range of Î± and Î².
Questions
What is the depth of a standard tictactow game?
Further Reading

Application of this pruning in Negamax algo: Research Paper by Ashraf M. Abdelbar

Detailed semantics by Donald E. Knuth and Ronald W. Moore