I have implemented minimax with alpha-beta pruning to play checkers. I am using only the summation of material value on the board regardless of position as my value heuristic.
My main issue lays in actually finishing games. An 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 significant material advantage with four kings and a piece against a single king, however, it moves only one piece.
I have randomly selecting a move from the list of equally valued moves and this lead 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 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 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!