Answers.Body: <p>The primary reason is that Breadth-First Search requires much more memory (and this probably also makes it a little bit slower in practice, due to time required to allocate memory, jumping around in memory rather than working with what's still in the CPU's caches, etc.). Breadth-First Search needs memory to remember "where it was" in all the different branches, whereas Depth-First Search completes an entire path first before recursing back -- which doesn't really require any memory other than the stack trace. This is assuming we're using a recursive implementation for DFS -- which we normally do in the case of minimax.</p>
  
  <p>You can clearly see this if you look at pseudocode for the two approaches (ignoring the minimax details here, just presenting pseudocode for straightforward searches):</p>
  
  <pre><code>BreadthFirstSearch(start):
      Q = new queue()
      Q.append(start)
      while Q is not empty:
          node = Q.pop()
          if node is leaf:
              do something with leaf
          else:
              for each child of node:
                  Q.append(child)
  
  DepthFirstSearch(start):
      if start is leaf:
          do something with leaf
      for each child of start:
          DepthFirstSearch(child)
          // probably do something with return value from the recursive DFS call
  </code></pre>
  
  <p>You see that the BFS requires a queue object that explicitly stores a bunch of stuff in memory, whereas DFS doesn't.</p>
  
  <hr>
  
  <p>There's more to the story once you get to extensions of Minimax, like Alpha-Beta pruning and Iterative Deepening... but since the question is just about Minimax, I'll leave it at that for now.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-12-20T17:58:38.493Z
Answers.LastActivityDate: 2019-12-20T17:58:38.493Z
Answers.UserDisplayName: Dennis Soemers
Body: <p>I understand that the actual algorithm calls for using Depth-First Search, but is there a functionality reason for using it over another search algorithm like Breadth-First Search?</p>
  
Tags: <search><minimax><breadth-first-search><depth-first-search><adversarial-search>
Title: Why does the adversarial search minimax algorithm use Depth-First Search (DFS) instead of Breadth-First Search (BFS)?
UserDisplayName: Alaz Sengul
ThreadText: # Why does the adversarial search minimax algorithm use Depth-First Search (DFS) instead of Breadth-First Search (BFS)?
  
  (Asked by: username_0 on 2019-12-20)
  
  I understand that the actual algorithm calls for using Depth-First Search, but is there a functionality reason for using it over another search algorithm like Breadth-First Search?
  
  **Tags:** search, minimax, breadth-first-search, depth-first-search, adversarial-search
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2019-12-20. Score: 3 | Accepted answer
  
  The primary reason is that Breadth-First Search requires much more memory (and this probably also makes it a little bit slower in practice, due to time required to allocate memory, jumping around in memory rather than working with what's still in the CPU's caches, etc.). Breadth-First Search needs memory to remember "where it was" in all the different branches, whereas Depth-First Search completes an entire path first before recursing back -- which doesn't really require any memory other than the stack trace. This is assuming we're using a recursive implementation for DFS -- which we normally do in the case of minimax.
  
  You can clearly see this if you look at pseudocode for the two approaches (ignoring the minimax details here, just presenting pseudocode for straightforward searches):
  
  ```
  BreadthFirstSearch(start):
      Q = new queue()
      Q.append(start)
      while Q is not empty:
          node = Q.pop()
          if node is leaf:
              do something with leaf
          else:
              for each child of node:
                  Q.append(child)
  
  DepthFirstSearch(start):
      if start is leaf:
          do something with leaf
      for each child of start:
          DepthFirstSearch(child)
          // probably do something with return value from the recursive DFS call
  
  ```
  
  You see that the BFS requires a queue object that explicitly stores a bunch of stuff in memory, whereas DFS doesn't.
  
  ---
  
  There's more to the story once you get to extensions of Minimax, like Alpha-Beta pruning and Iterative Deepening... but since the question is just about Minimax, I'll leave it at that for now.
  
  
  ---
  
  