Monte Carlo Level Simulation

[fizzix]

I've been poking around a lot in generate.c and simultaneously thinking about how to implement a monte carlo level simulation.


There are two options to simulation, one is to generate a level as it exists, and then go through manually removing the monsters and logging the treasure. The second simulation winds up being a change of how the level generation is done, this would involve a complete rewrite of generate.c

The advantage of killing all monsters on the level manually is that changes in generate.c will not effect the simulation. The main advantage to rewrite level generation is that the simulation can be done faster, and it's easier to log some specific items.

I'm leaning towards the manually killing monsters approach, with one change to generate.c, new floor designations PIT_FLOOR and NEST_FLOOR, so I can properly log monsters and treasure in these areas. If it turns out this approach is too slow, I'll look at the rewriting generate.c approach.

The main idea will be to go through each square. If you hit a treasure, record it and log it. If you hit a monster, record what treasure it would drop if you were to kill it, log it and the treasure, and remove it from the level.

The big question is what to record. I'm looking at something like this in average value per level:

total monsters
OoD monsters: in vaults: in pits/nests:
total unique monsters: in vaults:
At or OoD unique monsters: in vaults:

Gold:
from monsters
from ground (non vaults)
from vaults
from veins

Items (weapons and armor)
Total:
From ground: in vaults:
From monsters: in vaults: in pits/nests:
From uniques: in vaults:

(repeat for excellent, superb, endgame quality, artifacts, and artifacts with min levels near or above current depth.)

consumables: (i need some input here, what should I log...)

I'm thinking of putting all totals into longs (can I use floats?) and dividing by the sim number after it's done. Longs should be large enough for everything but money, and I can get around that by dividing by 10 or 100 or something.

thoughts/suggestions?

[RogerN]

It's an interesting an idea - I would love to see the results, and I'm sure others would also.

How would you use the results, though? Very few players actually kill every monster or loot every item on the floor, so I'm not sure how relevant this data would be to balance. Given that players may explore only 20 to 30% of a level, and consciously choose to avoid certain types of monsters, you wouldn't be getting a clear picture of a given player's experience.

I suppose it might provide information that's useful for balancing ironman-style games.

Oh - I think it's very important to calculate the standard deviations as well as average treasure values. That can give you a better clue regarding player frustration w/rt loot shortage vs. loot surplus on different playthroughs.

[d_m]

I think myshkin has implemented something like this (and is finishing it up before pushing it into trunk). I won't say more because I'm not totally clear on the details, but I really look forward to using it to profile level creation and item generation.

[Derakon]

I'm sure the data will be useful even if players only interact with 30% of the dungeon.

The way I'd do this would be to add a debug-mode command that would forcibly restart dungeon generation after it finishes (as when it has to restart e.g. due to having too many monsters in the dungeon) for the specified number of times. This would involve a fairly simple addition to generate.c's main loop (the "while (error) {cave_gen(); create level feeling; check for error conditions;}" bit).

As for actually examining the quality of the level, see if you can co-opt display_itemlist() and display_monlist().

[takkaria]

Note that wiz-stats.c in V already does some monte carlo experimentation already and I used it to change monster drops and objects found on the floor.

[fizzix]

I think myshkin has implemented something like this (and is finishing it up before pushing it into trunk). I won't say more because I'm not totally clear on the details, but I really look forward to using it to profile level creation and item generation.

should i interpret this as 'wait a bit before starting on this project?

Note that wiz-stats.c in V already does some monte carlo experimentation already and I used it to change monster drops and objects found on the floor.

cool, i'll check it out, and see how expandable it is.

[Magnate]

should i interpret this as 'wait a bit before starting on this project?

There are a few denizens of #angband-dev who don't post on oook, and it would be good to optimise the use of people's time. I'm still a bit sad that PyAngband went ahead and developed a new text file syntax, when someone already did that ... but now we have github, these links should be easier to make.

So by all means crack on with it if you're dead keen - but if you have other stuff to do as well, you might find that what myshkin pushes to github does most of what you wanted.

That said, it's impossible to guess when it will appear. Soon, I hope.

[myshkin]

should i interpret this as 'wait a bit before starting on this project?

Yes, I'm hoping to have something on github in the next day or two. (There's one main bug to fix.) My approach is a combination of wiz-stats.c and elly's main-test.c, and uses your second option. (It does not open chests, but it does kill all monsters.) The gist is

