Why does the adversarial search minimax algorithm use Depth-First Search (DFS) instead of Breadth-First Search (BFS)?

Question

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?

Answer 1

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.