Proficiency learning optimizer

Forum for game modifications and custom clients.

Re: Proficiency learning optimizer

Postby Kandarim » Thu Jan 29, 2015 9:35 am

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!
I have neither the crayons nor the time to explain it to you.
JC wrote:I'm not fully committed to being wrong on that yet.
User avatar
Kandarim
Customer
 
Posts: 5321
Joined: Mon Jan 21, 2013 4:18 pm

Re: Proficiency learning optimizer

Postby Blood » Thu Jan 29, 2015 9:55 am

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.
Blood
 
Posts: 259
Joined: Sat Nov 17, 2012 5:09 pm

Re: Proficiency learning optimizer

Postby EnderWiggin » Thu Jan 29, 2015 10:24 am

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.
User avatar
EnderWiggin
 
Posts: 339
Joined: Wed Aug 01, 2012 9:12 am
Location: Ukraine

Re: Proficiency learning optimizer

Postby Kandarim » Thu Jan 29, 2015 11:06 am

not really, from a genetic's program point of view: it's a valid, but non-optimal, option.
I have neither the crayons nor the time to explain it to you.
JC wrote:I'm not fully committed to being wrong on that yet.
User avatar
Kandarim
Customer
 
Posts: 5321
Joined: Mon Jan 21, 2013 4:18 pm

Re: Proficiency learning optimizer

Postby Gernot » Thu Jan 29, 2015 12:41 pm

Kandarim wrote: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.
Gernot
 
Posts: 38
Joined: Tue Dec 04, 2012 2:46 am

Re: Proficiency learning optimizer

Postby Kandarim » Thu Jan 29, 2015 1:48 pm

Gernot wrote: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.
I have neither the crayons nor the time to explain it to you.
JC wrote:I'm not fully committed to being wrong on that yet.
User avatar
Kandarim
Customer
 
Posts: 5321
Joined: Mon Jan 21, 2013 4:18 pm

Re: Proficiency learning optimizer

Postby Gernot » Thu Jan 29, 2015 2:33 pm

Kandarim wrote:
Gernot wrote: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 ;)
Gernot
 
Posts: 38
Joined: Tue Dec 04, 2012 2:46 am

Re: Proficiency learning optimizer

Postby Kandarim » Thu Jan 29, 2015 4:45 pm

sure. Smaller than 1e9. Why would the absolute smallest be easier than smaller than an arbitrary treshold ?
I have neither the crayons nor the time to explain it to you.
JC wrote:I'm not fully committed to being wrong on that yet.
User avatar
Kandarim
Customer
 
Posts: 5321
Joined: Mon Jan 21, 2013 4:18 pm

Re: Proficiency learning optimizer

Postby Gernot » Thu Jan 29, 2015 6:55 pm

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?
Gernot
 
Posts: 38
Joined: Tue Dec 04, 2012 2:46 am

Re: Proficiency learning optimizer

Postby JohnCarver » Thu Jan 29, 2015 8:18 pm

nerds
ceedat wrote:the overwhelming frustration of these forums and the unnecessarily over complicated game mechanics is what i enjoy about this game most.

Nsuidara wrote:it is a strange and difficult game in no positive way
User avatar
JohnCarver
Site Admin
 
Posts: 6826
Joined: Fri Jun 06, 2014 3:02 am

PreviousNext

Return to Artifice & Arcana

Who is online

Users browsing this forum: No registered users and 3 guests

cron