Optimising an exhaustive search for a card game

Question

I'd like to search for a combination of resources that when used, would produce at least up to a threshold of different kinds of materials. For the majority who are not in the know, I'll use an analogue for the rest of the question. For the few who benefit from this information: the game I'm referring to is Magic The Gathering, and the problem is finding whether or not a set of lands can cast a given card.

We can think of the materials as steel and wood. Any resource produces a combination of them. For example:

Requirement: 1 steel + 2 wood
Resources:
- 1 steel + 1 wood
- 1 wood
Verdict: POSSIBLE

There may be generic requirements, which can be fulfilled by whatever resource is available.

Requirement: 2 ANY + 1 wood
Resources:
- 1 steel
- 1 wood
- 1 wood
Verdict: POSSIBLE

Resources may be used to produce different combinations at will, when stated of course.

Requirement: 1 steel + 1 wood
Resources:
- 1 steel
- 1 steel OR 1 wood
Verdict: POSSIBLE

Finally, there may be costs associated with certain production. Here marked as cost -> production. Costs are production specific.

Requirement: 2 steel
Resources:
- 1 steel
- 1 wood
- 1 wood -> 1 steel OR 0 -> 1 wood
Verdict: POSSIBLE

Now, given a set of these resources it is relatively easy to figure out if a given requirement can be fulfilled. What I have currently is a naïve exhaustive search with one optimisation (step 1). In pseudo-python it goes as follows:

1. produce with resources that have only one production and no cost to have current "production"
2. can_fulfill(requirement, current production, resource list)

def can_fulfill(requirement, production, resources):
    for i, resource in enumerate(resources):
        remaining = resources[:i] + resources[i + 1:]
        for cost, gain in resource:
            if can_subtract(production, cost):
                new_production = production - cost + gain
                if fulfilled(requirement, production):
                    return True
                recur = can_fulfill(requirement, new_production, remaining)
                if recur:
                    return True
    return False

It does work, and for single-production resources it is lightning fast. But in this particular case there can be many resources with multiple production options, which slows the calculation. I think the exhaustive search is my only option, because one can't know which productions ultimately lead to the fulfillment of a requirement, but could there be more clever optimisations I could implement?

My parameters are somewhat conservative for these kinds of optimisation problems I think: I expect to have up to twenty resources, each with up to eight - typically three different productions. In the game there are five production types (steel, wood and 3 more).

Answer 1

I suspect this may be NP-hard in general but probably feasible to solve efficiently in practice for the parameter sizes you discussion.

I will suggest an approach based on comments from j_random_hacker. One plausible approach is to express this as an integer linear programming problem. Let $a_{im}$ be the amount of material $j$ you have after the $i$th step of applying sources, $b_{ir} = 1$ if you apply resource $r$ in the $i$th step or 0 otherwise, and then write constraints to express that each step obeys the rules you've followed. See Express boolean logic operations in zero-one integer linear programming (ILP) for some general techniques for that. For instance, you'll have a requirement that $a_{im}\ge 0$ for all $i,m$; that $\sum_i b_{ir} \le 1$, that $\sum_r b_{ir} = 1$; and so on. If you have a resource that contains multiple alternative combinations, treat each as its own resource and then add a constraint that if you pick one of those combinations in any step you can't pick any of the others ($\sum_i \sum_{r \in R} b_{ir} \le 1$, where $R$ is the set of all combinations associated with a single resource). If resource $r$ is "1 wood -> 1 steel", then we'd obtain a rule like

$$b_{ir}=1 \implies\\ (a_{i-1,\text{wood}} \ge 1 \land a_{i,\text{wood}} = a_{i-1,\text{wood}} - 1 \land a_{i,\text{steel}} = a_{i-1,\text{steel}}+1).$$

Then, convert that to an ILP constraint using the techniques at the link above.

Finally, you can apply an off-the-shelf ILP solver to search for a solution.

Note that the order in which you applies resources matters, because you can never go negative on any material, which complicates the ILP instance a little bit and requires you to have a separate copy of each variable per step.

---

If you prefer to adjust your exhaustive search, there may be ways. One possibility is to use branch-and-bound to prune off some parts of the search space. At any intermediate point in your search, you can get a simple bound on whether it's possible that a solution could exist from here by picking a single material, say wool, counting how many wool you already have, counting how much more wool you could possibly make if you used every remaining wool-producing resource to produce the maximum amount of wool (assuming optimistically all its preconditions can be met), and checking whether that would give you enough wool to meet the target. If not, then there's no point continuing the search from here; you can prune the search. Another way to get a simple bound is to look at the total number of materials, ignoring their type (e.g., total amount of mana, ignoring color); then using each resource that you haven't used so far that increases the number of mana (assuming optimistically that it can be used), and check how much mana total that would give you; if that's not enough for your target, then you can prune the search.

However, ILP solvers already use branch-and-bound, and they are probably doing something that generalizes this and is more powerful. So, rather than implementing branch-and-bound yourself with some limited set of bounds, I suspect it might be more powerful to use a full ILP solver.