Angband.oook.cz
Angband.oook.cz
AboutVariantsLadderForumCompetitionComicScreenshotsFunniesLinks

Go Back   Angband Forums > Angband > Development

Reply
 
Thread Tools Display Modes
Old April 10, 2012, 23:00   #41
Magnate
Angband Devteam member
 
Join Date: May 2007
Location: London, UK
Posts: 5,054
Magnate is on a distinguished road
Send a message via MSN to Magnate Send a message via Yahoo to Magnate
Quote:
Originally Posted by Riff View Post
Just out of interest, I tried looking at the correlations between some of the data. There's a high correlation(-0.849) between Depth and the Win/Lose Ratio, so that at least shows that the borg is generally finding the uniques progressively harder and harder to defeat. The next highest(-0.412) is between Power and the Win/Lose Ratio. So it seems as though Depth is a much better indicator than Power for the borg's survivability.
This is excellent though, as it provides a way to measure the validity of monster power - if that correlation improves, then the power algorithm is getting better (at least as far as this particular test is concerned!).
__________________
"3.4 is much better than 3.1, 3.2 or 3.3. It still is easier than 3.0.9, but it is more convenient to play without being ridiculously easy, so it is my new favorite of the versions." - Timo Pietila
Magnate is offline   Reply With Quote
Old May 28, 2012, 11:21   #42
Riff
Rookie
 
Join Date: Jan 2012
Posts: 23
Riff is on a distinguished road
Hi again! My finals just ended (last exams ever hurrah!), so I'm back to finish the project - deadline's looming in less than a month.

I had a talk with my supervisor and he noticed that I forgot to take into account that most people would try to max out their stats by the time they reach DL 50. So what I did was take an average of the base stats of the 4 character dumps I used (weighted by how close they are to DL 50), and reran the simulations on the existing uniques.

Additionally, I revised the criteria used for evaluating a unique.
1. Win/Lose ratio. Still the same.
2. Average item consumption. Now weighted by the cost of the item.
3. Average HP consumption. This now simply tracks how much HP the player has lost (can go over max HP due to healing and whatnot).
4. Reasonable turns. Not too long, not too short. I took the average number of turns for all uniques tested as a start, which turned out to be 42.

Some interesting correlations:
1. Win/Lose ratio and depth actually worsened slightly from -0.849 to -0.837. However, the change is less than 0.05(5%), so it's not too significant.
2. Item consumption and depth improved from 0.268 to 0.442! Which probably shows that the new weighted measure is a better indicator.
3. HP consumption and depth also shows a high correlation of 0.801.
4. Reasonable turns and depth barely have a correlation of 0.066...but that's no surprise considering it doesn't differentiate between winning or losing too fast.
5. Power also shows improved correlation with win/lose ratio from -0.412 to -0.491. Also has correlation with item consumption at 0.167 and HP consumption at 0.405. The correlations here actually look a bit similar to the earlier depth correlations, though not as strong.

My new proposed evaluation function takes these factors into account (closeness being a measure of W/L approaching 0.5):
1. Correlations with depth as sign of appropriateness/viability
Closeness = HP > Item (roughly)

2. HP consumption and reasonable turns require...a special kind of normalization(ie. have to predict the biggest range we might encounter in simulations). As such, we might not want to rely on them too much.

3. Interestingness measures based on previous theories and discussions here
Closeness is definitely important. It's a form of outcome uncertainty.
Item consumption as well, since a battle that requires you to actually use up your resources is more interesting than one where you can simply whack the enemy to death.
Reasonable turns has been shown in previous research to be a good indicator of interestingness.

So:
Closeness > Item > HP = Turns
4 : 3 : 1.5 : 1.5

Sorting the uniques by this evaluation formula, we get this top 10 list of interesting fights for a CL 40 Half-Troll Warrior:
  1. Atlas, the Titan
  2. Khamul, the Black Easterling
  3. The Lernaean Hydra
  4. The Phoenix
  5. Ar-Pharazon the Golden
  6. Omarax, the Eye Tyrant
  7. Saruman of Many Colours
  8. Dwar, Dog Lord of Waw
  9. Gorlim, Betrayer of Barahir
  10. The Balrog of Moria

It's quite a huge change from the previous experiments, largely because of the maxed out stats I believe! If we take a W/L of 0.451 to 0.550 to be close, then we get:
  • Easy and interesting: Atlas, the Titan; Ar-Pharazon the Golden; Dwar, Dog Lord of Waw; Gorlim, Betrayer of Barahir
  • Close and interesting: Khamul, the Black Easterling
  • Hard and interesting: The Lernaean Hydra; The Phoenix; Omarax, the Eye Tyrant; Saruman of Many Colours; The Balrog of Moria

Data here.

Next, I'll be implementing the algorithm for generating uniques. Hopefully I'll have something for you guys to play with by sometime next week so I can get some feedback. Cheers!
Riff is offline   Reply With Quote
Old May 28, 2012, 17:59   #43
Magnate
Angband Devteam member
 
