10-20-2009, 08:56 AM
Quote:Hi,
However, there is one more wrinkle that you need to consider, and that is how the monster is chosen. To work that out, you need to know the exact algorithm used. It is the same type of problem as dealing virtual cards from a deck. Let's consider two ways to do it which will give us two different answers.
The first way actually simulates the result of a real deal of a random deck. Number the cards in some manner, for instance (A, 2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q. K) of clubs is 1-13, diamonds 14-26, etc. Then generate a random integer in the range [1, 52]. The corresponding card is 'dealt'. Now, renumber all the cards above the dealt card by -1, thus eliminating the 'hole'. Generate a random integer from [1, 51] and repeat the process. Each time, the 'holes' in the deck are closed up and the random number generated is reduced by one. Using this method, any card in the deck has a 1/52 probability of being dealt first, a 1/51 probability of being dealt second, etc. However, setting up this algorithm is a bit of a pain and not too many people use it.
Now, the second way is much easier to calculate, but gives a different result. Like the first way, start by numbering the cards. Then to select each card, generate a random integer from [1, 52] each time. The first time, deal that card and mark it as 'dealt'. The second time, if the card chosen hasn't been dealt, then deal it and mark it as dealt. Repeat for the remaining cards. So far, so good. But how do we handle the case of the random integer pointing to a dealt card? We could re-roll, which gives us a 'true' deal. However, as the number of cards left gets small, it can take a *lot* of rolls before we hit one of the remaining cards. So, most people don't do that. A common way of resolving this is to go to the next undealt card. But this throws the odds off. Say we're working on the second card and the first card was 9. We roll a number, and if it is anything other than a 9, we pick that card. If it is a 9, then we pick the 10. This means that the remaining cards each have a 1/52 chance of being picked except for the 10 which has a 2/52 chance. As the holes in the deck get longer, the odds for the cards after the holes get more skewed.
There are other ways of doing this, some of which replicate a deal with real cards and some don't. But, a little though and you can see that the problems are common anytime you want to pick items randomly from a list. In the case of populating Diablo levels, after a certain point, the mobs whose value is greater than the remaining budget go into the 'can't pick' list with the mobs that have been picked. If the 'next available' algorithm is being used, this will further throw of the probabilities.
And, of course, the characteristics of the PRNG enter the picture. But that's a whole book in itself.
Have fun:)
--Pete
I love probabilty calculation......in high school we used to have quite a good book, and apart from learning some rules there is some puzzling and logic thinking to do, which I was able to do quite well at that time. Of course now I lost all that, and even don't have the books (we used to 'rent' books in high school). At university we didn't do probability calculus anymore.
Pete, do you happen to know some titles of good text books dealing with probability calculus (prefereably something that can still be ordered)? In terms of the level I am thinking about first year university course level (for general science students, not mathematics students) or maybe end of high school level.