An interesting search problem

[Markbnj]

Ok, so the best example to characterize this is that of a role-playing game. In this game each character has a number of 'stats': strength, agility, armor factor, that sort of thing. These stats can be improved by qualities of items that you find in the game. For each stat there is a base value, which can be ignored for the purposes of this problem, and a maximum 'boost' value.

Each character has, say, twelve slots for items from helm to rings and weapons, etc. In the game there are thousands of items that can be put in these slots. The items that a given character can use is restricted by various factors and so the usable number is less than the total number. Each item has from 1 to 5 individual qualities that improve from 1 to 5 character stats. The total number of character 'stats' that can be affected by items, including base attributes, skills, bonuses, etc., is a couple of dozen.

Summary: thousands of potential items to fit in twelve slots in such a way as to maximize stat improvement across a couple of dozen stats.

I've just started thinking about this problem, and wanted to toss it out there for some ideas from you guys. It seems like a variation on the knapsack problem to me, and is likely NP-hard.

My thoughts are to begin by sorting the list of all items into bags containing items that will fit in each slot and can be used by a given character, and then start some sort of random shuffling process.

 

[Cogman]

This is definitely the Knapsack Problem. The best approach will be a heuristic one.

My favorite approach since it is fairly easy and somewhat quick would be a monte-carlo simulation. This would be a fairly easy one to do it for as well. Pick some random items. See what gains they give, if the gains are "better" then the last value, save this configuration and update the last best value to be the current configuration. Choose another random set.

Within like 100 loops, you'll have an answer that is likely to be in the top 1% of best configurations. You may not find the best, but you will find the something pretty dang good.

 

[KIAman]

Are you looking for the fastest solution or an interesting solution? I think an interesting solution would be a variation on the multi-threaded genetic algorithm.

 

[Train]

This is definitely the Knapsack Problem. The best approach will be a heuristic one.

My favorite approach since it is fairly easy and somewhat quick would be a monte-carlo simulation. This would be a fairly easy one to do it for as well. Pick some random items. See what gains they give, if the gains are "better" then the last value, save this configuration and update the last best value to be the current configuration. Choose another random set.

Within like 100 loops, you'll have an answer that is likely to be in the top 1% of best configurations. You may not find the best, but you will find the something pretty dang good.

I was just going to post that. Classic knapsack.

And your solution is like a simplified genetic algorithm.

A more genetic approach would be to create 10 random configurations, rank them all, keep the 2 best and breed them (8 offspring, with a random half of each parents config) for another group of 10, repeat a few dozen generations.

 

[Markbnj]

Thanks for the interesting replies. Cogman, I agree that some sort of monte carlo shuffling is the right approach. I was intrigued by KIAman's question, and I think the answer is I want to come up with something that works fairly quickly, and then run some tests and evolve it. It should be interesting but the purpose of the exercise is not to explore the problem space.

Train, about your breeding idea: on the one hand this is a natural way that people manually create these configurations now. They get certain pieces in place and then experiment around that. On the other hand there's no real reason to think that having x stats close to cap at generation x means you can create generation x+1 as a permutation of x and improve. The addition of a new item might invalidate earlier item selections. In other words I am not sure that there are families of fit solutions that share common pieces. In practice there probably are, but I'm not sure whether implementing the search that way as opposed to a monte carlo shuffle would be likely to lead to better solutions.

I'm curious as to what algorithm might be used to permute from generation x to x+1. Obviously you're going to keep some part of the existing configuration and then evolve out from there. I'll have to do some reading, as it's been awhile since I thought about genetic algorithms. My first thought is to divide down the middle, and keep the half of the items that raises the most stats closest to cap.

Also, in practical terms people will have the ability to do this manually to some extent, because they will be able to tell the program to "pin" one or more items in the results and search only configurations that include those items.

 

[Train]

Train, about your breeding idea: on the one hand this is a natural way that people manually create these configurations now. They get certain pieces in place and then experiment around that. On the other hand there's no real reason to think that having x stats close to cap at generation x means you can create generation x+1 as a permutation of x and improve. The addition of a new item might invalidate earlier item selections.

Thats why you let the strongest survive. Notice in my example I said that a generation is children AND parents. So even if mutations repeatedly fail to improve on the parents, the parents live on.

