Welcome to the Heroes of Might and Magic III Tutorial! This tutorial is a great place to start, not only for players new to the Heroes series, but for seasoned veterans to get a taste of whats new to Heroes III. This tutorial is designed as a read-along, so for best results you should print this document before beginning, and follow the instructions as you play. In moments, you will be learning the ins-and-outs of Heroes III.
First, launch the game, either by selecting PLAY from the autorun window, by double-clicking the Heroes III desktop icon (if you chose to install it), or by selecting Heroes III from your Windows Start Menu. After watching the intro, choose NEW GAME, then TUTORIAL. This will bypass the scenario selection screen and directly load the tutorial map.
Week 1, Day 1 What you will see first is the Adventure Screen. This is where you will spend a great deal of time while playing Heroes III. The main window provides you with a close view around your heroes and cities, while the world map (located in the upper-right corner of the screen) shows you a small view of the entire world. Notice that most of the world map is black that is
because until you send a hero to explore an area you wont know what is there. Dont worry about any of the other buttons below the World Map, these will be described in greater detail later. Your first hero, Lord Haart, should already be selected (hes sitting on his horse, waiting for instructions). The first thing well want him to do is visit the town, so place your mouse cursor over the entrance to the town (between the two flag poles). Notice how the horse icon rears up on its hind legs this means that by traveling to that location, your hero will interact with whatever is there. Also, the name and a short description of the location appears in the Rollover Bar at the bottom of the screen (the rollover bar appears on nearly every screen in Heroes III and gives useful, context sensitive information). When you click on a location, a set of green arrows show the path your hero will take to reach the large green X. It is this X that marks your heros destination. Click again on the same location and your hero will move to the castle (a fast way to move is to simply double click on an intended destination the first click selects the path, the second click sends the hero). When the hero arrives at the entrance to the town, the view will change to the Town Screen.
Town Screen This is the Town Screen for the Castle town type (there are eight different town types in Heroes III, each with its own unique creatures and buildings). Most of this screen is taken up by the town view. Any structures or upgrades you build in this town will appear here. As you can see, several structures have already been constructed. Specific information about the town is displayed in the bottom-left corner of the screen, including town income (per day) and troop production (per week). To the right of the town info are two rows of boxes. The top row is for any troops that are currently in the towns garrison, the bottom row is for any troops currently visiting a town with a hero.
The first thing you will want to do is build a Fort. To do so, click on the larger of the two buildings on the left side of the town view the Town Hall to enter the Hall Screen. The Hall Screen is where you make all your construction decisions. Any building you can currently build is shown with its name in a green bar. Any building that you can not build, but can be built later is shown with its name in a red bar. If a building has been disabled or can never be built, its name will appear in a gray bar. Once you have completely built or upgraded a structure as high as it will go, its name will be displayed in gold. Click on the picture of the Fort. You will be shown a description of what the Fort does, as well as what resources are required to build it. Click on the Build button (in the lower left hand corner of the popup window) and the Fort will be constructed. Now that you have a Fort, click on it to view the Castle Window. This window shows you information about all seven units that can be produced by this town. Any troop-producing structures (usually referred to as Creature Generators) that are already constructed will show a number of Available units (currently the Guardhouse, Archers Tower, and Barracks show units available the other structures have not been built yet). Click the Exit button (lower right) to return to the Town Screen. The round tower on the right side of the screen is your Mage Guild. It is here that heroes go to learn the spells that they will cast while adventuring. Click on the Mage Guild, then choose to buy a spell book. Since Lord Haart is a Knight, he does not begin with a spell book. All heroes must have a spell book before they can learn or cast spells. Once you agree to purchase a spell book, you are shown the Mage Guild Screen. Each of the spells the Mage Guild offers is listed on scrolls on the various shelves in the guild. Left or right clicking on any spell scroll will show you a description of that spell. When you are ready to leave, click on the Exit button (lower right). Your hero starts with troops, but its really just a token force, so you should buy any available troops and add them to his army. Along the hill at the back of your town are three towers. Click on the large central tower. The Recruit Pikemen window is displayed. Using the scroll bar you can select how many troops you wish to purchase, and the total cost is calculated to the right. However, the fastest way to buy troops is to use the Maximum button (the four up arrows at the bottom of the popup window) which will automatically calculate the maximum number of troops available that you can currently afford. Click the Maximum button, then click the Recruit button (bottom center). Notice how there are now Pikemen in the garrison row of your town. The other two towers will allow you to purchase Swordsmen and Archers. Use the Maximum button and recruit these troops as well. Now that youve purchased troops, you will want to move them into your army. To do so, click on the unit you wish to move, then click on an empty slot in the heros army (bottom row). You can also move troops together, or rearrange them within an army. For example, if you click on the newly purchased Pikemen, then on the Pikemen that Lord Haart already had, they will combine their numbers into a single, larger stack. Now click on the newly purchased Swordsmen, then on the Pikemen in your heros army. Notice that since they were not the same troops, rather than combining, they switched places. Experiment with moving troops around, but

