Algorithm to solve a battle in a card game

Question

I am trying to write a solver for a sort of card game. I mainly do that for fun, and also to be able to learn a bit about the different types of algorithms I could use for this problem.

The rules of the card game is pretty simple:

• A card has a given amount of HP and Attack and potentially a skill that increases its stats
• Each card has an element. Each element has a weakness. E.g, if a fire card is attacked by a water card, the fire card will lose 2 times more HP
• All players have the same cards available to them (new random deck every day)
• Two players confront each other
• Each player can have up to 6 cards in his lineup
• Each turn, the front card of each lineup will attack each other, reducing the HP of the opponent by its Attack
• At the end of a turn, if one of the card has 0 HP, the next card enters the battle
• This goes on until one lineup is empty
• The players cannot interact with their cards during the battle: you set-up your lineup and then you watch the match

The game has 3 modes:

1. PvE: you know the enemy lineup and have to find a solution for the battle
2. PvP: you have a setup of 6 lineups. An enemy can attack you. The engine selects one random lineup for each player and the result of this battle determines the winner of the attack
3. Tournaments: You have a setup of 3/5/7 lineups. All players battle against each other. Each lineup will confront its opposite lineup (i.e. lineup 0 of the player A will battle against lineup 0 of player B, lineup 1 against lineup 1, etc.). The winner is selected based on the amount of wins.

I have made a battle simulator that gives you the amount of damage made by the winner (positive amount if left side wins, negative otherwise).

Currently, I use a genetic algorithm to solve the three cases.

1. PvE: my genome is my lineup, each chromosome being a card. My fitness is basically the result of the battle simulation, where I try to find the first solution that works.
2. PvP: my genome is my setup, each chromosome being a lineup. My fitness function makes every genome of my population battle against each other, and tries to maximize the lineup win ratio
3. Tournaments: Same as above, but instead of selecting the lineup win ratio, I select the setup win ratio. Basically, I don't want to win for every lineups, I just want to have more wins that my opponent

The issue I have with this is that it can be random at times. Also, for the PvP and tournaments mode, the crossover/mutation is hard because it is sometimes conflicting (e.g. if, after a cross over, you end up with 3 cards of type A, while you have only 2 in your deck).

Following this, I have some questions:

• Do you think that the genetic algorithm approach is good?
• What kind of problem is this? (Knapsack, Multi-Objective Optimization, or some other combinatoric problem). I have a hard time defining this.
• What kind of algorithm could give me good results, fast?

I'll take any suggestions for this :)

Thanks a lot!

---

Update:

A little bit more of context about how the game is played:

Your deck has 80 cards, and changes every day. In this deck, you can have multiple times the same card (there is no limit for this, so you can end up with 20 times the same card).

What I want to solve is mostly the tournament/PvP part.
PvE is easy because you know the lineup of the opponent.
But for the tournament/PvP mode, you just know that the opponents will have the same deck as you, you don't know the setup he will choose.
In these modes, all players have to set-up 3/5/7 lineups based on the deck of the day and, after a time, all players will fight all other players. At that point, you cannot interact with your lineups anymore, there are no user action during the fights, you can just see the replays.

A general strategy for this is usually to have half (rounded up) of your lineup as strong as possible, in order to win 3 of the 5 lineups so that it can be counted as a win against the player.

Pseudo-code for the tournaments would be something like:

numberOfLineups := rand(3|5|7)
tournamentWins := 0
for each otherPlayer in tournamentPlayers:
  matchWins := 0
  for each i in range(1 to 3):
    yourLineup := yourself.Lineups[i]
    otherLineup := otherPlayer.Lineups[i]
    winner := fight(yourLeftup, otherLineup)
    if winner == yourself:
      matchWins += 1
    else
      matchWins -= 1
  if matchWins > 0:
    tournamentWins += 1

The goal is to maximize tournamentWins.
In this context, I don't think there can be a globally optimal solution.

What's a good algorithm to find a solution that is somewhat good in this scenario?

I could potentially store the tournaments results if necessary, if I want to train a model that will predict the strategies used by other players.
But even in this case, what model could I use to do that?

---

Update 2:

As I said in the beginning, cards can have skills. Those skills can affect only the card itself, or other card as well. Some example of skills: - give x2 damage to the card itself - give +5 armor to all cards in front of the card in the lineup - attacking damage the opponent first card for 100%, and the opponent second card for 50%

It means that we cannot always say that Card A wins against Card B: it depends on what combination of cards are present in the lineup, which is why I believe it would be something like (80 * 79 * ... * 75) possibilities, instead of (80 + 79 + ... 75). But maybe I'm wrong?

Following is an example of what I mean by 'combination can change the result of the battle'.

Let's take the following card:

• Card A: 10 Atk, 10 HP, no skill
• Card B: 6 Atk, 10 HP, no skill
• Card C: 3 Atk, 10 HP, skill: +6 armor to all cards

Fight:

Turn | Left    (HP) | (HP)    Right
   0 |        A(10) | (10)B
   1 |        A( 4) | ( 0)B
-----------------------------------
          Winner

Turn | Left    (HP) | (HP)    Right
   0 |        A(10) | (10)C
   1 |        A( 7) | ( 6)C
   2 |        A( 4) | ( 2)C
   3 |        A( 1) | ( 0)C
-----------------------------------
          Winner

Turn | Left    (HP) | (HP)    Right
   0 |      A-A(10) | (10)B-C
   1 |      A-A( 4) | ( 6)B-C
   2 |      A-A( 0) | ( 2)B-C
   3 |        A(10) | ( 2)B-C
   4 |        A( 4) | ( 0)B-C
   5 |        A( 4) | (10)C
   6 |        A( 1) | ( 6)C
   7 |        A( 0) | ( 2)C
-----------------------------------
                         Winner

As you can see, even if A wins against both B and C in a one-on-one match, a A-A lineup cannot win against a B-C lineup because of the bonus that C gives to B.

Answer 1

Update 2: Your second update was very helpful/informative.

You have shown that this is a very large search space (roughly 2^38.) This is probably too big, but let's look at possible solutions from the Search perspective anyway:

• One could be breaking the problem up to approximate a good answer. Imagine finding the optimal pair for the deck; this is 80 * 79 for the first pair (which is only 2^13 or so), and similar for the other pairs.

• • Then one could imagine looking at optimal pairs of things, and performing a search on combinations of optimal pairs (the top 6 pairs or something) in order to find powerful combinations

If you were to go that route, you may be able to start your Learning AI search near very powerful (but likely not perfect) solutions. Intuitively, there should be some way to add heuristics for "This guy buffs the whole team, so pick him more often", but that'd be up to you to choose what makes sense.

From the learning perspective, I think Neural Nets make more sense for your problem than genetic algorithms. With such a giant search space, genetic algorithms will have to be lucky to start "nearby" a "global peak" and will only move slowly to "local peaks", where you may get "stuck" with a locally optimal but globally suboptimal solution.

Neural nets should be able to find trends of "what are powerful combinations" and it's fairly low effort to train 3 or 6 of them (starting with random weights) and just run it until it's win percentage is high. I would definitely run competing neural nets in a round robin tournament so that they don't just find solutions to the other neural net.

Hope this answer finds you well! Note: (if unfamiliar) look up Model Distillation and Model Calibration for combining neural nets.

---

Update:

If you were doing it such that it was like Pokemon (you use a guy until he dies) I could see it being an intractable search space without extreme pruning (80 * 79 * ... * 75); however, you are actually only looking for the best guy in each slot.

I'd consider simply using a search space as singleton matches in a search algorithm. This means you only have 465 (80 + 79 + ... 75) checks to make because you don't care what your previous choices were since they don't influence your current choice (other than what you can't choose.) If you actually make a list of the rankings, it's down to only 80 checks, because the top 6 would be your choices.

Simply calculating the average best character based on it's ranking against the full list of opponents you'll get something close to optimal (on average.) Then you can randomize this list slightly by reordering the choices it makes so it's difficult to meta-game against it.

If meta-gaming becomes an issue, now you can build more intelligent variations based on an even smaller search space, possibly starting your genetic algorithm with those who have high-average win rates.

Note: you should eventually use this AI with a group of interested players who will meta game and simply track statistics of average use of characters. Once you have an idea of this you can start deploying Ais that meta the meta and so forth.

---

Disclaimer: I am an AI Professional who works with neural nets but have a standard CS degree (so take it with a grain of salt.)

This is an optimization problem: Maximum Damage Dealt while Minimum Damage Taken

This is a deterministic problem, meaning you can math out the the entire solution space of a given problem simply by searching and ranking the results. This would mean it's definitely in the realm of "Search based AIs" and not "Learning AIs" IMO. EDIT: This is not quite true with a 2^38 search space and a low amount of time for "thinking." It may still be possible (for future readers) but I recommended a NN.

Similar to the above, deterministic solutions are easy to adjust for difficulty (make the search space smaller, choose suboptimal moves at times on purpose, introduce randomness); but will also give you the best possible solution immediately, every time.

---

Note: My university made a distinction that I realize a lot of people don't have, which is Search-based vs. Learning-based AIs; so I will explain.

Search Based AIs require no training to be effective and are done by searching all (or many) possible boardstates and weighing the results via heuristics (which could be trained if you desired.) They tend to require Perfect Information and will only choose a different move if you explicitly have randomization in part of your move-determination (usually picking between a set of equal moves within the search space.) A popular example of this is Chess. They also tend to be a deterministic approach to the problem.

Learning Based AIs require training and tend to be better at games that have random or a very high number of board states. A popular example of this is Backgammon. They also tend to be a statistical approach to the problem.

This is not to say the approaches can never be combined; just that this is the language/distinction used in my answer above that I have found is not universal among my peers.