In other words I am not sure that there are families of fit solutions that share common pieces. In practice there probably are, but I'm not sure whether implementing the search that way as opposed to a monte carlo shuffle would be likely to lead to better solutions.

The simple solution for that would be to run it multiple times. Eventually the various "families" will reveal themselves.

I'm curious as to what algorithm might be used to permute from generation x to x+1. Obviously you're going to keep some part of the existing configuration and then evolve out from there. I'll have to do some reading, as it's been awhile since I thought about genetic algorithms. My first thought is to divide down the middle, and keep the half of the items that raises the most stats closest to cap.

No! Completely random for best results.

 

[Cogman]

Doing trains example, breading would be a simple random pick of items from each parent until you have all items. If you do that, I would be sure to throw in like 10 random generations just to be sure your not stuck in a local optima.

Doing the genetic approach will probably lead to a more optimal solution, I just won't do it because I'm too lazy 🙂. The other is much simpler to implement as you don't have to worry about breading situations (Do you bread with only the best? Do you do a breading with a completely random generation? How many random generations do you include with the group?), Not that they add too much hassle, but they do add enough for me to say "Screw it."

 

[PhatoseAlpha]

Beforehand, it would be a good idea to sort through each slot and remove anything obviously not correct - ie, a sword +1 STR obviously won't be optimum if there is a sword with +3 STR, and a +1DEX/+20HP will always be worse then +1DEX/+25HP.

 

[Cogman]

Beforehand, it would be a good idea to sort through each slot and remove anything obviously not correct - ie, a sword +1 STR obviously won't be optimum if there is a sword with +3 STR, and a +1DEX/+20HP will always be worse then +1DEX/+25HP.

Ah, good point. That should significantly reduce the search space.

 

[Markbnj]

Beforehand, it would be a good idea to sort through each slot and remove anything obviously not correct - ie, a sword +1 STR obviously won't be optimum if there is a sword with +3 STR, and a +1DEX/+20HP will always be worse then +1DEX/+25HP.

It gets a little more complicated than that, if I'm understanding you. The +1 STR sword might be optimum in a different configuration where you get +5 STR from a helm, and the max is +6. The sword might also have +5 DEX or some other good stat.

Train, thanks for straightening me out on the permutations from one generation to the next.

 

[Cogman]

It gets a little more complicated than that, if I'm understanding you. The +1 STR sword might be optimum in a different configuration where you get +5 STR from a helm, and the max is +6. The sword might also have +5 DEX or some other good stat.

Train, thanks for straightening me out on the permutations from one generation to the next.

Well, he is saying if you have a +4 str sword and a +2 str Sword with exactly the same stats, there is no reason to include the +2 str sword in any of the searching.

You can leave the other stuff in that you might now be sure about, however, I would agree that removing the easy to remove stuff should be done.

 

[Train]

Not to throw another wrench into the whole thing but...

Wouldnt different users have different goals? Sure there is a "perfect" solution in which you max out everything as much as possible. But I assume that in a lot of cases, one config might be optimal with STR being the priority, yet another config would be optimal with DEX being the priority.

Perhaps another parameter to your algo is to have the user rank attributes in order of priority?

 

[Cogman]

Not to throw another wrench into the whole thing but...

Wouldnt different users have different goals? Sure there is a "perfect" solution in which you max out everything as much as possible. But I assume that in a lot of cases, one config might be optimal with STR being the priority, yet another config would be optimal with DEX being the priority.

Perhaps another parameter to your algo is to have the user rank attributes in order of priority?

Well, that would all be handled in the "Best" function. And really isn't too hard to deal with. You just put weights on stats, IE Score = str * .2 + dex * .5 + magic * 1 ect.

If you wanted to be more balanced, you could use logs and exponential growths to determine maximums as well. That way, you would make sure the user reaches some minimum level of str. or whatever.

 

[CycloWizard]

Genetic algorithms are great for rapidly finding good configurations, especially in response to changing goals (i.e. if your "best" function changes, the GA will rapidly adapt and find a new configuration which is very good under that function). However, it will almost never find a truly optimal solution. Instead, if you know which stats you want to maximize, a greedy algorithm might be much simpler and more efficient.

 

