I have this problem above and I'm trying to think of how to apply alpha-beta pruning to the above. The algorithm states that on you're opponents turn the (expecti turn) you just return the lowest value, but does that mean you apply the probabilities to those values? So for the far left you'd get 2 as the largest value then multiply that by 0.5, but then that set's $\\beta$ in the expecti node to $0.5*2=1$ and when it goes into the branch to the right it's comparing values without the probabilities applied to it when updating $\beta$.
alpha-beta-prunning algorithm is using for improve performance and reject the options, which not consist the condition - or it's possible to set some factors of probability to take into consideration or not.
This algorithm work on tree structure - and if there are a lot of levels (10-20) - It allows you to eliminate paths - which will logically not be used - saving memory and computing resources.
In this particular case - for finding the minimum value it works like this:
- Go to B
- Go to D - and there is 2 and 3 - so return the min 2
- Go From B to E - and choose 5 - the minimal value in B points is actually 3 - so there isn't need for checking the next - cause everything below E, will be higher than D (3)
- Go to
- Go to F - and check 0 and 1
- If C have 1 - than not necessary to go to G - cause 1 is the smaller.
The given sequence is a simplification - and in the case of this algorithm there are also layers - min & max
Implementation, however, is a more complex matter - unless we do copy and paste :-)