World's most popular travel blog for travel bloggers.

[Answers] Evaluation functions of Minimax algorithm

, , No Comments
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.

Asked By : Christian

Answered By : manlio

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):

enter image description here

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback