What do I not understand about Alpha-Beta-Pruning in Chess?

Question

I'm trying to write a chess engine, Min-Maxing works. Now I wanted to implement Alpha-Beta-Pruning, but despite reading about it and watching videos, I must have a severe misunderstanding somewhere.

• For Min-Maxing, I build the complete search tree, and evaluate only the nodes at the deepest depth. Then go upwards, and "carry" the scores, without evaluating other nodes; I only compare the carried scores.

• For ABP, I also build the complete search tree (?!), and evaluate only the nodes at the deepest depth. Then go upwards, and "carry" the scores; but this time I can often prune nodes, meaning that I don't need to min-max that often, and also don't have to evaluate all nodes at the deepest depth.

Thing is: I'm not limited by the times I have to evaluate nodes, I'm limited by memory (In size and access speed) because I still need to build a tree of millions of nodes, and prune it afterwards.

I assumed ABP should somehow occur earlier, so that I don't even have to create branches, but that doesn't work, since you have to always evaluate the deepest nodes for comparison (So you have to build the tree all the way).

I'm feeling like an idiot here, what do I miss?

Answer 1

Min-Max search (with or without ABP) is not supposed to "build the complete search tree" in memory. It is usually implemented as Depth First Search tree traversal, which traverses the complete search tree, but does not store it completely. In fact, at each point in time, there is only one node per level required in memory, so the memory usage is actually very low. All child nodes are generated recursively "on the fly" and can be thrown away when they are not needed any more.

For example, lets say the DFS has reached a node at level "depth -1", and all child nodes are leave nodes. Now the maximum score will be calculated by the following pseudo code:

 maxscore=-1
 for each child node C of "current node":
     score = evaluate(C)
     maxscore=max(maxscore,score)
 return maxscore

As you see, at one point in time, only one child node C is required, once it has been evaluated and compared to maxscore, it is not required any more.

There is no difference for the required nodes when extending Min-Max by Alpha-Beta-Pruning. ABP just reduces the number of loop cycles in shown example by stopping it when an intermediate value for maxscore reaches the minscore from the recursion level directly above.

Note that even a variation of this algorithm, where the child nodes of the current node are build beforehand and pre-sorted, before maxscore is calculated, does not require memory for the full search tree, it will only require memory in the order of

 O("searchdepth" x "maximum number of childs one node can have")

which is still a fraction of the number of nodes the full search tree has.