
Thread: On the internals of offered skills when levelingup a hero.  This thread is pages long: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 · NEXT» 

dimis
Responsible
Supreme Hero
Digitally signed by FoG

posted April 22, 2006 02:45 PM 

Edited by dimis at 11:13, 20 Mar 2007.

On the internals of offered skills when levelingup a hero.
This thread was inspired by the thread Heroes Stats and Skills Chances.
That thread is about facts that we know.
This thread is meant to broaden our understanding on the internal mechanisms of offered skills when levelingup a hero. In order to accomplish that some tools are needed. And these are mathematics, computer science and some times brute force computations given by modern PCs. Now, some people find it extremely boring to go through all mathematics that underlie a specific subject and need just plain results. I think the thread "Heroes' Stat's and Skills Chances" is more appropriate for them since this is the place they are going to get useful info about verified facts.
So, what is this thread for? To put it simply: This is a scratch place, where various ideas can be discussed and analyzed so that we obtain new verified facts which on a subsequent level will appear on thread "Heroes' stats and skill chances".
Let's start having some questions and answers then ...
EDIT (Mar 12, 2007): Edited this post so that I will add a table of contents here. In a month or so I will start working on the problems again.
____________
The empty set


dimis
Responsible
Supreme Hero
Digitally signed by FoG

posted April 22, 2006 02:48 PM 

Edited by angelito at 18:42, 11 Nov 2009.

