Answers.Body: <p>I know I'm a bit late, but here is a response from the book &quot;Artifical Intelligence, A Modern Approach&quot; from Russel and Norvig: &quot;It may have occured to you that something like alpha-beta pruning could be applied to game trees with chance nodes. It turns out that you can. The analysis for MIN and MAX nodes is unchanged, but we can also prune chance nodes, using a bit of ingenuity. At first sight, it might seem impossible to find an upper bound on the value of a chance node before looking at all its children, because the value of a chance node is the average of it's children's value, and in order to compute the average of a set of numbers, we must look at all the numbers. But if we put bounds on the possible values of the utility function, then we can arrive at bounds for the average without looking at every number. For example, say that all utility values are between -2 and +2; then the value of leaf nodes is bounded, and in turn we can place an upper bound on the value of a chance node without looking at all its children&quot;.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-08-19T15:00:01.937Z
Answers.Text: This does not provide an answer to the question. Once you have sufficient [reputation](https://ai.stackexchange.com/help/whats-reputation) you will be able to [comment on any post](https://ai.stackexchange.com/help/privileges/comment); instead, [provide answers that don't require clarification from the asker](https://meta.stackexchange.com/questions/214173/why-do-i-need-50-reputation-to-comment-what-can-i-do-instead). - [From Review](/review/late-answers/22146)
Answers.UserDisplayName: Rob
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-08-27T04:38:25.383Z
Answers.Text: As it’s currently written, your answer is unclear. Please [edit] to add additional details that will help others understand how this addresses the question asked. You can find more information on how to write good answers [in the help center](/help/how-to-answer).
Answers.UserDisplayName: Community
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-08-19T13:06:20.040Z
Answers.LastActivityDate: 2022-08-19T13:06:20.040Z
Answers.UserDisplayName: jules
Answers.Body: <p>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.</p>
  <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-12-15T17:51:36.747Z
Answers.Text: This is dead wrong. If we know the maximum and minimum value a node can have, we can estimate the max/min expected value of a chance node and prune there.
Answers.UserDisplayName: thecoolwinter
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-02-13T18:32:29.340Z
Answers.Text: @thecoolwinter I am talking about the question at hand, not in general. If you have an answer, please provide it. Except you cant because this question cannot be solved by pruning
Answers.UserDisplayName: Arjun Verma
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-02-13T18:32:49.130Z
Answers.Text: @thecoolwinter I am talking about the question at hand, not in general. If you have an answer, please provide it. Except you cant because this question cannot be solved by pruning
Answers.UserDisplayName: Arjun Verma
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-02-28T10:18:05.773Z
Answers.LastActivityDate: 2022-02-28T10:27:21.523Z
Answers.LastEditDate: 2022-02-28T10:27:21.523Z
Answers.UserDisplayName: Arjun Verma
Answers.Body: <p>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.</p>
  <p>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.</p>
  <p>In this particular case - for finding the minimum value it works like this:</p>
  <p>First branch:</p>
  <ul>
  <li>Go to B</li>
  <li>Go to D - and there is 2 and 3 - so return the min 2</li>
  <li>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)</li>
  </ul>
  <p>Second branch:</p>
  <ul>
  <li>Go to</li>
  <li>Go to F - and check 0 and 1</li>
  <li>If C have 1 - than not necessary to go to G - cause 1 is the smaller.</li>
  </ul>
  <p>The given sequence is a simplification - and in the case of this algorithm there are also layers - min &amp; max</p>
  <p><a href="https://i.sstatic.net/p0QEK.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/p0QEK.png" alt="enter image description here" /></a></p>
  <p>Source:
  <a href="https://www.javatpoint.com/ai-alpha-beta-pruning#:%7E:text=Key%20points%20about%20alpha%2Dbeta,values%20to%20the%20child%20nodes" rel="nofollow noreferrer">https://www.javatpoint.com/ai-alpha-beta-pruning#:~:text=Key%20points%20about%20alpha%2Dbeta,values%20to%20the%20child%20nodes</a>.</p>
  <hr />
  <p>Implementation, however, is a more complex matter - unless we do copy and paste :-)</p>
  <p><a href="https://gist.github.com/exallium/1446104/5109388cfc21578f555dcac0ba54da680326af7b" rel="nofollow noreferrer">https://gist.github.com/exallium/1446104/5109388cfc21578f555dcac0ba54da680326af7b</a></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-07-29T14:20:33.547Z
