Leveling-Up in Heroes of Might and Magic III
Dimitrios I. Diochnos Department of Mathematics, Statistics, and Computer Science, University of Illinois at Chicago, Chicago IL 60607, USA diochnos(at)math.uic.edu

Abstract

We propose a model for level-ups in Heroes of Might and Magic III, and give an O 2 ln learning algorithm to estimate the probabilities of secondary skills induced by any policy in the end of the leveling-up process. We develop software and test our model in an experiment. The correlation coecient between theory and practice is greater than 0.99. The experiment also indicates that the process responsible for the randomization that takes place on levelups generates only a few dierent pseudo-random sequences. This might allow exploitation techniques in the near future; hence that process might require reengineering.
Key words: learning, reverse engineering, inverse coupon collectors problem, software reengineering, Heroes of Might and Magic

Introduction

Heroes of Might and Magic III (HoMM) is a turn-based strategy and role-playing video game. It was developed by New World Computing for Microsoft Windows and was released by the 3DO Company in 1999. The game has been popular since its release and there is a big community worldwide. One of the major complaints of the players since the release of the game is that the manual was incomplete; in some cases facts were omitted, in other cases the phrasing was vague, and sometimes the descriptions were simply wrong1. In 2003 3DO went bankrupt, the rights of the game were sold to Ubisoft, and unfortunately, there has never been an update on the manual or answers to questions about mechanisms of the game. Typically players in the online community devise techniques which aim to uncover certain mechanisms, usually through excessive testing. This paper has similar avor. However, we want to minimize time-consuming human testing with the aid of algorithmic techniques. Section 2 has a brief description of the game, some fundamental denitions, and the two major problems related to this paper. Section 3 gives a model regarding a (fundamental from the players perspective) mechanism of the game. Section 4 presents a Monte Carlo approach on learning eciently the probabilities of certain attributes under that model. Section 5 has an experiment with a dual impact. First, we examine how close theory and practice are. Second, we derive quantitative estimates on the number of certain pseudo-random sequences generated by the actual game using the inverse version of the coupon
Research partially supported by NSF Grant CCF 0916708. For example, http://heroescommunity.com/viewthread.php3?TID=17267 has a collection of more than 250 such examples.
primary skill attack defense power knowledge

value 1 1

slot 7 8
secondary skill offense artillery

expertise basic basic

Figure 1: Skills at level 1 for Gurnisson; hero class: Barbarian (mighty hero).
collectors problem. Section 6 gives ideas about future work and extensions to our current opensource software2. Finally, note that a team of enthusiasts, since 2007, is reengineering the game under the title Tournament Edition. Hence, the content of the paper has independent interest since a process of the game that generates randomness might require reengineering for a more balanced game.

A Brief Description of the Game and Related Problems
The game allows from 2 up to 8 players to take part in the game, possibly forming allied teams. Each player rules a kingdom that belongs to one of nine dierent factions; not necessarily dierent. Each kingdom is composed primarily by dierent cities and armies. The goal for each player (or team of players) is to eliminate all the opponents. The army can be split into dierent parts and each part is guided by some hero. There are two classes of heroes per faction, which we call mighty and magic for reasons that will soon be apparent. Hence, we have 18 dierent hero classes. Heroes have abilities, called primary and secondary skills, that mainly reinforce the battles or help in the exploration of uncharted territory. Through victories in battles heroes acquire experience. As more experience is accumulated and certain values are surpassed, heroes gain levels. This leveling-up process typically enhances both the primary and the secondary skills, which, in principle, results in a stronger overall army. There are four dierent primary skills; attack, defense, power, and knowledge. Mighty heroes develop their attack and defense with higher probability, while magic heroes develop their power and knowledge (which are associated with magic spells) with higher probability. Moreover, there are 28 secondary skills, and each hero can acquire and store in dierent slots at most 8 during each game. Secondary skills have 3 dierent levels of expertise: basic < advanced < expert which are obtained in that order. Typically heroes start with two basic secondary skills or one advanced secondary skill, and some low non-negative integer values on the primary skills. We focus on mighty heroes of these two kinds only. We examine the dierent heroes between the starting level 1 and level 23; at level 23 the heroes have 8 expert secondary skills for the rst time. Figure 1 gives an example of the starting conguration for one popular hero of the game that starts with two secondary skills at basic level.
See http://www.math.uic.edu/~diochnos/software/games/homm3/index.php
attack +1 advanced offense basic earth magic Figure 2: Sample level-up dialogue when Gurnisson (see Fig. 1) reaches level 2. The left option is advanced offense; the right is a new secondary skill (basic earth magic).
Every time a hero gains a level, some primary skill is incremented by one; moreover, the user is presented with two secondary skills among which he has to choose one. We refer to the presented options as left and right option since they appear respectively on the left and right part of the users screen. Figure 2 gives an example of the dialogue that is shown on the users screen during a sample level-up. The details that determine the left and right option are given in Sect. 3. Denition 2.1 (Level-Up). Level-Up is the process that determines the pair (primary skill, (left secondary skill, right secondary skill)) which is presented to the user when some hero gains a new level. Figure 2 implies the pair (attack, (offense, earth magic)). The expertise is omitted for simplicity; it is straightforward to be computed. The pair which is presented on every level-up is called level-up oer. An action a A = {left, right} determines which secondary skill is selected on a level-up. A state K on a particular level for a particular hero contains the history of all the level-up oers up to this level, as well as the actions that were performed on every level. Denition 2.2 (Policy [6]). A policy is a mapping (, a) from states K to probabilities of selecting each possible action a A. A policy is called deterministic if there is a unique a A with (, a) = 1 for every K. Otherwise, the policy is called stochastic. Clearly, not all secondary skills have the same importance; dierent secondary skills enhance dierent abilities of the heroes. Since the release of the game there are two main problems that have tantalized the players. Prediction Problem: The rst problem has to do with the prediction of the oered skills during level-ups. We present a model in Sect. 3 and we focus on the secondary skills. Evaluation Problem: The second problem has to do with the computation of the probabilities of acquiring secondary skills by level 23 given the policy the players are bound to follow; see Sect. 4.

A Model for the Prediction Problem
We are now ready to examine a model for the level-ups as this has been formed by observations and testing throughout the years. A crucial ingredient is the existence of integer weights associated with the secondary skills. These weights can be found in the le hctraits.txt. On every level-up the model rst determines the left option and then the right.
The Basic Mechanism on Secondary Skills

We have two subcases.