Preliminaries / Background
This post is used to put preliminaries and background information regarding the conversation that takes place later on.
Basic Data Structures that help us solve problems.
Fortunately there are many good sources around on the net for the following topics:
Weighted Graphs, Tree Data Structure and Binary Search Trees. You can also try out more on the previous concepts with Wikipedia, if you want to know more and have some time.
Search Problems and 2 Basic Search Techniques.
On a first notice this might seem irrelevant to the problems we are going to pose and try to answer, yet the search techniques will help us estimate the probabilities.
So, what is a Search Problem? I think the most intuitive way of seeing such a problem is as follows: Somebody starts from an initial position (state) and through a series of legitimate available actions wants to reach one goalstate. Simple examples that can be viewed as Search Problems are tictactoe, find a way out through a maze, solitaire, chess, etc. (Heroes can also be viewed as another Search Problem: you reach a goalstate when you achieve victory and all your intermediate moves/decisions represent the search; yet I think this is irrelevant with what we are trying to find out). One of the properties that come together with search problems is the socalled exponential growth of states. This is what makes usually Search Problems hard to solve with brute force computation. Let's have a look on a simple game that ends in just 2 moves and the player has exactly 2 options on each available move:
Figure 1:
Figure 1.
From the above picture one can see that the amount of different positions for Level j is 2^j.
As a result the total number of different positions (for the above example) is
SUM ( 2^j ) = 2^{MAX(j)+1}  1 = 2^{#Levels}  1,
which is a function with variables on exponent and thus we say it has an exponential growth. You can check out that this changes dramatically as the number of levels increases.
Definitions: From the above picture we can give names to some special nodes and characteristics of the tree:
root: It is the initial state.
leaf: It is a state that has no successor. When viewing a game this is usually a state of win, loss or draw. Not all leaves have to be on the same level.
branch: A transition from one state to another. This typically represents one of the allowable moves and is denoted with a straight line between two consecutive states.
branching factor: Represents the amount of available choices one has on a specific state. For a simple binary tree as the one above, branching factor is 2 for each state.
statespace: It is the collection of all different states that can occur.
path: It is an ordered set of states (which usually leads to a leaf). e.g.: <root, v1, leaf2>
Search techniques: Usually, we know the rules of a game which in turn make up the set of available moves (branches) for a player in each state. So if we want to find a route to a goal state, we can use these rules and generate and visit some or all states (assuming that we reach a leaf after finitely many moves and we are patient enough). In order to view the concept behind these 2 basic search techniques, let's suppose there is a game as it is shown on the following picture (goalnodes are colored with orange):
Figure 2:
Figure 2.
Breadthfirstsearch: Breadthfirst search strategy chooses to visit nodes in ascending order of levels, i.e. chooses to first visit those nodes that are closest to the root of a tree. This results in a search process that focuses more into breadth than into depth and is usually applied on search problems where we want to find a solution with a minimum application (in number) of moves. Graphically, the following figure shows the solution that can be found on the problem posed by figure 2 (numbers on the side of the nodes indicate the order in which we visit nodes, i.e. the way our search takes place):
Figure 3:
Figure 3.
meaning that the solution path returned is <root, v2, leaf5>. Note also that in order someone generates nodes for the next level (plus the exact path from root), requires the nodes of the previous level, meaning that "spaceoccupation" (also known better as space complexity) grows exponentially as we procceed in levels.
Depthfirstsearch: Depthfirst search strategy chooses to visit nodes following a policy that leads you as far as possible from the root. This results in a process that focuses more into depth than into breadth and is usually applied when we know that a solution exists at a specific level and not earlier. Graphically, the following figure shows the solution that can be found on the problem posed by figure 2 (numbers on the side of the nodes indicate the order in which we visit nodes, i.e. the way our search takes place):
Figure 4:
Figure 4.
meaning that the solution path returned is <root, v1, v4, v6, leaf3>. Note, that in order someone generates nodes for the next level (plus knowing the exact path from root), requires the nodes only from the path that starts from the root and leads to the specific node, meaning that the amount of "storageoccupation" is linear to the level of the specific node. In other words, one can have exponential savings in space; the only problem that exists with this method is that it can enter a path which has no leaf and thus the search process never terminate (consider a case in chess where you repeat the appearence of the same position; of course no such thing will occur on levelingup a hero ) !
Note: You can find better info about these concepts by simply googling them... Too bad I didn't think of it earlier!
Modelling a casinolike game.
One of my deepest beliefs in life is learning by conceptual/simple examples. I hope the following falls in this category:
Consider that we play a casinolike game where we pull down a stick and numbers jump around in front of our eyes (sorry but I don't know the translation in English, neither was I able to find it in a dictionary ). Total amount of numbers is 5; more specifically 1, 2, 3, 4, 5. For some unknown (?) reason the machine (or the game if you prefer) is not fair and we lose if one of the numbers 1, 2 or 3 stays still in front of our eyes in the end; and win otherwise (4 or 5) an amount equal to our bet. All numbers have equal "chance" to appear in front of our eyes the first time we pull down the stick, but no two consecutive appearences of the same number can occur, meaning that the second time it is not possible to see the number of our first pull. Chances distribute equally among numbers on each occasion (first time each number has a 20% chance of appearing and second time each number has 25% chance of appearing). Suppose we know nothing about probabilities, yet we want to find out the likelihood that we accomplish after 2 stickpulls to leave from the casino with at least the amount of money we had when we entered. Having this knowledge the obvious way of handling the problem would be to enumerate (list) all possible scenarios on the outcome, i.e.:
<1,2>, <1,3>, <1,4>, <1,5>, <2,1>, <2,3>, <2,4>, <2,5>, <3,1>, <3,2>, <3,4>, <3,5>, <4,1>, <4,2>, <4,3>, <4,5>, <5,1>, <5,2>, <5,3> and <5,4>.
Observing the above list and according to the rules of the game, we have the following cases:
We lose 2 bets: on 6 out of 20 cases.
We leave casino with neither loss nor profit: on 12 out of 20 cases.
We win 2 bets.: on 2 out of 20 cases.
So, we expect after 20 visits on the casino to leave 14 times with at least the money we had when we entered.
The above process can be pictured with a tree (what did you expect?) like the ones discussed above:
Figure 5:
Figure 5.
where with yellow color you can view the situations where we left the casino with no profit and with green color you can view the situations where we left the casino with a profit of 2 bets.
But wait a minute ... Does it really matter that we actually lost the game because one is represented as 1, two is represented as 2, ..., five is represented as 5? Of course not! We could have very well represented one as A, two as B, ..., five as E, but this time we would lose if A, B or C came out and win on D and E. So, just to help my intuition I will represent one as L, two as L, three as L, four as W and five as W (where L comes from Loss and W from Win). As a result we could have had the same tree as the one in figure 5 but with 1 replaced by L, 2 replaced by L, 3 replaced as L, 4 replaced by W and 5 replaced by W. And finally, to move one step further, I realize that on each state leave behind as I go downwards the tree, I find 3 Ls and 2 Ws. So I will simply add weights in the branches to have a more compact representation as in the following picture:
Figure 6:
Figure 6.
where colors on leaves are defined as above (after all, for our purposes it doesn't matter if I lose due to a 2 or due to a 3, I simply lose in both cases). What have we achieved now? Simply by multiplying weights along a path you get the outcome of the specific path. In the end one sums up all these numbers for leaves with the same color and gets the desired results as stated above with a simple enumeration! Finally, one could have labeled branches instead of number of possible outcomes the exact probabilities (meaning 0.6 instead of 3 and 0.4 instead of 2) and reach immediately via multiplication on weights on each path and a further summation of the resulting numbers on leaves with same color, the required probabilities. Graphically we have:
Figure 7:
Figure 7.
And this is exactly the way I view those entries on the formentioned table on "Heroes' Stats and Skill Chances" thread, i.e. weights on branches of possible outcomes (gaining a skill).
Wellordered sets, Orderings and Relations to Skill Advancement Problems.
Brief description for the above mentioned to be placed here soon ...
Large numbers that don't fit on 32 and 64 bit computers.
There are various ways of seeing a problem as the ones this thread will try to investigate. But (nearly) all of them require the manipulation of large numbers when it comes to actual brute force computation. For that reason, a library is necessary so that one can have arbitrary precision on his/her computations when an actual implementation is needed. Due to that fact, for the time being, the library that is used is GNU MultiPrecision Arithmetic library (aka GMP).
A Glimpse on Random and PseudoRandom Number Generators.
To clear up something right from the beginning: There is no such thing as a "random" number generator in the sense we people understand the concept of "randomness".
If you want to intuitively justify it consider the following: Say we ask from the computer to give us a number between 1 and 100 at "random". How is the computer able to respond to our demand? It has to make a decision and return a number. But how is the pc actually going to take that decision? Either it has to ask an oracle for the number (and no such thing exists) or (and this is what happens) follows specific rules (stepbystep commands) to produce a number.
So, Random Number Generators are not so random after all! Instead, a Random Number Generator is a collection of (deterministic) commands that result in producing an (infinite if we want) sequence of numbers (let's say between 0 and one maximum integer value  in C and C++ this is called RAND_MAX). This concept is hidden behind every Random Number Generator on actual programming languages, by which in turn games as Heroes are made. If you want to see a Random Number Generator as a mathematical object, then you can view it as a function which is initiated by one number (typically this is called seed) and then (following specific instructions) this function starts "spitting out" integers (between 0 and RAND_MAX let's say) which "appear to be random". However, no matter how many times you feed this machine with the seed, you will always get the same sequence. So, how the programmers are actually trying to fool us and want to make us think they use a "truly" Random Number Generator? The answer is simple again: At the beginning of program execution, they catch the time it started and use this time as a seed. Typically, in C and C++ time starts counting after one timestamp (and something similar is followed by other programming languages as well)  I think it is 1st January 1970 or something similar  and time elapsed is in seconds. But, of course, each time the Generator is fed with the same seed, it generates the same sequence.
One final note on the production of random numbers between 0 and a number strictly smaller than RAND_MAX: The technique used for this purpose is to apply the mod () function on the "freshlygenerated" number in sequence, i.e. you want numbers between 1 and 100, then simply substitute each number with the remainder of this number in the division with 100 and add 1. All numbers are between 1 and 100 and appear to be random; but as you have realized (in case you didn't know) they are not random at all!
For more info you can check the following:
1) The GMP library above has its own (Pseudo)Random Number Generator and a brief description is placed on page 111 of the manual.
2) I think the definite reference is The Art of Computer Programming by Knuth.
3) Follow references on (1) above or start googling. That way you don't have to buy volume 2 on (2) above. Finally, in order to find some references it might come handy to use Google Scholar, which is miraculous!
EDIT (Mar 12, 2007): I edited this post before it gets locked. Soon I will have to place some additions here.
____________
The empty set


dimis
Responsible
Supreme Hero
Digitally signed by FoG

posted April 22, 2006 04:21 PM 

Edited by angelito at 20:18, 11 Nov 2009.

The
First Problem that we are going to investigate is the ANSA (Always New Skill Advancement) problem.
To put it simply:
What is the probability when levelingup a hero to gain a specific skill if the user always chooses the first new skill that is offered on each new level?
The idea of the solution:
The idea of the solution is pretty straightforward. One simply generates all possible paths P (different skill combinations) that can occur when levelingup a hero, following ANSA policy. Then, he simply enumerates the paths D where the desired skill shows up. So, the actual expected probability when leveling up a hero to achieve a specific skill is D/P.
Actually, what is described above was the original idea of the solution. In fact, the tree where computations take place has weights on probabilities for each offered skill at each level. As a result, the computed probability for a skill is the sum of "partial probabilities" of the specific skill through all possible paths; where "partial probability" is the overall probability for the specific instance of the path (multiplication of probability weights from root note to leaf node).
Some bounds on statespace and on the complexity of the problem:
It's always nice to have a general idea of how big a space can be in a worst case scenario. What is the worst case scenario then? We simply encounter it if our hero starts with only 1 skill. This means that he will have 7 leveladvances where he is going to receive his new skills (according to ANSA). Of course, to achieve worst case scenario, the amount of available skills (to be offered) should be maximal. One hero that covers this scenario is THANE, who may acquire all skills apart from Necromancy and at level 1 possesses only Scholar. This means that his subsequent slots (skills) can be filled in W = 26*25*24*23*22*21*20 different ways. But how big is that number?
Let's see:
20*20*20*20*20*20*20 < 20*21*22*23*24*25*26 < 26*26*26*26*26*26*26
or equivalently 20^7 < W < 26^7,meaning that 1,280,000,000 < W < 8,031,810,176.
But these are many positions so that someone stores them in RAM and do things. Luckily, we can do better, since we have some better understanding of the problem so far. We know, that by level 6, our hero will possess WISDOM.
So, a better upper bound on the amount of total "ways" can be achieved:
W < 25*24*23*22*1*21*20 + 25*24*23*1*22*21*20 + 25*24*1*23*22*21*20 + 25*1*24*23*22*21*20 + 1*25*24*23*22*21*20 or equivalently
W < 637,560,000.
We can go on further with this, since we know that the user must also possess at least one magic school on the first 3 slots that are filled during the process of levelingup. But I won't get into that, since this is not exactly what we are trying to find!
The problem is that not all skills have the same "weight" (check out Russ's third table here), i.e. they are not equiprobable and each one of these probabilities on each level is affected by user's earlier actions (another way of putting it and please make a good note on this: Hero remembers your past actions when you were picking skills for him! ).
So, what W stands for? Well, it is the number of different classes (i.e. ways to characterize) of paths. In order to understand the actual amount of states let's see what's going on on an intermediate state while leveling up a hero with an example.
Quote: Let's say hero has 25 available skills. Since these skills are weighted with the numbers you can find on the previous table, the total number of branches (i.e. different followups) is the sum of weights of these 25 skills. In other words for each 1 in every skill's weight we can follow a different path. So, it is these paths that are actually going to determine the number of different followups up to level 7 or 8 (depending on hero's starting number of skills). Of course, there are duplicates for most of the paths (the number of duplicates is exactly the "weight" of each skill). All these duplicates simply belong into the same class. But we can not forget duplicates, since it is this number (of same paths) that determines the actual
probabilities for various skills.
Luckily, we can work on classes. We can simply generate them and then, for each different class C_i, the total amount of paths that correspond to this class are_{C_i} = PRODUCT ( weight_{s_i} ), for each skill s_i that belongs in class C_i.
On the above computation the ordering of skills does not make a difference in the product, yet, not all possible combinations of skillordering (classes) do appear. To counter it simply consider the following situation:
Let's say you end up on a leaf with these skills (suppose 1,2,3,4,6,7 and 8 are legitimate skills):<1,2,3,4,WISDOM,6,7,8>
for a hero that starts out with just one skill. This is a valid class on our policy. But, the following permutation:
<1,2,3,4,6,7,8,WISDOM> can never occur for a hero that starts with just one skill and follows ANSA policy.
Returning to our point, what we really want to compute is the properties of all paths. But how many are they? Here we can give simple bounds to show that things can reaaaally go bad.
Lemma 1: The total amount of paths is:
TP = SUM ( P_{C_i} ), for each class C_{i} that can legitimately occur according to our policy (where i = 1, 2, ..., W).
(The above statement is nothing more than what I described when modelling a simple casinoexample in the background info.)
As one can easily realize, this shows that statespace is out of hand and there is no way of representing it in memory.
BUT, if we can have a fast implementation on the generation of the various classes, we can work on classspace (i.e. in a manner similar to figure 6 in the casinoexample) and with the application of the above lemma, check what we really want to check (i.e. which skills appear along various paths) and store what we really want to store (how many paths of same combination of skills can actually occur with the same order) in each class in O(1) asymptotic running time for each class time proportional to 8 (number of skills along the path), meaning that we can counter this problem efficiently and get results within reasonable time limits.
Implementation related:
So, how are we going to make some computations? This is the heart of the problem and the way of managing it. Even if it is OK to handle the problem on classspace, the problem is that all different states in classspace are way too many  even if for example we can lower the former upper bound on W to around 200,000,000  to store all necessary data in memory to speed up computation. But there is no obvious reason to store each different classstate in memory. After all, the outcome relates only to the actions taken along this short path. So, all we have to do is visit each classpath in a consecutive manner. For that reason, depthfirst search (refer to post on preliminaries) is used and as a result the amount of memory
needed is only the amount of memory needed to store 8 classstatestructures + a proportional amount of generic variables for each classstate, meaning that required memory can very well be a small multiple of bytes!
Now, that there is a way of searching efficiently, let me fill up some details:
1) Each skill is in 11 correspondence with one integer. For that reason, I use lexicographic ordering on skills and assign to Air Magic the number 1. Each consecutive skill is assigned the next integer, so we end up with WISDOM having number 28. For programming purposes I 've also added a NULL_SKILL (just a name for a skill that is equivalent to NOTHING) in the corresponding tables in source code (to which I assign number 0).
2) We have to visit the entire statespace, which is a tree with a variable branchingfactor. But we don't have to follow each path, because we already know exactly how many are going to be identical. This is exactly the point where Lemma 1 above can help us. Instead we follow only classpaths and get results at the same time on actual statespace (exactly the same way we did computations on the casino example). Furthermore, since we are interested in probabilities for each skill we give weights on each branch equal to:prob(s_i) = weight(s_i) / SUM (s_j), where in s_j we can find all available skills at that level,
i.e. exactly what was done on the casinolike game in figure 7.
For simplicity reasons, assume there is a state where we have 2 options: Option1 with weight 3 and Option2 with weight 2.
This can be pictured as below:
Figure 8:
Figure 8.
where, when one follows Option1 visits subtree S1, while when following Option2 visits subtree S2.
So, the transformation we implement (i.e. use weights on branches) can be pictured as below:
Figure 9:
Figure 9.
In other words, a path on this problem is simply a succession of branches that are weighted with their respective probabilities at each level and is at most of length 7 (for heroes starting with only 1 skill).
Of course there are 2 exceptions on the above assignments:
a) On the transition from level 5 to level 6 (and hero has not obtained WISDOM so far) WISDOM is the only available skill with probability = 1.
b) On the transition from level 3 to level 4 ONLY MAGIC SCHOOLS are available and as a result the probability each one receives is:
prob(s_i) = weight(s_i) / SUM (s_j),
where s_j now varies ONLY among the various magic schools.
4) Weights on branches are stored in mpq_t variables from the GMP library so that we have exact computations.
5) At the end of each "probability"path the respective probability is computed. This number is then added to the overall probability of each skill along the path.
6) At the end of walk through classspace the exact probabilities are returned in a fractional way (num/denom) with the help of mpq_t data structure by GMP. These values are transformed to double precision variables (through an intermediate transformation to mpf_t variables used by GMP to store floating points) and are printed in user's screen.
Modelrelated options:
Unless I forget something very basic, the model we have so far for skill advancing is the following:
1) If a hero does not get offered a Magic School prior level 4, he will get one as an option on that level. Of course, when following the ANSA policy this implies that this is the only one (among Magic Schools only) new skill offered at that level.
2) If a hero does not get offered WISDOM prior level 6, he will get offered WISDOM at that time. Again, with respect to the policy we are investigating, this is the only skill (happens with probability 1).
3) There are also 2 more notes on what happens when a hero rejects either a Magic School (and possesses no other Magic School at that time) or Wisdom, but these are irrelevent to our problem since our hero will always pick the freshlyoffered skill.
Source Code, Executable and Running Times:
You can find the "official" source code (implemented with the use of GMP Arithmetic Library) here. This zip also contains an executable (ansa) for systems running 32bit linux. The executable was created with g++ version 4.0.2 at optimization level 3. I don't know if there is a conflict with the executable in your machines because on autosettings for GMP installation everything was compiled with march=k8 parameter (used for opteron processors).
Within the above zip file you can find the corresponding makefile which in turn takes the responsibility of generating the executable. In order to generate the executable one has to give on command line:
Quote: % make f makefile
The program expects 2 arguments so that it can run. First one is Hero class and second one is hero name. For more info run 'ansa' executable without parameters.
A sample of program execution in an AMD64@3000+ on 32bit Ubuntu 5.10 distro is the following:Quote: $ ./ansa Knight Orrin > Orrin.txt
Part of computation: 1/28.
Part of computation: 2/28.
Part of computation: 3/28.
Part of computation: 4/28.
Part of computation: 5/28.
Part of computation: 6/28.
Part of computation: 7/28.
Part of computation: 8/28.
Part of computation: 9/28.
Part of computation: 10/28.
Part of computation: 11/28.
Part of computation: 12/28.
Part of computation: 13/28.
Part of computation: 14/28.
Part of computation: 15/28.
Part of computation: 16/28.
Part of computation: 17/28.
Part of computation: 18/28.
Part of computation: 19/28.
Part of computation: 20/28.
Part of computation: 21/28.
Part of computation: 22/28.
Part of computation: 23/28.
Part of computation: 24/28.
Part of computation: 25/28.
Part of computation: 26/28.
Part of computation: 27/28.
Part of computation: 28/28.
$ cat Orrin.txt
ORRIN
~~~~~
AIR MAGIC : 36.1088 %.
ARCHERY : 100 %.
ARMORER : 22.7628 %.
ARTILLERY : 22.7628 %.
BALLISTICS : 34.2332 %.
DIPLOMACY : 18.5736 %.
EAGLE EYE : 9.64718 %.
EARTH MAGIC : 24.7138 %.
ESTATES : 26.7687 %.
FIRE MAGIC : 12.6755 %.
FIRST AID : 9.64718 %.
INTELLIGENCE: 4.91268 %.
LEADERSHIP : 100 %.
LEARNING : 18.5736 %.
LOGISTICS : 22.7628 %.
LUCK : 14.2014 %.
MYSTICISM : 9.64718 %.
NAVIGATION : 34.2332 %.
NECROMANCY : 0 %.
OFFENSE : 30.5917 %.
PATHFINDING : 18.5736 %.
RESISTANCE : 22.7628 %.
SCHOLAR : 4.91268 %.
SCOUTING : 18.5736 %.
SORCERY : 4.91268 %.
TACTICS : 30.5917 %.
WATER MAGIC : 46.8568 %.
WISDOM : 100 %.
Duration : 245.64 seconds.
where cat command essentially does what type command does in Windows, meaning that it types filenames contents in ascii. Of course, running time will vary from platform to platform. Finally, for Heroes starting out with only 1 skill, one should be patient. Example running times on same machine:
* CragHack: About 1 hour 20 minutes.
* Thane ....: About 2,5 hours.
Double Precision Arithmetic and Windows 32bit Portability:
So far, I 've not examined portability options for GMP library in Windows. However, regarding the ANSA problem things can go pretty well even with double precision variables. The reason is the following: Nearly all 32bit modern architectures supply precision at least as small as 10^{15}. As it has been shown earlier, the amount of total paths can not exceed 637,560,000, which in turn implies that no more than 637,560,000 * 7 (< 5*10^{9}) multiplications in "probability weights" can occur. As a result, the "total error" can not exceed 5*10^{9}*(1/2)*10^{15} = 5/2 * 10^{6} < (1/2)*10^{5}, meaning that in worst case scenarios we can expect accuracy for at least the first 4 decimal digits!
As a result, here you can find the source code and executables for Linux 32bit and Windows 32bit OSs. For program execution, consult the example given in the previous paragraph. The improvements on the performance are fantastic. As an example, computations required for Thane take about 10 seconds while on same machine with the use of GMP library (infinite precision due to fractions) time required is about 2,5 hours!
Results:
You can view the results in this Excel book or view this picture.
Results transformed to Excel file:
This is for documentation purposes.
In order to generate the Excel file above, the ansa2excel program was used. The program expects to find on the same directory a file called
ansa_probs.txt which contains all "raw" results for the heroes that interest us. When ansa2excel program is executed, it generates ansa_probs.xls Excel file. One can view this .xls file with TextEdit, a program commonly used for Random Map Generators. Of course in order to view the file, one has to rename it to .txt.
EDIT: Feb 4, 2007.
Extending Computations:
Some interesting questions can be posed on ANSA, regarding combinations of skills. For example,
(EG1) What is the probability for a specific hero to gain Air Magic AND Tactics when following ANSA?
(EG2) What is the probability for a specific hero to gain Air Magic OR Tactics when following ANSA?
(EG3) What is the probability for a specific hero to gain ( Air Magic AND Tactics ) OR ( Earth Magic AND Armorer ) when following ANSA? (EGi) etc ... (if you are familiar with the terminology, constructed formulas are in Disjunctive Normal Form, if not make sure you understand the pattern in the examples above)
For a strict description on the meaning of OR and AND connectives above, please refer to Truth Tables here.
How can someone pose questions similar to the above?
The idea is simple: On the folder where you store the executable (I 'll give you shortly a link), you have to create a file named
selections.txt
Intuitively: Each line of this file should contain up to 8 preferred skills. All these skills are combined with AND connectives. Preferences on separate lines indicate combinations with the OR connective. You may place up to 30 different lines. As a consequence, a question similar to (EG3) above can be described in the file in the following format:
selections.txt
Air Magic Tactics
Earth Magic Armorer
 END OF FILE 
Practically: For ease in programming, file selections.txt is NOT structured as above. Here are the differences:
I) Skills should not contain blanks even if they are composed by two words. An underscore '_' should be used instead. Hence, 'Air Magic' should be written as 'Air_Magic', 'Earth Magic' as 'Earth_Magic' and so on...
II) Again for ease in programming, each line should contain exactly 8 skills. In cases where you don't want to use all 8 slots you have to fillin the 'blanks' with the 'Null_Skill'.
As a result the actual selections.txt file for example (EG3) is the following:
selections.txtAir_Magic Tactics Null_Skill Null_Skill Null_Skill Null_Skill Null_Skill Null_Skill Earth_Magic Armorer Null_Skill Null_Skill Null_Skill Null_Skill Null_Skill Null_Skill END OF FILE 
III) Further notes:
. (a) Valid names for skills:
NULL_SKILL, AIR_MAGIC, ARCHERY, ARMORER, ARTILLERY, BALLISTICS, DIPLOMACY, EAGLE_EYE, EARTH MAGIC, ESTATES, FIRE_MAGIC, FIRST_AID, INTELLIGENCE, LEADERSHIP, LEARNING, LOGISTICS, LUCK, MYSTICISM, NAVIGATION, NECROMANCY, OFFENSE, PATHFINDING, RESISTANCE, SCHOLAR, SCOUTING, SORCERY, TACTICS, WATER_MAGIC, WISDOM.
. (b) Naming skills can be done using any combination of lowercase or UPPERCASE letters. Ofcourse underscore '_' remains underscore '_' in every case (whenever needed).
. (c) The file selections.txt must finish at the final character of your last line; i.e. NO ADDITIONAL EMPTY LINES should appear on file. As an example, sample selections.txt described above should contain 2 lines like this one.
. (d) At the time being, file selections.txt should NOT be more than 30 lines long. I believe this is more than enough for all practical questions that can arise. If not, just drop a message on board, and I'll modify the code to extend it or make it dynamic.
. (e) That will be all. If you can follow all the above practical "limitations", then all computations are correct and exact for up to at least 2 decimal digits (on the resulting percent). If not, the behaviour of the program is undefined.
Please make sure you understand the simple rules above.
Where can I get the program?
The program that performs these extended capabilities (under ANSA) can be found on the following links:
source code
win32 executable
How does it work?
(1) Make sure selections.txt file is in the same directory as ansaExtended.exe.
(2) On command line give:
ansaExtended Hero_Class Hero_Name DNF
where Hero_Class the Class where the Hero belongs and Hero_Name the name of the hero. For example, if you want to find the probability that Orrin has to acquire ( Air Magic AND Tactics ) OR ( Earth Magic AND ARMORER ) when following ANSA, you have to give on command line: Quote: ansaExtended knight orrin dnf
and the sample output is the following: Quote:
ORRIN
~~~~~
Requested probability: 15.8895 %.
Duration : x.yz seconds.
Finally, the old computations made on ANSA, are performed if someone omits the final argument 'DNF' on command line. Give it a try and you'll see what I mean, i.e. execute Quote: ansaExtended knight orrin
and compare the outcome with the values on the ANSAtable.
Have fun!
 dimis 
