1
\$\begingroup\$

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?

\$\endgroup\$
3
  • \$\begingroup\$ It sounds like you've described an algorithm worth trying. Have you tried it? How did the outcome differ from what you need? \$\endgroup\$
    – DMGregory
    Nov 14, 2021 at 0:46
  • \$\begingroup\$ I just finished implementing and testing it, and it seems to produce good results - at least the moves the system generates look reasonable to me, as a player of the game. \$\endgroup\$
    – Ununoctium
    Nov 14, 2021 at 3:27
  • \$\begingroup\$ Sounds great. Want to write up your solution as an Answer below? \$\endgroup\$
    – DMGregory
    Nov 14, 2021 at 3:30

1 Answer 1

1
\$\begingroup\$

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.
\$\endgroup\$
4
  • \$\begingroup\$ Did you try 0.5 as the tie value vs 0.3? Did it behave differently? Curious why you wouldn't pick the midpoint. \$\endgroup\$
    – Stephan
    Nov 14, 2021 at 23:10
  • \$\begingroup\$ When you play against NPCs in this game, a win gets you a chance at a new card and some currency; a tie gives you currency; and a loss gives you nothing. The currency is negligible and t he chance at the card carries most of the value, so I weighted the tie below 0.5 to reflect that it has less value than 0.5 of a win. \$\endgroup\$
    – Ununoctium
    Nov 16, 2021 at 2:01
  • \$\begingroup\$ so it has no bearing on the performance of the algorithm? \$\endgroup\$
    – Stephan
    Nov 16, 2021 at 21:51
  • \$\begingroup\$ "Performance" meaning runtime duration - no impact. "Performance" meaning percent of time it's able to win - I'm not sure and that could do with some further research. Intuitively it makes sense to me that the algorithm would suggest moves that lead to ties less frequently than it otherwise would this way, but I haven't done enough testing to really be sure of that. \$\endgroup\$
    – Ununoctium
    Nov 17, 2021 at 22:18

You must log in to answer this question.

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