Cs440Wa3

Question 1

Minimax Bottom-Up Computation:
We start at a, we want to maximize our next step
Minimax Value of the following nodes that the opponent is trying to minimize:
We go to node

• $b = 4$
  Since it has a utility value assigned directly to it, we just take 4.
  Next, we go to c. We want to figure out the value of c, and c has three children. We do DFS and start exploring h, then i, then j, and take the Min of the values since the second layer is minimizing.
• $c = min(7,11,8)=7$
  After getting the value, we return the value back to c, and assign c this value. We would go to the next node d. We go to d's children, k and l, and take the min
• $d = min(9,2) = 2$
  then we go back up and assign d 2. Lastly we go to e, and take the min of e's children
• $e = min(11,3) = 3$
  We assign e the value of 3

Then, after the values are assigned for the nodes right under a, and
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 (some of) them aren't leaf nodes, but if they are, we would just use the terminal value.

   • 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 bad heuristic that makes no sense

3. Since $a$ is a MAX node, it picks the child with the maximum utility value (assigned by heuristic or in itself is a leaf node):
   $$
   \max{,h(b)=3,;h(c)=4,;h(d)=5,;h(e)=6};=;6,
   $$
   which comes from node $e$. So, at this depth limit of our resources, our the function would choose 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$

They are all terminal nodes (leaf nodes), so this is essentially vanilla minimax.

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.

Question 3