when you are done, make sure that all the troops are in Lord Haarts army, then exit the Town Screen by clicking on the Exit button (bottom right). Just to the east of your Castle town is a Sawmill. Click once on the Sawmills entrance, then again to start your hero moving. When you arrive, your hero will automatically claim the Sawmills production for your faction by placing a red flag (your factions color) on the Sawmill, and you will receive a message telling you the Sawmills production. As you will discover, many objects in Heroes III may be flagged. Also notice that while your hero moved toward the Sawmill, some of the dark shroud covering the map was revealed. Just to the southeast of the Sawmill is an Ore Pit. Wood and ore are the basic resources needed for building nearly any town structure, so these should be the first resources you seek out early in the game. Go claim the Ore Pit now. Excellent. You now have secured wood and ore for your faction. Now, just to the west is a treasure chest. Double click on it to move Lord Haart there, he will automatically pick it up when he arrives. Sometimes you will find that treasure chests contain some sort of magical artifact. Most times, though, they will contain gold, and you will be given a choice of either keeping the gold, or distributing it to the peasants in exchange for experience points. Choose the experience this time, because it should be enough for your hero to gain a level! Congratulations, Lord Haart now has enough experience to reach 2nd level. Two things happen when a hero gains a level. First, he gains +1 to one of his primary skills (Attack, Defense, Power, or Knowledge). Second, he is offered two choices of Secondary Skill that you must decide which you wish the hero to learn. The choices will either be a skill the hero does not have, or an improvement to a skill that he does have. Right clicking on a skill will display its description, so take a look at both, and pick whichever one you like. Well, that was enough for one day, dont you agree? Located at the bottom of the button row just below the World Map is a button with a picture of an hourglass. Click on that button to end the current turn. Your opponent(s) will then take their turns, and a new day will begin. Week 1, Day 2 The first thing youll want to do today is build up your town, so move your hero back to the castle. Once inside, click on the Town Hall and build a Griffin Tower. Recruit the available Griffins and add them to Lord Haarts army the same way you did for the other troops, then exit the Town Screen. Once back out on the adventure map, you should probably do a little more exploring, so have your hero follow the road east past the Sawmill and Ore Pit. You will soon see a waterfall with a stone face next to it. This is a Fountain of Youth, so be sure to pay it a visit. The Fountain of Youth is just one of many locations that will boost your armys luck or morale, or give you a movement bonus for the rest of the day or week. These objects do not get flagged like mines, and may be used by anyone. Morale and luck effects typically last until your next battle, so visiting one of these sites multiple times does nothing until the current effects wear off. End your turn.

