Is a genetic algorithm a correct approach to this problem?

Question

I am trying to calculate a set of items that produce the highest damage output in a video game. There are about 50 different items, of which you can choose 6. There are all sorts of conditions that each item creates. I am writing a small app in javascript that calculates your damage based on the items. Could I utilize a genetic algorithm to find out which item combinations are the strongest? Or is brute force acceptable for this size of a problem? Or is there another way?

Answer 1

There are 50 items, of which you can have 6 at a time, meaning you have 50 * 49 * 48 * 47 * 46 * 45 = 11,441,304,000 unique combinations of items (I think my math is right). As nikie points out below in the comments, if order of the items doesn't matter (probably not), this number is reduced to 50 * 49 * 48 * 47 * 46 * 45 / (1 * 2 * 3 * 4 * 5 * 6) = 15,890,700 combinations, a very manageable amount. This may be a little much for brute force every time, but on the other hand, if the items don't change you can probably perform this calculation once and store it somewhere (localStorage, whatever).

Genetic algorithm seems like overkill here, since I think it'll take too long for it to give you an ideal set compared to brute force. Assuming you can't run it once and store it, I would figure out if there's some way you can optimize the order of the items before running the query and prune out some of the weak combinations, and get that number down a bit before running your algorithm.

Answer 2

IT depends what the items and other variables of your problem are, but you can probably make good use of heuristics here.

Basically, there's probably a way to rule out some of the items right away because their stats distribution don't match your character. Then you can probably do stuff like "Most important stat is damage (for example), let's start by calculating the item set that maximizes this stat then see if swapping items from this set with others not previously retained to see if there's improvement in overall performance".

There's a lot of ways to approach this sort of problem, but genetic algorithms seem a little overkill here. Want to share more info specific to your problem? Maybe we can help you better then!

Actually, the way I would probably approach it would be to precompute a "score" for every item, then sort them and pick the 6 highest scores.

I'll still leave the rest of my answer as a reference.

Answer 3

a GA is one approach, if brute-force isn't practical

permutations of heuristics and calculating/simulating the effects may also be viable; there's good precedent for this approach in Doug Lenat's use of Eurisko to design ships for Traveller tournaments

Answer 4

I think the question needs some more explaining. If all that matters is choosing 6 items out of 50 that cause max damage, then if you sort the items in descending order of damage capability and pick the top 6 - that will do. However, I suspect that there is additional complexity associated with choosing these 6 items, i.e. maybe some cost associated with each item being chosen. In that case, it looks like a knapsack problem and can be crunched quickly using dynamic programming, for the problem size you have described. The knapsack problem is as follows: what is the optimal set of items (out of your 50 total) to carry in a knapsack to maximize benefit (in you case, damage) and stay under a certain cost (maybe total points available to choose items). In your case - if this number exceeds 6, then you can drop the least damage causing items until you get to exactly 6 items. Note, this will be an optimal solution.

Answer 5

If a genetic algorithm is suitable depends on the characteristics of the items. If similar items have a similar damage it would be more suitable than if there are items, that suddenly alter your damage, but they are only slightly different to others with much less/higher damage. For example usually STR will increase your damage, than the algorithm would probably start to favor those items with high damage, but it may never find a solution with that funky shiny helm that gives no damage, but adds half of your intelligence multiplied by your dexterity to you strenght.

Try to imagine the solution space and how the algorithm would "travel" around there. Im afraid its highly possible to get stuck with a solution thats far from the optimum.