How to display Alpha Beta Pruning algorithm result?

Question

Updates

Update 1

I tried this (2nd line): I added changing node color as first instruction in alphabeta function. I am getting this result:

Green nodes are visited nodes. It looks like, algorithm is going throw nodes correctly, right? But how to output correct values in nodes — I also need to do this? Minimum of children values, maximum of children values (excluding pruned branches).

Update 2

I tried to output alpha and beta to the tree nodes and didn't get correct result. This is code (line 18 and 31 were added). This is result of the code:

On this image I show strange places:

First arrow: why minimum of 7 and 6 is 5? Second arrow: why maximum of 4, 3 and 2 is 5? Strange. Thats why I think, that it is now working correctly.

Old question

Once upon a time I created similar question here. It was like: "why I get this error?". Lets rollback and created new one. This question will be: "How to display Alpha Beta Pruning algorithm result?"

I found pseudocode of this algorithm on the wiki. It can be found here.

My realization is below (it is on JavaScript, but I don't think that to answer this question you have to know JS or Java or C++ etc). The question is how to output result of this algorithm on the graph (tree structure)? On start I have this tree structure:

NOTE: I have tree structure (some amount of linked nodes), on which I will use alpha beta pruning algorithm, and I have another tree structure (for displaying results, lets call it "graph"). Nodes of tree, which I use to display graph are connected with nodes, which I use to find result of the algorithm.

So, code of the alpha beta pruning algroithm is below. Can you clarify what and where I have to output to display process/results of the algorithm correctly, please?

My assumption is to output alpha and beta, but I think, it is wrong. I tried it, but it doesn't work.

I want to display prunings and fill in all nodes in the tree with correct values.

This is my realization of minimax with alpha beta pruning:

function alphabeta(node, depth, alpha, beta, isMax, g) {
    if((depth == 0) || (node.isTerminal == true)) {
        return node.value;
    }
    if(isMax) {
        console.log('maximizing');
        for (var i in node.children) {
            var child = node.children[i];
            console.log(child);
            alpha = Math.max(alpha, alphabeta(child, depth-1, alpha, beta, false, g));
            if(beta <= alpha) {
                console.log('beta '+beta+' alpha '+alpha);
                break;
            }
        }

        return alpha;
    } else {
        console.log('minimizing');
        for (var i in node.children) {
            console.log('1 child');
            var child = node.children[i];
            console.log(child);
            beta = Math.min(beta, alphabeta(child, depth-1, alpha, beta, true, g));
            if (beta <= alpha) {
                console.log('beta '+beta+' alpha '+alpha);
                break;
            }
        }

        return beta;
    }
}

Answer 1

Why don't you just store the nodes that are actually visited, and colour those nodes Red. Then you will see which nodes got evaluated compared to the entire tree. E.g.

After a long discussion in the comments, I think I can now shed light on this. As the alpha beta goes around the tree, it has three values, when operating on a given node, it has the alpha and beta that were carried down to it from its parent node, and then it has the best value it has found so far. If it finds a value outside the alpha-beta window, it immediately prunes, as it knows that this node is not an optimal move, irrespective of its value. Thus, for some nodes alpha beta never works out the "true value" of the node.

Thus, when you are asked to display the "result" of alpha beta, I mistakenly thought that you meant the alpha-beta window, since the "true value" is never necessarily evaluated.

You would need to write separate code to print the "true node values". I think that the minimax algorithm will do this for you.

Also, be aware when comparing by hand that if you are using a "set" of nodes, the list iterator is not guaranteed to return the nodes in a predictable order, so if inside the nodes you are using sets rather than lists, you might find that its hard to follow by hand. List iterators return in insertion order. Set iterators have no predictable iterator.