Week 1, Day 3 You dont always have to march a hero into a town to view the town screen. Scroll the screen so that you can see the Castle town to scroll the screen, simply move the mouse cursor to the edge of the screen and the map will scroll until you move the cursor away from the screens edge then hold your mouse over the Castle (above the towns entrance). Notice how the cursor changes into a small castle icon. Click once on the Castle town to select it and center it in your view, and click on it again to view the Town Screen. Use the Town Hall to build a Blacksmith. Blacksmiths provide heroes with war machines. First Aid Tents heal the wounded during combat, Ammo Carts provide unlimited ammunition to your ranged troops, and Ballistas will assist your army in attack and defense. The Castle town builds Ballistas. Since there is no hero in town, there is no need to buy a Ballista, so exit the town screen and well go back to our hero. Just below the mini map you will see a portrait of your hero, Lord Haart. Click on the portrait to select him as the active hero and center him in your display. Continue to follow the road to the east, you will eventually see a Griffin Tower that bears a striking resemblance to the one you just built in your Castle town, and it should every week it has troops to recruit, just like the one in your Castle town. Visit the Griffin Tower and purchase any Griffins that are available. They will be automatically added to your army. Notice how the Griffin Tower is now flagged with your color. Every creature generator that can be built in a town can also be found as a stand-alone building. By flagging a creature generator, you add a portion of its production to every similar generator you own in a town, increasing the number of those creatures that are available in those towns at the beginning of each week. Having purchased the Griffins, head back to the road and follow it to the southeast through the mountain pass. The large skull-shaped rock up ahead is a Subterranean Gate. Enter it to see one of the entirely new features of Heroes III the underworld! This is the underworld, an entire subterranean level which behaves exactly like the surface level above. In any scenario which contains two levels, you may switch between them using the Surface/Underworld View button on the right-hand side of the screen. It is the top-right button, located just below the mini map. Travel between the Surface and Underworld levels is typically accomplished by Subterranean Gate, though you will undoubtedly discover other means of travel as you play the game. To the west of your current position is an artifact the Greater Gnolls Flail. It will provide you with a combat bonus, so go pick it up. Dont worry that its guarded, this should be an easy fight.
Combat Screen This is the Combat Screen. Your hero and his army are lined up along the left side of the screen. In any combat, this is the Attackers side of the screen. Defenders line up along the right side of the screen. Combat is detailed more fully in the manual (pg. 40), but since this is a simple fight, well just go over the basics. Combat is handled in turns. The order in which creatures act is based on their speed. Since your Griffins are the fastest unit on this battlefield, they get to act first, and to show this, they are highlighted by a yellow outline. The shaded area around your Griffins indicates how far they can move in a single turn. Move the mouse around the battlefield, and watch how the cursor changes. When the mouse is within the shadow of the Griffins, it becomes a fly icon (or a walk icon for non-flying troops), showing that you can move here. Click as close to your enemy as the movement shadow allows. If your Griffins (or any of your units) receive Good Morale, it means they may immediately attack again. If this is the case, move them closer to your enemy. The goal here is to close the distance between your troops so that you may attack them. Whenever units are adjacent to each other, they may attack. If you hold the mouse over the border between hexes where you and your enemy stand (or where you will be standing at the end of your move), the enemy unit will be highlighted in blue, and the mouse cursor will become a sword icon. The direction the sword points indicates the direction that you will attack from.

When it becomes your Archers turn, dont move them. Instead, place the cursor over one of your enemies and click. Units with missile weapons do not have to be adjacent to an enemy to attack. In fact, you can not make a ranged attack if an enemy unit is standing next to you. Continue moving, attacking, and shooting until all the Gnolls are dead. You will have won your first victory! After each combat, you will be shown the Combat Results Window. This window breaks down the losses to each side and any experience your hero has gained if you were victorious. Click the Check button to close this window. You will then be shown the Artifact you just won from the Gnolls. It will be automatically added to your heros inventory, and equipped on the hero if space permits (for more information on equipment, see pg. 31 in the manual). On the Artifact popup window, you may right click on the picture of the artifact to view information about it. If your hero has gained enough experience to gain a level, you will then be shown the Gain a Level window, which is identical to the one you saw when you received experience from the treasure chest on Day 1. So, with the full day that today has been, you should now end your turn. Week 1, Day 4 Lets go back a moment and take a look at your Castle town. Since youre underground, the fastest way to get there is to use the town portrait button on the right side of the screen, the same way you used the hero portrait button to select your hero. Single clicking on the town button will center your view on the town. Double clicking will open the town screen. Do that now. All units in Heroes III may be upgraded, but to do so you will need to upgrade the buildings that produce those units. Use the Town Hall to build a Guardhouse upgrade. Once the upgrade builds, click on the Tavern building located next tot he Town Hall. The Tavern is where you recruit new heroes. At any given time there will be two heroes available to hire. In this case, two Cleric heroes are available. Right click and hold on a heros portrait to display information about that hero. Look at both, and hire whichever one you want by clicking on the Recruit button. The hero will appear in the Visting Hero row on the Town Screen. Click on the Clerics portrait, then click on the box just above him. Notice how the hero and all troops under his command move into the garrison row. Every town may have a garrison hero, and if the town is attacked that hero will defend from within any fortifications that are present. Also, by moving a hero into the garrison, you allow another hero to be hired or to enter the town. Move your hero back out of the garrison by clicking on his portrait, then clicking on the box directly below him. Again, the whole army will move to the Visiting Hero row. Since you built an upgraded Guardhouse, it would be a good idea to upgrade your Clerics Pikemen. Double click on the Pikemen to bring up their info screen, then click on the Upgrade Unit button. You will be shown how much it will cost to upgrade your troops. Click Okay to accept the upgrade, and all your Pikemen will be upgraded to Halberdiers. Not forgetting about Lord Haart, exit the Town Screen, and notice that your Clerics portrait has been added to the portrait row on the right side of the screen. Just above the End Turn button is the Next Hero button. Each time you click this button your view will change to the next hero

