Question

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.

Answer 1

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:

• In game theory, minimax is a decision rule used to minimize the worst-case potential loss; in other words, a player considers all of the best opponent responses to his strategies, and selects the strategy such that the opponent's best strategy gives a payoff as large as possible.
• The pseudocode is given below :

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