Monte Carlo Level Simulation

Collapse
X
 
  • Time
  • Show
Clear All
new posts
  • fizzix
    Prophet
    • Aug 2009
    • 3025

    Monte Carlo Level Simulation

    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
    Swordsman
    • Jul 2008
    • 308

    #2
    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.

    Comment

    • d_m
      Angband Devteam member
      • Aug 2008
      • 1517

      #3
      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.
      linux->xterm->screen->pmacs

      Comment

      • Derakon
        Prophet
        • Dec 2009
        • 9022

        #4
        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().

        Comment

        • takkaria
          Veteran
          • Apr 2007
          • 1951

          #5
          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.
          takkaria whispers something about options. -more-

          Comment

          • fizzix
            Prophet
            • Aug 2009
            • 3025

            #6
            Originally posted by 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.
            should i interpret this as 'wait a bit before starting on this project?

            Originally posted by 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.
            cool, i'll check it out, and see how expandable it is.

            Comment

            • Magnate
              Angband Devteam member
              • May 2007
              • 5110

              #7
              Originally posted by fizzix
              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.
              "Been away so long I hardly knew the place, gee it's good to be back home" - The Beatles

              Comment

              • myshkin
                Angband Devteam member
                • Apr 2007
                • 334

                #8
                Originally posted by fizzix
                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.

                Comment

                • fizzix
                  Prophet
                  • Aug 2009
                  • 3025

                  #9
                  Originally posted by myshkin
                  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.

                  Comment

                  • myshkin
                    Angband Devteam member
                    • Apr 2007
                    • 334

                    #10
                    Originally posted by fizzix
                    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.

                    Comment

                    • fizzix
                      Prophet
                      • Aug 2009
                      • 3025

                      #11
                      Originally posted by myshkin
                      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.

                      Comment

                      • Sirridan
                        Knight
                        • May 2009
                        • 560

                        #12
                        Originally posted by Magnate
                        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).

                        Comment

                        • fizzix
                          Prophet
                          • Aug 2009
                          • 3025

                          #13
                          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)
                          Attached Files

                          Comment

                          • Estie
                            Veteran
                            • Apr 2008
                            • 2344

                            #14
                            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 ?

                            Comment

                            • fizzix
                              Prophet
                              • Aug 2009
                              • 3025

                              #15
                              Originally posted by 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 ?
                              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.

                              Comment

                              Working...
                              😀
                              😂
                              🥰
                              😘
                              🤢
                              😎
                              😞
                              😡
                              👍
                              👎