NETGAMES: MinMax

MinMax is a Search Algorithm.

MinMax(Player, Depth)
{
   if ( Depth == 0 )
     return Evaluation(Position)

   Generate_Moves(Player)

   Best_Score = -INFINITE

   while ( Get_Next_Move(Move) )
   {
     Make_Move(Move)

     Score = -MinMax(-Player, Depth - 1)

     UnMake_Move(Move)

     if ( Score > Best_Score )
       Best_Score = Score
   }

   return Best_Score
}

B = Branching Factor = Average Moves by Position
D = Depth
T = Total Searched Positions

T = B ^ D

This Algorithm makes to play players alternately all their legal moves.

First player searches for the move that gives him the highest score (Max-Side).

Second player searches for the move that gives him the lowest score (Min-Side).

This tree shows that the Score should be 10 after optimal game.