Case A: The hero has at least one free slot.
1. At least one of the secondary skills the hero currently has is not expert. On the next level-up the hero will be oered an upgrade of one of the existing secondary skills as the left option, while the right option will be a secondary skill the hero does not already have. 2. All the secondary skills the hero currently has are expert. On the next level-up the hero will be oered two new secondary skills. Case B: The hero does not have a free slot. We have three subcases. 1. The hero has at least two secondary skills not expert. On the next level-up the hero will be oered two dierent choices in order to upgrade one of the secondary skills that are not expert. 2. The hero has only one secondary skill not expert. On the next level-up the hero will be oered only this secondary skill upgraded. 3. All 8 slots of the hero are occupied by secondary skills at expert level. No secondary skills will be oered on level-ups from now on.
Presenting Secondary Skills on Level-Ups at Random
It is unclear who discovered rst the data of the le hctraits.txt and how. However, these weights appear in forums and various pages about the game for many years now. The interpretation is that the weights are directly related to the probability of acquiring a specic (left, right) secondary skill oer during a level-up. In particular, consider a set S of secondary skills, and to each s S we have a weight ws associated with it. We say that a secondary skill s is presented at random from the set S and we imply that s is selected with probability Pr (selecting s) = ws

s S ws

We implement (1) the usual way; i.e. a pseudo-random number generated on run-time is reduced mod s S ws , and then an ordering on secondary skills determines which s S is selected. In principle we have two sets of secondary skills that we are interested in; the set A of secondary skills the hero already has but are not expert, and the the set U of the secondary skills that the hero does not have in any of his slots.
Two Groups of Secondary Skills Appear Periodically
Two groups of secondary skills appear periodically and hence the randomized scheme presented in Sect. 3.2 is not always applied on level-ups; the limitations of Sect. 3.1 are always applied. These two groups are: The Wisdom group which is composed by one secondary skill; wisdom.
The Magic Schools group which is composed by the secondary skills air magic, earth magic, fire magic, and water magic. Let TWisdom be the period for the Wisdom group, and TMagic be the period for the Magic Schools group. Hence, every at most TWisdom level-ups, if the hero does not have expert wisdom, wisdom will be oered; as basic if wisdom does not appear in one of the slots (and clearly there is at least one empty slot), otherwise as an upgrade of the current expertise. Similarly, every at most TMagic level-ups a secondary skill from the Magic Schools group has to appear. We refer to these events respectively as Wisdom Exception and Magic School Exception; i.e. exceptions to the randomized scheme of Sect. 3.2. When these two exceptions coincide on a particular levelup, then Wisdom is treated rst; if necessary, Magic School Exception propagates to the next level-up. Hence it might take TMagic + 1 level-ups until Magic School Exception is applied; read below. The model rst determines the left option and then the right option. Hence, the model rst attempts to apply the Wisdom Exception on the left option, and if this is impossible (e.g. Case A1 of Sect. 3.1 but the hero does not have wisdom in any of the slots) then the model attempts to apply the Magic School Exception on the left option (which might be impossible again). If the above two steps do not yield a solution, then the randomized scheme of Sect. 3.2 determines the left option. The model then works in the same fashion in order to determine the right option. Note that each exception can be applied in at most one of the options on every level-up. For mighty heroes it holds TWisdom = 6 and TMagic = 4.

The Leveling-Up Algorithm
Algorithm 1 gives the overall prediction scheme by incorporating the descriptions of Sects. 3.1, 3.2, and 3.3. There are four functions of primary interest during the level-ups since they handle randomness. RndNew returns a secondary skill at random from the set U. RndNewMagic returns a secondary skill at random from the set of Magic Schools that the hero does not already possess. RndUpgrade returns an upgrade of a secondary skill at random among the skills the hero has but not at expert level. RndUpgradeMagic returns an upgrade of a Magic School secondary skill at random. Clearly, if there are two calls on the same function on a level-up, then, the skill that appears due to the rst call is excluded from the appropriate set in the computations of the second call. The function WisdomException returns true if at least TWisdom level-ups have passed since the last wisdom oer and the hero does not have expert wisdom. Similarly, MagicException returns true if at least TMagic level-ups have passed since the last oer of a Magic School and the hero does not have all the Magic Schools (with non-zero weight) at expert level. In any other case these two functions return false. HasWisdomToUpgrade returns true if the hero has wisdom in one of the slots but not expert, otherwise false. Similarly, HasMagicToUpgrade returns true if the hero has at least one Magic School not expert in one of the slots, otherwise false. HasWisdom returns true if the hero has wisdom in one of the slots, otherwise false. CanAcquireMoreSkills returns true if the hero has at least one empty slot, otherwise false. MagicSkillsAreAvailable returns true if there are Magic Skills with nonzero weight that the hero does not already possess, otherwise false. AllMagicAreExpert returns true if all the Magic Schools the hero has are expert, otherwise false. HasFreeSlots returns true if the hero has at least 1 slot empty, otherwise false. Finally, NumberOfSkillsToUpgrade returns the number of secondary skills that occupy one of the heros slots but are not expert. 5
Algorithm 1: Determine Skills on a Level-Up. Input: Appropriate amount of experience points to gain a level. Output: A level-up oer. 1 level level + 1; 2 primary GetPrimarySkill (); 3 if AllSecondarySkillsExpert () then 4 if not HasFreeSlots () then return (primary, (null, null)); 5 if HasWisdom () then 6 if MagicException () and MagicSkillsAreAvailable () then 7 left RndNewMagic (); 8 else left RndNew (); 9 right RndNew (); 10 else 11 if WisdomException () then 12 left wisdom; 13 if MagicException () and MagicSkillsAreAvailable () then 14 right RndNewMagic (); 15 else right RndNew (); 16 else 17 if MagicException () and MagicSkillsAreAvailable () then 18 left RndNewMagic (); 19 else left RndNew (); 20 right RndNew (); 21 else 22 if WisdomException () and HasWisdomToUpgrade () then 23 left wisdom; 24 else if MagicException () and HasMagicToUpgrade () then 25 left RndUpgradeMagic (); 26 else left RndUpgrade (); 27 if CanAcquireMoreSkills () then 28 if WisdomException () and not HasWisdom () then 29 right wisdom; 30 else if MagicException () and MagicSkillsAreAvailable () and (AllMagicAreExpert () or WisdomException () ) then 31 right RndNewMagic (); 32 else right RndNew (); 33 else if NumberOfSkillsToUpgrade () > 1 then 34 if WisdomException () and MagicException () and HasMagicToUpgrade () then right RndUpgradeMagic (); else right RndUpgrade (); 37 else right null; 38 return (primary, (left, right));

Evaluating Policies

