# Is a genetic algorithm a correct approach to this problem?

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?

-
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 Apr 15 '11 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. – MarcDefiant Feb 28 '14 at 6:53
genetic or generic? – tgkprog Feb 28 '14 at 7:40

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. – Steven A. Lowe Apr 15 '11 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. – Jimmy Sawczuk Apr 15 '11 at 2:13
+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. – Steve Evers Apr 15 '11 at 4:23
+1. And if the order of the items doesn't matter, there are only about 16 million combinations. – nikie Apr 15 '11 at 9:18
@Jimmy Sawczuk: The math is `50*49*48*47*46*45 / (1*2*3*4*5*6)`. See: en.wikipedia.org/wiki/Combination – nikie Apr 15 '11 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.

-
Could you describe the knapsack problem with an example (game inventory & damage capability) rather than link to a video? – user40980 Feb 28 '14 at 5:40
edited my original posting, thanks – akrishnamo Feb 28 '14 at 10:28

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.

-