Competition-agnostic item allocation

[Derakon]

I mentioned this in another thread -- currently, the frequency of a given item depends in part on the frequency of all other items that can possibly be generated. As an overly-reductive example, if the only item in the game is a rocket launcher, then of course only rocket launchers will be generated...but those rocket launchers will also be generated in massive numbers, even if rocket launchers are nominally extremely uncommon items.

This wreaks havoc on attempts to balance the game via item frequency, because any change to any item's allocation rules has an effect on all other items' drop rates. This applies to egos (and presumably to artifacts) as well. Most notably, if we decide to make junky items less common, then we de facto make non-junky items more common. This is why "big 3" weapon egos are such a big deal right now -- the Too Much Junk initiative meant that they don't have nearly as much competition at deeper dungeon levels. It's also why we had to add the junky DSM of Craftsmanship to "push out" DSMs of Speed and Elvenkind.

Here's my proposal to address this issue. Right now, we have a sort of "unitless" allocation rule. Let's change that to explicitly being "N out of every million items will be this item". For example, a Potion of CLW having an allocation of 10,000 at dlvl5 means that 10,000 out of 1,000,000 (i.e. 1%) of items generated at dlvl5 will be CLW. For any given dungeon level, it will be an error if indicated item frequencies sum to more than 1,000,000.

For each depth, we examine the frequencies for all items that have an allocation rule for that depth, and build a table of length 1,000,000 of the different odds. In our example, at dlvl5 CLW would occupy 10,000 slots on this table. The table will have gaps in it -- not every slot will be taken (the table generator can at least enforce that we do not overfill it). If we want to generate an item, we roll, find the corresponding item if any, and generate it. If we don't find an item (an "allocation miss"), then nothing is generated.

Note that we don't actually have to build out an entire table. We just need a list of all possible valid items at each depth, then make a random number between 1 and 1,000,000, and walk along the list until we hit the corresponding item or run out of items.