We resort to a Monte Carlo approach (Theorem 4.3) so that we can compute eciently the probabilities of acquiring secondary skills by level 23 given any policy with bounded error and high condence. Proposition 4.1 (Union Bound). Let Y1 , Y2 ,. , YS be S events in a probability space. Then S S Pr j=1 Pr Yj. j=1 Yj Proposition 4.2 (Hoeding Bound [3]). Let X1 ,. , XR be R independent random variables, each taking values in the range I = [, ]. Let denote the mean of their expectations. Then 1 e2R /(). Pr R R Xi i=1 Theorem 4.3 (Monte Carlo Evaluation). We can compute the probabilities of secondary skills induced by any policy using O 2 ln simulation runs such that the aggregate error on the computed probabilities is at most with probability 1 . Proof. Let Xi be the indicator random variable that is 1 if the secondary skill j appears in the i-th run while following a policy , and 0 otherwise. After R simulation runs, any skill j has (j) 1 been observed with empirical probability pj = R R Xi. We apply Proposition 4.2 to each i=1 pj with = 0, = 1, = /28, we require to bound the quantity from above by /28, and solve for R. We get R
. Let Yj be the event that pj is not within /28 of its true value /28 for every skill j. None of these bad events Yj

28 j=1 Yj

j. The above analysis implies Pr Yj will take place with probability 1 Pr 1

28 j=1 (/28)

. By Proposition 4.1 this quantity is at least
= 1 . We now sum the errors of all the 28 computed probabilities.

An Experimental Study

In 2006 a player named Xarfax111 suggested that the number of dierent sequences of secondary skill oers is actually fairly limited. An experimental study was conducted in order to verify the validity of the claim as well as test the eectiveness of the model. The experiment consisted of 200 tests with Crag-Hack (mighty hero, class: Barbarian). CragHack starts with advanced offense but has zero weight on two secondary skills (one of which is a skill from the Magic Schools group) and hence these two can not be obtained. During the rst 7 level-ups the new secondary skill that appeared was picked in every case, thereby lling all 8 slots of the hero by level 8; hence, all 8 secondary skills that appear in level 23 are determined by level 8. We call this policy AR (Always Right) since the user selects the (new) secondary skill that appears on the right of every level-up oer. Later in this section we examine estimates on the amount of dierent right sequences generated by the game; all imply expected values of at most 256. Note that the model allows more. For example, if we consider the cases where a Magic School appears every 4 levels and wisdom every 6 levels due to exceptions (see Sect. 3.3), and allow only very heavy skills (with weights equal to 7 or 8) in between, there are 3 = 7, 560 dierent ordered combinations of new secondary skills until level 8. A similar calculation allowing all possible skills in between gives 7, 325, 640 dierent combinations. Out of the 200 tests, only 128 yielded dierent sequences of new secondary skills; 76 sequences occurred once, 33 sequences occurred twice, 18 sequences occurred three times, and 1 sequence 7

1 0.95 0.9 0.85 0.8 0.75 0.7 expected 200 128

probability

0.65 0.6 0.55 0.5 0.45 0.4 0.35 0.3 0.25 0.2 0.15 0.1 0.27 28

secondary skill

Figure 3: Probabilities of secondary skills; Crag-Hack, AR policy. The boxes indicate the expected values based on Sect. 3, the +s present the values computed on all 200 tests, while the s present the values computed on the 128 dierent sequences. The secondary skills are shown in lexicographic ordering; i.e. 1: air magic, 2: archery, etc. Note that 28: wisdom and in every test wisdom was oered by at most level 6. occurred four times. Figure 3 presents graphically the probabilities of the secondary skills in three cases; the expectations according to the model, the values as these were recorded on the 200 tests, and the values when we consider only the 128 distinct sequences. The correlation coecient between the expected probabilities and the ones computed empirically after 200 tests was 0.9914. Moreover, the correlation coecient between the expected probabilities and the ones formed by the 128 unique sequences was 0.9946. We now turn our attention to the second part of the experiment. We want to estimate the amount of dierent sequences of new secondary skills that appear when we follow this policy up to level 8 based on our observations on the collisions of the various sequences. This problem is essentially the inverse version of the Coupon Collectors Problem, and is well studied in Statistics; see e.g. [1, 2]. We will follow the simple route of working with expectations, assume equal selection probability for each coupon, and in the end we will arrive to the same formula for prediction as in [1]; see also [5, Sect. 3.6]. Let HN be the N-th harmonic number. The expected time Ti to nd the rst i dierent coupons is given by

j=Ni+1

Ni j=1

N = N(HN HNi ). j

Lemma 5.1. Let N 3 and k be xed such that k {2, 3,. , N 1}. Then, the quantity Q(N) = N (HN HNk ) is monotone decreasing.
Proof. We want Q(N) > Q(N + 1) or equivalently N N+1 + N+1k > HN+1 HN+1k. N+k kN However, HN+1 HN+1k = i=N+2k i < N+2k. It suces to show (N+1)(N+1k) > k N+2k ,
which holds since k > 1. 8
240 upper bound lower bound maximum likelihood new sequences

sequences

Figure 4: New sequences and estimates on the amount of dierent sequences. The history of the 128 dierent sequences of new secondary skills is shown with a thick solid line in Fig. 4. Let Di be the number of dierent new secondary skill combinations that have occurred on the i-th test. Working only with expectations we want to use (2), set Ti = Di , and solve for N. This is precisely the solution asserted by the maximum likelihood principle. Typically, this is a oating point number; both the oor and the ceiling of that number are candidates for the solution; see [1]. We draw the average of those candidates with a thin solid line in Fig. 4. In order to get a better picture we apply Lemma 5.1 and calculate all the values of N such that Ti [Di 0.5, Di + 0.5); note that Ti rounded to the closest integer is equal to Di. We get a lower and upper bound on the above mentioned values of N and we plot them with dashed lines in Fig. 4. Another heuristic estimate can be obtained by looking at the ratio (x, t) = x (t) = new sequences found in the last x tests. x (3)

We use the ratios x (200) for x = 10, 20, 40, and 80 as heuristic approximations of the true probability of discovering a new sequence at test t = 200. All four of them lie in the interval [0.4, 0.5] which implies an estimate of 213 N 256 dierent sequences in total.

A Glimpse Beyond

