|
|
dimis
Responsible
Supreme Hero
Digitally signed by FoG
|
posted August 02, 2006 05:05 PM |
|
Edited by angelito at 18:52, 11 Nov 2009.
|
Empirical Skill Database / Homepage
 Version 1.0 [August 2, 2006]
Source Code.....: Here.
Win32 Executable:
Here.
Ok, I think there are many things I have to say, so I 'll edit this post probably more than 1 days per version release ( ). So, this is the homepage, of a simple tool that might help us attacking the problem of skill advancing. For starters, the only supported hero is Crag-Hack. In order to run the tool (from now on DB-Handler) and update / retrieve data from database one must use his terminal.
Suggested method:
1) Create a separate folder in your filesystem and place inside the executable you retrieved above.
2) Move to the directory you just created and give the following command:
Quote:
HackCrag help
This will provide you with information for various characteristics of the DB-Handler.
3) Try ALL of them at will. Familiarize yourselves with the program. Note also that a file named HackCrag.dat is generated when you initialize a new DataBase.
4) You are all smart guys for the rest, so I think I can stop here for today. For all your comments and ideas on what to implement on subsequent versions, post your suggestions below.
ONE FINAL NOTE: Please do NOT exhaust yourselves by generating data with ACTUAL EXPERIMENTS. We have to discuss many details, for the experimantation process, since on a subsequent level we will apply some kind of filtering on episodes generated. I hope this is clear enough.
Thank you in advance,
- dimis -
____________
The empty set
|
|
dimis
Responsible
Supreme Hero
Digitally signed by FoG
|
posted August 03, 2006 03:56 PM |
|
Edited by dimis at 17:45, 03 Aug 2006.
|
Birthday problem, Balls in Bins and relation to skill-advancing problems.
I will try to give my explanation on the sequences re-appearence matter.
Fact 1: First of all, sequences combinations are finite under any realistic model of game-play.
Fact 2: Whether these sequences are generated "on-demand" while someone is leveling up his hero or are pre-computed or even computed at the beginning of Heroes game-execution and then choosing which one is going to be implemented in someone's game still does not affect the chances for various skills.
Ok, let's see a similar problem. It is called Balls in Bins and you can find much info about it on the internet. The case is as follows:
Quote:
Suppose we have N bins and we randomly throw balls into them.
After that part, many questions can arise (variations of the problem). One of them, that is addressed in the link above is:
Quote:
What is the expected number (average case) of balls required to be thrown until exactly m bins contain at least two balls?
This problem is solved. Let's see the general case (note that some variable names change meaning):
Quote:
Given N bins, let E(m,k) denote the expected number of bins containing exactly m balls after k have been thrown.
And the solution is:
E(m,k) = N * Combination(k,m) * (1-1/N)^(k-m) * (1/N)^m,
where Combination (k,m) = k!/[(k-m)! * m!]
But the problem in our case is that we DON'T KNOW how many sequences can occur under our policy. HOWEVER, through testing we can approximate E(m,k) in the above situation and reverse the above equation. Here is why:
The process of throwing k balls can be practically identical to generating k episodes.
Distinct sequences are mapped to distinct bins.
m reflects the number of times a sequence has appeared in our episodic task (testing procedure: generating actual data from human-made level-ups)
E(m,k) reflects the obvious metaphor with the above mappings.
In other words, we can treat N as the unknown and try to reverse our search.  Let's see an example:
My tests on an earlier page of this thread (Crag-Hack on ANSA) have the following properties:
Quote:
Sequences that appeared exactly 1 times: 076
Sequences that appeared exactly 2 times: 033
Sequences that appeared exactly 3 times: 018
Sequences that appeared exactly 4 times: 001
Ok, let's see what the above predicts based on our experiments:
Open gnuplot (which you should have downloaded from the link in previous page on plotting tools) and give:
Quote:
set grid;
set xrange [1:1000];
plot x*(200*199)/2*(1 - 1/x)**198*(1/x)**2, 33;
where in the last command I implement the equation that solves Balls in Bins problem, by substituting k=200, m=2, N=x (unknown). Of course I check the second line on the above values with this setting. Try other values on your pc (for k and m variables) and play a bit with this. The result is:
which shows that this outcome is expected to occur on average if total number of different sequences is around 130 or around 330. But ofcourse, we can not get the expected scenario with a single test! So, either we need more tests to smooth out the "noise" of the experiment or/and "fold" the whole sequence and check averages on smaller (with respect to total number of episodes) tasks. In other words, for example, split the procedure in groups of 40-50 episodes and observe the above intersections based on averages.  However, I never found some time to do this, so I can not give you any data about it. I am just happy that we can have some predictions for the whole process.
____________
The empty set
|
|
Ecoris
Promising
Supreme Hero
|
posted August 04, 2006 02:35 PM |
|
Edited by Ecoris at 16:14, 06 Aug 2006.
|
Searching for skill groups v. 2
Since it's taken me a while to realize the importance of my results (if they hold) the first version of this post was perhaps a bit hasty and left out many details. This post is therefore an attempt to make things 100% clear to everyone.
The Model
In his "Crag-Hack on ANSA" post dimis described the so called "model so far" which include the following:
I. The secondary skill offers are determined by rolling a weighted die. Each skill has a value associated with it. These values are stored in the file HCTRAITS.txt in H3bitmap.lod file in the Data directory. The values are described there as "Probability of gaining a secondary skill (out of 112)".
II. The magic-school and wisdom exception.
However, testing results indicate that this model is wrong or at least insufficient. Naturally one asks oneself: Why shouldn't there be more skill groups that may cause exceptions, like combat skills, adventure map skills, etc. since we know that two of them exist?
In this post I will do my best to explain my tests that aimed to uncover such skill groups.
Terms
First I will need to introduce some terms and definitions:
Exception-group, EG (I felt that "skill-group" would be a confusing name): A group (or set) of one or more secondary skills, of which one must be offered (not necessarily accepted) either as an upgrade or as a new skill at least every Nth level (level 1 counts).
This may cause an exception to the general rules of level improvement.
I will say that N is the "grade" of the skill group, thus the magic schools constitute an EG of grade 4, and wisdom is an EG of grade 6.
E.g.: If a hero reaches level 5 and hasn't been offered wisdom yet an exception to the general rules of skill-offering will occur when he reaches level 6. This means that wisdom is automatically selected for one of the slots (depending on whethet it's an upgrade or not). The other skill offer will be generated as usual.
If the hero is offered wisdom before the level at which an exception would occur (i.e. the "normal" way) the "counter" is reset and he'll have to wait another N levels for the exception to oocur.
If the two known exceptions coincide we know that only one will occur and that wisdom has the higher priority. The magic school exception will then occur at the next level.
The Goal
The goal is to uncover other EGs if they exist, and prove that no other exists. Or just: To find all EGs.
The Mehtod
How shall one do this? One needs to level up to all levels and check whether some skill from some group of skills is always offered, but it is necessary that none of these skills have been offered before... That is the tricky part; how should one control that when we don't know what we're looking for? And there is another thing that could cause trouble: If there was a coincidence between one of the known EGs and one of the unknown EGs the known one could have a higher priority and thus prevent the exception of the unknown group of occuring (at least until the next level-up). This could make new EGs difficult to spot.
To deal with these complications included editing HCTRAITS.txt and reimporting it into H3bitmap.lod. What I did was the following:
First I created my test scenario and edited Crag's starting skills. I gave him these five skills: Wisdom + the 4 magic schools, all at basic level. Then I added a pandora's box with enough XP to bring him to level 12, i.e. 11 level-ups. Like that I select the left offer each time and end up with the 5 mentioned skills at expert level when I reach level 11, and then I'm offered two new skills. Notice that every time I'm offered an upgrade of one of the 5 starting skills in the left slot plus a new skill in the right slot. This prevents the known exceptions of occuring because they'll be offered too frequently. At each level up I can check what the new offer is and see if there is anything unusual. (At level 12 I can check what the the left offer is; if some exception applied it would occupy the left slot. Notice that such an exception could not be one of the known ones).
The second part of my idea is that I set the skills' odds in HCTRAITS like this:
1. Necromancy = 90
2. The five known skills (wisdom + 4 magic schools) = 0 (their values don't matter but I set them to 0 to be able to set necomancy's value as high as possible).
3. Remaining 22 skills = 1 for a total of 112.
Now Necromancy is very likely to show up as the right offer. If some EG exist it will have to show up at some level and running this test several times should uncover such an EG. For example if I'm offered some combat skill at level 5 every time it would indicate that a new EG existed. Why? Because it would be extremely unlikely that this happened every time due to chance alone. But I only need ONE counter-example to prove that such an EG doesn't exist: If I'm offered Necromancy as the right offer at levels 2, 3, 4 and 5 such an EG as described simply can't exist.
Validating the method
Just to be sure that this model actually works I did another test first. The idea is the same as above, but I stripped Crag of Wisdom and set its value to 1. Then I did the level-up a couple of times and I was offered wisdom every time at level 6. After that I stripped him of the 4 magic schools and gave him mysticism + wisdom as starting skills instead. I set the odds for the magic schools to 1, did the level up again. I was offered a magic school every time at level 4.
These simple tests show that the method actually works; it (re)discovered the known EGs  .
The actual test
At that point I was prepared to do the test itself. The odds and the setup were as described under the section "The Method" above. During each test if some other skill than Necromancy was offered in the right (which is not unlikely: 22/112) I wrote down the level and the skill. I did this several times until this happened: Necromany was offered as the new skill every time until level 11, and then in the left slot at level 12.
After that I "swapped" necromancy and pathfinding, and after a while the same thing happened: Pathfinding was offered every time until level 11, and then in the left slot at level 12.
After that I added Solmyr to my test scenario and edited him in the same manner as Crag. I was able to produce the exact same results with necromancy and pathfinding.
Conclusions
While this does not proof that there are more EG than the known two, the results imply that an unknown EG must meet one of the following criteria:
1. It has grade > 12
or
2. It contains both necromancy and pathfinding.
or
3. It contains at least one of the 5 starting skills.
or
4. The EG does not apply for Wizards and Barbarians
These are very strong restrictions, and the criteria 1., 2. and 4. seem absurd to me. Concerning 3.: No one says that a skill can't be part of more than one EG but I doubt it. You are free to test this.
Other results
During my tests I verified the following:
1. Exceptions are handled as the first thing, e.g. at level 4 when to new skills have to be offered and the magic exception applies the left offer will always be the magic school.
2. When two new skills have to be offered (no exceptions apply) the first one selected by the "roll of the weighted die" will be the left offer.
3. Exceptions can't give you a skill that has an odds value of 0.
|
|
dimis
Responsible
Supreme Hero
Digitally signed by FoG
|
posted August 04, 2006 07:20 PM |
|
Edited by dimis at 19:21, 04 Aug 2006.
|
Indeed very interesting tests and results Ecoris. Too bad I can't follow you everywhere so that I know exactly what you mean on every sentence, since up to now I've not found some time to play with skill-weights (and frankly I don't think I will until the early of September anymore). However, this is a very good and creative work. Well done!
Note: I might not participate in the conversation for the following 2-3 weeks, for various reasons. I just note it down here so that you know I am not ignoring anyone.
____________
The empty set
|
|
Ecoris
Promising
Supreme Hero
|
|
posted August 05, 2006 10:42 AM |
|
|
|
Well, I guess you're right that some things are a bit unclear. I might need to re-write some of it tomorrow, but I'll leave it for now.
|
|
Binabik
Responsible
Legendary Hero
|
|
posted August 05, 2006 11:32 AM |
|
|
Does this mean we can stop testing now? Someone should have thought of that test long ago, it's almost bullet proof. Actually after looking at my test results last night, I came up with almost the same thing, but it wasn't bullet proof.
So now what are we going to do?
____________
|
|
Ecoris
Promising
Supreme Hero
|
|
posted August 05, 2006 05:09 PM |
|
|
Well, at least I'm waiting until dimis (or someone else) finds out how many different skill trees there are (whatever that may tell us, no one can map them all) or until the number of ANSA results of Xarfax's thread is high enough to proof or reject the "model so far" with the wieghted die described by dimis.
I'm still wondering what the correct test statistic for doing this is.
Therefore I'll request the following: Tests that indicate that "the model so far" is insufficient or even wrong.
But I agree that currently I feel a little disappointed, like "is that really it?" and because I don't know what to test for now.
We testers may need to make a brainstorm for possible new projects .
But as I said there may be more left.
|
|
Xarfax111
Bad-mannered
Supreme Hero
The last hero standing
|
|
posted August 06, 2006 11:11 AM |
|
|
Mmmmh....do you think you did come to the correct conclusions by your testing?
I dont think so.
____________
|
|
Binabik
Responsible
Legendary Hero
|
|
posted August 06, 2006 01:54 PM |
|
Edited by Binabik at 13:57, 06 Aug 2006.
|
Why do I always post late at night when I'm too tired to think straight?
After thinking about it more, I don't think Ecoris' tests are as bulletproof as I did in my last post. But I still think it is a very strong argument that there are no guarenteed skill groups at a specific level.
Quote:
Is there some level at which Necromancy is never offered? That would indicate the existance of another skill group. But the tests I did show that no such level exist; during a few tests necromancy had appeared at all levels.
I completely agree with this logic, but it's not 100% bulletproof. But I came to much the same conclusion looking at my own test results using a different test method.
Xarfax, did you get the excel file I sent? Look at the sheet titled "Sort by probability" and look at the last 3 columns on the right. I'll post those three here for others to see. The number on the left is from the odds table. Reading down a column is a single test.
1 Diplo-----
1 1st Aid---
1 Intel-----
1 Scholar---
1 Sorcery---
2 Eagle-----
2 Estate----
2 Nav-------
3 Luck------
3 Myst------
4 Learn-----
5 Leader----
6 Arm-------0---7---8
6 Resist-----5---0---7
7 Archery---4---0---0
7 Log-------0---0---3
8 Art--------8---0---0
8 Bal--------0---2---0
8 Path------7---5---2
8 Scout-----0---3---0
8 Tactics----2---8---0
2 Wisdom---6---6---6
2 Fire-------0---0---5
3 Earth------3---4---0
3 Air--------0---0---4
The 12 least likely skills didn't appear in these three tests. And there are three more tests which didn't contain the first 11 skills. So what's this tell us? It doesn't tell us there aren't any skill groups. But it does tell us if any of the first 12 skills are part of a group, the group must ALSO contain one of the following combinations:
1) Pathfinding =<7
2) Armorer and resistance =<7
3) Armorer and archery =<8
4) Armorer and artillry =<8
5) Armorer and tactics =<7
6) Resist and ballistics =<7
7) Resist and scouting =<7
8) Resist and tactics =<8
9) Log and tactics =<8
10) Resist and log and ballistics =<5
11) Resist and log and scout =<5
Unless I missed one, these are the only posibilities for skill groups at level 8 or earlier. It's way too late to do it tonight, but I'm willing to bet I can look at the other tests result I have and eliminate all 11 of the above possibilites.
Gee, I'm really tired. I hope this makes sense.
____________
|
|
Ecoris
Promising
Supreme Hero
|
|
posted August 06, 2006 04:06 PM |
|
Edited by Ecoris at 16:12, 06 Aug 2006.
|
Quote:
Mmmmh....do you think you did come to the correct conclusions by your testing?
I dont think so.
That you're suspicious is fair, since there was a missing link in my logic, as Binabik also noticed:
Quote:
Quote:
Is there some level at which Necromancy is never offered? That would indicate the existance of another skill group. But the tests I did show that no such level exist; during a few tests necromancy had appeared at all levels.
I completely agree with this logic, but it's not 100% bulletproof. But I came to much the same conclusion looking at my own test results using a different test method.
Consider this example: Some skill group exists with grade 5, but it is offered at level 3 due to chance, next time it will be offered is at level 8 (if not before).
Therefore the question and answer: "Is there some level at which Necromancy is never offered?" That would indicate the existance of another skill group." is wrong because necromancy could appear at all levels like in the mentioned example.
It should have been "Can it happen that I'm offered Necromancy every single time in the right slot? That would indicate that no other skill groups exist."
I've rewritten the post with the results above, and I did a few new episodes. The answer to the question above is "Yes." but please refer to the post above for full details and an updated conclusion.
|
|
Binabik
Responsible
Legendary Hero
|
|
posted August 06, 2006 08:25 PM |
|
|
Quote:
3. It contains at least one of the 5 starting skills.
We already know those 5 skills are part of exclusive groups. You will always get them at levels =<4 for magic or =<6 for wisdom. So no other skills can be part of that group. The only way they can be part of a larger group is if they belong to more than one group. That's possible, but I don't think it's likely.
One idea I'll bring up is that there are skill groups which are weighted as a group, but are not guarenteed. Sometimes I wonder if we are involved in mental masturbation to explain pure coincidence. There are definitely things that "seem" to be more than coincidence. But "seem" doesn't mean it's true.
I have to leave, so more later.
____________
|
|
Binabik
Responsible
Legendary Hero
|
|
posted August 08, 2006 12:31 AM |
|
|
Quick report.
Even quitting homm between tests instead of going to the main menu, I'm getting duplicate skill trees. What's going on? Is this by design, or coincidence?
____________
|
|
Xarfax111
Bad-mannered
Supreme Hero
The last hero standing
|
|
posted August 08, 2006 10:16 AM |
|
|
Quote:
Quick report.
Even quitting homm between tests instead of going to the main menu, I'm getting duplicate skill trees. What's going on? Is this by design, or coincidence?
Thats where ny "sequenze theory" came from. It cant be "pure random" as those "sequenzes" repeat far to often within a comparable low data amount. If it would be pure random chances that a sequenze would
repeat would be the same as of lottery numbers do repeat.
____________
|
|
Ecoris
Promising
Supreme Hero
|
|
posted August 08, 2006 10:59 AM |
|
|
|
Perhaps the random seed for each hero is stored in a single bit. That would mean that there are only 256 possibilities. Or do you experience long identical sequences in different trees?
|
|
Binabik
Responsible
Legendary Hero
|
|
posted August 08, 2006 11:06 AM |
|
Edited by Binabik at 11:18, 08 Aug 2006.
|
I think there might be sequences, but they are generated at the start of the game. I got duplicate trees even when I quit the game. I don't know how to explain the duplicates. I can only make guesses.
If the duplicates had skills that were high probablity skills, I can see it being coincidence. But some of the duplicates had low probablity skills. It could still be coincidence, but the odds are against that.
There are also certain skills that seem to show up too much. Like luck shows up way too often. My first test of 100 and my second test of 47 both had luck too many times. The pdf file dimis linked to also showed luck too often. I think he did 200 level ups with hack.
I want to run some more tests with the same setup. Then look for more duplicates. I'll send you the excel file when I'm done.
edit: Ecoris, our posts crossed.
Are you suggesting that each hero has it's own seed? I'd have to think about it more, but that almost makes sense. It would explain duplicate trees. If the seed is randomly generated at the start of the game, but limited to one byte, then you would only have 256 possible sequences. But how long is the sequence??? With only 256 posibilities, you would EXPECT a certain number of duplicates from random chance. With my 47 tests, the odds would be strongly against every one being different.
The duplicates I mentioned were using "always click right" with unedited hack. So they were only 7 skills long. That's too short to look for overlapping sections of the sequence.
____________
|
|
Ecoris
Promising
Supreme Hero
|
|
posted August 08, 2006 11:36 AM |
|
Edited by Ecoris at 11:39, 08 Aug 2006.
|
Quote:
Are you suggesting that each hero has it's own seed?
Yes, this has always been the cornerstone of the "weighted die" or random conjecture , i.e. the one that doesn't contain pre-made sequences. It would also seem reasonable from a programmer's view since you wouldn't benefit from reloads.
To be precise (and speaking in programming language) the idea is that each instance of the hero class has its own random number generator field (that would also determine starting creatures and XP as the first two things). The initial seeds could be set for all heroes at the beginning of the game by another random number generator. Therefore it is interesting what dimis' research will bring.
I don't know if this is how it works, I just want to point to the fact that duplicate skill trees does not reject the "weighted die" conjecture. Though duplicate skill trees would be extremely unlikely if the die rolls were truly independent and random we have to consider that we're dealing with a computer program.
Therefore I'm requesting anyone to describe unusual behaviours that they've encountered that doesn't fit into this idea.
Quote:
With my 47 tests, the odds would be strongly against every one being different.
Which tests are you referring to?
Edit: Corrected spelling and clarified minor details.
|
|
Binabik
Responsible
Legendary Hero
|
|
posted August 08, 2006 11:58 AM |
|
|
Quote:
Which tests are you referring to?
Whoops, I thought I posted that. I did 100 tests for Xarfax's thread with unedited hack, by going to the main menu each time. Then I did 47 more of the same test, but quit homm each time. The second test is the one I was referring to.
Out of 47 tests, I had 3 pairs of duplicate trees. If it's true there's only 256 possible trees, then 3 pairs out of 47 tests seems very reasonable.
With the test of 100, I don't know how many duplicates I had. But there were only 27 different trees.
Also I combined the results from the test of 47 with the 27 unique results from the test of 100. I had 3 more pairs of duplicates when the two tests were combined. In other words, out of 74 trees (47+27) I had a total of 6 pairs of duplicates.
____________
|
|
Ecoris
Promising
Supreme Hero
|
|
posted August 08, 2006 12:10 PM |
|
Edited by Ecoris at 12:11, 08 Aug 2006.
|
Quote:
Out of 47 tests, I had 3 pairs of duplicate trees. If it's true there's only 256 possible trees, then 3 pairs out of 47 tests seems very reasonable.
Perhaps, this is what dimis is working with (and I may look into as well soon, look on the top of page 6): Determining N (total number of possible skill trees) through probability measures. The more ANSA data we get the better, since the total number of different skill trees we observe will converge to N.
However if the ANSA tests are you to detect skills that occur too often I'll recommend an exit of H3 between each tests; this doesn't matter when we only count skill trees.
|
|
Binabik
Responsible
Legendary Hero
|
|
posted August 08, 2006 12:42 PM |
|
|
I've taken a fair amount of math and used to love it. But after not using it for 30 years, I remember nothing but the very basics. So I'll let you guys do the math part. I approach the probability stuff from a logical point of view. I just look at what seems reasonable or unreasonable.
I don't know if you downloaded Dimis' pdf file for the hack tests. But he had results that were color coded showing skills that appeared well above or below expectations. I've thought about this, and if he's doing what I think he's doing, I'm not sure if the model is correct.
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.
I think the proper model would be to take into account all 28 skills. With a very large sample size you would expect the individual skills to converge on the expected result for that skill. But with smaller sample sizes you would expect SOME skills to be above or below expection. So I think the odds for the GROUP of 28 skills being within a range needs to be calculated. I assume he's using standard deviations, but for individual skills, not for the group of 28.
____________
|
|
Ecoris
Promising
Supreme Hero
|
|
posted August 08, 2006 12:59 PM |
|
|
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.
Yes of course. The tricky part is: Could these deviations be the result of chance or do they indicate that the model is wrong (or insufficient). This would be a matter for a statistician and even though I've had a course in this I don't know how to analyze the data in a proper way. When you have an set of oberserved and a set of expected values you usually do a chi-square test to test whether the observed values deviate significantly from the expected ones. But there are certain criteria to the destribution in order for such a test to be valid.
The actual distribution could be characterized as "weighted hyper-geometric" (including exceptions)... 
But you can test skills individually to see whether some skill appears way too often. But i still feel that it would be better to treat all the skills as a whole, because the observed values are dependent.
|
| |
|
|
This thread is pages long: 
