 |
|
|
|
|
|
||
|
|
||
|
|
||
|
|
|
|
|
|
||
|
|
||
|
|
||
|
|
|
|
|
|||||||||||||||||
Add Forum to Favorites | Send Topic To a Friend | View Forum FAQ | Track this topic |
Last Thread Next Thread |
| Randomness without Replacement |
|
 |
Unwise owl Member since: 12/30/2001 From: Sweden, United States of Europe |
|||
 Posted - 2/18/2005 4:56:11 PM |
||||
| I am a bit short of time as usual, but the subject that this article discusses is very useful. When I programmed my card game's shuffling function I came across a problem: Suppose each card has an index (from 0 to 51) in an array with size 52. The data of this array is an index to a player hand (0 to max_players - 1, or different negative constants to denote special areas). Now, the most obvious approach to dealing these cards in a seemingly random fashion as evenly as possible is to just call your random function to return a player index between 0 and max_players - 1. If the player of this index already has the maximum allowable number of cards on his hand just jump back and repeat until a valid index is found. It all looks nice in theory, however quite a big problem will occur. What happens is that often all but one or two players get all cards handed out to them first. This means that at a certain point only few players are left to receive the remaining cards, that can be rather many. If for example only one player is left, this means he will receive whatever cards are in the end of the loop; in my case the Hearts of ... 9, 10, Jack, Queen and King etc. One may argue here that probability theory states that this is supposed to happen, but the fact is that this happens far too often to resemble a well shuffled card deck. I'm sure someone can work out some mathematic proof for this, though I'm only interested in what works and this did not. I guess is because we are actually taking the probability of a card getting a player and not a player getting any specific card here. Whereas the probability of the first one remains constant until the cut off point in this obvious case, the second one would vary as in real life. The solution? Adjust the probabilites of a certain player getting a certain card. While this is easy in theory (just set P(Player 1) = x), there is no such convenience when for example using the C++ library rand(). Instead, my approach become to use a lot of integer math. The base here is that the maximum number of chances (or units of a chance) should equal the cards remaining waiting to be dealt. Each player's number of chances is equal to 13 - number_of_cards_dealt. This means that it was possible to take the random integer returned, and test it against certain zones generated. As a down to earth explanation, let's say: Ex: Player 1 has got 4 cards dealt, so P1 = 4, etc. same notation for others. x = a random number from RandInt(0, 52 - P1 - P2 - P3 - Pn - 1) (assuming 52 is maximum number of cards) So the test then goes like this (pseudo code): if(x < P1) Player 1 gets card else if(x < P1 + P2) Player 2 gets card else if(x < P1 + P2 + P3) etc. end if end if end if Of course, there is a number of algorithmic optimizations that can be done. There is no need to add up the players for every test each time (if you got more cards than in a standard set and more players this can become much). Instead, just store a temporary variable which is added with the number of cards dealt for each player. Assuming you got the number of dealt cards in a array you can make this process to an inner loop itself. The result of all this is a much more evenly spread deck (manipulated probabilities rock). There can still be some issues with it being too evenly distributed at times; you will seldom see a player getting many cards in a row for obvious reasons when in RL life the deck could be shuffled badly from the last game (which is often the case). I guess this can be solved by simply adjusting the probabilites (or chances as I've called this integer probability math). |
||||
|
||||
|
DavidKennerly Member since: 2/29/2004 From: USA |
|||
|
Posted - 2/19/2005 2:38:04 PM |
||||
| The problem of probability that you mention sounds interesting, but I didn't quite catch what the purpose of the card dealing is in the game you are discussing. Is the purpose to A) fairly and randomly deal cards from a deck to a specific number of players? Or is the purpose B) to deal a random card from a deck to a randomly selected player? Or something else? If it is A), then the following procedure is sufficient: 1. Shuffle the deck. 2. Until players have maximum number of cards: 2.1. For each player: 2.1.1. If the player does not have maximum number of cards: 2.1.1.1. Deal the player a card. If is is B), then the following is sufficient: 1. Shuffle the deck. 2. Randomly select a player. 3. Deal that player a card. In either case, the problem of biasing the player's hand is solved by shuffling the deck first. You could argue for a hybrid of A) and B), but the result would be equivalent to A). For example, when playing Spades, the dealer may deal the cards in any order he or she likes, so long as each player ends up with 14 cards. That is (in a perfect shuffling and randomization algorithm) equivalent to A). David |
||||
|
||||
|
Anonymous Poster |
|||
Posted - 2/21/2005 3:15:13 PM |
||||
| Excellent article. However, what about predictability? I could see enterprising players counting cards and waiting until the deck is stacked in the favor before executing something important (e.g., an expensive but risky recipe, or rolling on a big- ticket group-loot item). |
||||
|
||||
|
achacha Member since: 1/15/2004 |
|||
 Posted - 2/21/2005 9:56:21 PM |