Join Date: May 2007
Location: London, UK
Posts: 5,054
Magnate is on a distinguished road
Send a message via MSN to Magnate Send a message via Yahoo to Magnate
Thanks for the update. I'm surprised to see the two ringwraiths in the list - they're notably less worrying to most players than any of the other entries. Forgive me if I've forgotten something from an earlier post, but is native depth relevant here? ISTR it is, and it would point to an interesting idea that the two ringwraiths are quite tough for their depth, if not in absolute terms.

I look forward to seeing the generator ...
__________________
"3.4 is much better than 3.1, 3.2 or 3.3. It still is easier than 3.0.9, but it is more convenient to play without being ridiculously easy, so it is my new favorite of the versions." - Timo Pietila
Magnate is offline   Reply With Quote
Old May 28, 2012, 18:46   #44
Riff
Rookie
 
Join Date: Jan 2012
Posts: 23
Riff is on a distinguished road
Well, the idea is that this is all based on the composite player I created (which is an amalgamation of 4 characters from the ladder whose max depth ranges between 46-54), i.e. my approximation of a character at DL 50.

As a reminder, here's the details of the CL 40 Half-Troll Warrior I'm using as a model.

Quote:
Full stats (after applying bonuses etc.)
STR: 18/182
INT: 18/25
WIS: 18/20
DEX: 18/85
CON: 18/***
CHR: 15

Lance of the Eorlingas
Short Bow of Amrod
Ring of Constitution <+4>
Ring of Speed <+7>
Jewel 'Evenstar'
Phial of Galadriel
Augmented Chain Mail of Caspanion
Elven Cloak of the Magi [6, +8]
Small Metal Shield of Thorin
Hard Leather Cap of Thranduil
Set of Leather Gloves 'Cammithrim'
Pair of Leather Sandals of Speed [1,+7] <+8>

69 Arrows
26 Arrows of Venom

41 Potions of Cure Critical Wounds
5 Potions of Healing
Potion of Restore Life Levels
2 Potions of Speed
4 Potions of Resist Poison
14 Scrolls of Phase Door
9 Scrolls of Satisfy Hunger
Rod of Trap Location
Rod of Detection
4 Rods of Curing
Rod of Disarming
So essentially, I'm not looking for absolute measures(which is probably very difficult to ascertain...) but in terms of some player model.
Riff is offline   Reply With Quote
Old June 7, 2012, 16:39   #45
Riff
Rookie
 
Join Date: Jan 2012
Posts: 23
Riff is on a distinguished road


This is just a purely random enemy. The full generator will be using a simulation-based genetic algorithm to find 'interesting' enemies for the given situation. It's nearly done, but I likely won't have any results till next week.

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.
Riff is offline   Reply With Quote
Old June 7, 2012, 17:22   #46
Derakon
Prophet
 
Derakon's Avatar
 
Join Date: Dec 2009
Posts: 8,378
Derakon is on a distinguished road
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)
Derakon is offline   Reply With Quote
Old June 7, 2012, 18:47   #47
Magnate
Angband Devteam member
 
Join Date: May 2007
Location: London, UK
Posts: 5,054
Magnate is on a distinguished road
Send a message via MSN to Magnate Send a message via Yahoo to Magnate
Quote:
Originally Posted by Riff View Post
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?
__________________
"3.4 is much better than 3.1, 3.2 or 3.3. It still is easier than 3.0.9, but it is more convenient to play without being ridiculously easy, so it is my new favorite of the versions." - Timo Pietila
Magnate is offline   Reply With Quote
Old June 7, 2012, 22:33   #48
Riff
Rookie
 
Join Date: Jan 2012
Posts: 23
Riff is on a distinguished road
Quote:
Originally Posted by Derakon View Post
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.

Quote:
Originally Posted by Magnate View Post
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.

Quote:
Originally Posted by Magnate View Post
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.

Quote:
Originally Posted by Magnate View Post
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).

Last edited by Riff; June 7, 2012 at 22:44.
Riff is offline   Reply With Quote
Old June 8, 2012, 10:56   #49
Magnate
Angband Devteam member
 
Join Date: May 2007
Location: London, UK
Posts: 5,054
Magnate is on a distinguished road
Send a message via MSN to Magnate Send a message via Yahoo to Magnate
Quote:
Originally Posted by Riff View Post
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!
__________________
"3.4 is much better than 3.1, 3.2 or 3.3. It still is easier than 3.0.9, but it is more convenient to play without being ridiculously easy, so it is my new favorite of the versions." - Timo Pietila
Magnate is offline   Reply With Quote
Old June 8, 2012, 11:54   #50
Riff
Rookie
 
Join Date: Jan 2012
Posts: 23
Riff is on a distinguished road
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 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
[O] Levels are generated with no stairs at all Therem Harth Variants 3 June 28, 2010 23:08
Problems with Unique monsters Kulana Vanilla 18 December 31, 2009 07:39
The unique Qualthug dhegler Vanilla 11 October 20, 2009 18:18
unique drops working? CunningGabe Vanilla 6 February 8, 2008 17:00
Designing some new unique dragons Skyknight Vanilla 1 December 13, 2007 05:25


All times are GMT +1. The time now is 12:53.


Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2018, vBulletin Solutions Inc.