Macro Solver ‐ How it works

Introduction

Problem definition

Given a configuration (recipe, crafter stats), we want to find a crafting macro that has the following properties:

• It finishes the craft (gets Progress to 100%).
• It achieves the highest Quality possible (it should be impossible to find a rotation that gives higher Quality).
• (Optional, To-do) The macro duration is minimized.

Note: In-game crafting has random conditions (Normal, Good, etc.) at each step. However, we will assume that the condition is always Normal.

Solvers

What the user sees as the "Macro Solver" is actually a collection of 3 different solvers:

• Macro Solver (entry point, main search loop)
• Finish Solver (used for automatic branch pruning): Given a state, calculates if it is possible to get Progress to 100% from that state.
• Upper-bound Solver (used for automatic branch pruning): Given a state, gives an upper-bound on the maximum Quality achievable from that state while also getting Progress to 100%.

Macro Solver

Search space

The entire search space can be thought of as a directed graph, where:

• Each node represents a simulation state and each simulation state is represented by exactly one node.
• There is an edge from state S to state S' iff it is possible to get state S' from state S by applying a single action.

Because we assume that the condition is always Normal, the graph is actually acyclic.

Search space explosion

At the time of writing, there are ~27 actions that are relevant for crafting macros. With endgame crafting rotations easily requiring 20+ steps, the search space quickly grows out of control.

As an example, 20 steps with a branching factor of 27 results in 42391158275216203514294433201 total states. If we process 1 billion states per second (which is already a lot more than a normal consumer CPU can do), we would need to wait approximately 1344214810857 years.

De-duplicating states (only processing states that we have never seen before) helps, but the amount of states remains too large:

Each state is characterized by the following parameters:

• Main parameters: Progress, Quality, Durability, CP
• Effects: Inner Quiet, Waste Not, Innovation, Veneration, Great Strides, Muscle Memory, Manipulation.
• Last Action (needed for combos)

Assuming 5000 Progress, 10000 Quality, 70 Durability, and 600 CP (which is very realistic for late-game crafts), the number of search states is just way too high.

Branch pruning & Guided search

When confronted with a gigantic search space it is always a good idea to do some sort of branch pruning. In our case, we avoid visiting states that we know for sure don't lead to the optimal solution. This is where the other solvers come into play:

• Don't visit states where it is impossible to get Progress to 100%. (Finish Solver)

• Don't visit states whose Quality upper-bound is less than the current best Quality. (Finish Solver + Upper-bound Solver)

  • The best Quality is initially 0.
  • For each state visited, if it is possible to get Progress to 100%, we update the best Quality with the current Quality.

In summary, the branch pruning logic looks something like this:

best_quality := 0
for state in search_queue.pop():
    if not can_finish(state):
        continue
    if quality_upper_bound(state) <= best_quality:
        continue
    if state.quality > best_quality:
        best_quality := state.quality
    // push all children into the queue

The effectiveness of the Quality upper-bound pruning relies heavily on two things:

• The tightness of the upper-bound. (Covered in the section about the Upper-bound Solver)
• The tightness of the lower-bound, i.e. the current best solution.

To improve the lower-bound, we want to find a "good" solutions quickly. To this end, the Macro Solver uses a modified A* search:

• Instead of a min-heap for the search queue, we use a max-heap where each node/state is weighted by its Quality upper-bound.

Finish Solver

Given a state, is it possible finish (max out Progress) on that state?

Search space

Because the Finish Solver only cares about maxing out Progress, it can discard a lot of irrelevant information from a state. The reduced state only has to store the following information:

• Main parameters: Progress, Durability, CP
• Effects: Manipulation, Waste Not, Veneration, Muscle Memory
• Last Action (needed for combos)

The search space in this case is much, much smaller than the full search space of the macro solver, but it is still a bit large.

Dynamic programming

We can further reduce the search space by converting this problem into a dynamic programming (DP) problem. If we move Progress out of the state and make it the maximization goal, the problem becomes

Given a state, what is the maximum Progress that one can squeeze out of that state?

DP state:

• Main parameters: Durability, CP (8400 possible combinations, assuming 70 Durability and 600 CP)
• Effects: Manipulation, Waste Not, Veneration, Muscle Memory (2430 possible combinations)
• Last Action (needed for combos) (3 possible values, since we use the same value to represent all non-combo actions)

Because of the small search space, the problem is now easily solvable without any further optimization.