Reputation: 53
I have made game (Connect-4) and used MinMax algorithm with alpha-beta pruning for computer AI. What is good way to test correctness of my alpha-beta ? I am not sure of correctness, sometimes when playing against my AI it doesnt 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 litle deep (7-9 moves). How can one fix this ? (I know if alpha beta might prune something that give more difficult win if there is no way not to lose)
Upvotes: 5
Views: 2826
Reputation: 30245
Well alpha-beta pruning is only an optimization for the basic MiniMax algorithm (i.e. exclude paths that certainly won't be taken by an optimal playing enemy), so I'd just 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 wether 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 Unittests for all cases
Upvotes: 3