Minimax in a losing scenario vs an imperfect player

Question

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:

1. Use Negamax search to try to select your best move. Instead of finding one best move, find all moves with the highest score.
2. 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?

Answer 1

I ended up implementing and testing the Monte-Carlo method I described in my question, and it seems to work quite well as a tiebreaker for the Negamax search.

Here's some details and thoughts about the implementation:

• I ended up simulating 100k games for each tiebreak. I started with 10k, but didn't quite get the consistent results; with 100k, the output was the same every time I tested it.
• The simulation I went with is purely random - on each player's "turn", it gathers a list of all possible moves and randomly chooses one.
• Since ties are possible, when counting up the results of the simulations, I assigned values of 1 for a win, 0.3 for a tie, and 0 for a loss, and averaged those values across all the simulations, selecting the outcome with the maximum average value. These selections were arbitrary and different values might have significant improvements on performance.
• Performance: Using parallelization following the general Map-Reduce strategy (thanks to the Rayon library), I could run 50-60 Monte-Carlo simulations (each with 100k iterations) in about 1 second on my Ryzen 3700x. This is comparable to the time it takes to search the game tree itself (about 1.8 seconds from an empty board). Disabling that concurrency made the same simulations take about 10 seconds.
• The simulation leads to plays that seem to be "good", from the perspective of a human who also plays the game. For example, the overall algorithm now plays cards with high numbers facing inwards and low numbers facing towards the edges, which is basic good strategy in the game.