Answers.Text: This answer describes the application of alpha-beta pruning to minimax, not to expectiminimax.
Answers.UserDisplayName: beroal
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-07-29T14:25:46.067Z
Answers.Text: Hi, Whats the difference?
Answers.UserDisplayName: Piotr Żak
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-07-31T12:10:09.470Z
Answers.Text: Alpha-beta pruning for minimax doesn't specify what to do with chance nodes.
Answers.UserDisplayName: beroal
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-05-01T12:25:39.790Z
Answers.LastActivityDate: 2021-05-01T12:25:39.790Z
Answers.UserDisplayName: Piotr Żak
Body: <p><a href="https://i.sstatic.net/J2usn.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/J2usn.png" alt="enter image description here" /></a></p>
  <p>I have this problem above and I'm trying to think of how to apply <a href="https://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning" rel="nofollow noreferrer">alpha-beta pruning</a> 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 <span class="math-container">$\\beta$</span> in the expecti node to <span class="math-container">$0.5*2=1$</span> and when it goes into the branch to the right it's comparing values without the probabilities applied to it when updating <span class="math-container">$\beta$</span>.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-05-04T10:18:41.453Z
Comments.Text: 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.
Comments.UserDisplayName: nbro
Tags: <alpha-beta-pruning><expectiminimax>
Title: How to alpha-beta pruning to expectiminimax
UserDisplayName: user8714896
ThreadText: # How to alpha-beta pruning to expectiminimax
  
  (Asked by: username_0 on 2021-04-28)
  
  [![enter image description here](https://i.sstatic.net/J2usn.png)](https://i.sstatic.net/J2usn.png)
  
  I have this problem above and I'm trying to think of how to apply [alpha-beta pruning](https://en.wikipedia.org/wiki/Alpha%E2%80%93beta_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$.
  
  **Tags:** alpha-beta-pruning, expectiminimax
  
  > **Comments:**
  > **username_1**: 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.  
  
  ---
  
  ## 3 answers
  
  ### Answer by username_2 on 2022-08-19. Score: 0
  
  I know I'm a bit late, but here is a response from the book "Artifical Intelligence, A Modern Approach" from Russel and Norvig: "It may have occured to you that something like alpha-beta pruning could be applied to game trees with chance nodes. It turns out that you can. The analysis for MIN and MAX nodes is unchanged, but we can also prune chance nodes, using a bit of ingenuity. At first sight, it might seem impossible to find an upper bound on the value of a chance node before looking at all its children, because the value of a chance node is the average of it's children's value, and in order to compute the average of a set of numbers, we must look at all the numbers. But if we put bounds on the possible values of the utility function, then we can arrive at bounds for the average without looking at every number. For example, say that all utility values are between -2 and +2; then the value of leaf nodes is bounded, and in turn we can place an upper bound on the value of a chance node without looking at all its children".
  
  > **Comments:**
  > **username_3**: This does not provide an answer to the question. Once you have sufficient [reputation](https://ai.stackexchange.com/help/whats-reputation) you will be able to [comment on any post](https://ai.stackexchange.com/help/privileges/comment); instead, [provide answers that don't require clarification from the asker](https://meta.stackexchange.com/questions/214173/why-do-i-need-50-reputation-to-comment-what-can-i-do-instead). - [From Review](/review/late-answers/22146)  
  > **username_4**: As it’s currently written, your answer is unclear. Please [edit] to add additional details that will help others understand how this addresses the question asked. You can find more information on how to write good answers [in the help center](/help/how-to-answer).  
  
  ---
  
  ### Answer by username_5 on 2022-02-28. Score: 0
  
  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.
  
  > **Comments:**
  > **username_6**: This is dead wrong. If we know the maximum and minimum value a node can have, we can estimate the max/min expected value of a chance node and prune there.  
  > **username_5**: @username_6 I am talking about the question at hand, not in general. If you have an answer, please provide it. Except you cant because this question cannot be solved by pruning  
  > **username_5**: @username_6 I am talking about the question at hand, not in general. If you have an answer, please provide it. Except you cant because this question cannot be solved by pruning  
  
  ---
  
  ### Answer by username_7 on 2021-05-01. Score: -1
  
  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](https://i.sstatic.net/p0QEK.png)](https://i.sstatic.net/p0QEK.png)
  
  Source:
  [https://www.javatpoint.com/ai-alpha-beta-pruning#:~:text=Key%20points%20about%20alpha%2Dbeta,values%20to%20the%20child%20nodes](https://www.javatpoint.com/ai-alpha-beta-pruning#:%7E: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>
  
  > **Comments:**
  > **username_8**: This answer describes the application of alpha-beta pruning to minimax, not to expectiminimax.  
  > **username_7**: Hi, Whats the difference?  
  > **username_8**: Alpha-beta pruning for minimax doesn't specify what to do with chance nodes.  
  
  ---
  
  