Answers.Body: <p>Suppose that you have already search a part of the complete search tree, for example the complete left half. This may not yet give you the true game-theoretic value for the root node, but it can already give you some bounds on the game-theoretic value that the player to play in the root node (let's say, the max player) can guarantee by moving into that part of the search tree. Those bounds / guarantees are:</p>
  
  <ul>
  <li><span class="math-container">$\alpha$</span>: the <strong>minimum</strong> score that the <strong>maximizing</strong> player already knows it can <strong>guarantee</strong> if we move into the part of the search tree searched so far. Maybe it can still do better (get higher values) by moving into the unsearched part, but it can already definitely get this value.</li>
  <li><span class="math-container">$\beta$</span>: the <strong>maximum</strong> score that the <strong>minimizing</strong> player already knows it can <strong>guarantee</strong> if we moves into the part of the search tree searched so far. Maybe it can still do better (get lower values) by moving into the unsearched part, but it can already definitely get this value.</li>
  </ul>
  
  <p>The intuitive idea behind alpha-beta pruning is to prune chunks of the search tree that become uninteresting for either player because they already know they can guarantee better based on the <span class="math-container">$\alpha$</span> or <span class="math-container">$\beta$</span> bounds.</p>
  
  <hr>
  
  <p>For a simple example, suppose <span class="math-container">$\alpha = 1$</span>, which means that the maximizing player already has explored a part of the search tree such that it can <strong>guarantee at least</strong> a value of <span class="math-container">$1$</span> by playing inside that part (the minimizing player has no options inside that entire tree to reduce the value below <span class="math-container">$1$</span>, if the maximizing player plays optimally in that part).</p>
  
  <p>Suppose that, in the current search process, we have arrived at a node where the minimizing player is to play, and it has a long list of child nodes. We evaluate the first of those children, and find a value of <span class="math-container">$0$</span>. This means that, under the assumption that we reach this node, the minimizing player can already guarantee a value of <span class="math-container">$0$</span> (and possibly get even lower, we didn't evaluate the other children yet). But this is worse (for the maximizing player) than the <span class="math-container">$\alpha = 1$</span> bound we already had. Without evaluating any of the other children, we can already tell that this part of the search tree is uninteresting, that the maximizing player would make sure that we never end up here, so we can prune the remaining children (which could each have large subtrees below them).</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-02-26T09:48:05.383Z
Answers.Text: I think this answer gives some intuition behind the algorithm, but it lacks a few clarifications. For example, you do not explain the reason behind searching with respect to the root player (i.e. because the first player is the one that plays first...). Or what happens if the root player is not the maximizing player but the minimixing player? Also, what happens if one or both players do not act optimality?
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-02-26T09:51:01.047Z
Answers.Text: I think these things can confuse people. The idea of pruning parts of the tree because they will not be "explored", if both players act optimality, is clear, but it is not clear which players will play or not, what is the relation between the players, etc.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-01-04T12:43:57.207Z
Answers.LastActivityDate: 2019-01-04T12:43:57.207Z
Answers.UserDisplayName: Dennis Soemers
Answers.Body: <p><strong>Minimax</strong></p>
  
  <p>As the question author may already understand, minimax is an approach before it is an algorithm. The goal is to minimize the advantage of a challenger and maximize the advantage of the participant presently applying the minimax approach. This is a subset of a wider strategy of summing benefits and subtracting the sum of costs to derive a net value.</p>
  
  <p><strong>Alpha-beta Pruning</strong></p>
  
  <p>The strategic goal of alpha beta pruning is to produce uncompromized decision making with less work. This goal is usually driven by the cost of computing resources, the impatience of the person waiting on results, or a missed deadline penalty.</p>
  
  <p>The principle involved is that if there is a finite range to the net gain that can aggregate as a result of traversing any subtree in a search. It can be proven, using the algebra of inequalities, that no knowledge can be lost in the search if the subtree cannot, under any conditions, show any net advantage over the other options.</p>
  
  <p><strong>Some Graph Theory to Clarify Pruning</strong></p>
  
  <p>Vertices are the graph theory name for what are often called tree nodes. They are represented as <span class="math-container">$\nu$</span> below, and they correspond to states. The connections between vertices are called edges in graph theory. They are represented as <span class="math-container">$\epsilon$</span> below, and they correspond to actions.</p>
  
  <p>The minimax net gain thus far accumulated at an vertex can be calculated as the tree is traversed.</p>
  
  <p>As the limitations to net gain at further depths are applied to these intermediate net gain values, it can be inferred that one edge (action) will, in every case, be advantageous over another edge. If an algorithm reveals that one edge leads to disadvantage in every possible case, then there is no need to traverse that edge. Such dismissal of never-advantageous edges saves computing resources and likely reduces search time. The term pruning is used because edges are like branches in a fruit orchard.</p>
  
  <p><strong>The Condition of Pruning and the Algorithm To Accomplish It</strong></p>
  
  <p>Initialization for the algorithm begins by setting the two Greek letter variables to their worst case values.</p>
  
  <p><span class="math-container">$$ \alpha = - \infty \\
     \beta = \infty $$</span></p>
  
  <p>The pruning rule for edge <span class="math-container">$\epsilon$</span> leading to a vertex <span class="math-container">$\nu$</span> is simply this.</p>
  
  <p><span class="math-container">$$ \alpha_\nu \geq \beta_\nu \Rightarrow \text{prune}(\epsilon_\nu) $$</span></p>
  
  <p>Source code doesn't usually directly implement this declaration, but rather produces its effect in the algorithm, which can be represented in simplified pseudo-code. The algorithm to do such is simple once recursion is understood. That is an conceptual prerequisite, so learn about recursion first if not already known.</p>
  
  <pre><code>ab_minimax ν, α, β
  
      if ν.depth = search.max_depth or ν.is_leaf
          return ν.value
  
      if ν.is_maximizing
          for ε in ν.edges
              x = max(β, ab_minimax ε.child, α, β)
              if α ≥ β
                  ν.prune ε
                  return α
          return α
      else
          for ε in ν.edges
              x = min(α, ab_minimax child, α, β)
              if α ≤ β
                  ν.prune ε
                  return β
          return β
  </code></pre>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-01-20T19:09:43.473Z
Answers.LastActivityDate: 2019-01-27T04:17:22.177Z
Answers.LastEditDate: 2019-01-27T04:17:22.177Z
Answers.UserDisplayName: Douglas Daseeco
Body: <p>I understand the minimax algorithm, but I am unable to understand deeply the minimax algorithm with alpha-beta pruning, even after having looked up several sources (on the web) and having tried to read the algorithm and understand how it works.</p>
  
  <p>Do you have a good source that explains alpha-beta pruning clearly, or can you help me to understand the alpha-beta pruning (with a simple explanation)?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-01-27T07:28:16.120Z
Comments.Text: You can explore how alpha-beta prunes a tree here, but it doesn't animate the steps performed by alpha-beta: https://movingai.com/ab/
Comments.UserDisplayName: Nathan S.
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-01-27T13:58:15.770Z
Comments.Text: Have you read the following article: http://web.cs.ucla.edu/~rosen/161/notes/alphabeta.html? It should give you some intuition behind the algorithm.
Comments.UserDisplayName: nbro
Tags: <search><minimax><alpha-beta-pruning>
Title: Can someone help me to understand the alpha-beta pruning algorithm?
UserDisplayName: Sunshine 
ThreadText: # Can someone help me to understand the alpha-beta pruning algorithm?
  
  (Asked by: username_0 on 2019-01-03)
  
  I understand the minimax algorithm, but I am unable to understand deeply the minimax algorithm with alpha-beta pruning, even after having looked up several sources (on the web) and having tried to read the algorithm and understand how it works.
  
  Do you have a good source that explains alpha-beta pruning clearly, or can you help me to understand the alpha-beta pruning (with a simple explanation)?
  
  **Tags:** search, minimax, alpha-beta-pruning
  
  > **Comments:**
  > **username_1**: You can explore how alpha-beta prunes a tree here, but it doesn't animate the steps performed by alpha-beta: https://movingai.com/ab/  
  > **username_2**: Have you read the following article: http://web.cs.ucla.edu/~rosen/161/notes/alphabeta.html? It should give you some intuition behind the algorithm.  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_3 on 2019-01-04. Score: 3
  
  Suppose that you have already search a part of the complete search tree, for example the complete left half. This may not yet give you the true game-theoretic value for the root node, but it can already give you some bounds on the game-theoretic value that the player to play in the root node (let's say, the max player) can guarantee by moving into that part of the search tree. Those bounds / guarantees are:
  
  * $\alpha$: the **minimum** score that the **maximizing** player already knows it can **guarantee** if we move into the part of the search tree searched so far. Maybe it can still do better (get higher values) by moving into the unsearched part, but it can already definitely get this value.
  * $\beta$: the **maximum** score that the **minimizing** player already knows it can **guarantee** if we moves into the part of the search tree searched so far. Maybe it can still do better (get lower values) by moving into the unsearched part, but it can already definitely get this value.
  
  The intuitive idea behind alpha-beta pruning is to prune chunks of the search tree that become uninteresting for either player because they already know they can guarantee better based on the $\alpha$ or $\beta$ bounds.
  
  ---
  
  For a simple example, suppose $\alpha = 1$, which means that the maximizing player already has explored a part of the search tree such that it can **guarantee at least** a value of $1$ by playing inside that part (the minimizing player has no options inside that entire tree to reduce the value below $1$, if the maximizing player plays optimally in that part).
  
  Suppose that, in the current search process, we have arrived at a node where the minimizing player is to play, and it has a long list of child nodes. We evaluate the first of those children, and find a value of $0$. This means that, under the assumption that we reach this node, the minimizing player can already guarantee a value of $0$ (and possibly get even lower, we didn't evaluate the other children yet). But this is worse (for the maximizing player) than the $\alpha = 1$ bound we already had. Without evaluating any of the other children, we can already tell that this part of the search tree is uninteresting, that the maximizing player would make sure that we never end up here, so we can prune the remaining children (which could each have large subtrees below them).
  
  > **Comments:**
  > **username_2**: I think this answer gives some intuition behind the algorithm, but it lacks a few clarifications. For example, you do not explain the reason behind searching with respect to the root player (i.e. because the first player is the one that plays first...). Or what happens if the root player is not the maximizing player but the minimixing player? Also, what happens if one or both players do not act optimality?  
  > **username_2**: I think these things can confuse people. The idea of pruning parts of the tree because they will not be "explored", if both players act optimality, is clear, but it is not clear which players will play or not, what is the relation between the players, etc.  
  
  ---
  
  ### Answer by username_4 on 2019-01-20. Score: 0
  
  **Minimax**
  
  As the question author may already understand, minimax is an approach before it is an algorithm. The goal is to minimize the advantage of a challenger and maximize the advantage of the participant presently applying the minimax approach. This is a subset of a wider strategy of summing benefits and subtracting the sum of costs to derive a net value.
  
  **Alpha-beta Pruning**
  
  The strategic goal of alpha beta pruning is to produce uncompromized decision making with less work. This goal is usually driven by the cost of computing resources, the impatience of the person waiting on results, or a missed deadline penalty.
  
  The principle involved is that if there is a finite range to the net gain that can aggregate as a result of traversing any subtree in a search. It can be proven, using the algebra of inequalities, that no knowledge can be lost in the search if the subtree cannot, under any conditions, show any net advantage over the other options.
  
  **Some Graph Theory to Clarify Pruning**
  
  Vertices are the graph theory name for what are often called tree nodes. They are represented as $\nu$ below, and they correspond to states. The connections between vertices are called edges in graph theory. They are represented as $\epsilon$ below, and they correspond to actions.
  
  The minimax net gain thus far accumulated at an vertex can be calculated as the tree is traversed.
  
  As the limitations to net gain at further depths are applied to these intermediate net gain values, it can be inferred that one edge (action) will, in every case, be advantageous over another edge. If an algorithm reveals that one edge leads to disadvantage in every possible case, then there is no need to traverse that edge. Such dismissal of never-advantageous edges saves computing resources and likely reduces search time. The term pruning is used because edges are like branches in a fruit orchard.
  
  **The Condition of Pruning and the Algorithm To Accomplish It**
  
  Initialization for the algorithm begins by setting the two Greek letter variables to their worst case values.
  
  $$ \alpha = - \infty \\
  \beta = \infty $$
  
  The pruning rule for edge $\epsilon$ leading to a vertex $\nu$ is simply this.
  
  $$ \alpha\_\nu \geq \beta\_\nu \Rightarrow \text{prune}(\epsilon\_\nu) $$
  
  Source code doesn't usually directly implement this declaration, but rather produces its effect in the algorithm, which can be represented in simplified pseudo-code. The algorithm to do such is simple once recursion is understood. That is an conceptual prerequisite, so learn about recursion first if not already known.
  
  ```
  ab_minimax ν, α, β
  
      if ν.depth = search.max_depth or ν.is_leaf
          return ν.value
  
      if ν.is_maximizing
          for ε in ν.edges
              x = max(β, ab_minimax ε.child, α, β)
              if α ≥ β
                  ν.prune ε
                  return α
          return α
      else
          for ε in ν.edges
              x = min(α, ab_minimax child, α, β)
              if α ≤ β
                  ν.prune ε
                  return β
          return β
  
  ```
  
  
  ---
  
  