Artifacts slot into this rather nicely -- we can just say that the One Ring has a 1 in 1 million chance of being any given item at any depth. Egos are trickier, because they need a base item to be applied to. I believe this can be handled with a separate allocation table, though. Say we choose e.g. to generate a Dagger. This is an item that is potentially eligible for egos, so we look up in another table of ego frequencies, which contains all the egos that can be applied to a Dagger, as well as the frequency for merely good items (we can gloss "good" as . If we get an allocation miss on that table, then the item is generated as average.

For uniques or other situations where we want to boost the drop quality, I see two major possibilities. The simplest is to just drop the item as if it were at a deeper dungeon level. The second is to pick multiple times from the table, and choose the "best" result. That might mean applying some item power heuristics, but maybe it just means we take the least-likely result.

The overall process is straightforward. I recognize that it does make the numbers a little less pleasant-looking when writing allocation rules. However, the fact that allocation rules are now very clear about what they mean seems like a huge win compared to the current system.

[PowerDiver]

If you want straightforward, ditch the table. If you keep the table, in any form, it will be hard to keep things independent. Each item should have a distribution for number of instances on the level. Go through all the items, figure out how many of each, put them down. That's doesn't work for vaults, so do something separately for vaults.

[Derakon]

If you want straightforward, ditch the table. If you keep the table, in any form, it will be hard to keep things independent. Each item should have a distribution for number of instances on the level. Go through all the items, figure out how many of each, put them down. That's doesn't work for vaults, so do something separately for vaults.

I don't see how the table makes it hard to keep things independent. The important thing is that when we decide what to generate, there's a "generate nothing" option whose likelihood is set so that all other items have consistent frequencies per million item generation attempts.

That said, your suggested approach sounds potentially promising as well, though I think it needs more refinement. I take it you mean the game data should have something like "There should be 1.3 CCW potions per level at dlvl30", and then level generation plops down items according to those numbers? Vaults I suppose could be handled by saying they count as an extra N level's worth of items (N depending on the vault, maybe by examining the number of item tiles in it). But how would your proposal handle ego items? And what about monster inventories? For monsters that spawn after level generation completes?

[Nomad]

For each depth, we examine the frequencies for all items that have an allocation rule for that depth, and build a table of length 1,000,000 of the different odds. In our example, at dlvl5 CLW would occupy 10,000 slots on this table. The table will have gaps in it -- not every slot will be taken (the table generator can at least enforce that we do not overfill it). If we want to generate an item, we roll, find the corresponding item if any, and generate it. If we don't find an item (an "allocation miss"), then nothing is generated.

How about picking an item at random from all those available at the current depth, then rolling against some sort of "rarity value" to see if it's actually generated?

e.g.:
- Generation process determines the item type will be a potion.
- Build a list of all potions that are allowed at this depth, and choose one at random, with all having even odds of being picked.
- Roll against rarity to see if the selected potion is actually created. (For instance, say CLW is picked, then there's an 90% chance of actually getting a potion of CLW, 10% chance of getting nothing, but if Experience is picked, there's only a 5% chance of it being created and a 95% chance of nothing.)
- Perhaps attempt multiple rolls, but if you get, I don't know, three to five "failed to create item" results in a row, then give up and nothing is generated. (This would be a good value to tweak with a global difficulty setting, actually - at low difficulty the game will try many times to create an item, high difficulty it gives up quickly.)

[Carnivean]

Given we now have a powerful squelching tool to overcome the Too Much Junk problem, why not just put the junk back in?

[PowerDiver]

I'm saying that your approach is aesthetically unpleasing to my mathematical viewpoint. Generally speaking, such leads to contradictions sooner or later.

Consider a random monster dropping a drop. If you increase the likeliness of anything that might be dropped, that means that the expected size of the monster's drop needs to increase. That's the first thing you need to accept. You *cannot* generate the drop size first and then choose items and still accomplish your goals as I understand them. If you do, increasing junk densities means decreasing non-junk items and vice versa. It might only be implicitly calculated, but the drop size has to change with your item rates or else you will fail the goal.

The same argument applies to dropping a predetermined fixed number [typically 1] of ego weapons if you muck with ego rarities. Can't be done without violating your goal. More of one ego means less of the others.

I'd suggest that a monster's drop should be equated to what would be generated in a fixed area of dungeon at a particular level [restricting to particular pvals, or good/ego if desired], and that dungeon items be generated independently according to area and level. There are plenty of other ways to do this, but IMO this is the cleanest. You'd need to handle vaults and special rooms; e.g. spots that currently have guaranteed objects should have high measure. I'd allow 0 or 2+ objects, no big deal IMO if not exactly 1, but you could special case it to guarantee 1 object if you couldn't help yourself. Most likely that would break the basic goal at least a bit no matter how you fudge the calcs, but maybe it's close enough you wouldn't care.

If you want independence of item distribution, embrace it fully. Try to avoid data structures that allow even the appearance of interdependence. A choice into a table that picks one or the other but not both should worry you.

None of my hypothetical complaints are provable until you flesh out a specific proposal. You might be able to get around them with a lot of hard work and cleverness and implicit calculations. But if you are going to make a complete break, you might as well aim for the cleanest solution you can think of.

Don't take my specific suggestions too seriously -- they are just the first things that came to mind, in my sleep-deprived state.

[Nick]

OK, here's what my feelings boil down to (after considerable thought and lots of deleting):

• Consumables are fine, let's not bother with them.
• I'm inclined to say the same about all base items, subject to below.
• Egos - we could have fixed probability that any base item gets a particular ego. Problem here is that sometimes (unique drops, acquirement) we essentially insist on an ego, which messes up the probabilities.
• Artifacts - we could do like Derakon said, fixed (small) chance to appear, work out the total "get an artifact" chance based on that, then pick which one based on individual probabilities. Same caveats as to egos apply.

End of the day, we're picking items from a probability distribution, and there's no god-given one. I'm not convinced that big change is going to lead to anything better; it will probably just be bad in different ways, and everyone will want to go back to the old method

[Derakon]

I'm saying that your approach is aesthetically unpleasing to my mathematical viewpoint. Generally speaking, such leads to contradictions sooner or later.

Okay, mathematically displeasing I may grant you, but if it's ugly and it works at least it works! [/quote]

Consider a random monster dropping a drop. If you increase the likeliness of anything that might be dropped, that means that the expected size of the monster's drop needs to increase. That's the first thing you need to accept.

Correct. If we go from a total item chance (as determined by summing the allocations of all possible items at this dlvl) of 50% to 60%, then the monster has a 10% higher chance of dropping anything.

You *cannot* generate the drop size first and then choose items and still accomplish your goals as I understand them. If you do, increasing junk densities means decreasing non-junk items and vice versa.

Either you don't understand my proposal, or you're pointing out a flaw in my proposal in a way I don't understand. The way I understand it, you absolutely can accomplish my goals, so long as you're willing to accept that when you try to generate an item, the result may be "nothing is generated".

The key insight in my proposal is that any item generation attempt may fail, with the likelihood of failure varying such that the likelihood of any one item being generated is constant. Let's take a simple example with only 10 "item slots":

CLW | CLW | CLW | Phase | Phase | Phase | Dagger | Dagger | NULL | NULL

Here we roll a d10, then drop the corresponding item. If we roll NULL, then nothing is dropped. CLW and Phase are both 30% of all items, and Daggers are 20%. Let's remove Phase Door.

CLW | CLW | CLW | Dagger | Dagger | NULL | NULL | NULL | NULL | NULL

Now there's a 50% chance of getting nothing, but CLW and Daggers are still 30% and 20%, respectively. We haven't changed the allocations of them whatsoever, even though we just made a major change to the frequency of a different item.

Does this clarify things?

[Derakon]

OK, here's what my feelings boil down to (after considerable thought and lots of deleting):

I appreciate the time and effort you've spent on this.

• Consumables are fine, let's not bother with them.
• I'm inclined to say the same about all base items, subject to below.
• Egos - we could have fixed probability that any base item gets a particular ego. Problem here is that sometimes (unique drops, acquirement) we essentially insist on an ego, which messes up the probabilities.
• Artifacts - we could do like Derakon said, fixed (small) chance to appear, work out the total "get an artifact" chance based on that, then pick which one based on individual probabilities. Same caveats as to egos apply.

End of the day, we're picking items from a probability distribution, and there's no god-given one. I'm not convinced that big change is going to lead to anything better; it will probably just be bad in different ways, and everyone will want to go back to the old method

You may be right. I do feel like my proposed method would be more elegant implementation-wise and easier to make balance changes to, though. I believe fizzix has more experience on this side of things, though, so I'd also love to hear his opinion.

[PowerDiver]

Either you don't understand my proposal, or you're pointing out a flaw in my proposal in a way I don't understand. The way I understand it, you absolutely can accomplish my goals, so long as you're willing to accept that when you try to generate an item, the result may be "nothing is generated".

I'm late for something, so will be quick. Looking at it from this perspective, the "nothing" option will decrease any time you increase any density. Thus the expected number of dropped items will increase. There's no way around this.

You won't be able to accomplish your goal if you have spots with guaranteed single items. Once you throw in a loop: "continue until an item is generated" you break things, because you artificially set the likelihood of "nothing".

None of this matters, of course. Any method is fine, so long as you carefully rebalance after each change. The real problem is that so many of you want to make the sexy flashy change, but are unwilling to do the important gruntwork of rebalancing. That isn't about statistics. It's about getting experts to play and then listening to them. Reverting a bad change shouldn't be anathema, and easily 50% of changes are bad changes. Personally I believe Sturgeon's law applies here, as it does so often everywhere.

[Derakon]

I'm late for something, so will be quick. Looking at it from this perspective, the "nothing" option will decrease any time you increase any density. Thus the expected number of dropped items will increase. There's no way around this.

You won't be able to accomplish your goal if you have spots with guaranteed single items. Once you throw in a loop: "continue until an item is generated" you break things, because you artificially set the likelihood of "nothing".

Okay, yes, this is absolutely true. If we're unwilling to have empty spots in vaults, and unwilling to let unique monsters not drop anything, then we're back in the position of "the frequency of one item affects the frequency of all other items." Thanks for the clarification. Hence why my suggestion was that for situations where currently we say "we guarantee an item here", we should instead say "we will make N attempts to generate an item." Failure is still an option, but its likelihood is reduced by the repeats, without the relative frequencies of the item pool changing in any way.

None of this matters, of course. Any method is fine, so long as you carefully rebalance after each change. The real problem is that so many of you want to make the sexy flashy change, but are unwilling to do the important gruntwork of rebalancing. That isn't about statistics. It's about getting experts to play and then listening to them. Reverting a bad change shouldn't be anathema, and easily 50% of changes are bad changes. Personally I believe Sturgeon's law applies here, as it does so often everywhere.

Absolutely true! These things do need to just be iterated on over and over again until the balance is right. My goal with this proposal was to make it easier to do this. Right now balancing item frequencies is (to make a rather outdated reference) like trying to eliminate a bubble in some wallpaper -- if you press it down in one place, it'll pop up again in another place. The interconnectedness of all things makes it impossible to make a small isolated change. Whereas with my proposal, we absolutely can say e.g. "Amulets of Trickery are too common", make them less common, and not worry that now Amulets of Weaponmastery are now too common.

My hope is that if we make the job easier, then more people will be willing to tackle it.

[Pete Mack]

Eddie--
You are both saying the same thing: to reduce junk, you must reduce drops, not increase good items. I'd do it by just resurrecting the original model, and simply removing a fraction of the junk from the drops--which is what Derakon is suggesting as well.

[Nick]

You may be right. I do feel like my proposed method would be more elegant implementation-wise and easier to make balance changes to, though. I believe fizzix has more experience on this side of things, though, so I'd also love to hear his opinion.

I do see the appeal of your approach, and I guess in fact it could be implemented at a stroke just by summing over all the base item probabilities for each level, and then setting your "1 million" figure as the maximum of those (or maybe something a little bigger). I will think some more.

Not wanting to speak for fizzix, but he was one of the chief proponents of collecting game stats, which essentially try to solve this via posterior rather than prior probabilities - you just generate 100 levels (lots of times), bin up all the items, and see what you got. Then adjust things that look wrong.

[AnonymousHero]

I do see the appeal of your approach, and I guess in fact it could be implemented at a stroke just by summing over all the base item probabilities for each level, and then setting your "1 million" figure as the maximum of those (or maybe something a little bigger). I will think some more.

Not wanting to speak for fizzix, but he was one of the chief proponents of collecting game stats, which essentially try to solve this via posterior rather than prior probabilities - you just generate 100 levels (lots of times), bin up all the items, and see what you got. Then adjust things that look wrong.

I think the two approaches may actually be complementary? Derakon's idea will make the "adjust" bit of fizzix's approach a lot easier, AFAICT.

[Derakon]

I think the two approaches may actually be complementary? Derakon's idea will make the "adjust" bit of fizzix's approach a lot easier, AFAICT.

Indeed. My proposal makes it straightforward to know the percentage of "item attempts" that will be a specific item at a given depth, but it doesn't make any statements about how many actual items that is in practice, since that depends on floor item density, number of monsters, number of vaults, etc. The stats are absolutely still necessary for making informed decisions.