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:
- PvE: you know the enemy lineup and have to find a solution for the battle
- 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
- 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.
- 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.
- 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
- 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!
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
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?
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:
A: 10 Atk, 10 HP, no skill
B: 6 Atk, 10 HP, no skill
C: 3 Atk, 10 HP, skill: +6 armor to all cards
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
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