Procedurally Generated Unique Monsters

[Derakon]

Brutal!

Have you considered the risk/reward ratios for uniques as part of what makes them interesting? I'm more willing to go after an enemy if it has a good drop and gives lots of experience, even if it's a more challenging fight. Whereas I'd have very little motive to go after Guntur here, especially since she doesn't move.

To my mind, it seems like it ought to be relatively easy to decide on a drop quality and experience payout based on the monster's calculated power level. However I might well be missing subtleties.

(Also, there's a grammar bug in that monster memory -- "remains" should be "remain" since she's killed multiple ancestors. That of course is not your problem)

[Magnate]

Meanwhile, my code is on github: https://github.com/AriffWambeck/angband
I've been developing on Windows, but I might get around to compiling it on Linux later on.

Excellent, thanks for sharing. Did you start your commits on 28th May, or are there any before that? (There's been a lot of work on 3.4 since you forked on 10th Jan, but that doesn't necessarily matter if we can merge your commits without too much fuss.)

Can you explain why you've used the bitarray library? What does it do for you?

Are you using the existing monster power algorithm (see mon-power.c), or did you write your own way of evaluating monster power so that you can match a random monster to a given character's power level?

[Riff]

To my mind, it seems like it ought to be relatively easy to decide on a drop quality and experience payout based on the monster's calculated power level.

Yeah, that shouldn't be too difficult I think. Though with my method currently, the power level calculated is relative to a CL 40 Half-Troll Warrior rather than purely absolute... I'll see if I can come up with something later.

Did you start your commits on 28th May, or are there any before that?

That's my earliest commit. I started bits and pieces of coding in...February I think? But that was when I thought of coding my own borg, so most of the real work started in April...and I neglected version control at that time unfortunately.

Can you explain why you've used the bitarray library? What does it do for you?

I'm using it as a representation for a monster, i.e. the properties that can be randomised - for the genetic algorithm I'll be using, makes it much easier to manipulate. Currently, each monster is represented by a 250 bit array.

Are you using the existing monster power algorithm (see mon-power.c), or did you write your own way of evaluating monster power so that you can match a random monster to a given character's power level?

That's the idea of using simulation-based genetic algorithms and the proposed evaluation function I mentioned earlier: find the best matching monster to a given character. Of course right now I'm only doing it for a CL 40 Half-Troll Warrior, but ideally should do it for all possible race-class combinations and at different levels to see what kind of 'best-matching' monsters you get.

This does make the process take ages though (it took 3 hours for me to do simulations for 97 of the existing uniques...so if you imagine also 3 hours for a single generation of the genetic algorithm and maybe at least 10 generations for it to find a good match...).

But by doing so, it'll hopefully uncover some correlations between what flags and spells are ideal for characters at that level, i.e. contributing to a quicker means of matching monster to depth (similar to how mon-power is calculated).

I'm really short on time though (report's due in less than 2 weeks), so I doubt I'll be doing more than just the single character model I've presented - but it's definitely something to look at in the future!

Edit: On that note, my version of the game is pretty much dedicated to running simulations, so there's a few hacks to the game and the borg even. I doubt you'd want to merge this with the main game (maybe a special dev version for tinkering with simulations though).

[Magnate]

That's the idea of using simulation-based genetic algorithms and the proposed evaluation function I mentioned earlier: find the best matching monster to a given character. Of course right now I'm only doing it for a CL 40 Half-Troll Warrior, but ideally should do it for all possible race-class combinations and at different levels to see what kind of 'best-matching' monsters you get.

This does make the process take ages though (it took 3 hours for me to do simulations for 97 of the existing uniques...so if you imagine also 3 hours for a single generation of the genetic algorithm and maybe at least 10 generations for it to find a good match...).

But by doing so, it'll hopefully uncover some correlations between what flags and spells are ideal for characters at that level, i.e. contributing to a quicker means of matching monster to depth (similar to how mon-power is calculated).

I'm really short on time though (report's due in less than 2 weeks), so I doubt I'll be doing more than just the single character model I've presented - but it's definitely something to look at in the future!

Edit: On that note, my version of the game is pretty much dedicated to running simulations, so there's a few hacks to the game and the borg even. I doubt you'd want to merge this with the main game (maybe a special dev version for tinkering with simulations though).

Yes, I see that - I was just wondering whether any of your code would be helpful for starting us down the path of generating random monsters, instead of rewriting it from scratch. We have our own functions for bitflag manipulation (for monster race flags and spell flags) so might be able to adapt your algorithm. But you're probably right that the best we'll get is some qualitative pointers for improving the existing mon-power code.

I'm curious as to why it's so slow - it doesn't seem like extra iterations would improve the accuracy. I guess there are just a lot of combinations of 250 bits!

[Riff]

