Magic: the Gathering Combat Golf

Question

Magic: the Gathering is a trading card game where, among other things, players play cards representing creatures, which can then attack the other player, or defend against the other player's attacks by blocking.

In this code-golf challenge, your program will be in the place of a Magic player deciding how to block in combat.

---

Each creature has two relevant attributes: Power, and toughness. A creature's power is the amount of damage it can deal in a combat, and its toughness is the amount of damage necessary to destroy it. Power is always at least 0, and toughness is always at least 1.

During combat in Magic, the player whose turn it is declares some of their creatures to be attacking the opponent. Then, the other player, known as the defending player, may assign their creatures as blockers. A creature may block only one creature per combat, but multiple creatures may all block the same creature.

After blockers are declared, the attacking player decides, for each attacking creature that was blocked, how to distribute the damage (equal to its power) that that creature deals to the creatures blocking it.

Then, damage is dealt. Each creature deals damage equal to its power. Attacking creatures that were blocked deal damage as descibed above. Unblocked attacking creatures deal damage to the defending player. Blocking creatures deal damage to the creature they blocked. Creatures belonging to the defending player that did not block deal no damage. (Creatures are not required to block.)

Finally, any creature dealt damage equal to or greater than its toughness is destroyed, and removed from the battlefield. Any amount of damage less than a creature's toughness has no effect.

---

Here's an example of this process:

A creature with power P and toughness T is represented as P/T

Attacking:
2/2, 3/3
Defending player's creatures:
1/4, 1/1, 0/1
Defending player declares blockers:
1/4 and 1/1 block 2/2, 0/1 does not block.
Attacking player distributes damage:
2/2 deals 1 damage to 1/4 and 1 damage to 1/1
Damage is dealt:
2/2 takes 2 damage, destroyed.
3/3 takes 0 damage.
1/1 takes 1 damage, destroyed.
1/4 takes 1 damage.
0/1 takes 0 damage.
Defending player is dealt 3 damage.

---

The defending player has 3 goals in combat: Destroy the opponent's creatures, preserve one's own creatures, and be dealt as little damage as possible. In addition, creatures with more power and toughness are more valuable.

To combine these into a single measure, we will say that the defending player's score from a combat is equal to the sum of the powers and toughnesses of their surviving creatures, minus the sum of the powers and toughnesses of their opponent's surviving creatures, minus one half of the amount of damage dealt to the defending player. The defending player wants to maximize this score, while the attacking player wants to minimize it.

In the combat shown above, the score was:

Defending player's surviving creatures:
1/4, 0/1
1 + 4 + 0 + 1 = 6
Attacking player's surviving creature:
3/3
3 + 3 = 6
Damage dealt to defending player:
3
6 - 6 - 3/2 = -1.5

If the defending player had not blocked at all in the combat described above, the score would have been

8 - 10 - (5/2) = -4.5

The optimal choice for the defending player would have been to block the 2/2 with the 1/1 and the 1/4, and to block the 3/3 with the 0/1. If they had done so, only 1/4 and the 3/3 would have survived, and no damage would have been dealt to the defending player, making the score

5 - 6 - (0/2) = -1

---

Your challenge is to write a program which will output the optimal blocking choice for the defending player. "Optimal" means the choice which maximizes the score, given that the opponent distributes damage in the way which minimizes the score, given how you blocked.

This is a maximin: The maximum score over the damage distributions which minimize score for each blocking combination.

---

