|
|
dimis
Responsible
Supreme Hero
Digitally signed by FoG
|
posted August 11, 2006 02:40 PM |
|
Edited by dimis at 14:46, 11 Aug 2006.
|
Quote: He only looked at individual skills and calculated the odds of the skill appearing individually. The problem I have with the model is that with 28 skills, you would expect SOME of them to be above expected and some below.
This is exactly what the final column is trying to capture. It is obvious that some of them are going to be below the expected values and some above. However, one can estimate how likely it is to "deviate" from expected value for each skill. For this purpose I used the bell program I've uploaded on page 4 of this thread and give instructions for the use of it so that you can play with it at home with these or your own tests.
@angelito: I made some corrections on the pdf-file (last edit July 9)contrary to my belief of not editing bonus-posts. But I simply had some wrong values on the initial file. For instance: on page 7 I wrote that only 112 different sequences occurred while the correct value was 128 - this was just a typo by me, all calculations were made based on correct 128. Similarly on page 10 I "missed" some square-roots which resulted in not valid formulas. Furthermore I did some minor editing on fonts/typos/spelling (and I want to convert eventually "understanded" to "understood" on page 6 ...) so that I can be as accurate as possible. I hope there is no problem that I made those edits angelito and you can see that at-least for some of them there was a necessity.
@Ecoris: Another way of by-passing the problem with Offense/Crag-Hack on your tests is to always pick exp. Offense when reaching level 2. This will allow you to use the db-handler tool which I can easily extend it and allow you to generate the ouptut you wish (.txt file, .xls file, .tex and so on ...).
____________
The empty set
|
|
Ecoris
Promising
Supreme Hero
|
posted August 15, 2006 11:55 AM |
bonus applied. |
Edited by angelito at 19:16, 12 Oct 2006.
|
digging deeper -
the very nature of the algorithm
Background
The claim that changing HCTRAITS.txt would affect the skill trees of savegames inspired me to look further into this matter. If the "weighted die" model is correct one should still suspect that the pseudo-random values generated would be the same, and thus changing the weights in HCTRAITS.txt would explain the new skill tree. However if we only change the weights sligthly for a few skills should we not except that the first few offers might not change?
While considering this, the following idea of how the values of HCTRAITS.txt are treated came to me: The game generates a random integer R between 1 and 112. In the table presented in HCTRAITS.txt the skill that corresponds to this value is "looked up". For example for Barbarians: Pathfinding is mentioned first and has a value of 8, thus if R is one of the numbers 1,2,3,4,5,6,7 or 8 pathfinding will be offered. The next skill in the table is archery with a value of 7 so it would be reasonable to believe that archery has the next 7 values, which would be 9,10,11,12,13,14 and 15. Next is logistics (also 7), thus the values 16-22 would be assigned to logistics and so on.
Whenever an offer is determined the next random number is generated and looked up in the table.
That was my theory.
The setup
My test scenario was like this: Crag Hack, no starting skills, a learning stone next to him. He visits it and advances to level 2, offers are written down. That's all.
Testing
(you may skip this section)
First of all I deleted the current version of H3bitmap.lod (which had been changed by other tests) and copied the original one back into the Data folder. I started the test-scenario and saved right away (test111.GM1). The I advanced to level 2 and I was offered (Estates,Leadership). Then I used replace.bat to import the original HCTRAITS.txt into H3bitmap.lod (exiting before this is necessary). Reloaded test111.GM1; same offers again. Thus you have to change the values to affect the skill tree, simply overwriting them (and thereby creating a new version of H3bitmap.lod) is not enough. I just wanted to check this before starting.
From this point on I did several tests with various odds values. Each time I edited HCTRAITS.txt reimported it with replace.bat started H3 and loaded test111.GM1
The figure below shows the results. The rows next to "Test #X" contains the odds values that were used. The rows just beneath those ones are cumulative rows, the sum of the value above and all values to the left of that one. This just makes it easier to "look up" the random values as described.
As mentioned I was offered estates and leadership with the original odds. The corresponding values are higlighted in the table. One can see that estates has an odds value of 2, which are the two numbers 57 and 58. Leadership has a value of 5 and has all the values 34-38.
As a result I figured that the first random value rolled had to be either 57 or 58 if my theory was correct. In Test #1 the only change in the odds values are that necromancy has been given the value 57 instead of estates.
This time I was offered necromancy and pathfinding (highlighted, both at basic of course). We have now identified the first value as 57, but the second one is no longer between 34 and 38.
Why? The explanation is quite simple: Estates was selected as the first skill so it can't be offered as the right skill as well. In the first test it had an odds value of 2 so the next random number (the one that determines the right skill offer) has to be an integer from 1;110. This value is then found in the table, but estates would be ignored (i.e all skills to the right of estates would have their corresponding values "reduced" by 2). In test #1, however, estates had an odds value of 1 and the next random integer would therefore have to be in the range 1;111.
This suggests that the random values could be generated like this:
1. The next random integer R is computed. R is likely a very big number.
2. The sum S of odds values for all skills that may be offered is computed. (e.g. in test #1 necromancy could not be offered as the right skill offer, thus S = 111 in this case, but S = 110 in the test with the original odds values bacause estates was the first skill offer and had an odds value off 2).
3. S is subtracted from R until it equals of of the numbers 1,2,...,S I'll denote it X. Like this we generate a random integer X in the required range.
4. This value (X) is looked up among the skills that may be offered. (E.g. estates/necromancy was ignored when determining the right skill offer).
This would explain the behaviour. But the question is: What could the original value of R possibly be, and does such a value even exist?
In test #3 it is determined that the second value of X was 7 when X had to be selected in the range 1;111. The right skill offer was navigation in this test.
In test #5 it is likewise determined that the second value of X was 34 when X had to be selected in the range 1;110. This meant that Archery was the right offer in this test, and it also explains why leadership was offered in the original test and why mysticism was offered in test #4.
Test #6 just shows this again.
Test #7 and test #8 show that if estates is given an odds value of 3 (i.e. X has to be selected among the values 1,2,...,109 this time) X will be 66 (actually 63 bacause estates is skipped) for the right offer.
If the model proposed so far is correct it should be possible to determine the possible values that R originally could have had for the right skill offer. It must satisfy the following equation:
7 + 111*A =
34 + 110*B =
63 + 109*C = R
A,B,C have to be positive integers. One can show that R = 15214, A = 137, B = 138 and C = 139 is a solution. The next one has R = 13146104. 15214 requires at least 16 bits while 13146104 requires at least 21.
Test #9 and test #10 is just a continuation of the above. This time the odds value of estates is set to 4 and X is found to 94 (it appears as 98 in the table but we have to subtract 4 because we skip estates when we look up the skill that corresponds to X).
With this pair we can add another equation to the ones above:
94 + 108*D = R
The first solution is still valid with D = 140, but now the next possible value of R increases to 23971234, which requires at least 25 bits. Therefore we may assume that rhe true value of R is 15214.
Test #9 is interesting. The sum of the odds was no longer 112 but 56. This was allowed by the game, so the odds values don't have to sum up to 112. Notice that when the first offer is determined the result is 1. In all other tests with S = 112 it was 57 but now we have to generate a number in the range 1;56 and because 56 is the half of 112 we end up at 1. Then we have to generate a number in the range 1;55 for the right offer and we get either 34 or 35. Notice that because 55 is the half of 110 we reach the same value as in test #5. This is obvious since
15214 - 138*110 = 34
15214 - 276*55 = 34
This test verifies that the values of X are indeed computed by subtracting S from R until a value in the range 1;S is reached.
The model
To summarize we now know that the skill-selection model likely works like this:
Every hero has its own pseudo random number generator and a seed. This seed is generated when one starts a scenario and it is also stored in savegames. This means that the same sequence of random numbers is produced no matter what, and therefore the skill tree is fixed (or predefined).
When the hero reaches the next level he's offered two new skills A (left) and B (right). A is an upgrade of an existing skill if possible (otherwise it'll be a new skill), while B is a new skill if possible (otherwise it'll be an upgrade).
The game determines A first. Let us assume that we've not reached a level where an EG-exception applies. A is determined like this:
1. The hero's random generator is told to produce the next random number R (possibly a 16 bit integer).
2. The sum S of the odds values of all skills that may be offered is computed.
3. Then S is subtracted from R until a value X in the range 1;S is reached. (One can also put it like this: The remainder of the integer division S/R is computed as a value in the range 1;S).
4. The game "looks up" X in the table in HCTRAITS.txt from left to right ignoring (skipping) skills that can't be offered.
After that B is determined in the same manner.
I'm confident that these are the basics in the algorithm.
There are, however, still many details that need to be attended:
Further investigation
After that I've done some further tests in the same manner. They have discovered the following additional facts:
1. If the hero has a skill at basic or advanced level with an odds value of 0 it is treated as 1 when an upgrade offer is to be selected. Otherwise it is (of course) treated as 0.
2. If only one skill can be upgraded and that skill has an odds value of 0 or 1, no random number is generated to determine this offer. The skill is offered automatically. But if that skill has an odds value of 2 or greater the next random number will be used even though the skill is the only possible offer (odd beaviour!). This is a notible difference: In the latter case a random number in the sequence is actually "skipped" compared to the first case.
3. Odds values are treated as zero if they're 128 or greater. (Perhaps they can be set high enough to become valid again, i.e. signed 8-bit integers: -128;127).
4. Primary skill advancement works independently of the secondary skill system; what you select does not influence what primary skill you improve later on. "Skipping" random values does not matter either. It is as if it has its own random number generator.
To do
Knowing how the odds values from HCTRAITS.txt are treated and how the selection algorithm works may give us a new way if testing. If we determine the values of R at some level we can predict what the offers should be. If they're not what we expect we may have discovered further exceptions to the known rules.
The best-case scenario would be if we are able to copy the pseudo-random number generator that the game uses. Then we could implement a skill-predictor.
Any good guesses on what programming language H3 is written in (C?). In another test in the same test-scenario the first random number (the one used to determine A) was 7408 while the second one was 17001. This is a very short list of numbers but if anyone could find/construct a random number generator that produces these two values (they may need to be reduced to another range) it would be very interesting.
I have not yet tested how the magic school and wisdom exceptions are treated. I guess the list of valid offers is just reduced when the selection is made, but I don't know.
Edit by angelito
Even though I think most of the users won't understand your research 100%, coz it is very mathematical related, I found it a great effort to the library. Again I have to apologize for the long time till the reward was given.
|
|
dimis
Responsible
Supreme Hero
Digitally signed by FoG
|
posted September 05, 2006 02:12 PM |
|
Edited by dimis at 15:38, 06 Sep 2006.
|
Back from Holiday
I really enjoyed reading both of your long posts Ecoris.
First one Searching for skill groups v. 2 and then digging deeper - the very nature of the algorithm.
Regarding the first one I am convinced that you made an excellent job and right now I am eager to see the overall results from xarfax's thread on hacking mr. hack (where unfortunately I haven't been able to report my 2 month old data presented earlier in a simple excel file yet! - sorry Olaf ).
As for the second one, it is always nice that our intuition/ideas are verified.
Thanks again for your participation and inspiring posts in this thread.
- dimis -
____________
The empty set
|
|
Ecoris
Promising
Supreme Hero
|
posted September 05, 2006 02:46 PM |
|
|
Good to see that you're back dimis. Things have been very idle during the last few weeks and I've also had less time now that I've started at the university again.
Do you have any idea whether it would be possible to "copy" the random number generator that H3 uses? It is my impression that you know more about programming than I do. Even though it would be a breakthrough I feel that it would be like searching for a needle in a haystack.
|
|
dimis
Responsible
Supreme Hero
Digitally signed by FoG
|
posted September 06, 2006 03:27 PM |
|
Edited by angelito at 18:54, 11 Nov 2009.
|
Crag-Hack on ANSA - Data in Excel format
Here are 2 files in excel format for the 200 tests that were made on page 4 of this thread.
Hack.xls is the file I submitted on SKILLING TREE: Hack the Hack thread.
distinct_seq_dimis.xls is an excel file that lists all 128 different permutations that occurred.
- dimis -
Regarding ... Quote: Do you have any idea whether it would be possible to "copy" the random number generator that H3 uses? It is my impression that you know more about programming than I do. Even though it would be a breakthrough I feel that it would be like searching for a needle in a haystack.
... I really don't know if it is possible. Most likely the program uses the builtin generator (of the language), so, we can find which .dll contains it. After that we must check for the version of the dll and then start googling (or searching M$DN) for info on the algorithm used for rand() system calls. Eventually this will allow us to set up a replicate of the generator, and then we'll start playing with various seeds to check which one(s) result in the same short sequence we have obtained. But as you've said, it's like searching for a needle in the haystack, and I have little time as well at the moment.
However, as the problem matures as time goes by, we might come up with new ideas and directions for countering the problem. After all, we might be because we don't know everything yet, however, we know enough to build good approximation programs for various policies. Time will tell I guess ...
____________
The empty set
|
|
dimis
Responsible
Supreme Hero
Digitally signed by FoG
|
posted November 24, 2006 02:38 PM |
|
|
Disassembling
Good news I suppose so that we can generate our own copy of the random number generator. What we need is IDAFREE, more particularly idafree.zip.
This tool disassembles code in assembly and moreover tries to find more characteristics based on the inferred language of the executable you load. As a result, if you load Heroes3.exe it will find immediately that program is written in VC. Moreover, if you start digging around when this whole process finishes, you can find some pushes on Secskills.def (I assume this file is somewhere inside a *.lod file).
Unfortunately, I have not that much time right now, but I try to do much in the very near future. However, any comments by anyone digging/playing around with this are more than welcome!
Till then, have fun!
- dimis -
____________
The empty set
|
|
Ecoris
Promising
Supreme Hero
|
posted November 24, 2006 04:51 PM |
|
|
I'm certainly looking forward to using that tool. Maybe I'll do so already tomorrow. I was beginning to think that we would have to give up on finding the random number generator and instead find the first 20 numbers it produces (which is just as good), however that is an extremely tedious process (just the two first values I discovered took me about an hour, doing this for every skill tree (200-300 different) for every hero class would be practically impossible. I guess that all classes have the same possible seeds, and thus the same sequences of random numbers. It would still be more than 4000 numbers... that's why some of you may have noticed that I asked the WoG'ers if they knew how to create new secondary skills, which would make this approach possible).
But nevermind. I hope this tool will make further progress possible.
|
|
dimis
Responsible
Supreme Hero
Digitally signed by FoG
|
posted November 24, 2006 06:05 PM |
|
Edited by dimis at 18:06, 24 Nov 2006.
|
More on reverse engineering ...
Possibly another useful tool is SoftICE. With this tool we can view much more raw data; however, as I learnt today it allows you to put brakepoints at specific instructions on the dis-assembled code as well as on memory. The most logical scenario is that weights are stored on a 16x28 (or 18x28) table, so we can search for the exact sequence for a specific class of heroes. Next step (easy) find the starting block of the matrix and then use brakpoints to catch the function(s) that read that portion of memory. One of them must be the generator ...
That's the easy part I guess.
The main process starts right after that, when we'll end up explaining various assembly commands. But I don't know if it would be necessary to understand them in completeness. We might just find it extremely convenient for our purposes to replicate generator's behaviour and test it on various seeds. My prediction (hope?) is that we will not notice large variance on the outcomes.
But anyway, its too early to say anything. My best wishes on your searches guys!
____________
The empty set
|
|
Ecoris
Promising
Supreme Hero
|
posted November 25, 2006 11:31 AM |
|
|
I can't find SoftIce and I do not know how to use IDAFree. If load heroes3.exe it seems to recognize a bit, but then it says something like "cannot run in MS-DOS" and the rest of it is just hexadecimal numbers.
|
|
dimis
Responsible
Supreme Hero
Digitally signed by FoG
|
posted November 25, 2006 12:30 PM |
|
Edited by dimis at 13:07, 25 Nov 2006.
|
Tutorials and accounts
Ok,
Regarding SoftICE: I 'll search around and let you know if I find a good link. However, there is one pc in my office which has SoftICE installed. So, in a way, you can IM me to create you an account on that machine and subsequently use it from your home in that pc.
Secondly,
I think that some tutorials are needed. I never tried to get burnt so far with reverse engineering, so I am in the search of good tutorials too. Some preliminary googling returned: one and two.
two is a tutorial in greek, and seems very well written. I 'll contact the guy and ask him if he has an english version of what he writes and I'll give you necessary links.
In a nutshell, this whole process is not going to be easy, because as I can see we are all n00bs in this stuff. So, idafree and softICE, can not be used in parallel without a good tutorial/howto.
- dimis -
P.S.1: Just let me know if you want an account in my machine via HCM.
P.S.2: SoftICE is nothing more than an advanced debugger. So, in a sense, in absense of SoftICE locally on your machine, you can always use GDB which is well documented. There are many resources around relating GDB. As an example you can check my thread Intro to programming where I use DJGPP. DJGPP comes with gdb for debugging which I also include in the zip file I redistribute. More info on these can be found on my second post regarding installation of DJGPP on your pc. More on that, you can find a directory (inside zipped file) DJGPP\gnudocs\gdb-6.11 which contains documentation in .dvi, .ps, .pdf and .html format. Finally, using help inside gdb can be very good at this.
P.S.3: One more hint: Always use your wrist-watch because SoftICE operates in kernel-mode which will make windows clock NOT operate; i.e. when ever you pause on commands and study code, you'll end up pausing eveything in the OS - clock included! So, you might be looking code for an hour or so, and windows clock might indicate that only 15 minutes have passed!
____________
The empty set
|
|
dimis
Responsible
Supreme Hero
Digitally signed by FoG
|
posted February 05, 2007 02:05 AM |
|
|
Combinations of skills on ANSA
After a very long time I decided I had to finish with the theoretical predictions on ANSA problem when we want to check combinations of skills. Moreover, this also answers a question by Binabik in the past, when he wanted to compute combinations of skills for specific heroes under ANSA. For information on the extended-ANSA please refer here. I 've added a paragraph named Extending Computations on the post where the ANSA problem is countered. In fact, as you will realize, the power of our computing-abilities covers a superset of combinatoric questions and not just mere conjunctions.
Questions on the usage or the definitions of the new exacutable are strongly encouraged! Please post below. It is almost certain that I forgot to clarify something.
Regards,
- dimis -
____________
The empty set
|
|
Ecoris
Promising
Supreme Hero
|
posted February 05, 2007 11:24 AM |
|
|
Nice work, dimis!
I have always felt that ANSA probabilities were a little odd though. The selection policy may be objective but also irrational.
The probability that you receive both skill X and skill Y is very small under the ANSA policy since only 6 or 7 skills have to be selected.
I know the probabilities are only ordinal, but even for comparison between different heroes I am unsure how significant the fact that Crag has a 17.4% chance to get air magic and tactics while orrin only has a 10.7% chance to get the same skills really is.
The odds values (or weights if you prefer) for those skills are: Air Magic: 3 for both, Tactics: 8 for barbarians, 7 for knights. So perhaps the example only illustrates how much one more initially unused slot is worth. But is that really significant? I mean, 17.4 compared to 10.7 is a lot, but the selection policy is quite restrictive.
Also, knowing that there are only around 200 different skill trees could also have some impact practically speaking since this means that the calculations are overly ideal. But perhaps this is not significant since the 200 +-50 or so skill trees are representative for the purely random 'rolls'.
I hope I make sense .
Sometimes I wonder whether we should just send an email to bioware and ask what random number generator they used in H3...
... but that is kind of cheating.
|
|
maretti
Responsible
Supreme Hero
|
posted February 05, 2007 12:06 PM |
|
|
I find it pretty obvious that Crag has a somewhat bigger chance to get air than Orrin even though they both have 3 in air. Since magic is offered at certain times, the chance of getting air when magic is offered is whats important. Crag has a 3/8 chance to get air when its offered whereas Orrin has a 3/10 chance. Combined with Crags exstra skill and higher chance of getting tactics I find the %s u mention pretty natural.
____________
Crag rules, Orrin and Ivor suck
|
|
Ecoris
Promising
Supreme Hero
|
posted February 05, 2007 09:26 PM |
|
|
Yes. Good point. But it's not as much the percentage values as what they really tell you; if you follow the ANSA policy the magic school exception only applies once and unless you get a magic school offered naturally you only have one chance of getting air magic. Under a more realistic selection policy I suspect that the percentage values are relatively closer.
____________
|
|
dimis
Responsible
Supreme Hero
Digitally signed by FoG
|
posted February 05, 2007 10:37 PM |
|
Edited by dimis at 19:39, 07 Feb 2007.
|
I believe that we should compare more comparable heroes under this perspective, because both points are very good.
First of all, I think it is more natural to compare the effect of "extra-level" between heroes of the same class. Hence, the same question for the rest of the barbarians (excluding Tyraxor who starts with Tactics; all Knights start with 2 skills, so no accurate comparison for them) yields values in the range 14.42% - 14.72% compared to Crag's 17.37%. So, yes, maretti's arguments are very good justifications on the reasons of Crag's better chances. (Ofcourse, as it is also said, compared to Orrin, we "witness" the extra effect of more magic schools available on the magic-exception-level which in turn results in lowering the respective chances for Orrin.)
On the other hand, your point Ecoris on the sequences is very accurate and reminds us that with our present understanding on Skill-generation we cannot stretch the questions on ANSA, since it is almost certain that not all skill combinations can occur. Hence, when we pose questions on combinations of many skills (7-8), we should - in most of the cases - treat the value that appears on screen as the expected probability simply as an upper bound of the empirical probability that comes into practice (since it is most likely that it can be 0 as well if the sequence is never generated). For example, if we ask the probability of Crag receiving All-3-Magic-Schools, Wisdom, tactics, logistics, offense, and armorer under ANSA we end up with 0.0026% but it may also be the case that no-one will ever experience such a sequence under ANSA! But as you say, this most likely will have little impact on our "overall" prediction ability. Yesterday I read on a (non-technical; more like history-of-Riemann's-Zeta-Function-for-the-public) book that there is an operand that can tell you how close two distinct distributions are; it is called (if I translate correct) correlation-something. I 'll look more for that, since this seems to be a better tool for comparing our predicted distribution with the resulting distribution on skills.
Finally, as for the gap that the extra level generates on probabilities, I don't want to speculate. As you point out, it is true that as the number of available slots increases (and the available skills increase proportionally), its effect is diminished; however, we have a specific problem that we want to solve with a specific amount of slots. What I am trying to say, (because I might also be saying nonsense ) is that for starters I merely accept the values. If we solve more interesting problems all these ideas will be good starting points for more interesting conversations. Right now we need to move on and reach a good point on generated skills under ANSA in Xarfax's thread and continue with other policies.
EDIT [Feb 7]:
I tend to forget extra heroes such as Sir Mullich (who starts with a single skill). In his case, we have that 13.15% is the chance of getting both Air and Tactics compared to 10.66% - 11.01% for the rest of the knights (apart from Tyris who starts with tactics).
The respective percentages - on the effect of the extra slot - are:
barbarians: 2.65% - 2.95%
knights : 2.14% - 2.49%
____________
The empty set
|
|
dimis
Responsible
Supreme Hero
Digitally signed by FoG
|
posted July 09, 2007 12:53 AM |
|
|
Start your engines!
Are you ready to rock ?
____________
The empty set
|
|
dimis
Responsible
Supreme Hero
Digitally signed by FoG
|
posted July 09, 2007 02:03 AM |
bonus applied. |
Edited by angelito at 18:55, 11 Nov 2009.
|
Monte Carlo Methods
Ok,
I am proud to announce that the model (as we realize it at the moment; and most likely is the true model behind skill advancing) has been fully implemented in C++ and the project is able to continue for the evaluation of more difficult policies on skill selection.
The methods used for computing the probabilities of the various policies are Monte Carlo methods. In a very simple language, this means that we are simulating the skill advancing problem for a large amount of iterations. In theory, with an infinite amount of iterations, the probabilities should converge to their true (accurate) theoretical values. However, we don't have to wait for an infinite amount of time. We can simply iterate for a large number of times and take a closer look at the results. In other words, we simulate full skill advancing X times (where X is a large enough number) and observe the results. Hence, if a hero obtains Y times Earth Magic in X runs, then the empirical probability is Y / X. I 'll place more info about Monte Carlo methods on my second post in the first page of the thread.
At the moment I run some preliminary tests with ANSA and the results are very encouraging; i.e. the replies are very close to the theoretical (accurate) probabilities computed through brute force.
Moreover, at the moment I am checking out results for the Always-Left policy and the results are very interesting there.
To cover your appetite I briefly give you the following for Crag-Hack:
On ANSA with 1,000,000 episodes (simulations) we have:
CRAG_HACK
~~~~~~~~~
AIR MAGIC : 44.8057 %.
ARCHERY : 35.5529 %.
ARMORER : 31.3932 %.
ARTILLERY : 39.7716 %.
BALLISTICS : 39.6577 %.
DIPLOMACY : 5.9373 %.
EAGLE EYE : 11.5584 %.
EARTH MAGIC : 44.8893 %.
ESTATES : 11.5043 %.
FIRE MAGIC : 31.0331 %.
FIRST AID : 5.8801 %.
INTELLIGENCE: 5.8825 %.
LEADERSHIP : 26.8257 %.
LEARNING : 21.9902 %.
LOGISTICS : 35.668 %.
LUCK : 16.8667 %.
MYSTICISM : 16.8857 %.
NAVIGATION : 11.5511 %.
NECROMANCY : 0 %.
OFFENSE : 100 %.
PATHFINDING : 39.6538 %.
RESISTANCE : 31.393 %.
SCHOLAR : 5.903 %.
SCOUTING : 39.6501 %.
SORCERY : 5.9509 %.
TACTICS : 39.7957 %.
WATER MAGIC : 0 %.
WISDOM : 100 %.
Duration : 20.9 seconds.
Meaning 47,000-48,000 episodes per second. I should also state that I didn't write code with foremost concern the efficiency, rather than being cautious for accuracy. In any case, this will be augmented, as time goes by. We have more important stuff to deal with.
And to give you an idea on the Always-Left policy, again for Crag-Hack after 1,000,000 episodes we have:
CRAG_HACK
~~~~~~~~~
AIR MAGIC : 67.2858 %.
ARCHERY : 30.8887 %.
ARMORER : 27.0544 %.
ARTILLERY : 34.4656 %.
BALLISTICS : 34.5274 %.
DIPLOMACY : 5.0105 %.
EAGLE EYE : 9.7797 %.
EARTH MAGIC : 67.188 %.
ESTATES : 9.7928 %.
FIRE MAGIC : 55.8524 %.
FIRST AID : 4.9542 %.
INTELLIGENCE: 5.0001 %.
LEADERSHIP : 22.995 %.
LEARNING : 18.7615 %.
LOGISTICS : 30.8954 %.
LUCK : 14.4354 %.
MYSTICISM : 14.3979 %.
NAVIGATION : 9.8459 %.
NECROMANCY : 0 %.
OFFENSE : 100 %.
PATHFINDING : 34.4137 %.
RESISTANCE : 27.0915 %.
SCHOLAR : 5.0235 %.
SCOUTING : 34.5146 %.
SORCERY : 4.9891 %.
TACTICS : 34.5046 %.
WATER MAGIC : 0 %.
WISDOM : 96.3323 %.
Duration : 26.32 seconds.
So, there are matters that need further consideration.
a) First of all, what other policies are we going to implement and test? Propose!
b) Second, there are obvious ways to fix the numbers computed by Monte Carlo, since we have some information that is currently not used. For instance, skills that are neither WISDOM nor a MAGIC School and have the same weight ought to have the same probability under the above policies. For instance, check the values on ANSA above for Crag-Hack in the cases of Diplomacy, First Aid, Intelligence, Scholar and Sorcery. We can replace them all by their average. In contrast check the the accurate values for Crag-Hack here.
Other useful observations?
c) Third, we should allow the user to ask more delicate questions; meaning, we not only care whether someone acquires Earth. We also care about the timing! Hence it would be useful to draw distributions for all skills at the different levels of expertize (basic, advanced, expert) and compare different heroes. For example, assume you have two heroes with pretty similar probabilities for acquiring Earth. It is very useful to know that the first one receives Earth much earlier than the second one. And this can be seen with plotting and / or tables. Anything else that we want to observe?
d) Now depending on the performance boost on simulation and the results from the rate of convergence (which I have not yet looked at) there are some matters regarding the user-interface. Perhaps I should form a tiny database so that one can load previously computed results. But it's very early to think about that.
Now, feel free to post your ideas and what you would like to be computed / enumerated / etc through simulation or anything else!
Regards
P.S.: For starters, I hope we can easily implement at least one policy per day!
____________
The empty set
|
|
angelito
Honorable
Undefeatable Hero
proud father of a princess
|
posted July 09, 2007 09:38 AM |
|
|
Very nice work u did here dimis, as usual! +QP applied of course.
What I find kinda interesting is the "relatively" low percentage for logistics (around 35%). It only takes 9th place, even behind pathfinding. So it isn't just an imagination I always have problems getting log with Crag or Gurni....
____________
Better judged by 12 than carried by 6.
|
|
dimis
Responsible
Supreme Hero
Digitally signed by FoG
|
posted July 09, 2007 10:24 AM |
|
|
Thanks for the +QP angelito!
However, my post above is incomplete since I haven't uploaded yet neither source code nor executable which you can run on your computers.
I 'll do them asap because the interesting results are still ahead of us!
____________
The empty set
|
|
dimis
Responsible
Supreme Hero
Digitally signed by FoG
|
posted July 09, 2007 07:10 PM |
|
Edited by angelito at 10:31, 12 Nov 2009.
|
Monte Carlo: Always Left
The results obtained when following an Always Left policy can be found in the following files:Raw Data.This file can be used with conjuction of this file to transform the given data in an excel file. Note that you should rename the file containing the raw data to ansa_probs.txt. Rename accordingly the xls file in the output.
OpenOffice Spreadsheet
Image
The results were generated using internals_mc version 1.1. Ten million episodes were used in order to infer the requested probabilities.
Command line call was as follows:Quote: internals_mc class name al 10000000 deprecated
Soon I'll place some info for bounds on error as well as confidence intervals.
Have fun!
P.S.: Normally I would post results in Heroes Stats and Skills Chances thread. However, not everyone seems to agree with the model. For this purpose, I 've placed only links above similarly to what I did when evaluated ANSA policy earlier in this thread. At that time no-one had a problem with the model and for this reason I had posted at the other thread as well.
____________
The empty set
|
|
|
|