Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The context of this is that I am creating a turn-based RPG engine, and each of a set of players has a "speed", which determines the probability of moving earlier in a turn depending on how high it is. The higher the speed, the earlier in the turn the player is expected to move.

I would like to devise an algorithm to determine a random probabilistic turn order based off of these speed values.

The algorithm should have the following properties:

  • It is commutative. That is, no matter which player is used as the base for calculations, the algorithm will return the same probability of each turn order occurring.
  • It is consistent. The probabilities always add up to 1.
  • It handles equality well. When all the players have the same speed, they should have an equal probability of moving first, second, etc. When two players have equal speed, but dominate over the rest, they will have an equal probability between themselves and everybody else will have a lesser amount.
  • It is scalable. The same formula should work no matter how many players (even the degenerate case of one) there are.
  • It is smooth. That is, it does not suddenly snap from one case to another. If we make the fastest player always move first, the probability of a player moving first snaps from 0 to 1 on the basis of a single point difference, which is bad.
  • It preserves priority. That is, if the faster player does not move first, it should have a high probability of moving second, and if it doesn't, then it should have an even higher probability of moving third, etc.

And a few properties that are less important:

  • It is adjustable. Depending on how steep the user wants the increase in probability to be, there should be a parameter in the algorithm to account for it, without requiring a complete redesign of the algorithm.
  • It handles edge cases well. If we let $s$ be a variable representing the speed of one of the players and $p(s)$ represent the probability that that player moves first, then $\displaystyle \lim_{s \rightarrow \infty} p(s) = 1$.
share|improve this question
add comment

2 Answers

up vote 3 down vote accepted

For each player, pick a random number $t_i$ between $0$ and $T_i = 1/s_i$. Sort the players by $t_i$.


What's going on here is that we're assuming that each player takes a random time between $0$ and $T_i$ to charge up their moves, with $T_i$ inversely proportional to their speed $s_i$. All players begin charging their moves simultaneously, and then each one goes as soon as he or she is ready.

There are a couple of ways you can generalize this.

First, you could pick a different distribution of charge times. What I've described is equivalent to picking from a uniform distribution between $0$ and $1$, and multiplying the result by $T_i$. You could use a uniform distribution between $\frac12$ and $1$ instead, for example, and then someone twice as fast as the others will always get to move first. Or an exponential distribution, which I think gives first-move probabilities closer to $s_i/(s_1+s_2+\cdots+s_n)$. Or a bell curve with positive mean, or whatever.

Second, you could change the relationship between the specified speed and the time the player takes. You can let $T_i$ be any monotonically decreasing function of $s_i$. In particular, taking $T_i = (1/s_i)^x = s_i^{-x}$ for some $x>1$ will indeed work to exaggerate the differences between players with different speeds, because $T_i$ will vary more rapidly with $s_i$. Or you could design your own function if you have a discrete set of values that $s_i$ can take. (In my opinion, though, the word "speed" should only apply to things that are actually inversely proportional to time. If you're not using $T_i = s_i^{-1}$, call your $s_i$ something else, like "initiative points" or something.)

So, the general scheme is as follows. For each player: Pick a nonnegative random number $\alpha_i$ independently from some chosen distribution. Determine the time factor $T_i = f(s_i)$ using a monotonically decreasing function $f$. Let $t_i = \alpha_i T_i$. Then: Sort the players by $t_i$.

share|improve this answer
    
Am I correct in stating that if we take $1/s_i$ to a power $x$, then increasing x past 1 will make the curve more steep? –  Joe Z. Nov 20 '12 at 18:19
    
@Joe: Yes. Please see my edit. –  Rahul Nov 20 '12 at 20:18
1  
P.S. The $p/(p+q)$ of the exponential distribution is exactly your logistic function on $\log(p/q)$. –  Rahul Nov 20 '12 at 20:58
    
This is much more general than my system. Thanks a bunch! As for the speed being inversely proportional to time thing, I guess using another distribution would mean that speed vs. time it's not exactly inversely proportional, but it is monotonically decreasing. Because speed might not just refer to velocity, but also reaction time and etc. –  Joe Z. Nov 20 '12 at 21:14
    
I understand that, but even so: If your reaction time is half that of mine, then under any reasonable definition of "reaction speed", your reaction speed is twice my reaction speed. If increasing your reaction speed by 10% halves your reaction time, then that's not reaction speed, that's... something else. But we're really just arguing semantics, so I won't belabour the point. –  Rahul Nov 20 '12 at 21:23
show 1 more comment

The system I currently have devised is based on a generalization of the logistic function, and works as follows:

Let $s_1, s_2, ..., s_n$ be the speed values of each of $n$ players.

Then, raise each $s_i$ to a fixed power $x$, and add all of them up to create the sum $\sigma$.

Then, $\displaystyle\frac{{s_i}^x}{\sigma}$ is the probability that each player moves first. Then, remove this player and repeat the algorithm calculating a new $\sigma$ to determine who moves second, and etc. until all the players have been ordered.

This formula satisfies all eight of the properties that I listed above, and in the case of two players, it is identical to the logistic function on $log(p/q)$ where $p$ and $q$ are the speed values of the two players respectively.

The number $x$ is adjustable - increasing it increases the steepness of the curve. If we set $x = 11.5267$, then a player that is 1.1 times as fast as the other player has a 75% chance of moving first.

However, I am interested in learning in or hearing about alternative systems for doing such a thing, or improvements on this system. It is possible that the algorithm that determines the random move order does not need to select one member from each set like mine does, which may not have made it satisfy the first or seventh property as perfectly as it might.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.