Write an algorithm in pseudocode (following the style of the Minimax pseudocode) that will always make an optimal decision given the knowledge we have about DeepGreen. You are free to use the library function DeepGreenMove(S) in your pseudocode. How does this compare to Minimax wrt optimality of solution and the number of states explored.

In theory, the optimal strategy for all kinds of games against an intelligent opponent is the Minimax strategy. Minimax assumes a perfectly rational opponent, who also takes optimal actions. However, in practice, most human opponents depart from rationality.

Explanation:

function minimax(node, depth, maximizingPlayer)

           if depth = 0 or node is a terminal node

                  return the utility of the node

           if maximizingPlayer

                  bestValue := ??

           for each child of node

                  v := minimax(child, depth ? 1, FALSE)

                  bestValue := max(bestValue, v)

           return bestValue  

           else (* minimizing player *)

                  bestValue := +?

                  for each child of node

                         v := minimax(child, depth ? 1, TRUE)

                         bestValue := min(bestValue, v)

                  return bestValue