1
$\begingroup$

enter image description here

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$.

$\endgroup$
2
  • $\begingroup$ Could you please put your specific question in the title? $\endgroup$
    – nbro
    Apr 29, 2021 at 10:24
  • $\begingroup$ I don't understand the current title "How to alpha-beta pruning to expectiminimax" because a "verb" is missing. Please, edit your post to fix this. $\endgroup$
    – nbro
    May 4, 2021 at 10:18

2 Answers 2

0
$\begingroup$

The internet doesnt seem to have easily accessible resources on this topic. In my newbie opinion, it should not be possible to prune any nodes. Expectiminimax takes the weighted average of the children, so it would need to consider all leaf values in order to do so. There is no node which can be ignored, as it will an operand in a sum. Now lets say the left subtree was bigger, in the right subtree you evaluated the first min node and it is smaller: well since the second min node can contribute to the sum making it bigger, it cannot be ignored. Now lets say the first min node on the right subtree was bigger, well since the second term adds or reduces(reduces in this case) weight it still has to be considered to get the final value.

Since all the nodes are checked and added together with appropriate weights under chance nodes, I highly doubt there is any advantage of alpha-beta pruning here since it would take the same number of steps as regular expectiminimax. Perhaps if the tree was larger and the chance nodes were central, more nodes could have been pruned out.

$\endgroup$
-1
$\begingroup$

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:

First branch:

  • 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)

Second branch:

  • 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

enter image description here

Source: https://www.javatpoint.com/ai-alpha-beta-pruning#:~:text=Key%20points%20about%20alpha%2Dbeta,values%20to%20the%20child%20nodes.


Implementation, however, is a more complex matter - unless we do copy and paste :-)

https://gist.github.com/exallium/1446104/5109388cfc21578f555dcac0ba54da680326af7b

$\endgroup$
3
  • 1
    $\begingroup$ This answer describes the application of alpha-beta pruning to minimax, not to expectiminimax. $\endgroup$
    – beroal
    Jul 29, 2021 at 14:20
  • $\begingroup$ Hi, Whats the difference? $\endgroup$
    – Piotr Żak
    Jul 29, 2021 at 14:25
  • 1
    $\begingroup$ Alpha-beta pruning for minimax doesn't specify what to do with chance nodes. $\endgroup$
    – beroal
    Jul 31, 2021 at 12:10

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .