Minimax Algorithm: Tic-Tac-Toe

                   In this blog, we are going to learn about the new algorithm which is 'minimax algorithm' and will have a look at it's pseudo code....

                  Mini-max algorithm is a recursive or backtracking algorithm which is used in decision-making and game theory. It provides an optimal move for the player assuming that opponent is also playing optimally.

                  In this algorithm two players play the game, one is called MAX and other is called MIN.Both the players fight it as the opponent player gets the minimum benefit while they get the maximum benefit.Both Players of the game are opponent of each other, where MAX will select the maximized value and MIN will select the minimized value.The minimax algorithm performs a depth-first search algorithm for the exploration of the complete game tree.The minimax algorithm proceeds all the way down to the terminal node of the tree, then backtrack the tree as the recursion.


Let's have a look on Pseudo-code for MinMax Algorithm:

function minimax(node, depth, maximizingPlayer) is

if depth ==0 or node is a terminal node then

return static evaluation of node


if MaximizingPlayer then      // for Maximizer Player

maxEva= -infinity         

 for each child of node do

 eva= minimax(child, depth-1, false)

maxEva= max(maxEva,eva)        //gives Maximum of the values

return maxEva


else                         // for Minimizer player

 minEva= +infinity 

 for each child of node do

 eva= minimax(child, depth-1, true)

 minEva= min(minEva, eva)         //gives minimum of the values

 return minEva


Following are the properties of Mini-Max algorithm we have seen above:

1.Complete- Min-Max algorithm is Complete. It will definitely find a solution (if exist), in the finite search tree.
2.Optimal- Min-Max algorithm is optimal if both opponents are playing optimally.
3.Time complexity- As it performs DFS for the game-tree, so the time
4.complexity of Min-Max algorithm is O(bm), where b is branching factor of the game-tree, and m is the maximum depth of the tree.
5.Space Complexity- Space complexity of Mini-max algorithm is also similar to DFS which is O(bm).

                    I hope all of this discussion has helped you further understand the minimax algorithm, and perhaps how to dominate at a game of tic tac toe. If you have further questions or anything is confusing, leave some comments and I we'll try to improve the article.