algorithms – Optimising an exhaustive search for a card game


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.

Requirement: 2 steel
Resources:
- 1 steel
- 1 wood
- 1 wood -> 1 steel
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?