Input: The input will consist of two lists of 2-tuples, where each 2-tuple is of the form (Power, Toughness). The first list will contain the powers and toughnesses of each attacking creature (you opponent's creatures). The second list will contain the powers and toughnesses of each of your creatures.

Tuples and lists may be represented in any convenient format, such as:

[[2, 2], [3, 3]]
[[1, 4], [1, 1], [0, 1]]

Output: The output will consist of a series of 2-tuples, in the form (blocking creature, blocked creature) - that is, one of your creatures followed by one of their creatures. Creatures will be refered to by their index in the input lists. Indexes may be 0 or 1 indexed. Again, any convenient format. Any order is fine. For example, the optimal blocking scenario from above, given the above input, might be represented as:

[0, 0]    # 1/4 blocks 2/2
[1, 0]    # 1/1 blocks 2/2
[2, 1]    # 0/1 blocks 3/3

Examples:

Input:
[[2, 2], [3, 3]]
[[1, 4], [1, 1], [0, 1]]
Output:
[0, 0]
[1, 0]
[2, 1]

Input:
[[3, 3], [3, 3]]
[[2, 3], [2, 2], [2, 2]]
Output:
[1, 0]
[2, 0]
or
[1, 1]
[2, 1]

Input:
[[3, 1], [7, 2]]
[[0, 4], [1, 1]]
Output:
[1, 0]
or
[0, 0]
[1, 0]

Input:
[[2, 2]]
[[1, 1]]
Output:

(No output tuples).

Input and output may be via STDIN, STDOUT, CLA, function input/return, etc. Standard loopholes apply. This is code-golf: shortest code in bytes wins.

---

To clarify the spec and provide initial ideas, this pastebin provides a reference solution in Python. The best_block function is a sample solution to this challenge, and running the program will provide more verbose input and output.

Answer 1

JavaScript (ES7),  354  348 bytes

Takes input as ([attackers], [defenders]).

(a,d,O,M)=>eval(`for(N=(A=a.push([,0]))**d.length;N--;)O=a[X='map'](([P,T],i)=>S-=((g=(n,l)=>n?l[X](([t,S],i)=>g(n-1,b=[...l],b[i]=[t-1,S])):m=l[X](([t,S])=>s+=t>0&&S,s=0)&&s>m?m:s)(P,l[n=0,i][X](m=([p,t])=>[t,p+t,n+=p])),n<T&&P+T)+(l[i]<1?T/2:-m),S=0,d[X]((x,i)=>l[(j=N/A**i%A|0)<A-1&&o.push([i,j]),j].push(x),o=[],l=a[X](_=>[])))&&S<M?O:(M=S,o)`)

Try it online!

Less golfed and formatted

This code is identical to the golfed version, just without the map aliases and the eval() wrapping for readability.

(a, d, O, M) => {
  for(N = (A = a.push([, 0])) ** d.length; N--;)
    O =
      a.map(([P, T], i) =>
        S -=
          (
            (g = (n, l) =>
              n ?
                l.map(([t, S], i) => g(n - 1, b = [...l], b[i] = [t - 1, S]))
              :
                m = l.map(([t, S]) => s += t > 0 && S, s = 0) && s > m ? m : s
            )(
              P,
              l[n = 0, i].map(m = ([p, t]) => [t, p + t, n += p])
            ),
            n < T && P + T
          ) + (
            l[i] < 1 ? T / 2 : -m
          ),
        S = 0,
        d.map((x, i) =>
          l[
            (j = N / A ** i % A | 0) < A - 1 && o.push([i, j]),
            j
          ].push(x),
          o = [],
          l = a.map(_ => [])
        )
      ) && S < M ? O : (M = S, o)
  return O
}

How?

Initialization and main loop

The first thing we do is add a dummy attacking creature with an undefined power and a toughness of \$0\$. The push method returns the new number \$A\$ of attacking creatures, including this one.

A = a.push([, 0])

We are going to block this dummy creature instead of blocking no creature at all. This allows some simplifications in the code.

The number of combinations for the defending player can be expressed as \$A^D\$, where \$D\$ is the number of defenders. We use a for loop with the counter \$N\$ to iterate over all these possibilities.

for(N = (A = a.push([, 0])) ** d.length; N--;)

The score of the current iteration and the maximum score are stored in \$S\$ and \$M\$ respectively. Similarly, the current solution and the best solution are stored in \$o\$ and \$O\$.

At the end of each iteration, we test whether \$M\$ and \$O\$ need to be updated.

O = (...) && S < M ? O : (M = S, o)

Building our defense

Below is the block of code which is executed at the beginning of each iteration. A new important variable in there is \$l\$, which holds a list of blockers for each attacker.

d.map((x, i) =>              // for each defender x at position i:
  l[                         //   update l[]:
    (j = N / A ** i % A | 0) //     j = index of the attacker that we're going to block
    < A - 1 &&               //     if this is not the 'dummy' creature:
    o.push([i, j]),          //       add the pair [i, j] to the current solution
    j                        //     use j as the actual index to update l[]
  ].push(x),                 //   push x in the list of blockers for this attacker
  o = [],                    //   initialize o to an empty list
  l = a.map(_ => [])         //   initialize l to an array containing as many empty lists
                             //   that there are attackers
)                            // end of map()

Optimizing the attack

The decisions of the attackers are uncorrelated to each other. The global optimum for the attacking side is the sum of the local optima for each attacker.

We iterate on each attacker of power \$P\$ and toughness \$T\$ at index \$i\$.

a.map(([P, T], i) => ...)

To find the best decision for an attacker, we first build a new list derived from \$l[i]\$:

l[n = 0, i].map(m = ([p, t]) => [t, p + t, n += p])

Each entry in this list contains the toughness of the blocker, followed by its score (power + toughness). While building this list, we also compute \$n\$ which is the sum of the powers of all blockers. We'll use it later to test if the attacker is destroyed. (The fact that intermediate sums are stored as a 3rd entry for each blocker is just a golfing trick to save a few bytes. This 3rd entry is not used.)

We now call the recursive function \$g\$ with 2 parameters: the power \$P\$ of the current attacker and the list defined above. This function tries all possible ways of dispatching the damage points among the blockers.

(g = (n, l) =>            // n = remaining damage points; l = list of blockers
  n ?                     // if we still have damage points:
    l.map(([t, S], i) =>  //   for each blocker of toughness t and score S at index i:
      g(                  //     do a recursive call:
        n - 1,            //       decrement the number of damage points
        b = [...l],       //       create a new instance b of l
        b[i] = [t - 1, S] //       decrement the toughness of blocker i
      )                   //     end of recursive call
    )                     //   end of map()
  :                       // else:
    m =                   //   update the best score m (the lower, the better):
      l.map(([t, S]) =>   //     for each blocker of toughness t and score S:
        s += t > 0 && S,  //       add S to s if this blocker has survived
        s = 0             //       start with s = 0
      ) &&                //     end of map()
      s > m ? m : s       //     set m = min(m, s)
)                         //

Updating the defender score

After each iteration on an attacker, we update the defender score with:

S -= (n < T && P + T) + (l[i] < 1 ? T / 2 : -m)

The left part subtracts the score of the attacker if it has survived. The right part subtracts half the toughness of the attacker if the attack was not blocked at all, or adds the best attacker score otherwise (which is the worst one from the defending side perspective).