[Markbnj]

Well, he is saying if you have a +4 str sword and a +2 str Sword with exactly the same stats, there is no reason to include the +2 str sword in any of the searching.

You can leave the other stuff in that you might now be sure about, however, I would agree that removing the easy to remove stuff should be done.

In reality those scenarios would be largely nonexistent. Items in this case have a maximum "value" for augmenting stats that has to be distributed across all the stats affected by a given item. If one sword has +2 STR and another +5 STR then the other stats won't be the same. The first might have +5 DEX, while the second might have +2 CON.

You can do trivial reductions on the item population, however. There are class restrictions, restrictions on where items can be equipped, and users will want the ability to "pin" specific items to a search template as I mentioned before. All of these things will reduce the total size of the search space.

The question about goals is a really good one, but I think the answer is straightforward and along the lines Cogman suggested. Users need the ability to weight each stat, and the final ranking for a given result has to be the stat values times the weighting factor.

Another twist that I haven't mentioned yet is that users can create their own items, and it is common to create items to fill in spots where items from the world don't work. So ultimately the algorithm will also have to consider: how would this look if I created an item to fit in this slot?

 

[CycloWizard]

In reality those scenarios would be largely nonexistent. Items in this case have a maximum "value" for augmenting stats that has to be distributed across all the stats affected by a given item. If one sword has +2 STR and another +5 STR then the other stats won't be the same. The first might have +5 DEX, while the second might have +2 CON.

You can do trivial reductions on the item population, however. There are class restrictions, restrictions on where items can be equipped, and users will want the ability to "pin" specific items to a search template as I mentioned before. All of these things will reduce the total size of the search space.

The question about goals is a really good one, but I think the answer is straightforward and along the lines Cogman suggested. Users need the ability to weight each stat, and the final ranking for a given result has to be the stat values times the weighting factor.

Another twist that I haven't mentioned yet is that users can create their own items, and it is common to create items to fill in spots where items from the world don't work. So ultimately the algorithm will also have to consider: how would this look if I created an item to fit in this slot?

Adding additional items increases the size of the search space. That said, it would be easy to actually recommend an item that would optimize your performance (once you have stated what you want "performance" to mean).

 

[Cogman]

Genetic algorithms are great for rapidly finding good configurations, especially in response to changing goals (i.e. if your "best" function changes, the GA will rapidly adapt and find a new configuration which is very good under that function). However, it will almost never find a truly optimal solution. Instead, if you know which stats you want to maximize, a greedy algorithm might be much simpler and more efficient.

For Knapsack problem, the greedy algorithm often doesn't do so hot. It might do "OK" with this problem as you are limited to different item types, however, I still feel a couple of GA / fully random iterations will yield better results.

 

[CycloWizard]

For Knapsack problem, the greedy algorithm often doesn't do so hot. It might do "OK" with this problem as you are limited to different item types, however, I still feel a couple of GA / fully random iterations will yield better results.

It depends on the end result he's after. The greedy algorithm can be deterministic (that is, it will find a truly optimal solution) depending on how complex the cost function is, whereas the GA is heuristic (i.e. it will just suggest good configurations). The GA is also much more complicated to program, though I doubt this will be too much of an obstacle for Mark, depending on the GA features he chooses to incorporate (e.g. migration, elite status, etc.).

 

[Markbnj]

Adding additional items increases the size of the search space. That said, it would be easy to actually recommend an item that would optimize your performance (once you have stated what you want "performance" to mean).

Items aren't added in the scenario I described. The total item population remains the same, however by "pinning" a specific item in its position the user takes one whole item class (the items that fit in that slot) out of the search space.

 

[Train]

Can you define total search space?

I'm wondering if its worth solving incrementally. Such as using a GA to get a good solution now, but over time (I'm picturing weeks) keep track of what parts of the search space have been exhausted (by "blocks" or whatever) and then have your GA only select from configs that havent been tested yet.

And the more I think of it, this problem also seems like it could fit into a tree structure, especially if you start putting lots of restrictions on items, such as rings can only be worn on fingers, swords must be in a hand, armor can only be worn on torso, etc. Every time you put a restriction on an item, you reduce the total search space by several orders of magnitude.

 

