Answers.Body: <p>No.  You have to go to the end of that branch to decide if it is bad. </p>
  
  <p>pruning is done to help make the problem computationally feasible.  But there are risks that you might have eliminated a better branch.  That depends how far out you look and how good your algorithm is to assess the position before you trim it.  </p>
  
  <p>Cutting anything after only a few moves will lead to poor results in many cases.   The farther you go the better the results. </p>
  
  <p>Perfection is not possible.  </p>
  
  <p>You have to trade off time, complexity, and other factors to determine your optimum approach to deciding which branches, and how far you will  go down that rabbit hole searching for the answer.</p>
  
  <p>You can do everything at a small depth.  You can do a few things at enormous depth.  The best approach is in the middle somewhere , where you do enough branches far enough. </p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-01-09T05:53:06.317Z
Answers.Text: Thank you, that is what I suspected (and feared).
Answers.UserDisplayName: eligolf
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-01-11T15:03:57.377Z
Answers.Text: I'm not sure what type of pruning @yobamamama is refering to, but he seems to be implying that there is some type of trade off regarding alpha/beta pruning. This is false. There is no loss of information when transitioning from MinMax to alpha/beta pruning. See my answer.
Answers.UserDisplayName: Noah Caplinger
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-01-11T15:58:39.930Z
Answers.Text: I was trying to say the trade off is when where to prune.
Answers.UserDisplayName: yobamamama
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-01-11T16:35:23.360Z
Answers.Text: If you use alpha/beta pruning, there's no trade off. You're correct for null and late move pruning, but this question specifically asked about alpha/beta.
Answers.UserDisplayName: Noah Caplinger
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-01-11T16:58:01.957Z
Answers.Text: I defer to your answer.  All is know is how I pruned way way back when long long ago.
Answers.UserDisplayName: yobamamama
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-01-08T18:11:43.003Z
Answers.LastActivityDate: 2020-01-08T18:11:43.003Z
Answers.UserDisplayName: yobamamama
Answers.Body: <p>In alpha/beta pruning, you <em>only prune when further search cannot affect the outcome.</em> In particular this means there will be <em>no loss of information</em> when you transition from MinMax to alpha/beta. There is only upside to alpha/beta (in contrast to other, more aggressive pruning methods).</p>
  
  <p>The fundamental idea of alpha/beta pruning is that once you discover a branch to be inferior, there's no sense in figuring out <em>exactly how inferior</em>. </p>
  
  <p>Here's how we'll do it: (When <em>not</em> using NegaMax) You can think of alpha as the maximum of all white (maximizing) ancestor's max_eval, and beta as the minimum of all black (minimizing) ancestor's min_eval. </p>
  
  <p>Now, say you're searching a white node, w, and you discover the max_eval to be <em>larger</em> than beta. White is maximizing, so we know that the value of w can only go up. Then we are guaranteed that the value of w is larger than beta.</p>
  
  <p>This means that this (white) node must have a (black) ancestor with min_eval <em>smaller</em> than the value of w, by definition of beta. Let's think more about this: because that black ancestor has min_eval smaller than w, it is guaranteed the option of a move with value min_eval. But w has value <em>larger</em> than min_eval. That black ancestor will <em>always</em> choose the lower one, so it doesn't matter how much larger w is. From the perspective of that black ancestor, w and w+100 are the exact same: worse. </p>
  
  <p>Then, there's no reason to continue searching w: it can't possibly affect the outcome of the algorithm, so we prune the tree.</p>
  
  <p>This is the only situation in which the alpha/beta algorithm prunes: when the outcome of further search cannot possibly affect the result. </p>
  
  <hr>
  
  <p>If all of that is confusing, I really don't blame you. This is a topic that deserves lots of pictures and a few pages of explanation, not a few paragraphs. imo there aren't any great resources online, but if you (or anyone else) would like to contact me, I have something that might be helpful.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-01-11T15:01:01.440Z