____________
The empty set


FriendOfGunnar
Honorable
Legendary Hero
able to speed up time

posted April 22, 2006 10:04 PM 


Heh heh, you got me going on this too Dimis.
You know what's really annoying...
I'm like 4 years behind the curve on this one but all H3 save files are encrypted, which makes things a lot more difficult.
Truthfully though the "preordained yet appearing to be random" paradox is nagging at me too. (heh heh kind of like Life and the Universe)


dimis
Responsible
Supreme Hero
Digitally signed by FoG

posted April 23, 2006 02:25 AM 

Edited by dimis on 22 Apr 2006

Well, the paradox does not have to be a paradox after all. Thanks for pointing that out. I 'll give a simple description on random number generators on my second post "preliminaries/background" (which currently contains some very basic info related to source code and not what I actually intend to write there such as what you suggest) to explain why this thing happens. But this will have to wait at least one day. I need some rest now.
____________
The empty set


FriendOfGunnar
Honorable
Legendary Hero
able to speed up time

posted April 23, 2006 07:37 AM 


That's just the thing Dimi, after the game has started the secondary skill selection is not random. At the beginning of every game, HOMM3.exe randomly creates a list of secondary skills (which I suspect is exactly 112 skills long). HOMM3.exe then uses an algorithm to decide which skill to offer you depending on how whether or not you take an upgrade or a fresh skill. (in other words HOMM3.exe is kind of jumping back and forth on the list according to a prearranged set of rules). I'd peek at the list but like I already said the H3 save files are encrypted (and I believe it's against the CoC here to even suggest ways of cracking it...dunno)


Bastich
Hired Hero
Architect of Aggression

posted April 24, 2006 11:58 AM 


What's the mechanism of skill advancment in the campaigns? I have never been offered Luck in previsious missions, but now, ot the last mission I have one empty skill and I always get Basic Wisdom + Basic Earth, Basic Fire or Basic Air (I used the Level Up cheat to check out my skill progression and it's always the same).
____________


