# Finding an algorithm for the given problem

Let's presume that we have a PVP fight scene, where 1 or 2 heroes, are fighting 3 monsters.

The monsters that the heroes are fighting are the following:

Skeleton (2 of this monster)

Health: 1
Defense: 0
Attack: 1

Death Knight (1 of this monster)

Health: 4
Defense: 1
Attack: 3

Whenever a hero attacks, the defense of the monster is reduced from the damage the hero deals.

The heroes are the same, they can use one of two attacks, an attack, that deals 1 damage to every enemy, or an attack, that deals 3 damage to a single enemy.

The objective of the heroes are to sustain as few damage as possible from the monsters.

If a single hero faces this threat, the optimal move would be, to use it's mass attack, to kill the two Skeletons first with one shot, and then kill the Death Knight in the following two turns, this way sustaining a total damage of: (3)+(3)=6. (if the single hero tries to kill the Death Knight first, he needs two turns to do so, so he will sustain (3+1+1)+(1+1)=7 damage

But if two heroes are present, it would be more wiser for the heroes, to gang up on the Death Knight firstly, with two single attacks(which eliminate him), and then either clear out the skeletons with a single mass attack, or with two simple attacks. This way the total damage sustained would be (1+1)=2. (if they clear the Skeletons with a single mass attack, and the other hero attacks the Death Knight, they would sustain a total of (3)=6 damage, as they would still need a second turn to kill the Death Knight.)

NOTE: the parantheses are the damages sustained in a turn

How could I find an algorithm, that would tell my heroes which attack is more cost-worthy for them to use? I could try brute forcing it, but in larger scenarios (ie: 4 heroes vs 9 different monsters) it just too resource intensive to achieve.

This would be used in a little script, which makes some calculations for me, which will be used to balance a board game that I am in the progress of making. If this isn't the correct stack site for my question, please point me in the correct direction. Note: I only need an algorithm, which I should use, no programming advice needed for the completion of the script.

EDIT 1: Based on this example, I could say that the correct move is always the one, which kills the most monsters in a single case, but this isn't correct, if we increase the Death Knights damage, so the correct move must have a score which is calculated using the monsters attack, and the number of monsters that can be killed in a single turn. Am I right in assuming this?

• Well, sort of, but I rather remove that whole part of the question, cause it's kinda misleading, sorry Commented Dec 8, 2015 at 14:14
• I think there is a small error in your second example. If the two hero first kill the Skeletons with a single mass attack and the second hero attacks the Death Knight then the Death Knight has only 2HP left. Thus, he will be killed in the second round and the total damage would only be (3) = 3 (which is still worse than 2, though). Commented Dec 9, 2015 at 9:34
• You are right, thank you for the correction:) Commented Dec 9, 2015 at 12:32
• To clarify: mass attack can only attack enemies of the same type? Commented Dec 11, 2015 at 23:37
• note sure if this help enough, but en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning Commented Dec 12, 2015 at 19:57

The algorithm depends on the definition of "best", i.e., some kind of payoff function based on the outcome of the battle. In your example the negative payoff is the number of rounds before all enemies are dead; the good guys/gals try to minimize that function and the enemies try to maximize it (which may not be the same as dealing as much damage as possible).

In the same vein, one "move" consists not of a single player attacking another player, but all players of one party executing one attack each, followed by all remaining players of the opposing party executing one attack each. Because an attack does not alter the state of your companions, the order in which these individual attacks by the same party are executed is immaterial (but you can pre-optimize the strategy by avoiding moves that involve attacking an opponent that just died during the same round).

If there is a single move that kills all the remaining opponents then that is obviously the best move; we could say that it has penalty 1 because it adds 1 to the total number of moves needed to exterminate the enemy.

In general, the price of a move is the maximum, taken over all possible enemy countermoves, of the price of our best response to that countermove.

This recursive definition results in an algorithm that is guaranteed to terminate because every move strictly decreases the total defense of the enemy, which was finite to begin with. It is probably what you refer to as "brute force" and the technical name is minimax for what should by now be obvious reasons.

The most popular implementation of this algorithm contains an optimization called alpha-beta pruning. It is based on the observation that the brute force attack effectively runs through a tree (all possible evolutions of the battle), and it eliminates certain branches of the tree (thus avoiding to have to run through them) based on the observation that these branches are guaranteed to give no better results than branches that have already been examined.

The WP article that commenter Michael Medvinsky refers to mentions further improvements.

If the remaining total defense of the enemies is large, then there is a heuristic that will give an immediate result, almost always optimal or nearly optimal, without recursion: choose the attacks that inflict the maximum total damage to all enemies combined. Among such moves that inflict equal total damage, privilege the ones that "level" the score by decreasing as much as possible the highest individual defense score of an enemy (so that your later multi-target attacks remain more efficient).

This heuristic can be used to cut off the tree at a certain depth.

You want to use the class of algorithms like Minimax (https://en.wikipedia.org/wiki/Minimax). What you essentially want to do is to make a tree of all possible game states that emerge in the next 2 or 3 turns. That lets you decide which moves to make. If there is an element of chance or randomness, you can use a variant called Expectimax.

Algorithms like these are very frequently used in tic-tac-toe or chess playing softwares (with lots of changes to improve efficiency)