All the estimates of Sect. 5 are interesting since they are at most 256; a single byte can encode all of them. Quite recently (2009), a player named AlexSpl has developed similar software3 and according to the descriptions we have4 there are 255 dierent cases to be evaluated; there is a description of the random number generator too. Our model and AlexSpls description dier in the function RndUpgradeMagic of Sect. 3.4 where AlexSpl suggests treating all the
http://heroescommunity.com/viewthread.php3?TID=27610 http://heroescommunity.com/viewthread.php3?TID=17812&pagenumber=12
participating skills with weights equal to 1. Compared to our 0.9914 and 0.9946 values for the correlation coecient in the experiment of Sect. 5, AlexSpls approach achieves 0.9959 and 0.9974 respectively. AlexSpls software is not open-source, and there is no description about his method on attacking the problem. In any case, we embrace relevant software; at the very least it promotes more robust software for everyone. Both Sect. 5 and AlexSpls description imply a small space to be explored in practice. This suggests techniques of exploitation that will allow us to predict most, if not all, sequences online after a few level-ups, at least for a few popular heroes and policies followed in tournaments. Unfortunately, this will greatly reduce the fun and the luck factor of the real game! This is why reengineering is needed. Coming back to our approach, perhaps the most important thing is to extend the current implementations and compute probabilities for magic heroes too. Another important extension is the computation of the probabilities for all the intermediate levels. Moreover, there are policies closer to tournament play which have not been implemented yet. In addition, we would like to ask questions such as what is the probability of acquiring (tactics air magic offense) (earth magiclogistics) under various policies ? Some work has been done (ansaExtended); however, it is not part of the Monte Carlo approach. Also, parallelize the computations with the inclusion of a library such as [4]. Finally, is there a simpler alternative for Algorithm 1 of Sect. 3.4? There are certainly exciting times ahead of both the developers and the players. We are eagerly looking forward into that future! Acknowledgements. The author wants to thank the participants in the thread http://heroescommunity.com/viewthread.php3?TID=17812; a special thanks to Ecoris for his tests and techniques. His insight will aect future work for sure. Finally, the author thanks Gyrgy Turn for fruitful discussions, and the referees for their o a insightful comments.

References

[1] B. Dawkins. Siobhans Problem: The Coupon Collector Revisited. The American Statistician, 45(1):7682, 1991. [2] B. Efron and R. Thisted. Estimating the Number of Unseen Species: How Many Words Did Shakespeare Know? Biometrika, 63(3):435447, 1976. [3] W. Hoeding. Probability Inequalities for Sums of Bounded Random Variables. Journal of the American Statistical Association, 58(301):1330, 1963. [4] M. Mascagni. SPRNG: A Scalable Library for Pseudorandom Number Generation. In Parallel Processing for Scientic Computing, 1999. [5] R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995. [6] R.S. Sutton and A.G. Barto. Reinforcement Learning: An Introduction. MIT Press, 1998.

On the oered skills in Heroes of Might and Magic III

dimis January 6, 2008

Abstract In this document I will try to describe, to the best of my knowledge, the work and the results that are available online on problems related to the oered skills while leveling up a hero in HOMM-III. A new result is presented in section 4.4 as well as two unied tables with probabilities for hero classes; namely tables 3 and 4. Those that are interested in the problem might want to have a look on [9] which deals with a similar problem but is not within the scope of the document.

Instead of introduction

I guess everyone who reads this document is familiar with the game Heroes of Might and Magic III (HOMM-III for short). If not, details are given in section A in the appendix. I will summarize, to the best of my knowledge, the work and the results that are available online about matters regarding skills, and skills oered during level-ups. For me everything started with the thread Heroes Stats and Skills Chances [11]. In that thread some weight tables were presented and are these weights that inuence the skills that appear during level-ups. The way the weights are used for determining the oered skills is presented in section 2. Since we are dealing with a weight table, it is inevitable that we have some sort of randomness. However, practice indicates that heroes might get exactly the same skills as in a previous game. Therefore, the weight table alone is simply not enough to justify skill-advancing given that the implied state-space is huge [3]. That extra information we need is a model on how things work. More on that can be found in section 2. However, before I proceed I need a denition which is central throughout the document. Denition 1.1. Skill-advancing or (abusively) level-up is the process in which a hero gains one or more new skills.
Why is it important to know about skill-advancing?
Perhaps the most signicant part of the game is actually played on the way you level-up your (main) hero. The time that you accept or refute certain skills has an impact until the end of the game. And basically, all end-ghts (as well as all previous ghts against the map) are judged by the skills the main heroes have at that moment. Hence, the development of the heroes is News! the most crucial part of the game. This gives us a motive to spend our time with problems related to skill-advancing. 1
How do we know about the weight table and the model?
The weight table can be found in le hctraits.txt which is located in a bigger container le h3bitmap.lod. It is unclear who discovered it rst, or if it was discovered due to a leak by someone working at 3DO during the early days of the game. Regarding the model, the situation is more complicated. What we know about the model comes from careful observations while playing, and there are ways in which we validate or refute our understanding of the model. More on that will appear in section 2.

Questions and problems

There are two main goals. The rst one has to do with our understanding on the oered skills while leveling up a hero; i.e. what other parameters apart from the weight table inuence the oers the user faces. The other one has to do with evaluating the strategy the user follows while selecting specic skills and refuting others, i.e. computing the probability specic skills (or all of them) have under a specic strategy. The work that has been done in both directions will be presented in the subsequent sections.
The model and how it works
A recurring theme in Computer Science is the use of weight tables in decision problems. The idea is that weights on options generate non-uniform probability distributions and usually more interesting problems. Lets see an example: Example 1 (Biased Coin). We have a biased coin and a weight function w : {H, T } N which expresses this bias. Let w(H) = 3 and w(T ) = 1. The respective weight table is: option Head Tails weight 3 1
The important thing is the way you can compute the probability of each outcome. The most common way of doing so, is by dividing the weight of the option of interest by the sum of weights w(H) of all available options. Hence, the probability that Head occurs is: Pr[H] = w(s) =

s{H,T }

w(H) w(H)+w(T)

Similarly, Pr[T ] =

This is the way the weights are used in HOMM-III. Another way of using weights is by softmax selection methods which usually imply Boltzmann-Gibbs distributions [12]. However, this idea was refuted in [7]. So far, most of the work that has been done, focuses on mighty heroes since these heroes are preferred in human games. The only attempt that I know so far which focuses on magic heroes as well, is [10]. However, the project is incomplete and very limited results are available.
The basic mechanism on oered skills
Each time a hero acquires a new level he is presented with two skills. The rst (left) option will be a skill that he has already obtained but is not at Expert level so far. The second (right) option will be a skill that he has not already obtained. Example 2. Assume that you have a Barbarian who already possesses Advanced Oense and Basic Tactics and is about to acquire a new level. During this level-up, the left oer will be either Expert Oense or Advanced Tactics and nothing else. The right oer, can be any other skill apart from Oense and Tactics which have already been obtained, as well as Necromancy and Water Magic, both of which are skills that Barbarians cant learn. The reason that Barbarians cant get either Necromancy or Water Magic is justied in section 2.2. Concluding, in order to give an example, one possibility in this level-up could be the pair Expert Oense and Basic Fire Magic. Remark 2.1. In order to ll in the gaps, lets see what other possibilities are there. The hero might have already upgraded the existing skills at Expert level and has at least one slot available for a new skill. Then, both skills that are going to be oered are (dierent in between) skills that have not been already acquired by the hero. Another option is that the hero might have already obtained 8 dierent skills and at least two are not at Expert level. In this case, the hero will be presented with 2 dierent skills for upgrade; i.e. no new skill. Finally, if the hero already possesses 8 skills and 7 of them are at Expert level, then he will be presented with a single option; i.e. upgrade the only skill that is not at Expert level so far. Of course, once all 8 skills reach Expert level, the hero is no longer oered any skill on each subsequent level-up. This basic mechanism gives a rough overview of the procedure of skill-advancing. What is missing is a way of computing the probabilities for various skill-oers. This is the topic of the following paragraphs.