Vlaad
Admirable
Legendary Hero
ghost of the past

posted April 24, 2006 12:21 PM 


Quote: What's the mechanism of skill advancment in the campaigns? I have never been offered Luck in previsious missions, but now, ot the last mission I have one empty skill and I always get Basic Wisdom + Basic Earth, Basic Fire or Basic Air (I used the Level Up cheat to check out my skill progression and it's always the same).
Campaigns are no different (they are just a bunch of maps with carryovers). Campaigns are usually customized because of the storyline; that's why you couldn't get other skills  they had been disabled by the mapmaker.
____________


dimis
Responsible
Supreme Hero
Digitally signed by FoG

posted April 24, 2006 04:23 PM 

Edited by dimis on 24 Apr 2006

Near finishline ...
I added an "Improvement" section on the post regarding the ANSA problem and I changed my casinolike example in the background section (which I suggest you read first) so as to reflect better the concept of the general problem of "offered skills while levelingup a hero". I think it is now only a matter of time to tidy up source code and make necessary changes on weights on branches so as to have final conclusions.
____________
The empty set


FriendOfGunnar
Honorable
Legendary Hero
able to speed up time

posted April 24, 2006 06:30 PM 



dimis
Responsible
Supreme Hero
Digitally signed by FoG

posted April 25, 2006 06:22 PM 


It's all over now (regarding ANSA).
Source code along with a sample execution of the program can be found on ANSA post. I'll post results on "Heroes' Stats and Skills chances" thread once I 've finished necessary computations for all might heroes.
Till then,
all of you who have a UNIXlike OS,
enjoy!
 dimis 
____________
The empty set


dimis
Responsible
Supreme Hero
Digitally signed by FoG

posted April 27, 2006 03:26 PM 


New projects
Results regarding ANSA policy are near to an end.
Some extra modifications to source code (ANSA) have been made (fixed memory leaks while using GMP variables and soon will add Sir_Mullich and Gelu).
I am thinking of new directions for this thread (most likely during summer), so any comments/ideas are valuable and you are encouraged to share.
Here is a new direction I have in mind, called FMP (Follow My Policy):
The user classifies Skills in a descending order of preference. This preference is used as a "guide" when picking up new offered skills; meaning that hero gets one skill if the skill is on top 46 slots in his preference list otherwise he improves one of his already gained skills. However, we will not be able to go all the way down the tree (i.e. 20level tree for a hero starting out with just 1 skill). On the other hand I think we can progress more than 8 levelups (which is the case of ANSA) since this "list guide" is going to prune some branches: e.g. your hero possesses 4 skills which can all be upgraded and he is offered Eagle Eye. Obviously (if eagle eye is not in your first 46 slots in preference list ), one should not search that branch because you are going to upgrade one of the existing skills!
I 'll settle down some estimates on how "deep" we can go (i.e. number of levelups) on a subsequent edit/post, but for the time being I have many other things to attend to.
So, what are your suggestions/comments/ideas?
____________
The empty set


