Calculating the highest possible damage achievable using 6 items from a pool of ~25

Question

I am writing an app in javascript to try to figure out item builds for characters in a video game. There are about 25 top-tier items, and you can carry 6 at a time. They have very different effects, which leads me to believe that while one item may seem like it isn't very good by itself, it can become much stronger when combined with others. I can elaborate on that if there is interest.

Questions:

1. How can I get a list of all the different distinct combinations of 6 items? How many combinations will there be? Is it just 25c6 (~134k)? Or do I need to remove duplicates? (Sorry, I've been out of math class awhile.)

2. How would you implement something like this in Javascript? Is there already a math library that can do this? (Specifically, iterate through all of the possible combinations of items.)

3. Does it seem possible to brute force calculate the damage of all the possible combinations and save the top item combinations? If not, is there a better algorithm to find strong combinations?

Here's my code, based on everyone's input:

function getAllCombinations(n, k, callback)
{
    var iterate = function(remaining, args)
    {   
        var len = args.length;
        for (var i = args[len - 1]; i < n; i++)
        {
            args.splice(len);
            args[len - 1] = i;
            if (remaining)
            {
                args.push(i);
                iterate(remaining - 1, args);
            }
            else
            {
                callback.apply(null, args);         
            }
        }        
    }
    iterate(k - 1, [0]);
}

var itemsCount = 25;
var itemSlots = 6;
getAllCombinations(itemsCount, itemSlots, function(a, b, c, d, e, f)
{   
    // calculateDamage(hero, arguments);
});

Answer 1

1) Yes, it is just 25 choose 6

2) Well, if you only have to do this once, you can do it with nested loops. The key is to have each of the inner loops not start from zero, but from the outer counter.

for (int i = 0; i < 25; i++) {
    for (int j = i; j < 25; j++) { // note j=i not j=0
        // etc
        foo(i,j,k,l,m,n);
    }
}

If you need a generic solution for generic values of 25 and 6 it shouldn't be hard to write a recursive function with similar effects.

3) I think your only option is brute force. It may take a few minutes, but it should complete. I think it will be fastest in Chrome and unusable in IE. Other options like "local search techniques" don't seem like they would work for you because your space is not particularly continuous.

Answer 2

1. Yes, it's 25C6 (which is actually ~177k)

2. is a duplicate of, for ex. List all possible combinations of k integers between 1...n (n choose k) and How can I iterate throught every possible combination of n playing cards.
   If you know there are going to be only 6 items, you could just have 6-nested for-loops (though this obviously doesn't scale well).

3. Of course it's possible - 177k combinations would take a tiny fraction of a second to iterate through on a typical PC (probably a bit longer since you are using Javascript, but not more than a second or two)

Answer 3

Shawn,

That sounds like a job for the British Museum algorithm to me... with cheese, of course.

By cheese, I mean that the "cost" (or "profit" in your case) of traversing a particular node (overall priority) could be a function of this-node combined with all it's predecesors-in-this-path. Traversing any particular node will be a LOT more computationally expensive than the traditional "maze", where each node has a fixed-traversal-cost (like the length of a street for instance)... but with a maximum path length of just six nodes you should be able to allways reach the best result quickly (i.e. sub-second).

To avoid double up's just don't add node-A to a path which already contains node-A.

I see no reason why you shouldn't implement this in javascript, but I suppose you'd have to implement your-own Priority Queue, and that's pretty tricky in it's own right... The good news is that it's a published data-structure, so I'd start from Wikipedia to get my head around it, and then google hard to see if I can find a "decent" javascript implementation... or failing that I'd just port Java's implementation.

This is a challenging little problem. I'll be interested to see what you come up with, and what other people suggest along the way. Keep me updated willya?

And one other peice of advise... most often it's best for a game to NOT make optimal decisions; because your opponent a "mere human" is completely incapable of calculating a good (let alone THE optimal) combination of "6 from 25 powers" in under a second, and the probability of them getting THE best combination by accident is 1 in 25*24*23*22*21*20 = 127,512,000 ... espcially if those "powers" leverage each other in "secret" ways... even if the secrets are published it'll take a "programmers mind" to do the math, enough to achieve an "above average" result. Do you get what I mean?

Cheers. Keith.