(with remaining movement points) in order of how they appear on the portrait window. Click until the view is on your Knight. Move your Knight to the sign up ahead, and follow the instructions there. Once you have flagged all four mines, continue down the passage to the southwest as far as your hero can move. If you try moving farther than your hero has movement points to reach in the current turn, the movement arrows and destination X will be colored red instead of green. Red arrows show the path that the hero will take, but indicate movement that will take place on the next or subsequent turns. Since youre out of movement for this turn, end the turn now. Week 1, Day 5 Notice how the movement path from the previous turn has stayed, but has now turned green to indicate movement that can be completed this turn. Among the buttons on the right sided of the screen is a Move Hero button. Click on this to have your Knight complete any movement left over from last turn, then continue west and north and proceed through the Subterranean Gate. You have traveled clear under the ocean! But this isnt a vacation spot, this is the home of the Demons and Devils of the infernos. Its a good thing that there is a road here lava terrain causes a movement penalty for any heroes or creatures that are not native to the infernos. Other poor terrains you will encounter include rough, desert, swamp, and snow. To the southwest is a War Machine Factory. It behaves just like the various Blacksmiths that can be found in towns, but with one exception you can purchase all war machines. For now, go to the War Machine Factory and purchase a Ballista. Youre doing well, but with another day at an end, its time to end your turn. Week 1, Day 6 Move your Knight along the road to the Star Axis structure. As you can see, a visit to the Star Axis increases your Power skill by +1. Just like objects that increase your luck or morale, there are sites to visit that will increase your primary stats or teach you new skills as if your hero had gained a level. These effects are permanent. As a general rule, any number of heroes may visit a single site, but heroes my only gain the benefit of the site once. Further down the road is an Inferno town. The presence of a citadel means that the town has at least minimal fortifications, so its a good thing you stopped at that War Machine Factory. Move toward the town, where you will be joined by several Archangels, then launch your attack on the town by marching your hero up to the front entrance. Instead of a Horse icon, the mouse cursor will show that you are about to enter combat by turning into a Sword icon.

Siege Combat Screen The enemy units in this combat are significantly stronger, but should be no problem for you. Since the enemy is inside their castle, you will need to knock down the walls with your catapult, shoot over the walls with your archers or ballista, or fly over the walls with your archangels or griffins. Once your catapult breaches a wall, or when an enemy unit comes out of the castle gate, your footsoldiers can get involved in combat. Your hero can cast a spell once each round, until he has spent all of his spell points. To cast a spell, click the Cast Spell button at the bottom of the screen. The Spell Book will open, allowing you to choose a spell, then choose a target. Some spells are beneficial and may be cast on your own units, others are harmful and should be cast on the enemy. Right click on any spell to view its description. Fight the combat. Should you lose, simply load your Autosave, end your turn, and try again. Wow, that was some combat, and Lord Haart may have gained enough experience for two levels. Choose what you want, then march into your newly acquired town.
This is the Inferno Town Screen. Despite its different appearance, building and recruiting is handled exactly the same. Click on the Town Hall (on the hill on the left side of the screen), and build the Birthing Pools. The Birthing Pools are one of many Horde Structures that can be built in Heroes III. Each town type has one or two horde structures, which when built, increase the weekly production of the creature generator they are built for. Similar to the horde structures are Resource Silos. Resource Silos are added to an existing marketplace, and produce additional resources for your kingdom the same way a mine does. Switch to your Castle town by clicking on the town portrait button on the bottom-right of the screen. This works in the same fashion as the town portrait buttons on the adventure screen. Click on the Town Hall and buy a City Hall. Notice how the Town Hall Building has now been upgraded to the City Hall. In Heroes II you needed to build a Castle to increase your towns income, but in Heroes III, town income is dependant upon its Hall. Upgrading the Town Hall to a City Hall doubles your towns income. Later you can build the City Hall into a Capitol, which will double your towns income again. Exit the town screen and end your turn. Week 1, Day 7 Starting out from your Inferno town, send your Knight northeast along the road until he reaches the shipyard. Not all towns in Heroes III can build shipyards, so in many cases you will need to seek out one on the adventure map. Shipyards are flaggable structures, allowing you to build boats without actually sending a hero there. Visit the shipyard (it will flag to your color), and purchase a boat, then move your Knight onto the boat. Notice how the cursor changes to a boat icon to indicate that you will be boarding the boat. Boarding (or leaving) a boat uses any remaining movement points your hero may have for that day.

