Algorithm Overview
Raphael XIV is a crafting macro generator for the online game Final Fantasy XIV.
This document assumes that you are already familiar with FFXIV's crafting mechanics, dynamic programming, and best-first search on a directed acyclic graph. The goal of this document is to give a high-level overview of the algorithms Raphael uses to find a solution, focusing only on the default solver configuration.
Non-default configurations (e.g. 100% reliability, specialist actions, etc.) and low-level optimizations (parallelism, SIMD, etc.) will not be mentioned.
Note
This document reflects the state of Raphael version 0.25.0.
Given a recipe and the stats of the crafting job, we want to find the most "optimal" crafting macro. Different people may have different definitions for what makes a macro "optimal", but for Raphael, the optimal macro means (in order of importance):
- The synthesis is finished successfully.
- The final Quality is maximized (not counting any Quality above the maximum Quality of the recipe).
- The number of macro steps is minimized.
- The macro duration is minimized.
The first step to solving the problem is realizing that this is a shortest-path problem on a directed acyclic graph.
graph LR
Initial --> S1 --> x[...] --> S4 --> T1
Initial --> S2 --> y[...] --> S5 --> T1
Initial --> S3 --> S6 --> z[...] --> T2
S2 --> S6
Each node of the graph encodes a possible state in the crafting simulator (current progress, current quality, active effects, etc.). Each edge of the graph represents an crafting action that can be used on a state to get to a different state.
Note
From this point on, the terms "node" and "state" may be used interchangeably.
Each possible crafting action sequence is a path in the graph starting from the root node (the initial state). We want to find a macro that finishes the synthesis, so candidate solutions are paths from the root node to some terminal node. To find the optimal macro, we need to find the shortest path to the terminal node with the highest value.
Of course, just blindly exploring all possible routes in the graph is not feasible because there are simply too many possible nodes and edges.
As an example, consider the Rarefied Tacos de Carne Asada recipe with 600 CP. Let's list all the attributes stored in a state and their value ranges:
- Base attributes:
- Progress: [0-6600]
- Quality: [0-12000]
- Durability: [0-80]
- CP: [0-600]
- Effects:
- Inner Quiet: [0-10]
- Waste Not: [0-8]
- Innovation: [0-4]
- Veneration: [0-4]
- Great Strides: [0-3]
- Muscle Memory: [0-5]
- Manipulation: [0-8]
- Trained Perfection: [Unused / Active / Used]
- Combo: [None / SynthesisBegin / BasicTouch / StandardTouch]
Not all possible combinations of values are valid, but it's not hard to see that there are still too many unique states to store on any conventional computer.
We need to be able to find the optimal path without having to check all possible nodes. In other words, we have to be able to identify early on if a path is worth taking or not. If we can prove for some state S that the optimal path does not go through S, we are able to skip the entire sub-graph of S. This is called branch pruning. Raphael uses multiple branch pruning strategies together to reduce the number of nodes it has to visit to a reasonable number.
Instead of exploring nodes in an arbitrary order, nodes are explored on a best-first basis determined by a search score to make sure the solver finds the optimal solution as quickly as possible. The search score of each state consists of:
- An upper bound on the maximum attainable Quality from that state.
- A lower bound on the minimum number of macro steps required to reach .
- The current number of macro steps.
- The current macro duration.
The upper and lower bounds are calculated using QualityUbSolver and StepLbSolver, both of which will be explained further below.
Avoid states that do not lead to a terminal state where the state's Progress is at least the required Progress to finish the synthesis.
This branch pruning strategy is implemented as the FinishSolver. Given a state S, the FinishSolver decides if it is possible to finish the synthesis from S.
If we only want to find out if it is possible to reach max Progress from a state S, we can ignore all attributes of S that are only relevant for increasing Quality. This is already a lot fewer possible states than in the original search space. But we can reduce the problem space for the FinishSolver even further.
Instead of answering a yes/no question for each state S, it returns the maximum amount of additional Progress that can be gained starting from S. This essentially also moves Progress out of the base attributes that the FinishSolver has to keep track for S. The resulting attributes for each state S in the FinishSolver:
- Base attributes:
- Durability: [0-80]
- CP: [0-600]
- Effects:
- Waste Not: [0-8]
- Veneration: [0-4]
- Muscle Memory: [0-5]
- Manipulation: [0-8]
- Trained Perfection: [Unused / Active / Used]
- Combo: [None / SynthesisBegin]
Now we just need to do some simple dynamic programming to map each state S to a Progress value, the maximum additional Progress that can be gained starting from S.
For each state, find an upper bound on the final Quality that can be reached from that state, and avoid states whose Quality upper bound is less than the Quality of the current best solution.
This branch pruning strategy is implemented as the QualityUbSolver.
Ideally, we want to know exactly how much Quality can be achieved starting from some state, but that would require us to solve the original problem. Instead, the QualityUbSolver sacrifices accuracy for a smaller problem state.
Note
Sacrificing accuracy does not mean sacrificing correctness. The values returned from QualityUbSolver must still be an upper bound. Never ever should the QualityUbSolver return a value that is less than the actual maximum possible Quality reachable from a state, as that would lead to a potentially optimal solution being discarded.
Each action comes at a cost, mainly CP and Durability. Therefore, CP and Durability can be viewed as a sort of "currency" for the crafting macro to use. There are also actions and effects that aim to restore these currencies (e.g. Manipulation, Master's Mend). The main idea of QualityUbSolver is to merge all these attributes and effects into one unified "currency" to reduce the problem space:
- CP stays as CP.
- Durability gets converted to CP. The conversion ratio depends on which Durability-restoring actions are available.
- Manipulation gets converted to CP. Each stack of Manipulation effect gets converted to 1/8 the CP cost of the Manipulation action.
- Trained Perfection gets converted to CP. If Trained Perfection is available, it gets converted to the CP-equivalent of 20 Durability.
Converting all these values to CP already reduces the state space by quite a lot, but it's still not enough. To reduce the state space even further, we do something similar to what we did in the FinishSolver and pull Progress and Quality out of the state attributes. Instead, they become our solve objectives: What is the maximum Progress and Quality that can be achieved starting from a state S?
Because we have multiple maximization objectives, Progress and Quality, calculating one value pair for the maximum reachable Progress and Quality does not work, because from some state S, we may be able to reach higher Quality by sacrificing some Progress and vice versa.
Instead, for each state, we need to keep a list of all Pareto-optimal pairs of Progress and Quality attainable from that state. Once again, we use dynamic programming to map each state to its Pareto front of optimal Progress and Quality pairs.
Assume that the maximum Progress and Quality of a recipe can always be reached. For each state, calculate a lower bound on the number of steps required to reach max Progress and Quality, and discard states whose step lower bound is larger than the number of steps of the current best solution.
This branch pruning strategy is implemented as the StepLbSolver.
The FinishSolver and QualityUbSolver work great when there is barely enough CP to finish a synthesis with maximum Progress and Quality. In those cases, a single sub-optimal action will make it impossible to reach maximum Progress and Quality, which means that sub-optimal actions are quickly caught by the FinishSolver and QualityUbSolver.
When there is an excess amount of CP available, many sub-optimal actions have to be used before it is impossible to reach maximum Progress and Quality, which means the first few sub-optimal actions cannot be caught by either the FinishSolver or the QualityUbSolver. This is where the StepLbSolver comes in.
Because the StepLbSolver is designed for scenarios where there is a lot of excess CP, it can conveniently shrink the state space by ignoring CP (states no longer have CP and actions no longer cost or restore any CP). Instead, a new currency is added in its place, called step_budget.
Similar to QualityUbSolver, we use dynamic programming to map each state to its Pareto front of optimal Progress and Quality pairs. Then, to find the lower bound on the number steps required to reach maximum Progress and Quality a state, we increment its step_budget until the resulting Pareto front contains a pair that, when added to the state's current Progress and Quality, results in maximum Progress and Quality.
Keep track of the current set of Pareto-optimal nodes and only explore nodes that aren't Pareto-dominated by some other node. This also eliminates nodes with duplicate states.
Consider the following two action sequences, where one is clearly better than the other:
- Muscle Memory > Groundwork > Master's Mend > Manipulation (better)
- Muscle Memory > Groundwork > Manipulation > Master's Mend
The resulting state for the two sequences have almost the exact same stats. The difference is that the first node has 8 Manipulation, whereas the second node only has 7 Manipulation. And because having more Manipulation is always better, there is no reason to further explore the second sequence.
We call a node Pareto-dominated if there exists another node for which every stat of the other node is at least as good as the current node. A node is Pareto-optimal if it is not Pareto-dominated by any other node. Note that with this definition, a node always Pareto-dominates itself.
For most attributes (Quality, CP, Durability, Effects) having more is always better.
Progress is the odd-one-out. It is currently unclear whether having more Progress is always better. There could be scenario where having less Progress would enable the use of a large Progress-increasing action during a time when a lot of Progress-increasing effects are active that would otherwise complete the synthesis, whereas having more Progress forces the use of a smaller Progress-increasing action, resulting in having to use more actions to finish up Progress at the end. However, this has yet to be proven or disproven.
A naive implementation for Pareto-dominance checking would be to check the candidate node against all other previously explored nodes. This has
A different approach would be to treat each node as a point in
Raphael gives up on finding an exact Pareto-front and instead relies on an approximate Pareto-front for branch pruning. Nodes are divided into different "buckets", and Pareto-dominance checking only happens within the same bucket. As a result, a node is either reported as "definitely Pareto-dominated" or "maybe Pareto-optimal".
Pareto-dominance checking within a bucket is done using linear scan, and the bucket selection criteria is tuned in a way to balance the size of each bucket and the number of false negatives that happen because nodes are spread across too many buckets.
Because CP acts like a "currency" for the synthesis (more CP means you can use more actions, which means a bigger state space), looking at the number of processed nodes at increasing amounts of CP gives an idea of how effective a branch pruning strategy is. Let's look at the number of processed nodes for the Rarefied Tacos de Carne Asada recipe at 4900 craftsmanship and 4800 control on a level 100 job:
Key points:
- With no branch pruning, the number of nodes grows very quickly, already reaching ~45M nodes at 75 CP.
- For this recipe, at least 560 CP is required to maximize Quality.
- The
QualityUbSolverdoes a good job of keeping the number of processed nodes low, but as expected, fails spectacularly once there is more than enough CP available to maximize Quality. - The
StepLbSolverstrategy has no impact when there is not enough CP to maximize Quality. The effectiveness of the strategy increases the more CP is available and plateaus once adding more CP no longer reduces macro length or duration.