The weight tables

The weight tables which were presented in [11] and are used by default in the game are tables 1 and 2. Table 1 describes the weight distribution on the various skills for mighty heroes, while table 2 which deals with magic heroes is presented for completeness, since, as it has already been stated, no worth-mentioned results have been obtained while focusing on magic heroes. Remark 2.2. The sum of all weights for each hero class is equal to 112. It is unknown why this number was picked by the designers of the game. In [13] this is falsely interpreted as:. you will be oered skill choices (not only new ones, but to advance and expertise in a skill) 112 times before you cannot learn skills any further! The statement is false based on the facts presented in section 2.1; no need for weight tables! Remark 2.3. In [7] it is stated that by setting the weight values for specic skills greater than or equal to 128, then these weights are treated like zeros (0).
Hero Class Death Knight Planeswalker Beastmaster Barbarian Alchemist Demoniac Overlord
Air Magic Archery Armorer Artillery Ballistics Diplomacy Eagle Eye Earth Magic Estates Fire Magic First Aid Intelligence Leadership Learning Logistics Luck Mysticism Navigation Necromancy Oense Pathnding Resistance Scholar Scouting Sorcery Tactics Water Magic Wisdom

Knight

Table 1: The weight table for mighty heroes.

Ranger 3 2

Hero Class Necromancer Elementalist Battle Mage Warlock

Cleric

Table 2: The weight table for magic heroes.

Wizard

Heretic

Some extra details

There are two more results from [7] which have not been presented so far. Remark 2.4. If the hero has a skill at basic or advanced level weighing 0, it is treated as 1 when an upgrade oer is to be selected. Otherwise it is (of course) treated as 0. Remark 2.5. 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 oer. The skill is oered 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 oer. Corollary 2.6. Hence there is a notable dierence: In the latter case a random number in the sequence is actually skipped compared to the rst case. 2.2.2 Basic ingredient: the weighted die

Lets see an example of the idea that is presented in this section. There is nothing new; everything has been presented in [3] and [11]. Example 3. Assume that you have a Barbarian who has already obtained Advanced Oense and Basic Tactics and is about to acquire a new skill. How can you compute the probability of any possible combination of skill-oers? In particular, what is the probability that this hero will be oered Expert Oense and Basic Fire Magic in this level-up? The answer comes in two parts. First, the left oer has to be a skill that has been already attained since not all of them are at Expert level. The probability that Oense has to appear w(Oense). Based on table 1 we have that Pr[Oense] = 10 = 5. Second, the is w(Oense)+w(Tactics ) right oer has to be a skill not already obtained, since the hero has free slots for additional skills. Let S be the set of all skills not already obtained by the hero; i.e. all of the skills apart from Oense and Tactics. Then by table 1, w(S) = sS w(s) = 94. Therefore, the probability that Fire Magic is oered as a new skill is Pr[Fire Magic] = 94 = 47. Hence, the probability that this hero will be oered Expert Oense and Basic Fire Magic in this level-up, 1 is Pr[Oense] Pr[Fire Magic] = = 423. The above example presents what is the so called weighted-die idea due to the resemblance of computing the probabilities with the outcome of an oddly-weighted die (biased coin with many sides if you prefer). However, experience with the game provides indications that this is not very accurate. The main reason is that the above description actually implies a huge number of possible combinations of skill-oers. On the other hand, players typically experience identical (not similar ) level-ups in their games. This is a very strong indication that something is missing.
Forming a model: Allowing exceptions
In fact there are some rules which prune a lot the number of possible combinations on skilladvancing. We call such rules as exceptions (to the general rule). The weighted die idea is the general rule on skill-advancing, and exceptions force specic skills to appear here and there on level-ups. There are two kinds of exceptions: 6

exception :

exception : A hero can not wait for more than 6 levels so that Wisdom is oered
to him; either as a brand new skill or as an upgrade. Remark 2.7. In [8] a method is described that re-discovers the exceptions dened above. Moreover, it is shown that it is almost certain that these are the only exceptions in the model. Corollary 2.8. Heroes that are allowed to get only 3 out of the 4 Magic Schools are able to get all those 3 Schools by simply accepting each oer that is made on Magic Schools. Corollary 2.9. Barbarians, Beastmasters, Overlords, and Rangers are able to get Expert Earth Magic always.
A hero can not wait for more than 4 levels so that a Magic School is oered to him; either as a brand new skill or as an upgrade of an existing one.
Remark 2.10. Note that Magic and Wisdom exception, reduce a lot the number of possible combinations of skill sequences. Still, alone this information is not enough. I ll come back to this problem at a later section. Example 4 (Sample Crag-Hack skill-advancing). Lets see an example from actual leveling-up. level left oer right oer Expert Oense Basic Tactics Expert Oense Basic Fire Magic Advanced Tactics Basic Pathnding Expert Tactics Basic Pathnding Basic Wisdom Basic Ballistics Advanced Wisdom Basic Earth Magic Advanced Earth Magic Basic Ballistics Expert Earth Magic Basic Resistance Advanced Wisdom Basic Archery Expert Wisdom Basic Scouting Basic Logistics Basic Leadership Advanced Logistics Basic Air Magic Expert Logistics Basic Scholar Basic Eagle Eye Basic Archery Advanced Archery Basic Scouting Expert Archery Basic Air Magic Advanced Air Magic Basic Ballistics Expert Archery Basic Eagle Eye Expert Air Magic Basic Learning Basic Scouting Basic Armorer Advanced Armorer Expert Armorer primary Defense Attack Spell Power Attack Defense Attack Attack Defense Attack Knowledge Defense Knowledge Spell Power Attack Spell Power Defense Knowledge Defense Attack Spell Power Attack Attack
As expected, Crag-Hack is oered a Magic School before he exceeds level 4; Fire Magic at level 3. Moreover, at level 6 he is oered Wisdom due to the Wisdom exception. Note that a Magic School oer is made at most every 4 levels; e.g. Air Magic at levels 17, 18, and 20. 2.3.1 Handling collisions
Note that it is possible for the above exceptions to coincide at some level. In [3] (posts 7 and 8 at page 2) it has been shown (with high probability: > 0.999999) that when the above exceptions coincide at some level, Wisdom exception has higher priority over Magic exception; meaning that if you are supposed to be oered a Magic School and Wisdom at a specic level, you will be oered only Wisdom and on the very next level you ll get a Magic School. Example 5 (Advancing Crag-Hack with collision). Reload the previous position and try again: level left oer right oer Expert Oense Basic Tactics Basic Archery Basic Resistance Advanced Archery Basic Fire Magic Advanced Archery Basic Ballistics Expert Archery Basic Wisdom Advanced Fire Magic Basic Diplomacy Expert Fire Magic Basic Tactics Basic Armorer Basic Scouting Advanced Armorer Basic Logistics Advanced Armorer Basic Artillery Advanced Logistics Basic Wisdom Expert Logistics Basic Earth Magic Advanced Earth Magic Basic Mysticism Expert Logistics Basic Leadership Expert Earth Magic Basic Artillery Expert Armorer Basic Artillery Basic Wisdom Basic Pathnding Advanced Pathnding Basic Eagle Eye Expert Pathnding Basic Air Magic Expert Pathnding Advanced Air Magic Expert Pathnding Expert Air Magic Expert Pathnding primary Defense Attack Spell Power Attack Defense Attack Attack Defense Attack Knowledge Defense Knowledge Spell Power Attack Spell Power Defense Knowledge Defense Attack Spell Power Attack Attack

