6
$\begingroup$

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!

Improve this question
$\endgroup$
1
  • $\begingroup$ It may be that you don't have a good condition for "tie-breakers" in your terminal states(try boundary value analysis, fiddle with your if-statement conditions), so it keeps undoing its own progress. What are the evaluation- and utility functions in your implementation? $\endgroup$
    – Jack Of Blades
    Jan 5, 2020 at 5:21

1 Answer 1

Reset to default
1
$\begingroup$

I think this issue stems from the fact you aren't taking position into account. I would think this because as the game progresses, the number of moves that will result in a piece being taken becomes less and less, especially when there's only a few pieces left and quite a bit of "chasing" must occur before a piece is taken, likely more chasing then a depth of 14 allows.

To remedy this, you could, towards the end of the game, add to the value of a state the inverse of the total distance each friendly piece has from other pieces, that way the agent will try to move towards other pieces and minimise this distance. If you find the right scale for this heuristic, the agent will prioritise moving towards enemy pieces only when it cant find any moves that result in taking a piece, helping it break out of this loop.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .