World's most popular travel blog for travel bloggers.

# [Answers] Evaluation functions of Minimax algorithm

, ,
Problem Detail:

Let's say we have the following relationship between $f_1$ and $f_2$:

$$f_2(s) = \sqrt{1 + f_1(s)}$$

And $f_1$ returns a positive value. Why is it that minimax search using $f_2$ is guaranteed to the same action as using $f_1$ but is not guaranteed to return the same action as $f_1$ when used in expectimax search?

I understand that expectimax takes into account the weight of the arcs to compute the possible path. But I am still not able to understand how the aforementioned conclusion is being made.

An example for Expectimax (root node is a Max node):

(image from CSE AI Faculty / Dan Klein, Stuart Russell, Andrew Moore)

changing the evaluation function changes the action taken.

For Minimax, since $f_1(s_i) \ge f_1(s_j) \implies f_2(s_i) \ge f_2(s_j)$, the best node (action taken) doesn't change (Minimax is insensitive to monotonic transformations):