Note that due to the Wisdom exception, Crag-Hack is oered Wisdom at level 6, and since it was rejected, again at level 12. However, note that at level 8 he was also oered Fire Magic, hence a Magic School should appear in the following 4 level-ups; i.e. in the worst case by level 12. However, since at that level only one new skill can be oered, and since Wisdom exception has higher priority over Magic exception, we see that Wisdom is oered at level 12 and Earth Magic at level 13. 8
Remark 2.11. Inspecting examples 4 and 5 one can see that the primary skill advancement is identical. This was implied but I am not sure if it was clear in [7]. Your selections on (secondary) skills do not inuence primary skill advancement once the game starts.
Problems that interest players
Of course the mechanism that decides the oered skills is important for game playing. But the most interesting questions w.r.t. skill-advancing deal with computing the probabilities that specic skills have to appear for certain heroes. A technical word which is used in [3] and will be used in this document as well is the word policy. Denition 3.1. Policy is the strategy followed by the user when selecting specic skills on level-ups while refuting other skills. The term comes from the area of Machine Learning; [12]. Obviously the probabilities that specic skills have to appear depend on the policy the user follows. Hence, the answers (probabilities) vary as the policies vary even on the same heroes. So far work has been made on the following (deterministic) policies: Denition 3.2 (AR or ANSA). This is the Always Right policy; i.e. the user always picks the right oer (new skill). Initially, this policy was named as ANSA from the initials of the words Always New Skill Advancement. Both terms are used although AR should be slightly preferred. Of course this is a silly policy when playing the game. However, it has some useful properties that allow testing. Denition 3.3 (AL). This is the Always Left policy. The user constantly picks the left oer; i.e. upgrades already possessed skills to Expert level and on the following level picks the left oer that is made. This policy is much closer to real games than the previous one. However, there is still one silly step. In particular, when the user is presented with two new skills (Basic level) he blindly selects the left oer. Still, this policy has some useful features as well for testing the model. There are two more interesting policies where actual work and results are provided. Denition 3.4 (ALTP). This policy is a variation from the one above. The initials come from the words Always Left Then Preference. In other words, this time, the silly step described above is omitted. Now the user declares a strict preference of skills and the skill selection is based on that preference. Denition 3.5 (SPOU). The term comes from the initials of the words Seek Preference Otherwise Upgrade. In a manner similar to ALTP the user declares a linear ordering on his preference on skills. Then, as soon as one of the top 8 skills appears as an oer, that skill is selected by the user, otherwise an already obtained skill is upgraded. Other interesting policies are under consideration. Perhaps the most signicant one is an idea due to maretti which is based on groups of skills [3]. However, so far, no policy apart from the four described above is currently implemented or concrete results are available.

Implementation and Results.
The main problem among most policies is the state-space that is induced by them; i.e. in most of the cases the model implies a huge amount of dierent combinations that have to be evaluated. However, the AR policy implies relatively few combinations of skill oers w.r.t. the computing power of modern computers; hence brute force search can compute exactly the correct values implied by the model. For the rest of the policies, where brute force computation is impossible, results reside on Monte Carlo algorithms at the moment. Lets see briey what has been done.

AR policy

In [4] it has been shown that the problem of computing the probabilities that various skills have for any hero under this policy is tractable with brute force computations. Overall results for various hero classes are shown in table 3. Note that the numbers presented in the table are the averages among all heroes in each class. For comparison purposes, heroes that start with a certain skill, while others do not, are excluded from computing those averages. Detailed results for each hero are also available in [4] which is the home of this solver. In that same post examples are given so that someone can replicate the results in his/her own computer. Example 6 (Averages on table 3). Consider the entry on Archery on Barbarians. Since Jabarkas starts with Archery he is excluded from the average computations. Hence, 31.89 which is the number presented in table 3, is the average probability (%) for all other Barbarians. However, since all Barbarians start with Oense, it is reasonable to take into account all of them. For this reason that entry on Barbarians is 100%. Initially the problem was solved with the use of the gmp1 library which allowed the use of fractions and hence innite precision in computations. However, since the number of all combinations is relatively small, it can be shown that double precision arithmetic suces for exact computations up to at least 4 decimal digits. As a result, all arithmetic operations can be done with fast registers and hence this is the program that is used nowadays in order to compute results for specic heroes. Moreover, this observation made it easy to transfer the program under Windows without the need of external libraries. Hence, if you want the program (source code and executable) make sure you download it from the link found in the paragraph Double Precision Arithmetic and Windows 32-bit Portability in [4]. Finally, similar results can be obtained with the program found in [5]. 4.1.1 More delicate questions

