Minimax algorithm

https://i.stack.imgur.com/PCAPQ.jpg


Hello, This image above, is kind of vague to me, it was from a MIT lecture about minimax with Alpha/Beta pruning now I don't understand why was 7 picked from the left tree although for the minimizing there is a branch with a 3 that GOT CANCELLED, and why was 8 picked and and the branch with a 1 got cancelled too and many other branches got cancelled aswell. I understand that is how Alpha/Beta pruning works to lessen the computations a bit but I want a clearer explanation. I am sorry if the question looks/sounds dumb to you. I have been trying to understand it really hard and I am just failing q.q
Let's focus on the leftmost part of the tree.

MAX      ? 
       /   \
MIN  ?       ?
    / \     / \
   8   7   3   9 


After visiting the first node (8) we know that the value of the minimising player is going to be equal to or less than 8.

MAX      ?
       /   \
MIN  ≤8      ?
    /  \    / \
   8    7  3   9 


We still need to check the next node because it could be less than 8. It turns out to be 7 which is less than 8 so the value of the minimising player for this part of the tree is 7.

MAX      ?
       /   \
MIN  =7      ?
    /  \    / \
   8    7  3   9 


Now that we know that the left subtree has a value of 7 we know that the value of the maximising player will be at least 7.

MAX     ≥7
       /  \
MIN  =7     ?
    /  \   / \
   8    7 3   9 


We still need to look at the right subtree because it might result in a value that is larger than 7. After visiting the first node of the right subtree (3) we know that the value of the minimising player is going to be 3 or higher.

MAX      ≥7
       /    \
MIN  =7      ≤3
    /  \    /  \
   8    7  3    9 


Now to the clever part. We know that the value of the maximising player will be 7 or higher so the only way to affect that value is to return a value that is greater than 7 for the minimising player. We already know that the value is not going to be larger than 7, because it's at most 3, so we can safely ignore the last node.

MAX      =7
       /    \
MIN  =7      ≤3
    /  \    /  X
   8    7  3    9 
Last edited on
Now to the clever part. We know that the value of the maximising player will be 7 or higher so the only way to affect that value is to return a value that is greater than 7 for the minimising player. We already know that the value is not going to be larger than 7, because it's at most 3, so we can safely ignore the last node.


I am sorry I didn't quite get that last part :c especially this:

We know that the value of the maximising player will be 7 or higher so the only way to affect that value is to return a value that is greater than 7 for the minimising player.
To make it clearer what values I'm talking about I'm introducing the following names.

        max
      /     \
    min1    min2
    /  \    /  \
   8    7  3    ? 

Max will be the smallest largest value of min1 and min2.

We have already concluded that min1 is 7 (because 7 is less than 8).

That means max is at least 7. Max can't be less than 7, but it can be greater than 7 iff min2 is greater than 7.

After having looked at the value 3 we know that min2 is at most 3. This means min2 can't possibly be greater than 7 so it will never affect the value of max, no matter what the last value is. That's why we don't even have to look at the last value.
Last edited on
Max will be the smallest value of min1 and min2.


You mean the largest one right cause that is confusing me rn
Yeah, I meant the largest. Sorry about that.
Thanks <3
Topic archived. No new replies allowed.