Consider the following minimax game tree search What will be the value…

Solution: Evaluate the tree bottom-up, computing values at MAX nodes above the leaves, then MIN nodes, and finally the root MAX.

• Left top-level branch:

  • First MAX child has leaf [4] → value 4.

  • Second MAX child has leaves [6, 2, 6] → max = 6.

  • Third MAX child has leaves [3, 9] → max = 9.

  • MIN at this branch chooses min(4, 6, 9) = 4.

• Middle top-level branch:

  • First MAX child has leaves [5, 2] → max = 5.

  • Second MAX child has leaves [7, 3] → max = 7.

  • MIN at this branch chooses min(5, 7) = 5.

• Right top-level branch:

  • First MAX child has leaf [1] → value 1.

  • Second MAX child has leaves [7, 2] → max = 7.

  • Third MAX child has leaves [4, 6, 3] → max = 6.

  • MIN at this branch chooses min(1, 7, 6) = 1.

Finally, the root is a MAX over the three top-level branch values: max(4, 5, 1) = 5. So the value propagated at the root is 5.