I think the simulation harness might be a handy tool! You could probably do away with the bit array representations for actual monster generation in-game (they just make it much easier to manipulate for what I'm doing).

Well, think of this process as a search problem - we're trying to find a combination of monster properties such that it maximises a defined function for what's a best match. 250 bits gives us 2^250 such possible combinations so....yeah, that's a lot!

Genetic algorithms are a popular method for this kind of problem and have shown pretty good results after letting it run for several generations. So I'm hoping it'll be able to do the same here.

After this project is over (and a short break from all of this lol), I'll see if I can tidy up some of my code. Truth be told, this is probably the most work I've ever done in C - more of a Python/Java/C# guy...heck, I'd prefer C++ even!

[Riff]

Well. Today I learn that Angband has sounds.

Something I didn't mention before was the fact that the borg still crashes the game during my simulations occasionally (usually a segmentation fault in one of the borg files). Which is why I always have it constantly log stuff so that I don't lose any data, and so that I can pick up where I left off.

Today after running the simulations for a while for generated uniques, I started hearing weird noises coming from my headphones. I thought I had something on YouTube left running. But no. They were coming from Angband.

Somehow the sounds got turned on.

I'm hoping this is just some weird bug in the borg code. From what I've observed, the borg's behaviour doesn't seem to deteriorate as time goes on. But in any case, with a week left to wrap this project up, I'm terribly short on time to figure this out for sure.

Here's 2 examples of high-scoring enemies I've found so far - they score almost as high as Atlas. The borg's got about 50:50 chance against them.

N:617:Estarim
T:xorn
C:V
I:120:700:20:194:10
W:50:1:0:0
B:SPIT:HALLU:11d4
B:STING:LOSE_STR:21d3
B:KICK:LOSE_CON:29d12
B:TOUCH:PARALYZE:7d14
F:UNIQUE | QUESTOR
F:DROP_2 | DROP_3 | DROP_4 | MULTIPLY
F:PASS_WALL | ATTR_FLICKER | OPEN_DOOR | UNAWARE
F:IM_ELEC | KILL_ITEM | KILL_WALL | NEVER_BLOW
F:REGENERATE | RAND_25 | DROP_60 | ANIMAL
F:DEMON | IM_FIRE | BASH_DOOR | POWERFUL
F:HURT_LIGHT | HURT_FIRE | IM_WATER | SMART
F:ATTR_MULTI | DROP_20 | RES_PLAS | NO_FEAR
F:ESCORT | DROP_GREAT | HURT_COLD | DRAGON
F:FRIEND | ONLY_ITEM | RAND_50 | FRIENDS
F:ORC
S:1_IN_8
S:ARROW_1 | ARROW_2 | ARROW_3 | ARROW_4
S:BA_ELEC | BA_FIRE | BA_NETH | BA_WATE
S:BOULDER | BO_COLD | BO_ELEC | BO_FIRE
S:BO_ICEE | BO_MANA | BO_PLAS | BO_POIS
S:BO_WATE | BRAIN_SMASH | BR_ACID | BR_CHAO
S:BR_DARK | BR_ELEC | BR_FIRE | BR_GRAV
S:BR_NETH | BR_TIME | CAUSE_1 | CAUSE_2
S:CAUSE_3 | HEAL | HOLD | MIND_BLAST
S:MISSILE | SCARE | SHRIEK | SLOW
S:S_AINU | S_HI_UNDEAD | S_HYDRA | S_MONSTER
S:S_SPIDER | S_UNDEAD | TELE_TO | TPORT

N:617:Ruth
T:orc
C:V
I:120:5900:20:248:10
W:50:1:0:0
B:HIT:EAT_ITEM:17d8
B:ENGULF:LOSE_ALL:12d3
B:SPIT:PARALYZE:32d4
B:TOUCH:EXP_80:1d8
F:UNIQUE | QUESTOR
F:IM_POIS | NO_SLEEP | RES_NEXUS | HAS_LIGHT
F:NO_STUN | CHAR_CLEAR | MULTIPLY | IM_ELEC
F:KILL_ITEM | KILL_WALL | NEVER_BLOW | ATTR_CLEAR
F:MOVE_BODY | STUPID | RAND_25 | DROP_60
F:INVISIBLE | TROLL | UNDEAD | GIANT
F:DEMON | ESCORTS | POWERFUL | HURT_LIGHT
F:HURT_FIRE | RES_DISE | EMPTY_MIND | ATTR_MULTI
F:NO_FEAR | HURT_COLD | TAKE_ITEM | ONLY_ITEM
F:FRIENDS
S:1_IN_16
S:ARROW_3 | BA_ACID | BA_COLD | BA_ELEC
S:BA_FIRE | BA_MANA | BA_NETH | BA_WATE
S:BLINK | BOULDER | BO_ACID | BO_COLD
S:BO_ELEC | BO_FIRE | BO_ICEE | BO_PLAS
S:BO_POIS | BO_WATE | BR_ACID | BR_COLD
S:BR_DISE | BR_INER | BR_LIGHT | BR_MANA
S:BR_NETH | BR_NEXU | BR_PLAS | BR_POIS
S:BR_SHAR | BR_TIME | CAUSE_4 | DARKNESS
S:HASTE | HOLD | MIND_BLAST | MISSILE
S:SLOW | S_AINU | S_ANIMAL | S_DEMON
S:S_HI_DEMON | S_HYDRA | S_MONSTER | S_SPIDER
S:S_UNIQUE | TELE_AWAY | TELE_TO | TPORT

[Derakon]

I believe that NEVER_BLOW means that the monster will never try to make melee attacks. You might consider removing NEVER_BLOW and NEVER_MOVE from the allowed flags for monsters, since only one unique monster currently has them (the unique Q).

The sounds will really slow your game down if you leave them on, since IIRC they pause the game while they play.

Good luck!

[myshkin]

(Also, there's a grammar bug in that monster memory -- "remains" should be "remain" since she's killed multiple ancestors. That of course is not your problem)

Good catch. Added to #1424. (Why did I take ownership of that ticket?)