Wednesday 17 May 2017

FE Heroes: Arena Tiers

Recently FE Heroes adopted a new reward system which is kind of an extension of the classic promotion/demotion system. Players start from the tiers they have been in in the last season. At the end of each season a portion of players are promoted/demoted from their current tier (promotion to tiers more than a rank higher is possible).  Such system is quite popular among games that use tier rewards instead of fixed ranking (that saves the work of calculating the suitable amount of prize you want to give), and it enhances consistent participation. Another game that uses similar structure is the Venus Eleven.

In terms of mathematics, we may transform population into proportion, and instead of a distribution at a certain moment we look at probability distribution of a single node in the system. There are something from conventional mathematics that we can use immediately - the queuing theory.

The whole thing is basically just a birth and death process. You equate the in-flow rate and out-flow rate, set up the equations then it can be solved easily. Results say that the transition matrix has eigenvalues at most 1, so it is going to converge. You can always find the stable state vector by doing some tedious linear algebra work...but well we only care about the numerical result here, so it won't be a shame to solve the stable state vector using numerical method.

We do expect something like a geometric distribution. The reasoning from queuing theory is simple as well: let $p_n$ be the probability (proportion) of object at state 0, and let $\rho = \lambda / \mu$ be the traffic density. By checking the first equation with $\mu p_1 = \lambda p_0$ so that by induction you have $p_n = \rho ^n p_0$. If you have a queue of infinite capacity then $p_n = (1-\rho ) \rho ^n$. Here $\rho _i $ is not fixed but it's still approximately throughout and double promotion is possible, but if we focus at the top (recall the memoryless nature of this process) the process is pretty close to a classic M/M/1.

Below is the plotted graph for the long time distribution:

That could be a pleasant surprise to the players (in terms of its generosity) and to the mathematicians.

Why is it not geometric? Well it is quite geometric if you break it into two parts: tier 7-16 and tier 17-20. On the lower section we have $\rho >1$ so that most players tend to advances from their current tier, and on the upper section we have $\rho < 1$ so players struggles to go up.

What is surprising is that they did not make the top tier unreachable -- tier 20 contains top 7% of the players instead of like, 0.5~1% as (Asian) gaming veterans would have been expecting. This is quite generous --- or overly generous. Consider that there are around 100k active players in the pool currently, 7000 of them could be in the top tier that corresponds to the top 5.5 categories in the old system.

Putting that generosity aside, the idea of loosening award tiers in FEH does fit the philosophy of Nintendo / IS running the game. As mentioned, the game can be treated as part of the their experiment of adopting Japanese styled mobile online into western consumption patterns. They want to attract more consistent light spenders (mid-top players) rather than letting the game being dominated by a small group of heavy spenders.

Note the dynamics in the system: when we say 7% in the system that is for the population at the moment, but the proportion of players that wanders between 19-20 could be a lot more than that. In terms of feather rewards it's linear with tiers except for the top tier with a huge jump (2000 -> 3000), so if we want to draw a spectrum the reward for those high-end players are majored by their time spending in tier 20, and for the rest their average tier would be a good enough approximation.

The actual spectrum relies on the strength of the players that cannot be determined, so here is my approximated spectrum. Square bracketed number indicates the tier where player usually sits in (otherwise we assume they spend about equal amount of time among those tiers):

- Tier 20 Avg. 3000 (2%)
- Tier 19~20 Avg. 2500 (4%)
--------------------------------Top 7% // Tier 20
- Tier 18~[19]~20 Avg. 2200 (4%)
- Tier [18]~19~20 Avg. 2000 (5%)
- Tier 17~[18]~19 Avg. 1800 (5%)
--------------------------------Top 21% // Tier 19+
- Tier [17]~18 Avg. 1720 (5%)
--------------------------------Top 44% // Tier 18+

Even without drawing the spectrum explicitly you would expect the spike to occur among players who topped 19 but not quite enough to stabilize in 20. That includes 8~12% of all players and they are exactly the mid-top players that the developing team is aiming for -- if they spend some money (and effort) onto the game they might be able to push a bit further and receive a significantly increased award.

And, for me...I am sitting around the upper quartile line, I would expect myself to wander between 17~18 steadily. Of course, 18 gives an orb more so I should push a bit harder, too...

Tuesday 2 May 2017

Two game mechanics (2)

Here are two more observations that was made long time ago but recently came into my mind in some other form again.

Question from a Monopoly-like board game