Answers.LastActivityDate: 2020-01-11T15:01:01.440Z
Answers.UserDisplayName: Noah Caplinger
Body: <p>I am creating a chess AI using the minimax method with alpha-beta pruning. I am trying to understand how the alpha-beta pruning works, but I can't get my head around it when it comes to chess where you set a certain search depth.</p>
  <p>How do minimax with alpha-beta solve sacrificing a piece for advantage 2-3 moves ahead? Won't it just look at the position at the sacrifice and immediately discard that branch as bad, therefore missing the good &quot;sacrifice&quot;?</p>
  <p>My code so far:</p>
  <pre><code>def minimax(board, depth, alpha, beta, maximizing_player):
  
      board.is_human_turn = not maximizing_player 
  
      children = board.get_all_possible_moves()
  
      if depth == 0 or board.is_draw or board.is_check_mate:
          return None, evaluate(board)
  
      best_move = random.choice(children)
  
      if maximizing_player:
          max_eval = -math.inf
          for child in children:
              board_copy = copy.deepcopy(board)
              board_copy.move(child)
              current_eval = minimax(board_copy, depth - 1, alpha, beta, False)[1]
              if current_eval &gt; max_eval:
                  max_eval = current_eval
                  best_move = child
              alpha = max(alpha, current_eval)
              if beta &lt;= alpha:
                  break
          return best_move, max_eval
  
      else:
          min_eval = math.inf
          for child in children:
              board_copy = copy.deepcopy(board)
              board_copy.move(child)
              current_eval = minimax(board_copy, depth - 1, alpha, beta, True)[1]
              if current_eval &lt; min_eval:
                  min_eval = current_eval
                  best_move = child
              beta = min(beta, current_eval)
              if beta &lt;= alpha:
                  break
          return best_move, min_eval
  </code></pre>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-01-08T18:08:07.327Z
