5

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).

Still the whole tree has been build before pruning. Picture by Jez9999@Wikipedia

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

  • 2
    pssst. Just a tip - when trying to understand this sort of thing, google for gifs. – T. Sar - Reinstate Monica May 13 '19 at 20:16
  • @T.Sar: Ah, I see! That's already an answer in spirit. If somebody doesn't answer in the next days, I will answer it myself. I just need some time to think how to go about this. – Robert Tausig May 13 '19 at 20:26
6

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.

  • Why did you answer to this question here rather than flagging it as off-topic? This question would have been better asked on AI SE. That's why there's AI SE or DataScience SE. – nbro May 17 '19 at 17:27
  • 2
    @nbro: the fact a question might fit to another SE site as well does not make it off-topic for SE.SE. Algorithmic questions had been on-topic here for years. I don't know much about AI.SE and DataScience.SE, but from their title, I would expect those sites to be places best suited for questions which are less basic than this one. See also softwareengineering.meta.stackexchange.com/questions/7967/… – Doc Brown May 17 '19 at 20:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.