Alpha-Beta Pruning:

 An adjustment to Minimax to decrease the runtime by not going down paths that the other player wouldn't let you go down anyway; i.e. paths that could not possibly improve your max value or your min value (depending on which player you are).

Minimax works by using a numeric value to the state of the game.  In Othello, this is easy.  Use Black Tokens - White Tokens.  In other games, finding that numeric isn't as straightforward...especially for games with a large search space.

In Chess, we can give an approximate value to the state of the game.  Q = 10, R = 5, N = B = 3, P = 1.  And our numeric value could be W - B, with white trying to maximize and black trying to minimize it.

Another reason we might want to prune the tree, is if we come to a state of the board that we have already seen.  In checkers or chess, you can hit a state of the board that you have already visited.  However, in Othello, this never happens, since the number of pieces increases by one on each move; you have a game state occurring twice. (Actually, if you're computing lookahead moves, you may very well come across the configuration more than once.) In games where a game state occurs more than once, you might want to use a hash table to something to keep track of previous states so that you don't have to recompute them while you're doing your alpha-beta pruning.

The other major reason to prune the tree is because you don't have the resources or the lifespan to work out the exact answer all the way to termination of the game.  So, you have to make some sort of decision as to which path is the correct path to take without actually computing the final destination.  This decision may actually turn out NOT to yield the best choice of move, but it's based on the limited, imperfect information we have at the time.  This sort of pruning is called a heuristic.  Heuristics drive theoreticians crazy.  It's not worth your time to "prove" anything about heuristics.  You want to prove that this heuristic guarantees a value within, say, a certain range of the best minimax result.  But these proofs are notoriously difficult, and by the time you work it out, someone else will have a better heuristic.

So, with Othello, a very easy to compute heuristic, what is B-W k moves from now?  Is this a perfect strategy?  Of course not.

int min (int a, int b) {

 return (a < b)?a:b;
}

#undef min