I’m working on a solver for Triple Triad, a simple two-player zero-sum card game. Right now, I’m using Negamax (a variant of the well-known Minimax algorithm) with alpha beta pruning, and the game is simple enough that I can usually explore the entire search tree in a reasonable amount of time. I have it working, but I’m running into an interesting problem: in many cases, if A’s deck is much better than B’s, then no matter what move B makes first, A can always win with perfect play.
But in this game, normally you play against an opponent who doesn’t actually make perfect plays. I’m trying to think of a way to still optimize for B to make the move that gives them the best chance of winning. Right now my best idea is essentially:
- Use Negamax search to try to select your best move. Instead of finding one best move, find all moves with the highest score.
- For each possible move with the highest score, apply that move and simulate a large number of games with random play by both players for the remainder of the game. Select the move in which you won the largest number of games.
Heuristics could be applied to the Monte-Carlo search to make certain moves more likely based on their immediate outcome.
Are there any well-known algorithms for this type of problem – a problem where you want to maximize your odds of winning a losing game versus a sub-optimal opponent? Are there any obvious problems I’m missing with my proposed solution?