||||
| When using this kind of system you have to do what big casinos do, use lots of decks and shuffle before the deck runs out. So using lets say 20 decks and shuffling when you have 5 decks left will remove a lot of card counting as the use never knowns when you reshuffled (unlike casinos). The players can and will try to predict the RNG (random number generator) to get an advantage, but they will also do that to any RNG, take samples and predict the distribution and if an RNG is correlated in any way. This deck approach works well for combat systems where you don't sit around predicting the outcome, once you start a fight a few decks are shuffled on the server and the outcome if almost known to the servre but not to the player. This can even allow the server to prepare for the inevitable, if it is obvious a player is about to lose the fight and did not put up a good fight (length of fight) they can have reinforcements arrive and try to help the player, while it may be inevitable they will get killed at least it was not a usual stand next to moster, hit attack key, then hit a few power keys and hope all is well. There are a lot of possibilities, this particular system can make the play experience a bit more enjoyable which is why many people play games in the first place. Also don't forget you can have multiple RNGs in your game each tuned to the user experience you want to portray. |
||||
|
||||
|
Anonymous Poster |
|||
Posted - 2/22/2005 8:35:25 AM |
||||
| Yes, but adding decks leaves you right back where you started...with the possibility of multiple consecutive failures. |
||||
|
||||
|
Aprosenf Member since: 5/8/2001 From: USA |
|||
|
Posted - 2/22/2005 12:36:37 PM |
||||
| In what RPGs is the chance of a successful attack 50%? In virtually every RPG I've played, you hit at least 90-95% of the time, though in some older ones that number is lower, but still nowhere near 50%. If we assume a generous 80% chance of hit, then the probability of 10 misses in a row using the dice method is (1 - 0.80)10 = 1.02 × 10-7 For 90%: (1 - 0.90)10 = 1.00 × 10-10 Both of which are many magnitudes smaller than the numbers presented in the article. |
||||
|
||||
|
dazilla Member since: 6/13/2004 From: Canada |
|||
|
Posted - 2/22/2005 2:28:25 PM |
||||
| Very interesting article. It does, however bring a few problems. If the probability of frustration DOES occur, then you have a guaranteed string of 10 successes. Also, what determines the size of the deck? Different fights will take a different number of hits to finish. If, say, a deck is reshuffled after each fight, and the player got lucky, so they got 10 hits in a row with zero misses, they have a higher effective probability of hitting. This happens most of the time, since if 50% is the probability of hitting, and it takes an average of 10 hits to down a creature (for sake of the 20-card deck with 50/50 hit/miss probability), then in almost every case the player will not encounter 10 misses. This raises the probability of hitting significantly (I don't really have time to do the calculation right now). If, however, the deck is not reshuffled after each fight, then as another poster mentioned, it can be stacked very easily. Using the casino method completely removes the purpose of using randomness without replacement, since you're trying to more closely approximate randomness with replacement with multiple decks and shuffles at random periods. |
||||
|
||||
 |
Stoffel Member since: 12/2/1999 From: San Diego, USA |
|||
|
Posted - 3/2/2005 1:32:41 PM |
||||
| Thanks for the contribution. One other thing that goes unmentioned is that removing or reducing extraordinary frustrations will do the same for extraordinary successes. Do we remove the possibility of critical misses an sacrifice the joy of critical hits (to use some old-school terminologies)? Also, in any sort of scalable situation, I think the added complexity would be too great. I don't see the advantage of lowering the frustration probability of an order of magnitude by completely reworking the randomization algorithm, rather than just simply adjusting the difficulty of the roll such that its probability distribution matches what you desire. |
||||
|
||||
|
frostburn Member since: 6/27/2000 From: Sogndalsfjora, Norway |
|||
|
Posted - 3/18/2005 9:53:07 AM |
||||
| Interesting read, but how about just biasing the rolls toward the player? Use a dice, and for each failure add 1 to a counter. When the counter reaches X, the player automatically succeeds. X must of course reflect the difficulty of the roll. At every success the counter is cleared to 0. The biggest gameplay-problem with this approach is to figure out a good value for the allowed number of fails in a row. It must be determined by the difficulty, but it shouldn't be the same as it. X shouldn't be 2 at difficulty 50%, but perhaps closer to 10. This might be an OK value for easier rolls as well. However, if the player has 1% chance to succeed at some difficult task, then roll nr 100 should succeed if none of the previous 99 rolls did. The failure-counter could also be cleared if the player decides to try something else and makes a roll with another difficulty. In my opinion this system would be easier to implement than a deck-system, and would be easier to tweak for various difficulties. I think the efficiency of it would be about the same as the deck-approach, or perhaps a little higher. It also makes it possible to avoid frustration while using other systems than the d20 system which I personally dislike. With a d100 system using a deck you could have 50 failures before you'd get a success at 50% diff, while using my system you could tweak the maximum allowed failures in a row. Of course, it doesn't remove the possiblity of having 9f(fail),1s(success),9f,1s,9f,1s, but a similar solution could be found for that case. 10f,10s,10f,10s etc with the deck system would be just as weird. It's biased towards the player however, so in 2n rolls with difficulty 50% you'd have slightly more than n successes, but I don't think players would notice or mind. In PvP situations both players would have the same advantage, so it would still be fair. Another thought: An additional randomness factor that could be added is to make an additional roll with the difficulty X/counter. This might just be a waste of cycles though. |
||||
|
||||
|
DavidKennerly Member since: 2/29/2004 From: USA |
|||
|
Posted - 8/9/2005 10:38:22 PM |
||||
| Sorry, I hadn't realized that there were comments after the first few days of the article's publication. I'll reply to the most interesting of these now. Stoffel wrote: [QUOTE] Thanks for the contribution. One other thing that goes unmentioned is that removing or reducing extraordinary frustrations will do the same for extraordinary successes. Do we remove the possibility of critical misses an sacrifice the joy of critical hits (to use some old-school terminologies)? [/QUOTE] Actually, this article is not about critical failures or critical successes. The topic is a consecutive string of failures. In that sense, you are right, a deck reduces the maximum length of a consecutive string of successes. However, limiting the maximum number of consecutive successes is ALSO desirable. The most devastating experience is a consecutive string of failures. But a consecutive string of successes is also boring. Stoffel wrote: [QUOTE] Also, in any sort of scalable situation, I think the added complexity would be too great. I don't see the advantage of lowering the frustration probability of an order of magnitude by completely reworking the randomization algorithm, rather than just simply adjusting the difficulty of the roll such that its probability distribution matches what you desire. [/QUOTE] Adjusting the difficulty of the roll does not guarantee against the longest string of failures. The motivation of the deck is to tailor the probability distribution to the player's requirements, which includes a maximal number of consecutive failures. Certainly the mechanism mentioned in the article is not the only mechanism, nor necessarily the mechanism that fits every game. Frostburn gave an example of another mechanism, which has its own computational elegance: [QUOTE] Use a dice, and for each failure add 1 to a counter. When the counter reaches X, the player automatically succeeds. X must of course reflect the difficulty of the roll. At every success the counter is cleared to 0. [/QUOTE] This is a fine solution for many games. It does alter the distribution slightly. With a deck of cards, the distribution is guaranteed to be fair over the course of N attempts, where N equals the number of cards. For MMORPG players, this long-term fairness is an important factor. The reason for the deck is not to reduce the probability of a single failure, but the reduce the probability of a long string of failures. For hyperbole, failing once is exciting; failing 10 times in a row is frustrating. Aprosenf wrote about probability of failure ten times in a row: [QUOTE] If we assume a generous 80% chance of hit, then the probability of 10 misses in a row using the dice method is (1 - 0.80)10 = 1.02 × 10^-7 For 90%: (1 - 0.90)10 = 1.00 × 10^-10 Both of which are many magnitudes smaller than the numbers presented in the article. [/QUOTE] But Aprosenf did not consider the probability for frustration using the deck mechanism. Since the deck is assumed to have 20 cards, then for a probability of 80%, there would be 4 failure cards, and 16 success cards. Since frustration, in the article's hypothetical situation, is defined as 10 or more consecutive failures, and since the first result out of 20 is assigned to a success, the maximal string of failures is only 4 attempts. Therefore, using the deck mechanism the probability of frustration is 0. More generally, any reasonable value of a Bernoulli trial that is chosen is guaranteed to have a lower rate of frustration when converted into a hypergeometric distribution (i.e., a lottery of cards in a deck) than with a strict Bernoulli trial (i.e., dice). An anonymous poster brings up an interesting scenario: [QUOTE] However, what about predictability? I could see enterprising players counting cards and waiting until the deck is stacked in the favor before executing something important (e.g., an expensive but risky recipe, or rolling on a big- ticket group-loot item). [/QUOTE] That depends on the state machine that generates the random number. If it never resets and random results can be saved indefinitely, then yes it would be possible. But the example is combat, which is in itself not fine-tunable. You cannot decide to "save" your attacks. You either enter combat or do not, and once there you hope you hit. Furthermore, the maximal string of consecutive successes is limited by the exact same mechanism that limits the maximal string of consecutive failures. Therefore, the deck mechanism limits run away success as much as it limits run away failure. Despite my defenses, it's by no means the be-all-end-all, nor is it the entirety of an RPG game system, whether MMO or SP. It is meant to illustrate a game mechanism. And in doing so, provide the reader with insight into how to evaluate, analyze, and design their own game mechanisms. In pursuit of a fine game, David http://finegamedesign.com |
||||
|
||||
| All times are ET (US) |
Last Thread Next Thread |
|
