1Jr10Fnalv01

Question 1

Minimax Bottom-Up Computation:
Minimax Value of the following nodes that the opponent is trying to minimize:

• $b = 4$
• $c = min(7,11,8)=7$
• $d = min(9,2) = 2$
• $e = min(11,3) = 3$

Because $a$ is a MAX node, it takes:
$max(4,7,2,3) = 7$

Best move for the MAX player at $a$: Choose child $c$ (which results in a minimax value of 7).

Rationale (for understanding):

• look at the graph, we're tryna win here, and we assume our opponent is very smart and will choose the smallest possible option when it's their turn(min)
• if we choose b, we get 4 points, end of the game
• if we choose c, ok, then it's our opponent's turn, obviously our smart opponent is going to choose the one that's smallest, which is h = 7
• if we choose d, ok, opponent's gonna choose l = 2 for sure
• if we choose e, smart opponent's gonna choose e = 3
• So our best bet is c

Question 2

Depth Limit = 1

1. Treat the children $b, c, d, e$ as leaves at this depth limit

2. Use heuristic on each of the nodes, since they aren't leaf nodes, and we don't really know anything about them

   • Level = 2:
     • $b$ is a leaf node $;\rightarrow; b=4$
     • $c$ has index 2 $;\rightarrow; h(c)=2+2=4.$
     • $d$ has index 3 $;\rightarrow; h(d)=2+3=5.$
     • $e$ has index 4 $;\rightarrow; h(e)=2+4=6.$ Wow that's a shit heuristic that makes no sense

3. Since $a$ is a MAX node, it picks the child with the maximum heuristic value:
   $$
   \max{,h(b)=3,;h(c)=4,;h(d)=5,;h(e)=6};=;6,
   $$
   which comes from node $e$.

If the depth limit is 1, we would go with $e$ as the best node we could choose, I don't think the problem specified a depth limit so I'm gonna just go ahead and explore the next depth.

Depth Limit = 2

Now we search to expand two levels down from $a$.

• b is a leaf and has value 4, so the MIN of b is $4$

Child $c$ (MIN node):

• Children: $h(7), i(11), j(8)$.
• Since $c$ is a MIN node, it takes the minimum of its children’s values:
• $\min{7, 11, 8} = 7$

Child $d$ (MIN node):

• Children: $k(9), l(2)$.
• MIN chooses the minimum:
• $\min{9,2} = 2$

Child $e$ (MIN node):

• Children: $f(11), g(3)$.
• MIN chooses the minimum:
• $\min{11,3} = 3$

At this point, we would flush out the heuristic of the previous layer, and use the information we have now.

Flush out the previous depth's heuristic!

Since the root $a$ is a MAX node, we take the maximum among its children:

$$
\max{ b=4,; c=7,; d=2,; e=3 }
;=; 7
$$

This maximum value is still 7 and a will continue to choose child $c$ at the root.