I have implemented minimax with alpha-beta pruning to play checkers. As my value heuristic, I am using only the summation of material value on the board regardless of the position.
My main issue lays in actually finishing games. A search with depth 14 draws against depth 3, since the algorithm becomes stuck in a loop of moving kings back and forth in a corner. The depth 14 player has a significant material advantage with four kings and a piece against a single king, however, it moves only one piece.
I have randomly selected a move from the list of equally valued moves and this leads to more interesting games (thus preventing the loop). However, whichever player used this random tactic ended up far worse off.
I am not quite sure how to solve this problem. Should I do a deeper search of the best moves with the same value? Or is the heuristic at fault? If so, what changes would you suggest?
So far I have tried a simple genetically generated algorithm that optimizes a linear scoring function (that accounts for the position). However as the algorithm optimized, it led to only draws and the same king loop.
Any suggestions for how to stop this king loop are very welcome!