# diochnos/software/games/homm3

Programs related to Heroes of Might and Magic III can be found here. The programs were developed under the long term
project that started with the thread On the internals of offered skills
when leveling-up a hero at Heroes Community.

The aim is dual:

- To uncover the Level-Up mechanism; i.e. create an effective model.
- To evaluate various policies efficiently.

## Related Papers and Surveys

- Leveling-Up in Heroes of Might and Magic III. Appeared in FUN with Algorithms, Jun 2010.
- On the offered skills in Heroes of Might and Magic III. Survey, Jan 2008.

## Exhaustive Search

Here we can find various methods that evaluate simple policies. Simple here has the meaning that the induced state-space that we have to explore in order to evaluate the policies is bounded reasonably by the model.

Essentially, ANSA policies are implemented. The reason is that the probability distribution which is formed at level 23 is the same as the one at level 7 or 8 (depending on the amount of secondary skills the hero has at level 1), since up to that level all ANSA policies form an equivalence class, with their main representative the AR (Always Right) policy.

There are three different implementations.

- ansa: Uses the GMP Arithmetic library and allows exact computations.
- ansa_double: An implementation that uses double precision arithmetic. It is faster from the above one, the results contain bounded error, but it can be shown that it is insignificant for our purposes.
- ansaExtended: An extension of the above program (double precision) that calculates the probability certain combinations of skills have. The combinations of skills are posed in Disjunctive Normal Form.

Examples for the execution of the above programs can be found in the thread where all the above programs first appeared. Check the third post in page 1.

## Monte Carlo Approach

Here we can find programs that evaluate more interesting policies. This is achieved with a Monte Carlo approach.

- internals_mc: This is the latest version (2.0) which is implemented with POSIX threads. Under MS Windows we incorporate the implementation of Ross Johnson here.
- Version 1.1: This is nowadays deprecated. It is useful compared to version 2.0 above since it requires less memory.

Examples for the execution of the above programs can be found in the thread where all the above programs first appeared. Check the tenth post in page 8.

### Pending

- Incorporate the SPRNG library in the multi-core version of the program.
- Update the single-core version so that it supports all the implemented policies found in the multi-core.
- The computation of the probability distributions on all the intemediate levels up to level 23.
- Support magic heroes.

## Skill Trees and Limited Randomness

Here we can find the program skills which incorporates the descriptions of AlexSpl on the way randomness is treated on level-ups (as well as the way pseudo-random numbers are generated on level-ups).

Examples for the execution of the above program can be found in the thread where the above program first appeared. Check the eleventh post in page 14.