Tool Optimization

[Grenwood]

Hello! I'm hoping to get some help from the community on a tool I'm working on. You see, I am trying to write an algorithm that can help me optimize equipment in an RPG.

Given the stats of the character and the monster, I need to qualify the "best" gear for certain specifications. For example, if my specifications are the "highest damage over time", I need to find the equipment set that leads to that result. The formulas are all there, although quite complicated, in resolving a given set of gear's value, but the problem is less about the actual implementation of the math and more about the heuristics of the problem set.

There are 16 different equipment slots (hands, body, weapon, feet, etc.), and each slot can have thousands of equipment options. This means the combinations available of gear is a near impossible number. A brute force method would be impractical if not impossible to do. I can filter by character level and impossible to equip gear. I can do a simple filter of "similar" gear, such as eliminating a ring of Dex +2 in favor of the higher level ring of Dex+3, which shrinks down the problem space, but in the end I believe it's still going to be too large and still have at least 1000 options per gear slot.

My goal here then becomes, can anybody help me find an algorithm or heuristic that lends for this type of sorting? I'm researching marching ANTS, genetic sorting, and other algorithms, but this is far from my expertise and I'm lost in the terminology. I'm not much for algorithm writing myself, but this seems like an NP-complete problem. I need an exact, yet possibly non-deterministic method. If this community doesn't have that sort of expertise, does anybody know of another community I can approach?

My thanks go out to anybody who can help!

[MattEvans]

I don't think it's NP complete, not the example you've given anyway.

If you assign every viable object it's 'score' for a certain requirement, ( i.e. highest protection ); including negative scores if a piece of equipment 'removes protection'... It's just a case of finding the maximum score item for every slot. ( Highest protection is clearly afforded by equipping oneself with the pieces of equipment that afford the highest level of protection. ) If you have multiple requirements (i.e. highest protection and highest damage ), you can use a weighted sum or a rank calculation for each item's 'score'. Generally, I would try to use an statistical method rather than a reasoning method, unless the problem really requires reasoning.

Are there other constraints though? i.e. If a player has N equiped they can't have E equiped, or similar? Or, do you want to reach an EXACT level of protection/damage/etc?

[jwenting]

And you need to keep track of item sets, where items reinforce each other.
For example Dungeon Siege has those. If you equip 2 items, each becomes extra strong, if you equip 3 that bonus goes up, until you have the maximum percentage bonus when you equip the entire set.

So an item with stats of +10 life could end up giving you +25 life if you have the rest of the set equipped as well.

[Grenwood]

Well, it's not quite as simple as one piece being better than another. Many of the equations for damage output and defense work on multi-variable sloped equations.

Strength and Attack stats do just that. Strength measures the slope of your damage function, while Attack will affect how often you hit on the higher end of your slope.

Such as, a helmet with Strength +2 or a helmet with Attack +10, and body piece with Strength +1, Attack +3 or a body piece with Attack +15. In the end, one helmet is good with one piece for the body, and another helmet is good with a different piece for the body.

These are just two of the many stats that go into the game. You can see just from this example that no piece can be flat out considered "better" in all situations. In fact, the level difference, Vitality, Agility, Defense, and Evasion of the enemy can greatly affect which gear you should be using.

I don't believe that in this scenario weighted sums would work, otherwise I'd have gone with pre-calculated results.

[MattEvans]

Well, sorting wont hurt you; lets put it that way. At the least, you can remove a number of the potential items that really dont help for a given query. You don't have to pre-compute the weights, you could calculate them for every item based on external factors like the enemies nearby, or the player's intrinsic stats, they don't have to be normalized weights either, just numbers that sumarize each item's 'raw usefulness' in a given situation.

That still leaves a problem of multiple items reinforcing/weakening each other. Are there ways you can categorize items and groups of items based on their effects or dependancies? jwenting mentioned specific 'sets' of co-reinforcing items, I can almost think of an optimization if that's the case.. it's based on sorting again; but sorting 'sets' and their subsets in with the other items and then forming and shunting 'shapes' that come in at the top of the lists.. you could only do something like that if there are little finite groups of items that work together, not if all items have effects on all other items. If all items do affect each other; you could certainly pre-compute the 'interconnections' between items/groups, where they may have effects on each other; there may be a route to optimization there.

