Greedy Algorithms

Deep Dive: Understanding the Optimizer

This page explains how our optimization algorithm works, its trade-offs, and known edge cases. Understanding these details helps you get the most out of the tool and know when to apply workarounds.

Heads-up for Lordrush: some examples below reference Red Gear, Mithril, and ascension. Those unlock once Gear Ascension is available in your Empire; until then your hero gear runs on XP (enhancement) and Forgehammers (mastery). The algorithm works the same way, so the reasoning still applies.

What is a Greedy Algorithm?

A greedy algorithm makes decisions one step at a time, always choosing the option that looks best right now. It's like shopping with a limited budget and always picking the item with the best value-per-dollar at each moment.

How Our Optimizer Works

The optimizer evaluates every possible upgrade and asks: "Which single upgrade gives me the most bang for my buck?" It picks that upgrade, removes the spent resources from your pool, and repeats until resources are exhausted.

Step-by-Step Example

You have 50,000 XP to spend. The optimizer:

1. Scans all pieces - finds Infantry Gloves (weight 1.5x) at level 60 and Lancer Helm (weight 0.8x) at level 40
2. Calculates efficiency - Infantry Gloves: 15 weighted stat gain per 5,000 XP = 3.0 efficiency. Lancer Helm: 12 weighted stat gain per 4,000 XP = 3.0 efficiency
3. Picks the best - Both have equal efficiency, so picks Infantry Gloves (higher weight means more impactful)
4. Updates state - Now has 45,000 XP remaining, Infantry Gloves at level 61
5. Repeats - Scans again with new state, finds next best upgrade

This process continues until you're out of resources or no beneficial upgrades remain.

Why Use Greedy? Comparing the Alternatives

There are several approaches to optimization. Here's why we chose greedy:

The Brute Force Problem

The "perfect" approach would be to try every possible combination of upgrades and pick the best one. This is called brute force optimization. Here's why we don't do that:

The Math Problem

With 12 gear pieces, each with:

• 100 possible enhancement levels
• 20 possible mastery levels
• Multiple quality tiers

The number of possible combinations is approximately 10^30 (a 1 followed by 30 zeros). To put this in perspective:

• Atoms in a grain of sand: ~10^23
• Stars in the observable universe: ~10^24
• Possible gear configurations: ~10^30

Even if a computer could check 1 billion combinations per second, it would take longer than the age of the universe to find the optimal solution.

Other Optimization Approaches

Beyond brute force, there are several algorithms used in computer science:

Why Greedy Wins for Gear Optimization

Speed matters: You want results in milliseconds, not minutes. Greedy runs in under 100ms.

Constraints are complex: Mastery gates, ascension prerequisites, and resource dependencies make dynamic programming impractical.

Good enough is good enough: The difference between greedy and theoretical optimal is typically less than 1%. That's not worth waiting 100x longer.

Real-world validation: Greedy algorithms power your GPS routing, delivery logistics, and compiler optimizations. They're proven for resource allocation problems like ours.

The trade-off is that greedy algorithms find local optima - solutions that are excellent but may not be the absolute mathematical best. We address this with smart guardrails (more on that below).

Advantages of Greedy Optimization

1. Speed

The optimizer runs in milliseconds, not minutes or hours. This means you can:

• Experiment with different weight profiles
• Compare strategies quickly
• Re-run after applying upgrades

2. Interpretable Results

Each recommendation has a clear explanation: "This upgrade was chosen because it had the highest weighted gain per resource spent." You can understand and verify the logic.

3. Handles Complex Constraints

The algorithm naturally handles game mechanics like:

• Mastery gates - You can't enhance Red gear past level 120 without Mastery 11
• Resource dependencies - Ascension requires Mythic Gears AND Mithril
• Quality transitions - Mythic to Red ascension prerequisites

4. Consistent Behavior

Same inputs always produce same outputs. If you and a friend enter identical gear and resources, you'll get identical recommendations.

Disadvantages and Limitations

Greedy algorithms aren't perfect. Here are the known limitations:

1. Local Optima, Not Global Optima

The algorithm finds a great solution, but not necessarily the best possible solution. Like hiking and always going uphill - you'll reach a peak, but maybe not the highest peak in the range.

In practice, this rarely matters. The difference between the greedy solution and the theoretical optimal is typically less than 1%.

2. Path Dependency

The order in which upgrades are evaluated can affect the final result. If two upgrades have identical efficiency, which one gets picked first can change what happens next.

3. Sensitivity to Input Changes

Small changes in resources can sometimes cause the optimizer to take a completely different path. This leads to the edge cases described below.

Known Edge Cases

Through extensive testing and user feedback, we've identified specific scenarios where greedy optimization produces unexpected results. Here's what to watch for:

Edge Case 1: The Resource Paradox

The Paradox: In rare cases, adding more resources can result in lower improvement percentages.

What Happens

When you have resources near certain thresholds, the optimizer may choose a completely different strategy. With fewer resources, it might use an aggressive reforge strategy that yields high returns. With more resources, it finds a "safer" path that actually performs worse.

Real Example

A user reported that changing Forgehammers from 1,500 to 1,600 caused their improvement to drop from +14.4% to +11.7%.

What happened: With 1,500 Forgehammers, the optimizer determined it needed to reforge low-weight pieces to fund four Red gear ascensions. With 1,600 Forgehammers, it passed a threshold where it abandoned this aggressive strategy and took a safer (but worse) path. After the fix (the Monotonicity Guard described below), the 1,600-Forgehammer case recovers to +14.8%.

The Mitigation

We've implemented a Monotonicity Guard that automatically tests multiple resource budgets and picks the best result. When you have large amounts of resources, the optimizer now tries several different budget levels behind the scenes and gives you whichever produces the highest improvement.