Comments.Text: Similar question [here](https://cs.stackexchange.com/questions/11800/alpha-beta-pruning-in-chess) may help
Comments.UserDisplayName: Michael West
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-01-09T23:44:26.517Z
Comments.Text: Just a note: you've got repeating code under if and else. You can parameterize it and abstract into a function - will make it easier to work with.
Comments.UserDisplayName: postoronnim
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-01-10T10:20:57.050Z
Comments.Text: I know, thanks :) I think the reduced one is called negamax. But I am too lazy to change and try to get that to work with alpha-beta.
Comments.UserDisplayName: eligolf
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-01-11T08:48:27.263Z
Comments.Text: One good strategy is iterative deepening search, where you do the minimax algorithm at depth 1, then depth 2, etc, until running out of the time limit for thinking. On each iteration, you get an idea of which branches to spend more time on, since the resulting positions at a lesser depth seem good.
Comments.UserDisplayName: Inertial Ignorance
Tags: <engines><programming><minimax>
Title: Minimax with alpha-beta pruning for chess
ThreadText: # Minimax with alpha-beta pruning for chess
  
  (Asked by: username_0 on 2020-01-08)
  
  I am creating a chess AI using the minimax method with alpha-beta pruning. I am trying to understand how the alpha-beta pruning works, but I can't get my head around it when it comes to chess where you set a certain search depth.
  How do minimax with alpha-beta solve sacrificing a piece for advantage 2-3 moves ahead? Won't it just look at the position at the sacrifice and immediately discard that branch as bad, therefore missing the good "sacrifice"?
  My code so far:
  def minimax(board, depth, alpha, beta, maximizing_player):
  
      board.is_human_turn = not maximizing_player 
  
      children = board.get_all_possible_moves()
  
      if depth == 0 or board.is_draw or board.is_check_mate:
          return None, evaluate(board)
  
      best_move = random.choice(children)
  
      if maximizing_player:
          max_eval = -math.inf
          for child in children:
              board_copy = copy.deepcopy(board)
              board_copy.move(child)
              current_eval = minimax(board_copy, depth - 1, alpha, beta, False)[1]
              if current_eval > max_eval:
                  max_eval = current_eval
                  best_move = child
              alpha = max(alpha, current_eval)
              if beta <= alpha:
                  break
          return best_move, max_eval
  
      else:
          min_eval = math.inf
          for child in children:
              board_copy = copy.deepcopy(board)
              board_copy.move(child)
              current_eval = minimax(board_copy, depth - 1, alpha, beta, True)[1]
              if current_eval < min_eval:
                  min_eval = current_eval
                  best_move = child
              beta = min(beta, current_eval)
              if beta <= alpha:
                  break
          return best_move, min_eval
  
  **Tags:** engines, programming, minimax
  
  > **Comments:**
  > **username_1**: Similar question [here](https://cs.stackexchange.com/questions/11800/alpha-beta-pruning-in-chess) may help  
  > **username_2**: Just a note: you've got repeating code under if and else. You can parameterize it and abstract into a function - will make it easier to work with.  
  > **username_0**: I know, thanks :) I think the reduced one is called negamax. But I am too lazy to change and try to get that to work with alpha-beta.  
  > **username_3**: One good strategy is iterative deepening search, where you do the minimax algorithm at depth 1, then depth 2, etc, until running out of the time limit for thinking. On each iteration, you get an idea of which branches to spend more time on, since the resulting positions at a lesser depth seem good.  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_4 on 2020-01-08. Score: 2 | Accepted answer
  
  No. You have to go to the end of that branch to decide if it is bad.
  
  pruning is done to help make the problem computationally feasible. But there are risks that you might have eliminated a better branch. That depends how far out you look and how good your algorithm is to assess the position before you trim it.
  
  Cutting anything after only a few moves will lead to poor results in many cases. The farther you go the better the results.
  
  Perfection is not possible.
  
  You have to trade off time, complexity, and other factors to determine your optimum approach to deciding which branches, and how far you will go down that rabbit hole searching for the answer.
  
  You can do everything at a small depth. You can do a few things at enormous depth. The best approach is in the middle somewhere , where you do enough branches far enough.
  
  > **Comments:**
  > **username_0**: Thank you, that is what I suspected (and feared).  
  > **username_5**: I'm not sure what type of pruning @username_4 is refering to, but he seems to be implying that there is some type of trade off regarding alpha/beta pruning. This is false. There is no loss of information when transitioning from MinMax to alpha/beta pruning. See my answer.  
  > **username_4**: I was trying to say the trade off is when where to prune.  
  > **username_5**: If you use alpha/beta pruning, there's no trade off. You're correct for null and late move pruning, but this question specifically asked about alpha/beta.  
  > **username_4**: I defer to your answer.  All is know is how I pruned way way back when long long ago.  
  
  ---
  
  ### Answer by username_5 on 2020-01-11. Score: 3
  
  In alpha/beta pruning, you *only prune when further search cannot affect the outcome.* In particular this means there will be *no loss of information* when you transition from MinMax to alpha/beta. There is only upside to alpha/beta (in contrast to other, more aggressive pruning methods).
  
  The fundamental idea of alpha/beta pruning is that once you discover a branch to be inferior, there's no sense in figuring out *exactly how inferior*.
  
  Here's how we'll do it: (When *not* using NegaMax) You can think of alpha as the maximum of all white (maximizing) ancestor's max\_eval, and beta as the minimum of all black (minimizing) ancestor's min\_eval.
  
  Now, say you're searching a white node, w, and you discover the max\_eval to be *larger* than beta. White is maximizing, so we know that the value of w can only go up. Then we are guaranteed that the value of w is larger than beta.
  
  This means that this (white) node must have a (black) ancestor with min\_eval *smaller* than the value of w, by definition of beta. Let's think more about this: because that black ancestor has min\_eval smaller than w, it is guaranteed the option of a move with value min\_eval. But w has value *larger* than min\_eval. That black ancestor will *always* choose the lower one, so it doesn't matter how much larger w is. From the perspective of that black ancestor, w and w+100 are the exact same: worse.
  
  Then, there's no reason to continue searching w: it can't possibly affect the outcome of the algorithm, so we prune the tree.
  
  This is the only situation in which the alpha/beta algorithm prunes: when the outcome of further search cannot possibly affect the result.
  
  ---
  
  If all of that is confusing, I really don't blame you. This is a topic that deserves lots of pictures and a few pages of explanation, not a few paragraphs. imo there aren't any great resources online, but if you (or anyone else) would like to contact me, I have something that might be helpful.
  
  
  ---
  
  