Answers.Body: <p>The vanilla Alpha-Beta Pruning algorithm as it has been taught to you in class does not assume any domain knowledge / knowledge about the game / knowledge about the tree it is searching. Therefore, if it immediately finds a score of 10 directly to the left of the root node, it can not prune yet, because... maybe there's a score of 20 somewhere else in the tree?</p>
  
  <p>In your description, you seem to assume prior knowledge that the maximum score that can possibly be obtained in the entire game is 10. This is not typically assumed to be available knowledge ahead of time, at least not in the original formulation of Alpha-Beta. That is why in pseudocode of the algorithm (for example on <a href="https://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning" rel="nofollow noreferrer">wikipedia</a>), they initialize <code>alpha</code> and <code>beta</code> at minus and plus infinity.</p>
  
  <p>You are right though. If you have better estimates of the upper and lower bounds on scores that can every be achieved throughout the entire game, you can use better initializations of <code>alpha</code> and <code>beta</code> than minus and plus infinity. <code>alpha</code> and <code>beta</code> would have to be <code>-11</code> and <code>11</code> if the true bounds are <code>-10</code> and <code>10</code>. I suspect you'd also have to make some additional changes to the typical pseudocode to actually make use of this though.</p>
  
  <p>In more complex games than Tic Tac Toe, you're often not going to have very useful knowledge of better bounds though. Typically you can't afford to search all the way to terminal game states, you'll have to stop the search earlier and use heuristic evaluation functions to estimate scores. If you do that, you'll often want to assign really high constants (like +/- 1Million) to actual terminal nodes (wins and losses), so that all your heuristic scores for non-terminal nodes can be somewhere in between. If you have such a large range of possible scores, your idea stops having much value.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-11-24T11:20:22.777Z
Answers.LastActivityDate: 2017-11-24T11:20:22.777Z
Answers.UserDisplayName: Dennis Soemers
Answers.Body: <p><a href="http://inst.eecs.berkeley.edu/~cs61b/fa14/ta-materials/apps/ab_tree_practice/" rel="nofollow noreferrer">http://inst.eecs.berkeley.edu/~cs61b/fa14/ta-materials/apps/ab_tree_practice/</a></p>
  
  <p>you can make practice for better understanding the topic.</p>
  
  <p>And i also recommend this lecture from MIT</p>
  
  <p><a href="https://www.youtube.com/watch?v=STjW3eH0Cik&amp;index=6&amp;list=PLUl4u3cNGP63gFHB6xb-kVBiQHYe_4hSi" rel="nofollow noreferrer">https://www.youtube.com/watch?v=STjW3eH0Cik&amp;index=6&amp;list=PLUl4u3cNGP63gFHB6xb-kVBiQHYe_4hSi</a></p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-11-25T01:09:46.530Z
Answers.LastActivityDate: 2017-11-25T01:09:46.530Z
Answers.UserDisplayName: Sinan Çalışır
Answers.Body: <p>So I assumed that we know that the maximum value overall is 10. But we do not know that, therefore we need to continue and cannot cut off the way I was thinking. </p>
  
  <p>Although we would know that the max. value overall is 10, then we can cut off there. </p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-11-24T11:17:16.330Z
Answers.LastActivityDate: 2017-11-24T11:17:16.330Z
Answers.UserDisplayName: Peter
Body: <p>I have an AI class this semester. For our exam, we also cover alpha-beta pruning.</p>
  <p>I found an old example, where I think we can stop already earlier.
  Here is a picture of it.</p>
  <p><a href="https://i.sstatic.net/VMyg3.jpg" rel="nofollow noreferrer"><img src="https://i.sstatic.net/VMyg3.jpg" alt="enter image description here" /></a></p>
  <p>I think, because <span class="math-container">$X$</span> wants to maximize his win, and finds 10, he knows that he cannot get better. Therefore he cuts and puts 10.</p>
  <p>I marked my &quot;improvement&quot; with red.</p>
  
Tags: <search><minimax><alpha-beta-pruning>
Title: Can I prune the tree if alpha-beta pruning finds 10 to the left of the root node?
UserDisplayName: Peter
ThreadText: # Can I prune the tree if alpha-beta pruning finds 10 to the left of the root node?
  
  (Asked by: username_0 on 2017-11-23)
  
  I have an AI class this semester. For our exam, we also cover alpha-beta pruning.
  
  I found an old example, where I think we can stop already earlier.
  Here is a picture of it.
  
  [![enter image description here](https://i.sstatic.net/VMyg3.jpg)](https://i.sstatic.net/VMyg3.jpg)
  
  I think, because $X$ wants to maximize his win, and finds 10, he knows that he cannot get better. Therefore he cuts and puts 10.
  
  I marked my "improvement" with red.
  
  **Tags:** search, minimax, alpha-beta-pruning
  
  ---
  
  ## 3 answers
  
  ### Answer by username_1 on 2017-11-24. Score: 2 | Accepted answer
  
  The vanilla Alpha-Beta Pruning algorithm as it has been taught to you in class does not assume any domain knowledge / knowledge about the game / knowledge about the tree it is searching. Therefore, if it immediately finds a score of 10 directly to the left of the root node, it can not prune yet, because... maybe there's a score of 20 somewhere else in the tree?
  
  In your description, you seem to assume prior knowledge that the maximum score that can possibly be obtained in the entire game is 10. This is not typically assumed to be available knowledge ahead of time, at least not in the original formulation of Alpha-Beta. That is why in pseudocode of the algorithm (for example on [wikipedia](https://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning)), they initialize `alpha` and `beta` at minus and plus infinity.
  
  You are right though. If you have better estimates of the upper and lower bounds on scores that can every be achieved throughout the entire game, you can use better initializations of `alpha` and `beta` than minus and plus infinity. `alpha` and `beta` would have to be `-11` and `11` if the true bounds are `-10` and `10`. I suspect you'd also have to make some additional changes to the typical pseudocode to actually make use of this though.
  
  In more complex games than Tic Tac Toe, you're often not going to have very useful knowledge of better bounds though. Typically you can't afford to search all the way to terminal game states, you'll have to stop the search earlier and use heuristic evaluation functions to estimate scores. If you do that, you'll often want to assign really high constants (like +/- 1Million) to actual terminal nodes (wins and losses), so that all your heuristic scores for non-terminal nodes can be somewhere in between. If you have such a large range of possible scores, your idea stops having much value.
  
  
  ---
  
  ### Answer by username_2 on 2017-11-25. Score: 1
  
  <http://inst.eecs.berkeley.edu/~cs61b/fa14/ta-materials/apps/ab_tree_practice/>
  
  you can make practice for better understanding the topic.
  
  And i also recommend this lecture from MIT
  
  <https://www.youtube.com/watch?v=STjW3eH0Cik&index=6&list=PLUl4u3cNGP63gFHB6xb-kVBiQHYe_4hSi>
  
  
  ---
  
  ### Answer by username_0 on 2017-11-24. Score: 0
  
  So I assumed that we know that the maximum value overall is 10. But we do not know that, therefore we need to continue and cannot cut off the way I was thinking.
  
  Although we would know that the max. value overall is 10, then we can cut off there.
  
  
  ---
  
  