* Initialize the game
* Dump to file any necessary data from a_info and perhaps m_info
* For each DL 1-99:
* Generate the level
* Dump to file all of the monsters generated
* Kill all the monsters
* Dump to file all of the objects generated, including origin depth and source

I will also supply a sample (extensible) perl script to run this test N times and take various statistics on the output. The combination of the changes and the perl script should be easily portable to older versions of V (and probably variants as well). My primary goal is to measure how randart and standart distribution (how many, source of drops, etc.) have changed over time, but I'll also take requests for other measurements. Magnate asked for number and average number of levels OOD for OOD artifacts. I'll have something for speed rings, at least max pval. All of the data from fizzix's first post will be available in the raw dumps, except that there's no code to differentiate pits and nests from regular rooms.

[fizzix]

I will also supply a sample (extensible) perl script to run this test N times and take various statistics on the output. The combination of the changes and the perl script should be easily portable to older versions of V (and probably variants as well). My primary goal is to measure how randart and standart distribution (how many, source of drops, etc.) have changed over time, but I'll also take requests for other measurements. Magnate asked for number and average number of levels OOD for OOD artifacts. I'll have something for speed rings, at least max pval. All of the data from fizzix's first post will be available in the raw dumps, except that there's no code to differentiate pits and nests from regular rooms.

Cool. After you get it online, I'll look into adding differentiation from pits/nests. I think these are necessary as I get a very large amount of consumables and artifacts from pits.

[myshkin]

Cool. After you get it online, I'll look into adding differentiation from pits/nests. I think these are necessary as I get a very large amount of consumables and artifacts from pits.

The tricky thing is that the cave_info array has a flag for vaults (CAVE_ICKY), but not for actual room type. I didn't want to mess with this data structure to avoid any portability headaches, but it shouldn't be too hard to record room type somewhere.

[fizzix]

The tricky thing is that the cave_info array has a flag for vaults (CAVE_ICKY), but not for actual room type. I didn't want to mess with this data structure to avoid any portability headaches, but it shouldn't be too hard to record room type somewhere.

I agree, the easiest way to do that is to modify the structure. This would not affect gameplay in any way but would greatly help diagnosis, so it might be easy to get into V.

If you don't modify it, it gets harder. There is a 'crowded' flag that dictates whether a pit or nest exists somewhere on the level. Finding it on the level might be possible if a bit difficult.

[Sirridan]

There are a few denizens of #angband-dev who don't post on oook, and it would be good to optimise the use of people's time. I'm still a bit sad that PyAngband went ahead and developed a new text file syntax, when someone already did that ... but now we have github, these links should be easier to make.

Can you link me the new style syntax? I'm using what I have now as a stop-gap, I find it a big pain in the tochas to write, but it works for now. (Plus no parser to write since it's just basically python code).

[fizzix]

I got a preliminary monte carlo version up. So far all it does is scan the floor and count the gold, artifacts and ego_items. Outputs go to stats.log in the user file. It is activated by the debug command "_"

I'll add more functionality with time.

(outputs from standart and randart sims are attached, I used 1000 simulations on each level)

[Estie]

Not sure if it matters for the purpose, but I assume deeper level artifacts dont take into account the possibility that a given artifact might have been found before and thus be unavailable ?

[fizzix]

Not sure if it matters for the purpose, but I assume deeper level artifacts dont take into account the possibility that a given artifact might have been found before and thus be unavailable ?

It definitely does matter, but rather than worry about handling that the plan is to add more granularity into the artifact printout. This is more of a proof of principle than anything else. A test to see how fast the sim runs, and whether I am capable of coding up the full thing. Looks like it's fast enough for sure, and I might be ok on the second as well. (I feel like I really suck at coding in C...)

Here's the path I'll take, probably later today or tonight:
First, I'll separate special artifacts from artifact equipment. Special artifacts have a different generation path, and are more likely to suffer from the 'not found before' effect

Then, I'll separate other artifacts into aritfacts that are 25 levels above depth and shallower. Artifacts that are between 25 levels above and 1 level below. And artifacts that are deeper than 1 level below.

I could also add granularity between weapons and armor, but I'm not sure this is needed.

After that, I have to get drops from monsters, but this is a slightly more difficult problem.