dimis
Responsible
Supreme Hero
Digitally signed by FoG

posted April 28, 2006 11:25 PM 


Win32 executable
Near the end of ANSA post you can find an executable for win32 platforms.
Enjoy!
____________
The empty set


maretti
Responsible
Supreme Hero

posted April 29, 2006 12:38 AM 

Edited by maretti at 13:44, 29 Apr 2006.

First of all I would say great work, it seems you have a pretty strong brain for these things.
I have been wondering how usefull the ANSA tabel really is cause its not how you pick skills in a real game. But I cant really figure it out.
The FMP method is more interesting imo. Im really looking forward to seeing some results. However its very hard to say which skills are better in many situations. For example what is better for Crag as lvl 3, earth or logistics? It comes down to many factors, what town and map are u playing and what are the chances the hero will be offered this skill again etc. But I guess you have to make some disicions about what is better for each heroclass. Also this is only usefull for main heroes, scouts need other skills.
Maybe you should make some groups of skills that should allways be picked before other groups, and in the same group you should pick the skill that has the smallest chance of reappearing (which can be very hard to figure out between magic and other skills im affraid because that is what the test is about)
Imo the prefered skills and groups should be as follows:
Group 1: Earth, logistics
Group 2: Offence, air, armor, tactics and pathfinding
Group 3: Archery, resistance, artillery, fire, water, wisdom
Group 4: Leadership, luck, intelligence, scouting
Group 5: Rest
If a skill from the first 2 groups is offered it should be picked, if they are all picked and a group 3 skill is offered it should be picked, if 2 new skills are offered the one from the highest group should be picked.
Just a brainstorm of mine to give some inspiration. Might not be usefull.
____________
Crag rules, Orrin and Ivor suck