Go back to the Inferno Town Screen, and use the Town Hall to build Brimstone Stormclouds. Every town has at least one special structure that it can build. These structures typically add morale or luck to garrison heroes, or stats or skills to visiting heroes. Right clicking on any building will display specific information about it and any bonuses it provides. Having done that, end your turn. Week 2, Day 1 With the start of a new week, all creature dwellings in towns and on the adventure map repopulate. Since Lord Haart is already on a boat, and it would take too long for him to come back to the Inferno town for troops, youll have to hire another hero to bring them to him. Go into the Inferno Town Screen, then use the Town Hall to build a Tavern. Enter the Tavern and recruit a Heretic hero. When the hero appears on the town screen, recruit any Familiars that are available and move them into the Heretics army, then exit the town screen. The Heretic should already be selected. Move him to the ship. The cursor will change to two arrows pointing opposite directions, indicating that heroes will trade. Details on the Trade Screen can be found in the manual (pg. 32), but all you need to concern yourself now is moving the Imps from the Heretics army (on the left), into Lord Haarts army (on the right). Troops and items are moved the same way as in the town screen. Click on the Imps, then click on an empty spot in Lord Haarts army. When youre done, exit this screen. Use the Next Hero button to select your Knight. Boat movement is treated exactly like land movement. The cursor will change when placed over any object you can visit at sea, and will change to a Boat Anchor over any piece of land where your hero could leave the boat. Sail the boat east to the grassy island, then land anywhere along the shore. Since getting off the boat used the remainder of your Knights movement, end the turn. Week 2, Day 2 There is one more battle you must fight, and that is against an enemy hero! Just up ahead is Charna, a Death Knight of the Dark Necropolis cities. Shes a little far from home and has a small army with her, but you should be able to defeat her with little effort. Conduct combat, then continue here. Having dealt with Charna, you can now visit what she was guarding an Obelisk. Whenever you visit an Obelisk you will be taken to the Puzzle Screen. Pieces of the puzzle will be revealed each time you visit a new obelisk. The area shown in the puzzle shows you the location of the Grail, an item that you should always seek out any time you play, as it will give you a significant advantage against your enemies. Since there is only one obelisk on this map, the entire puzzle has been revealed. Do you recognize the location marked by the X on the map? You should, its right near your starting Castle town! Exit the puzzle screen and go take a look.

Select your Cleric hero and move him so that he is standing between the two large tree stumps southeast of the Castle town. This is the location where you will dig to see if the Grail is actually here (sometimes the map indicating the location of the Grail is not entirely accurate some of the lands features may have changed in the years since the Grail was hidden and its map was made). Since digging for the Grail is a full days work, your hero will have to spend the night here and dig in the morning. End the turn. Week 2, Day 3 Select your Cleric hero. Press the D key to dig for the Grail. Congratulations! Youll want to take this back to town, but since you spent the whole day digging, youll need to spend the night here again. End the turn. Week 2, Day 4 Select your Cleric hero, and move him back to your Castle town. Click on the City Hall you will be asked if you wish this town to be the permanent home of the Grail. Say yes. There is only one Grail in any game, which means that only one city will gain the benefit of the Grail during any game. Additionally, a Grail Structure is a permanent feature, so dont lose the town to your enemies or they will gain the benefits of ownership for themselves! By building the Colossus, you have won the game. When you exit the town screen you will be shown your score, but for now, right click on the Colossus to view its benefits. As you can see, sucessfully finding the Grail and bringing it to one of your cities is worth all the time and effort! Not only does it greatly boost your income and creature growth, but each town gets a unique bonus, just for being known as the Home of the Grail. Congratulations! You have completed the Heroes of Might and Magic III Tutorial. You may wish to read more of the game manual, or you may wish to just jump right in and play either a single scenario or begin the campaign for the Restoration of Erathia. Good luck!
Copyright 1999, The 3DO Company. All Rights Reserved. Heroes of Might and Magic, New World Computing, 3DO, and their respective logos are trademarks, and/or service marks of The 3DO Company in the U.S. and other Countries. All other trademarks belong to their respective owners. New World Computing is a division of The 3DO Company.

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.