In my AI class this term, I’ll make a Checkers game strategy with my group, I think maybe we will use decision tree, and if using decision tree, an alpha-beta-pruning algorithm will be very useful.

Alphaâ€“beta pruning is a search algorithm that seeks to decrease the number of nodes that are evaluated by the minimax algorithm in its search tree. It is an adversarial search algorithm used commonly for machine playing of two-player games. It stops completely evaluating a move when at least one possibility has been found that proves the move to be worse than a previously examined move. Such moves need not be evaluated further. When applied to a standard minimax tree, it returns the same move as minimax would, but prunes away branches that cannot possibly influence the final decision.

I wrote this algorithm in C++ code, and I’ll give out my pseudocode:

cut(node, num){ if(node.child.size()>num+1){ for(j=num+1; j< node.child.size(); j++){ erase(node.child[j]); } } } int alphabeta(node, depth, alpha, beta){ if(depth == 0 || node.child.empty()) return node.data; if(nod.type == MAX){ for each child of node{ temp=alphabeta(node.child[i], depth-1, alpha, beta); alpha=maxof(alpha, temp); if(beta<=alpha){ cut(node, i); //beta cut-off } } return alpha; } else{ for each child of node{ temp=alphabeta(node.child[i], depth-1, alpha, beta); beta=minof(beta, temp); if(beta<=alpha){ cut(node, i); //alpha cut-off } } return beta; } }

For testing this, I used this tree, and the tree is from an alpha beta pruning example from youtube. Values of each node is showed in parentheses.

And by running my code, we can see the result:

In my interpretation, if the state of one node, and the state of the node’s parent, is incompatible, that is, when the intersection set of these two states is NULL (in most situations) or the intersection set is one number, we can cut the unexplored subtrees of this node. Let me use our test tree to explain it.

In this picture, by searching H,M,N, we updated the state of C if “less than or equal to 4”, and the state of A is “bigger than or equal to 4”, so the intersection set is exactly 4, so no matter what value J is, everything do not change, so we cut J off; and the state of D is “less than or equal to 3”, the intersection set of A and D is NULL, so we cut L off.