Do you think you could convert this to a linear programming problem? Have a look at examples of LP problems ( google, wikipedia ).. they can all be solved via a generalized means; but, it may not be optimum for your situation, and you may not be able to convert this problem into an LP problem that isn't prohibitively complicated to work with. Math-specific forums might be a good place to look for help; www.mathhelpforum.com is somewhere that my girlfriend and myself have gone before, with good result; but, you'd have to make it into a math problem rather than a computing problem..

Is the problem to find the best equipment from the things that a player has available at a given moment in time; or from the entire set of game items? If it's just from what's equipped, is the player ever gonna have all 1000 game items equipped?

The problem isn't NP-complete, however complex the rules are. A brute force every-permutation approach is a P-class solution; it's a big P, and it'd take a long time on 1000 items, but, it would have the same run-time for any size of n.

[MattEvans]

EDIT: ha.. i wanna rephrase this "it would have the same run-time for any size of n." to; "it would have the same run-time for any input of a given size of n."

[Grenwood]

To answer your question, the problem is to find the best equipment from all items available in game. The reasoning behind this has to do with an economy controller and setting NPC sell prices based upon the gear's usefulness and fluctuating player controlled auction system. Also, some of the enemy designers are using this to gauge monster difficulty based upon optimum scenarios.

With the way the formulas for damage and hit accuracy are formed on a multi-variable curve and based upon situational variables (enemy statistics), there really isn't a static "raw usefulness" for an item. An item that enhances the graphs slope isn't as useful against an enemy that lowers the curves maxima. Essentially, Strength is not greater than Attack, and Attack is not greater than Strength, but the proper combination of both in accordance to the enemy level, Vitality, Evasion, and Defence will create the best outcome. My job is to find the "best combination", or gear set, for a given situation (input from user).

Let's say for example you have an item that has the greatest Accuracy bonus for headgear. You also have an item that has the greatest Accuracy bonus for a body piece. Although Accuracy is needed, it would be useless to wear them both. At level 20, there's a headgear that grants a large Attack bonus, so at level 20, you might wish to wear the Attack headgear and the Accuracy body piece. At level 40, a large Attack bonus body piece becomes available. At this point, it might be prudent to wear the Attack body piece and the Accuracy headgear. These are just two variables that go into an effective combatant, but you can see how one piece's usefulness is actually dependent upon the options available in other equipment slots. All gear is synergistic to each other to create the optimal curve.

Let's take the example further and say that now you are fighting an enemy with incredibly low Evasion. Now, the affect of Accuracy on the curve is less dramatic, and Strength suddenly becomes more prudent. You may completely wish to un-equip the Accuracy bonus gear in exchange for something else. This also helps demonstrate how a situation can change the usefulness of a single piece of gear.

Also, a difficulty of this is that the tool should work across expansions, when variable amounts of gear are added to the game. Although if I need to pre-compute values, I can always just check expected version against current and only do a full recompute when they differ.

I can filter out items that are utterly useless, and I can filter out items that are less useful "in the same way" (eg. Defense 5 vs. Defense 6 or Attack +10 vs. Attack +15) as other items, but really that leaves a great number of items left. I've finished doing some of these filters and have come up with the number of items:
Back - 104
Body - 206
Ear (2 slots) - 250
Finger (2 slots) - 281
Feed - 173
Hands - 193
Head - 226
Legs - 161
Neck - 140
Waist - 130
Primary Weapon - 430
Secondary Weapon - 59
Ranged Weapon - 129
Ammo - 120

This means that a brute force approach to every gear combination would have to parse 1.108x10^36 possible gear sets for sorting (if the numbers don't add up it's because of how secondary weapons stack and are limited in use with dual primary weapons). In other words, you are completely correct, it is a P-class solution, but it's a very big P.

Linear programming might be the way to go. Thank you for that referral, I'll be checking it out. This is precisely what I meant when I said that I'm not particularly up to the expertise required to jump into this, as I have no idea how to communicate properly with a mathematician about this. I was hoping to find the proper heuristic to make this sort possible in a reasonable amount of time (< 2 hours).

Thanks once again for your help, you may have already gotten me onto the right track and I appreciate your interest!