[Markbnj]

Can you define total search space?

I'm wondering if its worth solving incrementally. Such as using a GA to get a good solution now, but over time (I'm picturing weeks) keep track of what parts of the search space have been exhausted (by "blocks" or whatever) and then have your GA only select from configs that havent been tested yet.

And the more I think of it, this problem also seems like it could fit into a tree structure, especially if you start putting lots of restrictions on items, such as rings can only be worn on fingers, swords must be in a hand, armor can only be worn on torso, etc. Every time you put a restriction on an item, you reduce the total search space by several orders of magnitude.

What I meant was this: if I have five slots, and 50 items that will fit in each slot, and I am looking for the best fit w/o any preconditions, then I believe there would be 50^5 configurations to be searched. If I start the search with the condition that I want to keep item X in slot 1 because I like that item and I know there are good configurations that include it, I now have to search only the 50^4 configurations that include item X. Does that make sense?

The tree idea... I very briefly flitted by this when I first started thinking about it. It's hard for me to envision how you would build a tree that represents this problem, or what dimensions you would partition on. The monte carlo or GA approaches seem much more likely to be effective, so I didn't follow that line of thought very far. I would be interested in hearing any ideas you have.

 

[Train]

What I meant was this: if I have five slots, and 50 items that will fit in each slot, and I am looking for the best fit w/o any preconditions, then I believe there would be 50^5 configurations to be searched. If I start the search with the condition that I want to keep item X in slot 1 because I like that item and I know there are good configurations that include it, I now have to search only the 50^4 configurations that include item X. Does that make sense?

Yes thats exactly what I meant too. The question is, can you DEFINE the search space, as in, how many options for slot 1? how many options for slot 2? 3? ... n? Then total seach space = options for 1 * options for 2 * .... * options for n. Of course its more complicated because an item may only be used once but can fit in multiple slots, and certain items may not be used together, or whatever restrictions you may have.

What I was getting at is, can you definitively say when you are DONE searching?

The tree idea... I very briefly flitted by this when I first started thinking about it. It's hard for me to envision how you would build a tree that represents this problem, or what dimensions you would partition on. The monte carlo or GA approaches seem much more likely to be effective, so I didn't follow that line of thought very far. I would be interested in hearing any ideas you have.

I havent taken this thought far, and what I have envisioned so far is hard to put into words. I guess I started with each slot being a node, and each subnode is a different item that you could put in that slot. Then sub nodes below that would be all other slots (or all slots that have not already been defined in parent nodes)

Sub nodes would then be interchangeable. Lets say you have the last 3 nodes in a sub tree, with the root node having a sum of its ideal attribute modifiers. While traversing the tree, anytime you get down to the last 3 nodes (assuming you always calculate nodes in order) then you just tie in the root node of the sub tree you already optimized.

Ok not very complete but that's the basic Train of thought as I typed it out.

This would be a fun problem to white board.

 

[Markbnj]

Can I definitively say when I am done searching? In theoretical terms, sure. There are a fixed number of items that can fit in each slot given the restrictions of each character class, and so there are a fixed number of combinations. The real number might be something on the order of 200^10. If I was able to methodically search all of those combinations I would be able to say when I was finished. But in that sense it's a little like the combinatorial problem of chess, i.e. we can't search all the way to the end of the game using current technology, so we focus on searching as deep as we can. The way I envision this working using an approach like Cogman outlined would be: the user sets the goals and weights, and the number of loops to run, and the results come back as, say, the top ten configurations. The user then has the option to run the loop again starting from scratch, adjust the inputs, run it from one of the current results by pinning one or more items, etc.

 

[Schmide]

If you assign an inverse weight to each item you could use the simplex method to solve the series of linear equations and find the optimum path combination.

 

[KIAman]

Hmmm, I have more questions as well.

1. Are any items duplicate stats (perhaps with different skins)?
2. You mention you +1 str sword would work with +5 str helmet, is the stat cap simply limiting or restrictive? (does it have to equal EXACTLY cap value or does it ignore all values beyond cap?)
3. Are you looking for a single perfect solution or is it conceivable to have numerous amounts of perfect solutions?