Project on Github here.
Crafting in Final Fantasy 14 is a minigame. The outcome of a single crafting attempt can be no items, a standard item or a HQ (high quality) version of your item that has better stats. A max-level crafter may have up to 24 skills, some of which are not obvious when to use so it seemed like an interesting problem to solve programatically with a simulation.
How crafting works
Each craft requires some input materials. You are able to select actions based on your current crafting class (blacksmith, goldsmith and so on) and you can also borrow a subset of actions from other crafting classes. There are a number of different resources involved with crafting - progress, quality, cp and durability which are affected by the skills.
Example of crafting:
First attempt
There are a couple of solutions already, such as Crafting Optimizer which has a good user interface, but doesn’t take advantage of random occurences that happen while crafting. It’s open source so I decided to base my solution on this and swap out the core algorithm, which was using a genetic algorithm approach.
Probability
I first considered using minimax, but realized that probability is involved in several places in crafting (action success and item quality are random). I found out that the expectiminimax algorithm is a suitable variation of the minimax algorithm. Expectiminimax works similar to minimax except to evaluate the fitness of a node it will apply its heuristic to the world then multiply by the probability of that node being reached. One disadvantage of expectiminimax is that it’s harder to prune branches (like with alpha-beta pruning) because things that have low probability could still still be a worthwhile gamble if they offer a lot of value.
Branching
Crafting in FFXIV works something like this: select action -> success / failure -> apply new random condition
This will continue to loop until you run out of durability or fill up the progress bar.
In terms of the branching factor this means that for a single depth of the tree the branching factor is (worst case):
24 X 2 X 4 = 192 branches (24 = number of possible user actions, 2 = success/failure, 4 = possible resulting conditions)
Looking ahead four moves this would mean we’d have to simulate 1,358,954,496 worlds (192^4). I decided to eliminate the condition branching because in some cases it is deterministic, and in the other cases it tends to be a single value unless you’re lucky. This brought me down to a branching factor of 48, which was still too high for the javascript code base - looking ahead three moves still took minutes. So I ported to C++.
C++
After porting the code base to C++ and doing some refactoring the program ran fast enough to use for low-mid level crafting and look ahead up to five or six moves. I discovered the CLion IDE while doing this which I strongly recommend as a good multiplatform C++ IDE (it’s small and well featured, the only thing it doesn’t have that I really miss from Qt or Visual Studio is a visual ui editor).
Profiling
I used gprof for profiling to see if I could discover any obvious bottlenecks. Suprisingly the time spent was more or less evenly distributed over my functions. Noticing that the program was only utilizing 25% of the cpu I made it multithreaded.
Multithreading
Since the algorithm needs no cross thread communication C++11 std::future was an option:
auto future = boost::async(boost::launch::async, Expectimax::getActionScore, this, worldState, depth, actionIdentifier);
// Create the rest of the threads as above
future.wait(); // Wait for the task to finish (repeat for all futures)
ActionEvaluationResult actionEvaluationResult = future.get(); // Get the result
Each branch of the tree is run on its own thread, and its parent waits for it (and its siblings) to finish before retrieving the result and comparing their fitnesses. std::future wasn’t implemented in g++ for Windows, so I used boost::future which has almost identical syntax.
The chart above shows thread count vs time to finish (seconds). I found out that to a certain extent the higher the threadcount the better (way higher than the number of physical cores). This is partly because the work is not evenly distributed between threads. In order to improve the performance I’d need to have a threadpool - if a thread completed its work, it would signal availability and one of the other running threads would transfer some of its work to it.
After making it multithreaded the algorithm was running in 1/3rd the original time.
Results
I didn’t want to spent time making a UI for an experiment so here’s an example of the interactive mode output:
Welcome to Goobbue!
-- Main Menu --
1. Configure your crafters.
2. Perform a craft
Please enter a choice (1 or 2):
>2
Enter the name of your crafting class
>Leatherworker
Crafter: Leatherworker level: 25 craftmanship: 137 control: 142 cp: 278 [manipulation, hastyTouch, rapidSynthesis, carefulSynthesis, basicSynth, basicTouch, standardTouch, mastersMend, mastersMend2, wasteNot, innerQuiet, steadyHand, greatStrides, ]
Enter the name of the recipe
>Aldgoat Leather
Searching for Aldgoat Leather
Found recipe.
Recipe: Aldgoat Leather level: 17 difficulty: 33 max quality: 898 durability: 40
Enter the starting quality
>200
Starting Craft!
WorldState : durability 40 Quality 200 Progress 0 Cp 278 Buffs 0
Use the Inner Quiet skill!
What is the condition: (p)oor, (n)ormal, (g)ood or (e)xcellent?
>n
WorldState : durability 40 Quality 200 Progress 0 Cp 260 Buffs 1
Use the Great Strides skill!
What is the condition: (p)oor, (n)ormal, (g)ood or (e)xcellent?
>g
WorldState : durability 40 Quality 200 Progress 0 Cp 228 Buffs 2
Use the Standard Touch skill!
Did the action succeed? (y or n)
>y
WorldState : durability 30 Quality 519 Progress 0 Cp 196 Buffs 1
< a few skills removed for brevity >
Use the Standard Touch skill!
WorldState : durability 20 Quality 898 Progress 0 Cp 22 Buffs 3
Use the Basic Synthesis skill!
WorldState (terminal): durability 15 Quality 898 Progress 33 Cp 22 Buffs 1
Congratulations on HQing your craft!
Repeat the craft with the same recipe and quality? (y or n)
In this instance I was doing a level 25 craft, so I was able to set look-ahead to 8 moves. It gave the congratulations for HQ’ing the craft! message two skills before I finished. It was useful to use the interactive mode as a trainer so I could learn general approaches to crafting. It tended to use the steady hand skill more than I would previously, and even when the buff was still applied.
I may revisit this project and make a user-friendly interface and method of pruning branches for higher level crafts.
Project on Github here.