Difference between revisions of "Discussions/XPMinAlgorithm"

Latest revision as of 01:15, 6 April 2010

Spawned from the Discussions/SoybeanTrading Discussion.

How hard would it be to write an algorithm to determine min xp for a given configuration?

Maybe I'm missing something, but this doesn't seem to be impossibly hard(or in the NP category, either). You can do a lot of the work for you by looking at statistics. For example, your favored abilities should be the abilities that you've put the most rating into and that you've bought the most charms from. Attributes are straight forward; max as many as possible with bonus points, buy the rest with xp. Virtures/Willpower gets a little interesting, but I don't think it would be that difficult.

Comments? I've only reached 300-level undergrad courses, so I very well might be missing something. -Fifth

I don't think it would be hard.

First I would maximise the XP cost of non-bonus-point character creation (e.g. on abilities, first buy all the 1 dots, then buy all the pairs of 2-3 dots I can afford that still remain, then buy any remaining 2 dots if there are points over).

Then with my new base Character, I would set up a few if-then assignments of bonus points (can I do this which would be most efficient? Yes, then do it. No, then check if I use my XP in the next most efficient way). The only tricky part would be allocating the last few points, but this could be checked too.

XP cost for remaining creation would do the rest. ^_^ --BrokenShade

Instead of going to all that trouble, why not just ditch the bonus-point system (which pretty much only exists for simplicity), and make everyone buy up their dots with xp during chargen? The only drawback I can see to that it that the bp system sort of enforces balanced characters; you can't ditch all your Attribute points to get more Charms, for example.\\ _Ikselam

Well, it's fairly easy to do the BP/XP ratios.

Just hard code a table from most efficient to least efficient bonus point use, then have the program maximize each level as much as it can before going to the next. So, do Favored/Caste Specialties as much as it can first, then go to on to the next most efficient, and then the next, and so on. -Fifth

That's the algorithm I tried at first. It gets stuck in local minima and doesn't find the most efficient solution. --MF

The BP to Xp one, you mean? I'm trying to figure out how it would get stuck... if you spend bonus points on the most efficient places, that will be the maximum value you can get from your BPs. Right? -Fifth

Consider that the XP/BP ratio varies depending on how many dots you buy. The third dot of a Caste/Favored Ability has a 3:1 ratio--usually not a good buy--but if you then go on to buy the fourth and fifth dots as well, the total works out to 5:1--which is a good buy. --MF

Mmmm, I see what you mean, but I figured handling that by going for maximums; ie, buying the final 3 dots, buying the final two, etc. You will almost always want to min-max with BPs, rather than have an even spread, so if the algorithm calculates efficiency over maximum dots, it might work out.

A question for you all, though: If we're dealing with bonus points, we also need to deal with most efficient character generation with the assigned dots. How hard is that to implement? Again, for lots of these I think a simple min-max algorith might give the most efficient answer, but I'm not sure. -Fifth

It's also necessary to compute tradeoffs with base dots. There's a three-way tradeoff between base dots, bonus points and XP in most cases. That's where I really bogged down. --MF

True. I wonder if it'd be easier to use a Greedy algorithm, and have it look for a min xp solution? Or even a genetic algorithm; those are pretty easy to program. -Fifth (Someone keeps forgetting to sign their posts. I'm just assuming this came from Fifth and adding his signature. --MF)

I was kind of thinking simulated annealing or A*. I'm a little too long out of school to be really comfortable with genetic algorithms, but if that floats your boat, by all means, go for it. --MF

--

At creation and after it if you really want maximize your BP and expend less experience after creation, you should take essence 2 (it costs a lot for little benefit, except if you are going to start with sorcery), expend most points maximizing virtues because they will increase willpower and give more motes to expend, for example a comparation look at bellow. I will pick only max biggest values avaliable at creation because they are best. It is cheaper get a Attribute 5 and increase a 1 or a 2 as well any other thing in this game.

-Just one pratical example- Base Attribute Dexterity 4 Virtues Comp 3 Conv 3 Temp 2 Val 1 Essence 2 Background 3 Base Willpower 6 Favored/Caste Ability 3 dots Unfavored Ability 3 dots

Cumulative costs and exp cost of same increase. - Essence 2 to 3 = 7 BP (16 exp), to 4 = 14BP (40 exp) Average 1BP = 2.86 exp - Backgrounds 3 to 4 = 2BP (3exp), to 5 = 4BP (6 exp) Average 1BP = 3 exp - Unfavored/Caste Ability 3 to 4 dots = 2BP (8 exp), to 5 dots = 4BP (18 exp) Average 1BP = 3.5 exp - Attribute 4 to 5 = 4 BP (16 exp), 1 BP= 4 exp - Favored/Caste Ability 3 to 4 dots = 1 BP(7 exp), to 5 dots = 2BP (16 exp) Average 1 BP = 8exp - Virtue 3 to 4 dots = 3 BP (9 exp plus WP bonus), to 5 dots 6 BP (21 exp plus 2 WP bonus)

 - Just one virtue increased from 3 to 4 = 3BP (21 exp), one to 5 = 6 BP  (47 exp) Average 1BP = 7.83 exp
 - And incresing another virtue to 4 = 9 BP (72 exp) Average 1BP= 8 exp, to 5 = 12BP (100 exp) Average 1BP = 8.33 exp

Conclusion - The best exp / BP rate is to put 12 BP at virtues to increase two to 5 dots each, followed by increase of abilities as the expression bellow indicates. - Virtues >= Favored/Caste Abilities >>> Attributes > Unfavored Abilities > Backgrounds > Essence.

- Shiki