If you have played Monopoly before you must have met situations where you really want to land on a certain grid for whatever reason (to grab a set of lands, to build houses etc) right? In that case the only thing you can do it to ride you luck and hope that you diced the right number.

Of course, however, in online games these can be easily negotiated. Item comes into play and give certainty on what number you can get from the dice, with some cost as well. You want to use those item wisely, so here is our model:

- A circular board of 22 grids.
- A fair square dice is used each round by default. Items maybe used to specify the dicing outcome.
- 4 bonus grids spreads uniformly over the 21 grids (except the starting grid). One must land on that grid exactly to receive bonus.
- 6 rounds in total. Note that it is theoretically possible to get all 4 bonuses regardless of the bonus distribution.
Goal: we want to land on all 4 bonus grids every time, while minimizing the usage of items.


You would expect that 3~5 items are used each time: if the distance from treasure is less than 6 you have no choice but to use an item to make sure that you reach the treasure. Sometimes you have to stretch faraway enough to reach those grids.

But what about the average usage of each of those numbers 1/2/3/4/5/6? Are they the same?

Well, simple simulation shows that the distribution is approximately geometric. But it turns out that my average usage on all 6 items are almost the same, which is an interesting fact to investigate at. Below is my thoughts:

First of all, it's natural to use a lot of 1/2 according to our distribution. At the same time if we uses lots of 1/2 then we might need to use more 5/6 as the rest of the grids are more sparsely spread.  What about 3/4? This is in fact the most mysterious part in my point of view but a possible reason is that the most probable distance that requires multiple rounds is of course the 7-9 range, and there is a high chance that you will need to use 3/4 to correct your position.

(For instance if the distance is 8 then there is a 4/9 chance that you will be using 3/4 once. This can be done by simply listing all possible outcomes. (x) is the correction step:

6 - (2)
5 - (3)
4 - (4)
3 - (5)
2 - 6
2 - 5 - (1)
2 - 4 - (2)
2 - 3 - (3)
2 - 2 - (4)
2 - 1 - (5)
1 - 6 - (1)
1 - 5 - (2)
1 - 4 - (3)
1 - 3 - (4)
1 - 2 - (5)
1 - 1 - (6)

Therefore the chance is 2/6 + 4/36 = 4/9.)

But given the geometric/exponential nature 7-9 won't happen that often after all. It is still very hard to explain my uniform usage of those items.

Of course, this is not even a problem for the developers -- this is something that only the players should worry about. Imagine that the board game comes from an extremely popular online game where 24/7 grinding + unlimited potion is required to get a rank up high, and the actual usage is uneven ("the alternative hypothesis"), knowing the correct distribution would save you several minutes from going back to the shop, hence giving you an edge over other players ---

Luckily the game I mentioned, is not competitive at all.

Exponential effort resulting in linear growth

Systems requiring exponential effort for linear growth is a canonical choice. It appears in most RPG (as well as idle games), based on the fact that exponential growth overwhelms any polynomial growth from whatever percentage bonus. The implementation is usually simple too. EXP bar that grows exponentially, item prices that grow exponentially, time requirements that grow exponentially...

But are there more implicit implementation of this trick? Some may suggest an item forging system so that when you forge A into B, A gains a fraction of the power of B -- you can still see the exponential nature behind: you need $2^N$ items to boost the item $N$ times (proportionally, and if we ignore the higher terms).

But recently there is a game that allows unlimited forging on the same item: on the Nth forge, 1/(N+r)k fraction of the power is merged into the item, where r and k are constants.

The developer is using harmonic series smartly here, with the fact that harmonic series is asymptotic to the log function. Let us do the mathematics here:

Suppose we have $2^N-r$ identical items of power 1. By forging everything into the same item, the new power is given by:

$1 + \sum _{i=r}^{2^N}\frac{1}{ik} \approx 1 + k^{-1}(N\ln 2 - \ln r)$

And if we have $2^N$ items and we forge it in the usual `exponential way' we get

$(1+\frac{1}{rk})^N  \leq 1 + \frac{5}{4}\frac{N}{rk}$

we use the constant 5/4 as for a generous upper bound.

Exponential effort is clearly necessary for linear growth. It prevents players from forging items using the usual `exponential way' as well. This is clear by checking the following equation

$N \ln 2 - \ln r - \frac{5}{4}\frac{N}{r} \geq 0$

to be feasible for most reasonable $r, N$, like $(N,r) = (5,3)$.