Testing MinMax with alpha-beta pruning and strategy for play

Question

I have made a game (Connect-4) and used the MinMax algorithm with alpha-beta pruning for computer AI. What is a good way to test the correctness of my alpha-beta? I am not sure of correctness, sometimes when playing against my AI it doesn't make the play that will make the game last longer if it has seen a loss deeper down and it is difficult to check things by hand and with unit testing when it starts searching just a little deep (7-9 moves). How can one fix this? (I know if alpha-beta might prune something that gives more difficult win if there is no way not to lose)

Answer 1

Alpha-Beta pruning is not a new algorithm, rather an optimization technique for the minimax algorithm. It decreases the computation time by a huge factor. This allows us to explore much faster and even go into deeper levels in the game tree. It cuts off branches in the game tree which need not be explored because there already exists a better move available. It is known as Alpha-Beta pruning because it passes 2 extra parameters in the minimax function, namely alpha and beta.

You just have to compare the results of the alpha-beta algorithm to the simpler MiniMax one. As soon as they disagree you've got a bug in one of the two algorithms.

That simplifies the problem to testing whether your MiniMax algorithm is correct and well I can't think of any special tricks for that - but since it's a recursive function it should be possible to write unit tests for all cases.