dimis
Responsible
Supreme Hero
Digitally signed by FoG

posted April 29, 2006 03:58 AM 

Edited by dimis at 16:53, 29 Apr 2006.

Groups!
Quote: I have been wondering how usefull the ANSA tabel really is cause its not how you pick skills in a real game. But I cant really figure it out.
To be honest, I don't know exactly how usefull the ANSA table really is, exactly for the same reason. However, I think that the values it presents can be seen as "trends" for each hero. Obviously, to my eyes, it is not coincidental that Tazar has the highest chance on getting Earth when following ANSA policy. At least, this reflects my experience with Tazar, in the sense that it was much easier in my games to have Earth with him, than let's say Orrin or Mephala. I also want to add a note here regarding the table. The table is correct and shows the expected chances for each skill when following ANSA policy under 5 assumptions:
Assumptions:
1) Table with weights for each hero class is accurate. By the way, do we know who posted first that table? And what was his relation to 3DO?
2) A hero is offered a magic school when he reaches level 4 if he has not been offered earlier.
3) At level 4 when hero is "obliged" to be offered a magic school (the case above), he is offered that (let's say Earth) with probability equal to:
Probability(Earth) = weight(Earth) / (weight(Air) + weight(Earth) + weight(Fire) + weight(Water)).
4) At level 6, if our hero has not been offered Wisdom so far, he does so with probability 1 (certainty).
5) The above assumptions are ALL correct and are all what is needed up to level 8 (for ANSA).
The way I interpret the table with an example: If someone follows ANSA policy for 1000 games with Tazar, then he is expected to get Earth on 557558 games.
For that reason I prefer to see these values as "trends" and as a simple "extension" (I believe this is the most appropriate characterization) to the original weight table. So, although it does not say much for actual game playing, I think it help us have a better intuition for each hero class and each hero. At least, for starters.
Another way on finding usefullness on the ANSA table I think is the realization of whether or not we have an accurate model of hero levelingup  at least up to 8th level. If a class of heroes, or even if only one hero can be used as a refutation of the above table, then I think we 've made a step forward. We know we have to search more for patterns in the first 8 levels. If, on the other hand, every hero can be used so as NOT to refute table, then again we have made a small step forward because now our assumptions are now better founded.
Quote: The FMP method is more interesting imo. Im really looking forward to seeing some results. However its very hard to say which skills are better in many situations. For example what is better for Crag as lvl 3, earth or logistics? It comes down to many factors, what town and map are u playing and what are the chances the hero will be offered this skill again etc. But I guess you have to make some disicions about what is better for each heroclass. Also this is only usefull for main heroes, scouts need other skills.
I also had in mind only main heroes when I made the proposition of FMP. But I don't see the problem for scouters as well ... You can rerun the program with a different prefered list, so that it matches better the hero for scouter.
Quote: Maybe you should make some groups of skills that should allways be picked before other groups, and in the same group you should pick the skill that has the smallest chance of reappearing (which can be very hard to figure out between magic and other skills im affraid because that is what the test is about)
Imo the prefered skills and groups should be as follows:
Group 1: Earth, logistics
Group 2: Offence, air, armor, tactics and pathfinding
Group 3: Archery, resistance, artillery, fire, water
Group 4: Leadership, luck, intelligence
Group 5: Rest
If a skill from the first 2 groups is offered it should be picked, if they are all picked and a group 3 skill is offered it should be picked, if 2 new skills are offered the one from the highest group should be picked.
Just a brainstorm of mine to give some inspiration. Might not be usefull.
Apparently these thoughts are very usefull and with most of them I agree. But some of them are still not clarified and it is rather difficult to take a decision. Let's see what I am trying to say. First of all, the grouping is a very good idea. On the second part, when one has to choose between skills of the same group that are offered as basic, we still need a preference. The reason is that both skills might have the same "weight" and as a result none is smaller. One more comment, regarding FMP/ANSA: It is not actually a test, rather than an enumeration of all possible "weighted" outcomes, meaning that the numbers we receive on probabilities for each skill, are exactly the numbers we should observe in actual game play by following this policy (of course assuming that we have a perfect model on the behaviour of offered skills while levelingup and the weighttable is correct ...). So, grouping is certainly not enough to give birth to a program. We need a complete enumeration. We need to state clearly that we prefer Eagle Eye to Navigation because Eagle Eye is stronger on maps with no water at all.
Now, regarding the reappearence matter, it is computationally difficult (meaning lots of time) with classic techniques to approach it, yet we are not at all lost in this one yet. I can think of 2 reasons:
1) The hero always remembers your past actions. If you pursuit on getting skills that have large weights, you tend to decrease the total amount of the sum of weights for the rest of the skills. As a result, skills that have high weight and are needed (Group 1 or 2), "gain" more by your earlier selections because their probability on getting them increases on "ordinary" levels (levels where we have no exceptions, e.g. 6/wisdom). I think this is a good idea at least on influencing the tree and certainly easy to implement since we base our selection only on present/past knowledge.
2) I think that the question of "reappearence probability" is a bit vague. What do we really mean by that? Do we want to maximize probability on the very next level? If that is the case then the above rule suffices because everything will be done in just one step.
Do we want to maximize probability on the subsequent 4 levelups? Do we want to maximize probability up to 8th slot?
I believe it is the latter one. Yet, this probability not only relates with the internals of offered skills  which we still are not certain that we know everything about  but also with the policy we follow while leveling up our hero, meaning our preference on skill selection on various cases. So, I think that the question is too delicate with our present understanding in order to respond.
A note: I think that we must focus on a specific hero and examine results from actual gameplayingsimulation with this hero exactly as Xarfax has proposed in the past. Moreover, if we have a large dataset and on a specific hero we can draw some "general" assumptions and see if these fit with simulation on other heroes as well.
Thanks again for sharing your thoughts maretti.
____________
The empty set


Binabik
Responsible
Legendary Hero

posted April 29, 2006 10:18 AM 

Edited by Binabik at 10:31, 04 May 2006.

