Search code examples
algorithmminimaxalpha-beta-pruning

Why is this prune being done by my program?

I created program which does alpha beta algorithm on a graph.

(Images are clickable for a larger version)

I have this graph:

my graph

Result of the algorithm:

result

This image shows the problem area:

Why were these two nodes pruned? First node of group is 5, parent node of previous vertexes is 2, so we compare 5 and 2. 5 is not less than 2, but the program made the cut-off. Why? It must do it only if node value is lesser then 2, but it is not in our case.

Am I misunderstanding something in alpha-beta pruning theory, so I am comparing the wrong values? Or is it a problem of my realization? All other branches before worked perfectly, so why does the problem only appear here? On the other hand, look at this image:

The program must prune and the prune is done. Why is it pruning when the first child vertex is either 5 or 1?

My alpha beta function (on GitHub): 

function alphabeta_blank(node, depth, alpha, beta, isMax, g) {
    g.nodes[node.name].shape.items['0'].attr('fill', 'green');

    if((depth == 0) || (node.isTerminal == true)) {
        return node.value;
    }
    if(isMax) {
        for (var i in node.children) {
            var child = node.children[i];
            alpha = Math.max(alpha, alphabeta_blank(child, depth-1, alpha, beta, false, g));
            if(beta <= alpha) {
                break;
            }
        }
        return alpha;
    } else {
        for (var i in node.children) {
            var child = node.children[i];
            beta = Math.min(beta, alphabeta_blank(child, depth-1, alpha, beta, true, g));
            if (beta <= alpha) {
                break;
            }
        }
        return beta;
    }
}

This function is a translation of the pseudocode on Wikipedia to JavaScript.

Note: if you open the full source, you will notice that I showed the alpha_beta_blank function here - this function is a translation of the Wikipedia pseudocode. Actually, I am using another function in my program, but neither are working correctly, as described above.

About debugging. You can look at this function (original function with all debugging statements) and see that I am printing debug messages. This part from debug trace belongs to the problem vertexes:

minimizing (min312)
getting value from terminal node node31 (value is 5)
beta value is set to 5
alpha cut-off (5<=5), others children of max31 wouldn't be visited
min312 — minimum of childs of min312 is 5
min312 — childs of node min312: [5]
returning beta, minimal node is 5, node min312 value is set as 5
going back to node max31

Part of graph with names (so you can understand the logs):

             max31
            /       \
      min311         min312
     ........     /    |     \
                 /     |      \
child:          5      4       5

Full repository on GitHub.

Solution

  • By exploring 1st sub-tree (from root) we have found out that we are guaranteed to get the result of 5 so when we go to that "troublesome" node and get the value of 5 we can prune because there's no way the min node would take higher value and of course we don't want to try get even lower value since we can always go to the first sub-tree and get the result of 5 (same applies to your other example when its 1, because 5 is better than 1). Although if it was 6 instead then it wouldn't prune.

    The alpha value is not 2 at that place but it's 5 because it get carried over from 1st sub-tree as the guaranteed maximum value. So that's why your written comparison 2<5 is incorrect and should be 5<=5 which is true.