Improvements to Loot Solver Algorithm

[freyamade]

What is this about?

The Loot Solver section in a Team's Loot Manager is a little extra algorithm that is designed to help Teams hand out loot in a way that is fair and balanced but optimises for having everyone geared in as few fights as possible.

In my own Team, we discovered a setup that caused the original naive approach to break and add an extra week to M1S when it wasn't needed, and a patch is coming for this soon.

However, I figured this was a good time to use the discussions thing on Github and chat about the why and the how of the issue, and what I've done to solve the problem. This is going to be a long and fairly intricate post, so if you don't want to read it all, I'll try to add a TL;DR at the end!

What's the Problem?

Firstly, a brief explanation of the algorithm is in order.

For each fight, we track the number of items each person in the Team needs. We then prioritise these in descending order of total items required, and break ties by a job-based priority. The job based side can be re-ordered in Team Settings, but by default it is Melee > Phys Ranged > Caster > Tank > Healer, in release order typically.

As an example, we can use my static and the very situation that has caused this to be brought up to begin with;

M - DRK
E - GNB
A - AST
B - SGE
R - VPR
S - MNK
T - BRD
D - PCT

We have some overrides; VPR is higher than MNK, and PCT is before `BRD.

If the items required from M1S are as follows;

Earrings: E A B D
Necklace: M E R T
Bracelet: A B S D
Ring: E A B S R T D

Then the priority system that is built up internally looks like this;

3: D E A B
2: R S T
1: M

The Naive Approach

The initial algorithm functions on a naive approach. Every week that it simulates, it goes through the items in order, picks the highest priority person that still needs that item and assigns it to them.

Whenever a person gets an item assigned, they are removed from their priority bracket and added to the end of the one below (if they still need items).

Every 3/4 weeks, when items are buyable with tokens, then the simulation will take that into account and remove one item from everyone. This is always a tome-item augment if possible.

Running through the simulation, we can come to the core problem of what is going on;

Week 1

Earrings: D
Necklace: E
Bracelet: A
Ring: B

Turning the priorities into;

2: R S T D E A B
1: M

and requirements into;

Earrings: E A B
Necklace: M R T
Bracelet: B S D
Ring: E A S R T D

Week 2

Handouts;

Earrings: E
Necklace: R
Bracelet: S
Ring: T

Priorities;

2: D A B
1: M E R S T

Requirements;

Earrings: A B
Necklace: M T
Bracelet: B D
Ring: E A S R D

Week 3

The issue is about to make itself clear, so we'll step through this week one item at a time.

Earrings:

• D doesn't need them
• A is next in line, needs Earrings so gets them

2: D B
1: M E R S T

Necklace

• D and B don't need it
• M is next highest, who does need it, so gets it

2: D B
1: E R S T

Bracelet

• D is highest in priority, gets it

2: B
1: E R S T D

Ring

• B already got their Ring, so cannot get another
• Ring is given to someone who needs only one item left

After this week, everyone can buy an item and, if the algorithm was more optimal, the Team would be done with M1S. However, B is left requiring one more item, so another week is required.

If you look at the requirements going into week 3 though, it is clearly possible to hand an item to D, A, and B, to bring the whole of the Team to requiring 1 item at most.

The Less Naive Way

Instead of running through each item in order, and finding a person for the item, we should do more clever matching to ensure we give items to the highest priority people every week.

The plan is to take people from the top of the priority list, until we have enough people to give one item each to, while covering each of the items that are still needed.

Running through the above example once again;

Example

Requirements

Earrings: E A B D
Necklace: M E R T
Bracelet: A B S D
Ring: E A B S R T D

Priorities

3: D E A B
2: R S T
1: M

Week 1

The fight drops 4 items, so we need to look at the top 4 people at least. Taking the first 4, and mapping them to the items they need, we can see the following;

D: Earrings, Bracelet, Ring
E: Earrings, Necklace, Ring
A: Earrings, Bracelet, Ring
B: Earrings, Bracelet, Ring

We can start naively; take the first person (highest in priority), and give them the first item in their list. In this case, we hand the Earrings to D.
Then, we remove Earrings from the other players' lists, and remove D from the map entirely.
Since everyone has multiple items they can still receive, nothing of importance happens this week. We follow the algorithm through and everyone gets their items happily, ending up with the following handouts;

Earrings: D
Necklace: E
Bracelet: A
Ring: B

Turning the priorities into;

2: R S T D E A B
1: M

and requirements into;

Earrings: E A B
Necklace: M R T
Bracelet: B S D
Ring: E A S R T D

Week 2

Again, let's take the top 4 people and see what they need;

R: Necklace, Ring
S: Bracelet, Ring
T: Necklace, Ring
D: Bracelet, Ring

However, the top 4 won't cut it. We have Earrings to hand out and yet the top 4 people do not need it. Let's add another person to see if we can fix this missing item.

R: Necklace, Ring
S: Bracelet, Ring
T: Necklace, Ring
D: Bracelet, Ring
E: Earrings, Ring

Okay nice! Now let's start naively again; give R the Necklace;

S: Bracelet, Ring
T: Ring
D: Bracelet, Ring
E: Earrings, Ring

Now we have a person who has only one item they could get this week. Instead of moving on to give S their item, we instead skip straight to T and give them a Ring.

S: Bracelet
D: Bracelet
E: Earrings

This removes Ring from everyone else, and drops everyone down to a single possible item this week. Both S and D need the Bracelet, and E can only get Earrings. Due to S being ahead of D in priority, S is handed the Bracelet, and E gets the Earrings by default, leading to the following handout;

Earrings: E
Necklace: R
Bracelet: S
Ring: T

Turning the priorities into;

2: D A B
1: M R T S E

and requirements into;

Earrings: E A B
Necklace: M R T
Bracelet: B S D
Ring: E A S R T D

Week 3

Let's once again take the top 4 people and see their requirements;

D: Bracelet, Ring
A: Earrings, Ring
B: Earrings, Bracelet
M: Necklace

All items are accounted for, so we just look at these 4 people.

• D gets Bracelet, reducing B to having only Earrings left.
• B is guaranteed Earrings, reducing A to only have Ring left
• A is guaranteed Ring
• M gets the Necklace by default

Final handouts are

Earrings: B
Necklace: M
Bracelet: D
Ring: A

Lastly, everyone gets to buy the one extra item they need with books, and guaranteeing the end with only 3 clears instead of 4!

TL;DR

• The original algorithm is extremely naive, basing the handout on a per-item, highest-prio system.
• If a situation occurs where this handling causes the same item to be given to the same person when they are highest in priority, it would push required clears back by a week.
• The new algorithm is a system of selecting highest N priority people to satisfy all potential items for a week, and ensuring that every one of them gets an item that they still need, instead of handing the items out by iterating down the loop of the items for a given fight

Release

This patch should be out sometime this week, I need to plug this scenario into the tests and build the new algorithm within SavageAim accordingly.

[freyamade]

A side-effect I noticed while prepping tests for the new algorithm is this new version prevents one person getting multiple pieces of loot in the same week.

This could potentially be sub-optimal but I can't exactly think of a test case where this would add on an extra week. If anyone else can and provides one, I'd be super happy to refine this and make a version 3!

[freyamade]

The above comment has been addressed and is included in release 20240809!