Under the paragraph Extending Computations in [4] you can nd the program ansaExtended. This program allows the users to ask questions about the probabilities specic combinations of skills have under the AR policy. Explanations about the questions the user is allowed to ask, as well as the syntax, and sample executions are given in that same paragraph.
GNU Multi-precision arithmetic library. Home: http://gmplib.org/
46.91 22.29 33.53 18.18 26.21 13.90 13.90 36.15 18.18 12.70 9.44 18.27 13.90 40.18 26.21 9.44 18.61 13.90 0.00 26.23 18.18 22.37 13.56 18.25 13.97 18.25 24.75 100.00
43.24 31.89 27.85 35.60 35.60 5.14 10.08 43.24 10.08 29.66 5.14 5.14 23.70 19.36 31.79 14.82 14.82 10.08 0.00 100.00 35.60 27.97 5.14 35.60 5.14 35.60 0.00 100.00
19.19 31.26 100.00 34.91 31.20 5.03 5.03 54.40 5.03 0.00 27.31 5.03 23.35 18.97 34.89 9.86 9.86 34.89 0.00 23.35 34.91 23.35 5.03 31.26 5.03 27.31 37.32 100.00
25.21 24.03 24.12 24.12 32.19 10.24 19.64 47.55 0.00 12.96 0.00 24.03 0.00 19.74 24.03 5.22 19.64 35.97 100.00 32.24 19.64 24.12 10.24 19.64 19.64 24.12 36.74 100.00
25.39 28.56 31.81 24.23 32.20 19.68 15.08 36.97 15.08 47.81 10.26 10.26 15.08 19.68 43.13 10.26 10.26 19.68 0.00 35.94 19.68 28.52 10.36 24.11 15.08 28.52 13.07 100.00
36.41 23.59 23.49 23.49 35.10 19.11 9.95 24.95 27.56 12.82 9.95 5.07 100.00 19.11 23.41 14.63 9.95 35.10 0.00 31.43 19.11 23.41 5.07 19.11 5.07 31.43 47.19 100.00
19.18 27.09 27.09 34.66 30.94 14.39 9.78 54.38 18.81 37.30 4.98 4.98 35.55 18.81 34.58 4.98 14.39 18.81 0.00 33.50 23.04 27.19 5.04 23.17 9.78 41.24 0.00 100.00
25.09 35.45 23.66 35.64 35.45 10.06 10.06 36.58 15.19 36.58 5.13 5.13 14.80 35.57 35.53 10.06 14.80 23.66 0.00 38.41 27.78 10.06 5.13 27.78 5.13 35.98 25.09 100.00
16.91 34.54 34.72 27.08 18.82 18.99 9.79 47.98 9.79 0.00 14.40 9.79 27.69 18.82 23.17 27.17 14.40 14.40 0.00 23.17 30.99 37.53 4.99 30.93 9.79 23.05 47.98 100.00
Table 3: Average probabilities (%) for mighty heroes classes under AR (ANSA) policy.

Ranger

AL policy
This is the rst policy that has been encountered in [5]. Similarly to the AR policy, table 4 presents the probabilities on average for each hero class when someone follows the AL policy. Again, in cases where one or more heroes start with a specic skill, while others in the same class do not, are excluded from computing those averages; see example 6. Results are based on a Monte Carlo method implemented in [5] and were computed with 10, 000, 000 runs (episodes). Note that now that it takes longer for the 8 skills to be formed, the impact of the exceptions is more evident. Probabilities for available Magic Schools in each hero class increase, while the probabilities for all other skills decrease. Detailed results for each hero in each class can be found in [6] which is based on [5].

ALTP and SPOU policies

These are two other policies that are implemented in [5]. Note, that under these policies the user must dene a strict preference on skills. Therefore, for each possibility on skill preferences the results for each hero change. Hence, it is no longer possible to create tables like 3 and 4. However, there are detailed instructions and examples in [5], so that someone can compute the probabilities that interest him.

On the validity of the results
So far there have been two (indirect) attempts on validating the theoretical results implied by the model. These two are [2] and [14]. Unfortunately, [14] seems to be incomplete. However, [2] boosted our level of condence on validating the results. In fact, the statistical correlation between the theoretical values computed by the model and the values obtained through experimentation is 0.995. Finally, a very good source of testing level 1 to level 2 skill oers is that of Binabik in [1].
But is the model correct?
This is a question that is yet to be answered although some steps have been made towards this direction. The main problem is that the company who created the game has been dissolved. This makes it almost impossible for someone to have access to the original source code of the game. One way of attacking the problem would be directly with the use of decompilers and careful study of the assembly code. The other way, is trying to gure out a model for the behavior of the game and verifying (with high probability) the model with as limited experimentation as possible. This is the approach that has been followed so far.

Interesting results.

Everyone with some experience on the game could observe peculiar behavior in many cases. Random events occurred repeatedly while reloading saved positions. Several guesses have been proposed so far (page 5 in [3]) so that they can justify the strange behavior that is encountered. No denite conclusions have been drawn. 12
Hero Class Death Knight Planeswalker 39.41 30.70 20.33 30.88 30.70 8.58 8.58 51.98 13.01 51.98 4.36 4.36 12.64 30.82 30.77 8.58 12.64 20.33 0.00 33.27 23.91 8.58 4.36 23.91 4.36 31.22 39.41 96.29 Beastmaster Barbarian Alchemist Demoniac Overlord
63.28 19.13 29.01 15.55 22.54 11.86 11.86 54.83 15.55 23.62 8.04 15.63 11.86 34.90 22.54 8.04 15.93 11.86 0.00 22.55 15.55 19.20 11.56 15.61 11.93 15.61 42.14 92.30
64.87 26.98 23.45 30.18 38.91 4.26 8.37 64.87 8.37 52.73 4.26 4.26 19.90 16.19 26.87 12.35 12.35 8.37 0.00 100.00 30.18 23.58 4.26 30.18 4.26 30.18 0.00 96.25
43.58 25.78 100.00 28.91 25.71 4.04 4.04 76.40 4.04 0.00 22.41 4.04 19.10 15.45 28.88 7.96 7.96 28.88 0.00 19.09 28.91 19.10 4.04 25.78 4.04 22.41 66.42 96.34
42.10 20.78 20.86 20.86 27.97 8.78 16.93 62.95 0.00 23.66 0.00 20.78 0.00 17.02 20.78 4.46 16.93 31.31 100.00 28.00 16.93 20.86 8.78 16.93 16.93 20.86 54.60 92.01
43.59 24.58 27.43 20.78 27.79 16.82 12.85 56.02 12.85 64.27 8.73 8.73 12.85 16.82 37.51 8.73 8.73 16.82 0.00 31.06 16.82 24.53 8.84 20.65 12.85 24.53 25.24 93.91
54.21 20.27 20.17 20.17 30.36 16.36 8.47 41.57 23.72 23.23 8.47 4.30 100.00 16.36 20.09 12.49 8.47 30.35 0.00 27.09 16.36 20.09 4.30 16.36 4.30 27.09 62.63 94.84