Quote: 1) Table with weights for each hero class is accurate. By the way, do we know who posted first that table? And what was his relation to 3DO?
The table comes from game data so it should be correct unless something got corrupted. I spot checked about 15 of the numbers in Russ's post and they appear to be correct.
Something I've also tested is that the same table appears to be used when upgrading existing skills. For example if Edric starts with Leadership(10) and Armorer(5), then levels up, advanced Leadership is twice as likely as advanced Armorer.
Quote: 2) A hero is offered a magic school when he reaches level 4 if he has not been offered earlier.
This has been tested by several people and I would consider it fact.
Quote: 3) At level 4 when hero is "obliged" to be offered a magic school (the case above), he is offered that (let's say Earth) with probability equal to:
Probability(Earth) = weight(Earth) / (weight(Air) + weight(Earth) + weight(Fire) + weight(Water)).
Not sure about this one. I haven't specifically tested it. But from overall test results, I'm not sure I would assume this is true......not without more testing.
Quote: 4) At level 6, if our hero has not been offered Wisdom so far, he does so with probability 1 (certainty).
This also has been well tested.
As for FMP, I agree grouping is the best way to do it. It can only be approximate because there is no way to account for all situations.....wouldn't that be like designing your own AI?
What I think would be more useful is Always Upgrade Skills If Existing (AUSIE). The reason being that it's more useful for testing actual results against expected results. ANSA and AUSIE would be the two most useful type tests to find if there are any more special exceptions like Wisdom and Magic School.
For example ANSA would be the quickest way to find the level 4 magic and level 6 Wisdom. But AUSIE is needed to find that Wisdom will be offered at levels 12 & 18, if not offered earlier. And a magic school is offered at levels 4,8,12,16,20 if not earlier. So the two test types give you different information.
FMP is more useful for actual gameplay. But it doesn't do any good unless all the rules are known first. I think it's very likely there are rules we don't know about.
____________


dimis
Responsible
Supreme Hero
Digitally signed by FoG

posted June 25, 2006 12:48 AM 

Edited by dimis at 02:41, 25 Jun 2006.

Help needed
In a few days I will be able to start spending time with the problems posed on this thread. But before I start writing code, I want to determine the bounds on statespace on the different variations on policies (actually the abovementioned 2 different policies). These bounds will help us determine  among others  the necessity of a library such as GMP on some occasions, which in turn has a dramatic impact from a computational point of view.
Anyway, I want you to share with me all possible exceptions you have noticed on hero levelup. An example is the Wisdom exception on Might heroes which occurs every 6 levels. In other words, help me realize what is the current model we have so far on herolevelup. Of course I would like to hear about exceptions for Magic heroes as well. That way, whatever we do (including ANSA) will be (edit: hopefully! EOE) eventually complete.
Thank you all in advance for your help.
 dimis 
____________
The empty set


Xarfax111
Badmannered
Supreme Hero
The last hero standing

posted June 25, 2006 01:31 AM 


All what you peeps do with the skill table iMvhO is leading to
...Naddajadahada.
Why? iMvhO there are NO probabilities at all.
Lets say i made 80 test with a hero classe and in 3 cases i got the same 8 skills. So NO probabilities ...at least iMvhO.
On the other hand you can influence the skilling with the txt. Plus you can influence skilling by taking certain skills.
____________


dimis
Responsible
Supreme Hero
Digitally signed by FoG

posted June 25, 2006 01:51 AM 

Edited by dimis at 02:39, 25 Jun 2006.

I am glad you are here
Quote: All what you peeps do with the skill table iMvhO is leading to
...Naddajadahada.
Why? iMvhO there are NO probabilities at all.
Lets say i made 80 test with a hero classe and in 3 cases i got the same 8 skills. So NO probabilities ...at least iMvhO.
On the other hand you can influence the skilling with the txt. Plus you can influence skilling by taking certain skills.
I will start with the things that I know:
So, you agree that your actions influence the tree! This is exactly what I am saying and for that reason I ask for help on the exceptions. All probabilities one computes for various skills, are related to his preference on skills while levelingup. So what I really want to compute (and thought it was very clear) is exactly the probabilities for certain skills (perhaps also combination of skills) under a specific POLICY by the user. And by the word "policy", I mean an ordering on preference when selecting skills, like what has been proposed above, i.e. the naive ordering or the better (to my opinion) grouping of skills one prefers.
EDIT: Just a clarification. ANSA was an easy problem to solve by the way. In fact the POLICY of the user there does NOT influence the tree. So, probabilities given there are just expected outcomes of an oddly weighted die with 28 different faces (6 or 7 rollouts depending on hero's initial skills). Now, on every other POLICY the user may follow I believe that the tree is influenced (and I mean that I can not think of another policy that does not influence the tree apart from ANSA and I assume there is none because a rejection of a skill while levelingup implies a nonpreference for the specific skill rejected which in turn implies a preference on other skills.) So, from now on, each one of us is going to "feed" a machine with his preference on skills and get as a result the probabilities he wants BASED on his preference, i.e. on his influence on the tree. At least, this is my aim.EOE
Now what I don't know:
What do you mean I can influence the skilling with the txt?
____________
The empty set


maretti
Responsible
Supreme Hero

posted June 25, 2006 05:52 PM 


I think it works like this:
About new skills that you are offered:
You are offered wisdom at lvl 6 if not earlier. Earlier than lvl 6 the chance of getting wisdom is the same as for other skills (means it depends on the number each heroclass has in wisdom, for example knights 3, barbarians 2). If you do not choose wisdom it will be offered again 6 levels later if not earlier.
You are offered a magic skill at lvl 4 if not earlier. Which of the magic skills you will be offered depends on your numbers in the diffrent magic skills). Earlier than lvl 4 the chance of getting magic is the same as for other skills.
If you do not choose the magic skill offered you will be offered magic again 4 levels later if not earlier.
If you choose the first magic skill offered I dont know when you can be sure to be offered magic again but I have had games where it was as late as 1213 levels later.
About improving skills you allready have:
I have heard it mentioned that you have a bigger chance of being offered adv or exp in skills where you have high numbers compared to skills where you have lower numbers but I dont know exactly how it works.
____________
Crag rules, Orrin and Ivor suck



