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?

  • 1
    FYI, a well written genetic algorithm will find a good solution but it does not guarantee that it will find the optimum solution no matter how well you write the algorithm.
    – Dunk
    Commented Apr 15, 2011 at 17:08
  • Is it Dota 2, LOL or HoN? Then there'll be no simple solution, because different items will be better depending on the enemy's armor. If the enemy has more armor a damage item may be better, if he has less armor an attack speed item may be better for a higher DPS. There are also items which reduce the enemy's armor, which doesn't make things easier. Commented Feb 28, 2014 at 6:53
  • genetic or generic?
    – tgkprog
    Commented Feb 28, 2014 at 7:40

5 Answers 5


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.

  • a brute-force calculation done once is not unreasonable for a small state-space like this. If you can evaluate 1 million cases per second, it will only take about 3.5 hours to complete. Commented Apr 15, 2011 at 2:11
  • You're right that it isn't out of the question, but being that its Javascript (by his tag), I figure some amount of speediness was required. I stand corrected though, if it's a node.js app or something. Commented Apr 15, 2011 at 2:13
  • 1
    +1: If the result can be stored and it's not an exercise, I think that the time to develop should be taken into account. Tweaking the crossovers/mutations/fitness and the testing in-between so that it's not settling on a local maxima could take much longer than taking a brute force approach. Commented Apr 15, 2011 at 4:23
  • 6
    +1. And if the order of the items doesn't matter, there are only about 16 million combinations.
    – nikie
    Commented Apr 15, 2011 at 9:18
  • 1
    @Jimmy Sawczuk: The math is 50*49*48*47*46*45 / (1*2*3*4*5*6). See: en.wikipedia.org/wiki/Combination
    – nikie
    Commented Apr 15, 2011 at 13:46

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.


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


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.

  • 1
    Could you describe the knapsack problem with an example (game inventory & damage capability) rather than link to a video?
    – user40980
    Commented Feb 28, 2014 at 5:40

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.