After implementing the guard, major paradoxes like this one are now caught automatically.

Workaround if You Suspect a Paradox

If you have large amounts of resources and get unexpectedly low improvement:

1. Try with fewer resources - Reduce Forgehammers, mithril, or mythics by 10-20%
2. Compare results - If fewer resources give better improvement, use that strategy
3. Apply and re-run - Apply the first batch of upgrades, then run again with remaining resources

This "iterative optimization" approach often yields better total results than optimizing everything at once.

Edge Case 2: XP Shuffle Inefficiency

The Issue: Sometimes the optimizer shuffles XP between similar pieces for zero net benefit.

What Happens

When two pieces are at similar enhancement levels with equal weights, the optimizer might recommend reforging one to fund the other - even though this provides no actual improvement.

Real Example

User had Infantry Gloves and Infantry Chest, both at level 89 with Mastery 4.

The math problem: Gloves at level 90 + Chest at level 88 = 147.68% total stat

But: Gloves at level 89 + Chest at level 89 = 147.68% total stat

Both approaches yield identical stats, but the optimizer's recommendation wastes 50 XP in unnecessary transfers.

Why It Happens

The reforge logic was designed for transferring XP from low-weight pieces to high-weight pieces. It doesn't check for the edge case where shuffling between equal-weight, same-level pieces is wasteful.

The stat formula is linear within a quality tier:

• +1 level on piece A = same stat gain as +1 level on piece B
• Therefore: +1 level on A and -1 level on B = net zero

Current Status

This is a known limitation with Low severity:

• Results are still correct (stats are accurate)
• XP waste is typically small (50-200 XP per occurrence)
• You can manually keep pieces at equal levels if desired

Edge Case 3: Milestone Priority Mismatch

Reported by Moeseph

The Issue: The optimizer may choose a lower-value milestone over a higher-value one on a similar piece due to greedy path dependency.

What Happens

When multiple pieces of the same stat type compete for resources, the optimizer processes higher-priority pieces first (Infantry, then Lancer, then Archer by default). By the time it reaches lower-priority pieces, the remaining resources lead it down a different path than if those pieces were evaluated in isolation.

This can result in a piece with a less valuable milestone getting upgraded, while the piece with the more valuable milestone stays behind.

Real Example

A player running a Lethality-focused Archer build (Archer Lethality weighted 1.2x, Archer Health 0.6x) had two Archer Health pieces both at E139/M11:

The optimizer recommended pushing Archer Chest to E160 (unlocking Defense +30%) while leaving Archer Gloves at E139 with just a mastery bump. The Attack milestone on Gloves is worth twice as much, but didn't get selected.

Why It Happens

In a head-to-head comparison, the optimizer correctly picks Gloves (Attack) over Chest (Defense). But in the full 12-piece optimization, high-priority Infantry and Lancer pieces consume most of the XP, Mithril, and Mythic Gears first. The greedy algorithm locks in those decisions, and by the time Archer Health pieces are evaluated, the remaining resource budget creates a different landscape where the path to Chest E160 becomes available before Gloves E160.

This is the same path dependency behavior described in the disadvantages section above. The overall recommendation is still excellent (22%+ improvement), but the specific ordering of which Archer piece gets the milestone is suboptimal.

How to Spot This

Look for pairs of pieces with:

• Same stat type (both Health or both Lethality) at similar enhancement levels
• Different milestone values at the next target (one gives Attack, the other gives Defense)
• The lower-value milestone piece getting upgraded while the higher-value one stays

Workaround

1. Check milestone types in the results table. If a Defense milestone was chosen over an Attack milestone on a similar piece, this edge case may apply
2. Swap the upgrades manually by applying the milestone upgrade to the piece with the more valuable milestone instead
3. The total resource cost is the same since both pieces have identical base stats and costs at the same enhancement level. You won't spend more by swapping
4. Re-run after applying the first batch of upgrades to let the optimizer recalculate with the updated gear state

How We Address These Issues

Multi-Budget Testing

Rather than optimize once and hope for the best, we run the optimizer multiple times with different resource budgets. Think of it like trying on different amounts of spending money to see which gives the best deal.

How it works:

1. You have 1,600 Forgehammers
2. We also test with 1,500 Forgehammers and 1,400 Forgehammers
3. We compare all the results
4. We give you whichever produces the highest improvement

This catches the "resource paradox" situations where using fewer resources actually yields better results. You still get access to all your resources - we just find the smartest way to use them.

Result: Major paradoxes (2-3% reversals) are now caught automatically. Only tiny variations (<0.1%) remain in rare edge cases.

What This Means For You

Trust the Results (Mostly)

The optimizer produces excellent recommendations 99%+ of the time. The edge cases described here are rare and well-understood.

When to Be Skeptical

Consider double-checking if:

• You have very large resource pools (50+ mithril, 1,500+ Forgehammers)
• The improvement seems surprisingly low
• The recommendation involves heavy reforging between similar pieces

Best Practices

1. Run multiple times with slightly different resource amounts if results seem off
2. Apply recommendations in batches and re-run for remaining resources
3. Check the Execution Order sort to ensure you're applying upgrades correctly
4. Report unexpected results via our feedback form - we use these to improve the algorithm

Future Improvements

We're continuously working to improve the optimizer:

• Thorough Mode - Optional toggle that tests more budget variations for maximum accuracy
• Reforge Pre-check - Skip XP shuffles between equal-weight, same-level pieces
• Paradox Warnings - Alert when you might benefit from trying different resource amounts

Have a suggestion? Let us know!

Learn More

• How It Works - Detailed explanation of the optimization mechanics
• Build Profiles - Understanding weight profiles and customization
• Basics - Introduction to hero gear optimization