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;
    }
}

Mcreynolds

What exactly are you trying to display? Do you want a tree like in the picture, or just log information that will allow you to follow the tree? Do you want labels on nodes so that you can verify whether your code is running correctly? – Hamman

@NathanS yes I want nodes on tree, which are blank in the task to be filled in. Also, I want to show pruning, for example by color – Mcreynolds

The problem with this question is that it doesn't look like a technical problem to solve but just like some work that you want to be done for you. If there's a precise technical blocking point, please precise what it is. – Persnickety

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.

Ellsworth

I tried it. Where exactly, I should change color of node? 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). – Mcreynolds

I tried to output alpha and beta to the tree nodes and didn't get correct result. This is code (lines 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. – Mcreynolds

Yes, this is odd. First check (1) Are you calling the algorithm with sufficient depth to reach the final level of the tree? Calling code should be e.g. alphabeta(root, 1000, -1000, +1000, true, g) Your code looks right but you have correctly identified nonsensical results. Alternatively, are you possibly not outputting every node for some reason? Make a result where you print (alpha, beta), and a different colour depending on which if statement was called. – Ellsworth

I think yes, I am calling it with correct depth. I do it with depth five, but I will try later 1000, as you suggested. Also, I will try to color different nodes by different colors, but a bit later, at the evening, but I think it will be hard to understand new coloured image, because this function is recursive and colors will be overwrited some times (just my assumption and, I think, I tried it and only first (left) node had become green). Anyway, I will try it again. Thank you. – Mcreynolds

Regarding the colours, alphabeta is called once per node, as its recursive, so if you put the colouring statements just before each return statement, you know that every node will be coloured exactly once if it is visited. – Ellsworth

I just had tried to call functions as you suggested: alphabeta(root, 1000, -1000, +1000, true, g);. Result with 1000 depth. This is result, showing that 3 is not sufficient depth: bad result. So five depth is ok. – Mcreynolds

Regarding the colours: this code (33 line and 19 line) shows this result. If maximizing then color of the node is blue, if minimizing then color of the node is red. – Mcreynolds

SO it looks like your code works correctly. Its just displaying values for nodes it didn't evaluate independently. Where we have the 5,7,6 oddity, what its doing is carrying the beta down from the second level, since it has already has a guaranteed move from the first tree to get to a 5. However, because its recursive, it must go down to the bottom once before it starts evaluating and can prune. – Ellsworth

Think of alpha and Beta as the best moves for each player given all of the paths which have already been evaluated, so they get carried from one tree to the next. So the fact that the 5 on the left most third level means that no node on the first level can have a beta less than 5. Since it gets carried up to the root node, and then down to the next tree. – Ellsworth

Yes, I understand that. But how I can make algorithm working correctly? Looks like I need some additional variable or two. What do you think? – Mcreynolds

I tried this code and got this result. At this image I pointed some vertexes. Vertexes, pointed with arrows are looking correct now, but this image shows, that some vertexes still assigning with wrong value. – Mcreynolds

I think that it is working correctly, though I have not actually checked every alpha beta value by hand. – Ellsworth

It can't work properly because it shows wrong result. Algorithm by itself might work correctly, but visualisation of it doesn't work properly. – Mcreynolds

I think it is displaying the right result, see, for example, youtube.com/watch?v=xBXHtz4Gbdo and watch how the alpha and beta are carried around. I think that the algorithm just doesn't quite do what you think it does. – Ellsworth

Try printing (alpha, Beta) in every node, and printing a graph every time it returns, so you can see how these odd results are generated. It will take a little time, but you will see that the algorithm is working. It prunes precisely because the alpha beta are not always dependent on the child nodes, if they carry sufficiently good values as it traverses the tree they are used, not the child values. – Ellsworth

When you doing same on paper with a pen you are getting normal result, right? I think algorithm should show same result, as on paper. I saw such examples, as you provided. – Mcreynolds

How sure are you that the iterator of the child nodes returns them in order? Is that guaranteed? – Ellsworth

You understand that you are out putting the alpha/beta value, not the value of the node itself - is that your confusion here? When I do it by hand I get the same alpha/beta values as your thing. But the "value" of the node is different. Nodes are pruned with the "value" violates the cut off, but you are printing the alpha.beta cut of values, not the node valules? – Ellsworth

I output all steps in console and see, that order is correct. I can copy paste it here, if you need. – Mcreynolds

I think I understand the confusion now, see my update to my answer, is that clear now? – Ellsworth

Nodes are opening in correct orders. One problem is that that nodes on 3rd level (from bottom) values are wrong. Why? – Mcreynolds

It is because I output alpha and beta to the nodes and values of alpha and beta are saving from the start. They are not resetting on new branches. So values in nodes are wrong, because values, printing to this nodes, are saving from start of the algorithm. Oh, hope you understand me. My English is bad ( – Mcreynolds

You are thinking that alpha beta is like minimax, but its not, the whole point of of this algorithm is that it does not work out the node values, it does not have to, if it find any child outside the alpha beta window the whole leg is pruned. You are out putting the alpha and beta values, the window where it won't prune, this is not the same as the node values. – Ellsworth