Angband.oook.cz
Angband.oook.cz
AboutVariantsLadderForumCompetitionComicScreenshotsFunniesLinks

Go Back   Angband Forums > Angband > Development

Reply
 
Thread Tools Display Modes
Old December 13, 2016, 21:38   #1
Derakon
Prophet
 
Derakon's Avatar
 
Join Date: Dec 2009
Posts: 7,878
Derakon is on a distinguished road
Competition-agnostic item allocation

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.
Derakon is offline   Reply With Quote
Old December 14, 2016, 02:04   #2
PowerDiver
Prophet
 
Join Date: Mar 2008
Posts: 2,712
PowerDiver is on a distinguished road
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.
PowerDiver is offline   Reply With Quote
Old December 14, 2016, 02:20   #3
Derakon
Prophet
 
Derakon's Avatar
 
Join Date: Dec 2009
Posts: 7,878
Derakon is on a distinguished road
Quote:
Originally Posted by PowerDiver View Post
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?
Derakon is offline   Reply With Quote
Old December 14, 2016, 03:20   #4
Nomad
Knight
 
Nomad's Avatar
 
Join Date: Sep 2010
Location: England
Posts: 958
Nomad is on a distinguished road
Quote:
Originally Posted by Derakon View Post
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.)
Nomad is offline   Reply With Quote
Old December 14, 2016, 03:25   #5
Carnivean
Swordsman
 
Join Date: Sep 2013
Posts: 476
Carnivean is on a distinguished road
Given we now have a powerful squelching tool to overcome the Too Much Junk problem, why not just put the junk back in?
Carnivean is offline   Reply With Quote
Old December 14, 2016, 08:01   #6
PowerDiver
Prophet
 
Join Date: Mar 2008
Posts: 2,712
PowerDiver is on a distinguished road
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.
PowerDiver is offline   Reply With Quote
Old December 14, 2016, 10:46   #7
Nick
Vanilla maintainer
 
Nick's Avatar
 
Join Date: Apr 2007
Location: Canberra, Australia
Age: 52
Posts: 6,518
Donated: $60
Nick is on a distinguished road
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
__________________
One Ring to rule them all, One Ring to find them,
One Ring to bring them all and in the darkness bind them.
Nick is offline   Reply With Quote
Old December 14, 2016, 14:24   #8
Derakon
Prophet
 
Derakon's Avatar
 
Join Date: Dec 2009
Posts: 7,878
Derakon is on a distinguished road
Quote:
Originally Posted by PowerDiver View Post
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]

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.
Quote:
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":

Code:
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.

Code:
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 is offline   Reply With Quote
Old December 14, 2016, 14:27   #9
Derakon
Prophet
 
Derakon's Avatar
 
Join Date: Dec 2009
Posts: 7,878
Derakon is on a distinguished road
Quote:
Originally Posted by Nick View Post
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.

Quote:
  • 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.
Derakon is offline   Reply With Quote
Old December 14, 2016, 16:51   #10
PowerDiver
Prophet
 
Join Date: Mar 2008
Posts: 2,712
PowerDiver is on a distinguished road
Quote:
Originally Posted by Derakon View Post
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.
PowerDiver is offline   Reply With Quote
Reply


Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
 
Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump

Similar Threads
Thread Thread Starter Forum Replies Last Post
item suggestion quarague Vanilla 6 July 15, 2013 06:30
New item changed name, what gives? Zambaku Vanilla 13 May 22, 2013 19:45
Item design: I like it. seebs Vanilla 3 May 17, 2013 22:07
[item's] are OP! (possible item spoilers) Elsairon Vanilla 3 June 5, 2012 10:04
Item names Kiyoshi Aman Vanilla 3 May 5, 2007 23:01


All times are GMT +1. The time now is 21:09.


Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2017, vBulletin Solutions, Inc.