Proficiency learning optimizer

[Kandarim]

that doesn't take into account overflow though, e.g. your system very well may study an aphid if only 200 s&c is required and a brain would suffice
It's called the knapsack problem, and there are no efficient optimal solvers: it's an NP-hard problem. Genetic algorithms are probably the way to go, but that doesn't mean I have to like it.

Praise be to JC for such an interesting system!

[Blood]

Nice little tool you developed there im sure it will help quit a few people that want to get to the needed level but don't wanna go through alot of hassle of researching everything. For me though i could never give up on my good ol excel sheet and doing a pick and choosing of available curios and ip:points efficiency calculations.

[EnderWiggin]

Nice tool. But it has some bugs with calculating cost. It shows Brilliant Honeydew + Foetid Ooze cost 27375 or 29500. Which is strange. Looks like it has something to do with order of consumption.
Plus it often includes combinations like 1st place A+B, 2nd place A+B+C. 2nd option is clearly wrong.

[Kandarim]

not really, from a genetic's program point of view: it's a valid, but non-optimal, option.

[Gernot]

that doesn't take into account overflow though, e.g. your system very well may study an aphid if only 200 s&c is required and a brain would suffice
It's called the knapsack problem, and there are no efficient optimal solvers: it's an NP-hard problem. Genetic algorithms are probably the way to go, but that doesn't mean I have to like it.

Praise be to JC for such an interesting system!

This is not true in this case. For this to be a Knapsack problem, the amount of inspiration you are willing to spend would have to be limited. However, there is no limit on inspiration; the only restriction is that you want it to be small. Explicitly, you are not saying it has to be smaller than an arbitrary limit L. It is still NP hard (though in practice, given the very limited set of input variables, it may very well still be tractable).

The problem really DOES stem from overspill. While overspill can easily be compensated for, its very existence precludes a guaranteed optimal solution based on a greedy algorithm. First, about compensating: when you have got the bound for a given proficiency, then if an inspirational would go beyond the desired value, the new efficiency ratio would still be (useful amount / total amount), with the correction that part of "useful" goes to "waste" instead. Say you're at 4000 / 6000, something would add 2500 at cost 5000, then the actual ratio in this case would be 2000 / 5000 = 0.4 instead of 0.5. Now, the problem why this may not result in an optimal solution is simple: assume you want to reach 5000. If you study the aphid first, you've got 500 remaining. According to the calculation above, the best thing to study may be a wicker man. But if you had studied a mayapple first, you might have been able to study a more efficient second inspirational.

For the single proficiency case, the scheme above is still asymptotically optimal (if the desired proficiency goes toward infinity, the described overspill problems vanish . In other words, the error gets smaller the higher the proficiency you're aiming for. It would need testing, but I believe that this already holds true for all practical purposes once your desired proficiency is noticeably higher than your inspirational values.


About genetic algorithms, I'm not getting into that debate sometimes they do work better than alternatives, sometimes they don't. They are definitely very hard to judge mathematically in terms of any guarantees.

[Kandarim]

However, there is no limit on inspiration; the only restriction is that you want it to be small.

I don't want it to be small. I want it to be the smallest.

[Gernot]

However, there is no limit on inspiration; the only restriction is that you want it to be small.

I don't want it to be small. I want it to be the smallest.

Indeed, but not smaller than a given value. Just the smallest

[Kandarim]

sure. Smaller than 1e9. Why would the absolute smallest be easier than smaller than an arbitrary treshold ?

[Gernot]

I agree that for practical purposes, it probably does not make a difference.

What I meant is that there are cases (and depending on the algorithm used this may matter) where there are solutions for the case "as small as possible" but not for the case "smaller than x". In your example, you imply that you want "smallest possible and smaller than Y". If Y is large enough, obviously the second condition is always true and thus does not matter.

We agree on the important part anyway. But thanks to your input, I got a new suggestion:

suppose we actually try to modify the standard knapsack problem (which would be nice, since we could then use a standard solver):

for the single proficiency case our problem would be: we want to have at least weight W (but as low as possible beyond that) and minimize utility. W would then be the proficiency we want and utility the cost in inspiration. Suppose we fill a first bag with all items and then remove items into a second bag, our knapsack, with a limit of totalWeight (sum of all proficiency values) - W and maximal cost. Once we solved the knapsack, the rest left in the original bag should be our real solution.

What do you think?

[JohnCarver]

nerds