43.92 22.30 22.30 28.76 25.58 11.70 7.92 76.56 15.35 66.65 4.02 4.02 29.62 15.35 28.69 4.02 11.70 15.35 0.00 27.59 18.87 22.41 4.08 19.00 7.92 34.50 0.00 95.02
40.43 29.04 29.24 22.59 15.59 15.75 8.05 72.98 8.05 0.00 11.88 8.05 23.20 15.59 19.27 31.27 11.88 11.88 0.00 19.27 25.94 31.53 4.09 25.88 8.05 19.14 72.98 95.05
Table 4: Average probabilities (%) for mighty heroes classes under AL policy.
Another interesting idea, was that of predened skill sequences by Xarfax. In fact, this idea triggered the experimentation made in [2]. Although the initial idea was (partially) refuted, we discovered that indeed a very limited number of skill sequences can be generated by the game. At that experiment, 200 episodes were generated following the AR policy, and only 128 ended up giving dierent sequences of skills, while a loose lower bound by the model implies well more than 1 million. However, the values of the empirical probabilities of gaining specic skills as they were formed through testing were very close to what the model predicted. As it has been already stated, their statistical correlation was 0.995. Another result, was that the ratio of previously unobserved skill sequences over the total number of sequences generated in the last x episodes converged exactly to 0.5 for x = 20, 40, and 80. But this ratio is close to the empirical probability of generating a skill sequence that has not been discovered so far; which implies a total of 128/0.5 = 256 = 28 dierent skill sequences; i.e. all of them can be addressed utilizing a single byte.
On the validity of the model.
Under this perspective, the approval / refutation of the model (with high probability) seems perfectly doable. Approximate methods reside on the Birthday Problem, and variations of the Balls in Bins Problem. Another sort of certicate is obtained (and quantied exactly) through experiments. The outcomes between dierent episodes are independent; therefore by observing the discrepancy of the empirical probability on the occurrence of a specic skill from the theoretical prediction, we have a measure of condence on validating the model. Note that we dont have just a single skill; rather than 28, which means a vector of such measures in [0, 1]28 R28 and this makes things more complicated.

Future work

A more extensive experiment on AR policy thereby producing accurate values for our condence on the model as well as make it easier to use approximate methods for verication; in other words [14] should reach an end soon. If this goes well, implement at least two more strategies on Monte Carlo methods since they have extremely practical importance: the idea on groups of skills and the idea on always picking each new Magic School oered. In addition, extensions of the implemented methods should be considered since there is a problem of who is reaching faster a specic skill. This is of extreme practical importance since typically heroes that break into the treasure area on random maps are between levels 11 - 14. Finally, we can switch to a learning problem: that of letting an agent nd an optimal policy while trying to maximize a specic function; at the moment we are only able to evaluate certain policies. The implementation of neural networks on (some of) the above problems also comes into consideration.

References

[1] Binabik. 1, 300 tests from level 1 to level 2. Library of Enlightenment, December 2005. Post 13 at http://heroescommunity.com/viewthread.php3?TID=16647&pagenumber=1. [2] dimis. Crag-Hack on ANSA. Library of Enlightenment, July 2006. Post 12 at http://heroescommunity.com/viewthread.php3?TID=17812&pagenumber=4. [3] dimis. On the internals of oered skills when leveling-up a hero. Library of Enlightenment, April 2006. http://heroescommunity.com/viewthread.php3?TID=17812. [4] dimis. The Always New Skill Advancement (ANSA) problem. Library of Enlightenment, April 2006. Post 3 at http://heroescommunity.com/viewthread.php3?TID=17812&pagenumber=1. [5] dimis. internals mc: Evaluation of users policy with Monte Carlo methods. Library of Enlightenment, July 2007. Post 10 at http://heroescommunity.com/viewthread.php3?TID=17812&pagenumber=8. [6] dimis. Monte Carlo: Always Left. Library of Enlightenment, July 2007. Last post at http://heroescommunity.com/viewthread.php3?TID=17812&pagenumber=7. [7] Ecoris. digging deeper - the very nature of the algorithm. Library of Enlightenment, August 2006. Post 2 at http://heroescommunity.com/viewthread.php3?TID=17812&pagenumber=7. [8] Ecoris. Searching for skill groups v. 2. Library of Enlightenment, August 2006. Post 3 at http://heroescommunity.com/viewthread.php3?TID=17812&pagenumber=6. [9] Ecoris. Spell probabilities by town type. Library of Enlightenment, May 2006. http://heroescommunity.com/viewthread.php3?TID=17964. [10] LegendMaker. Reliable Results / Legendary Selection Method. Library of Enlightenment, February 2006. Post 2 at http://heroescommunity.com/viewthread.php3?TID=16647&pagenumber=2. [11] Russ. Heroes Stats and Skills Chances. Library of Enlightenment, December 2005. http://heroescommunity.com/viewthread.php3?TID=16647. [12] R.S. Sutton and A.G. Barto. Reinforcement Learning: An Introduction. MIT Press, Cambridge, MA, 1998. http://www.cs.ualberta.ca/sutton/book/ebook/the-book.html. [13] The Nether Gods team. Secondary Skill Advancement - Heroes of Might and Magic III / Heroes 3. http://www.heroesofmightandmagic.com/heroes3/secondaryskilladv.shtml. [14] Xarfax111. SKILLING TREE: Hack the Hack. Library of Enlightenment, July 2006. http://heroescommunity.com/viewthread.php3?TID=18922.

A general framework.

There is a group of resources R; |R| = N. There is a basket B with M < N slots; each slot si is composed by k pockets which is constant for all slots. There is also a weight function wB : R N, which depends on the basket B. We place resources into pockets, subject to the restriction that all k pockets in the same slot have the same resource. Moreover, dierent slots contain dierent resources. Initially l pockets are non-empty (either in the same or in dierent slots). Now we have the following game. The game is played with rounds. It lasts (M k l) rounds and at each step we assign a resource to one of the pockets. A sequence of (M k l) rounds forms an episode. At each step (round) there are two options (resources) and the player picks one of them to be added into the basket B. The way the two options are presented to the player is determined by the weight function wB and some underlying model. For the moment lets forget about the model. The two options, say a and b are presented as follows: a (left option) is a resource that can be found in some slot of the basket, but not all k pockets of that slot are full so far, while b (right option) is a resource that can not be found in any slot (pocket) of the basket so far. In the case where all k pockets are full for the resources occupying all j < M slots, then both a and b are resources that have not been selected so far. In the case where all M slots have lled at least 1 pocket, then both a and b are selected among the resources already in the basket for which there is an available pocket.

The main problem.

The user has a strategy (preference) when selecting resources. The computational goal is to determine the probability that each resource has to be in the basket at the end of the game according to users strategy for various strategies.
How does the model aect the options.
There are some groups of resources, possibly all with dierent cardinality. Each group g has a period pg. Now, if pg 1 steps of the game have been played and no resource r g has been oered as an option, then on the next step of the game, we have an exception and one of the resources in g will be oered. The probability for each resource r g to appear is again dependent on wB. If two (or more) exceptions coincide, then, there is a hierarchy function h which determines which exception will be enforced. All other exceptions are stored as exceptions for the next step.

The real deal.

Motivation comes from a computer game played widely on the internet. The resources are skills that can be obtained by a hero controlled by the user. The basket slots are the available slots for dierent skills and the pockets reect the level of expertise of each skill. In this case it holds |R| = N = 28, M = 8, k = 3, and l = 2. Moreover there are 3 known groups of skills, one of them (WISDOM) containing 1 resource (wisdom) with period p1 = 6, the other (MAGIC) with 4 resources (air, earth, re, water) with period p2 = 4, and the third (REST) containing 23 resources with p3 =. The sets are disjoint. wB (r) {0, 1,. , 10}, for any r and B. 16