Simplified Game Rules:
- Pawns can move once per turn.
- Pawns can move in 4 directions. (up, down, left, right)
- Pawns move on a grid like a chess board.
- Pawn reaching the other's row wins.
- Other rules can be ignored for simplicity.
Evaluation Function:
- If
reached to the target, return 100. - Else:
return Opponent Distance From Target-Own Distance From Target
I implemented minimax with alpha-beta pruning and specified a max-depth. I compared my implementation with several 3rd party implementations and it looks the same. So, instead of pasting my implementation, I want to ask my question directly:
When 2 AI competes against each other. They become unable to chose a meaningful direction as soon as they detect any of them wins the match, because the score becomes the same for more than 1 choice. Choosing any of those choices randomly, does not improve it as they move meaninglessly forever.
Is this (deadlock) an expected thing? If not, what can be the problem? If so, how can I fix it?
Yes, this can happen easily with a simple implementation of alpha-beta/minimax.
The best fix for this is probably iterative deepening - searching at 1...max-depth ply iteratively. This works well for several reasons:
The overhead of the extra iterations is minimal, because each iteration is much more expensive than the last. (The tree is growing exponentially.)
When you get a win for yourself on a given iteration you immediately terminate (eg don't continue searching larger iterations) and take the winning move. This avoids the problem of finding longer winning sequences and not taking the shortest one. (Solving your problem.)
You can use something like the history heuristic on the early iterations to improve your ordering on the later iterations and improve the efficiency of alpha-beta. (Which doesn't matter if you limit the max depth, but if you limit the time instead, it can be helpful.)