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)$.


Thursday, 27 April 2017

夢.十夜 (1) The beginning

做了這樣一個夢。

我手上提著一盒壽司,慢慢地爬上四周貼滿補習社、樓上書店、理髮店以及色情玩具店海報的樓梯,進入一部由更多海報舖成的狹窄空間。前後左右,連頭頂也不放過;唯一可以看見素色的就只有地板了--不、地板上也散滿了掉下來的紙張,只是空白的背面沒那麼刺眼而已。

「叮」一聲,電梯緩緩在四樓打開了門。穿過左邊的文青型樓上書店和右邊的波鞋店,眼前是一條連接著兩梗大廈的橋樑。說是橋也不過是三四米左右的距離而已。兩邊用鐵絲網圍住大概就是防止有人在這裡跳下去吧。站在橋的中間向下望依稀可以看見幾座老舊的唐樓之間剛好空出了一小塊空地,上面排滿了一個個被清理完不久的垃圾筒,飄上來的一絲垃圾味被濃重的油煙味蓋過--魚蛋燒賣、煎釀三寶……還有新有的炸雞?不過我的思緒卻沒有和這些氣味糾纏太久,一個有趣的問題在我腦中閃過:在寸金買不到尺土的這片地方,空出這樣「被遺忘的一畝」是一件很奢侈的事情。到底以前是發生了甚麼事讓大廈圍繞這裡建成?這一格土地又屬於何人、以後又會怎樣--嘛,在這條街衰落之前大概不可能被重建吧。

其實穿過這條橋也就數秒的事。在兩層防火門之間我好好檢查一下這次的的裝備;水手服、有!過膝襪、有!水和毛巾、有!這可是去練舞的必要裝備,無論缺那一樣都會讓我渾身不舒服從而令表現變差。今天就先打兩道DEA(Dance Evolution Arcade)然後練十刀DDR(Dance Dance Revolution),以1100大卡為底限吧。我這樣想著推開了防火門,眼前的景象從破舊的唐樓變成了荒廢的商場:兩尺見方的白方瓷磚大概是唯一比較淨的東西;乾透的醬汁一點點地散落在牆邊的桌子上,幾張膠椅在旁邊東倒西歪;垃圾筒早已超過它所能承載的容量,本來可以旅轉良蓋子現在反面朝天,露出裡面的快餐紙袋,還有顯然是我前天來時留下的空壽司盒。完全空置的三樓從扶手電梯那邊傳來野戰的聲音;有人或許會問到底是軍事宅對這個免租的樓層加以利用,還是一對對小情侶在享受價比千金的happy moment--管它呢,那種地方我死也不會去。

一陣違和感從商場的另一邊傳了過來,明明是死寂的地方卻傳來了不該有的電子聲音。我把貼滿遊戲海報的玻璃門推開,模糊聲音立刻變得清晰可辨:前排是四個一組的街霸、拳王和鐵拳三代格鬥遊戲;中間放了傳統俄羅斯方塊(Classic tetris)、Pang、魂斗羅等中古經典小遊戲;後面貼牆的部分則是秋名山司機三五成群飆車的指定地點。裡面的違和感與其說是各種在發聲的機台倒不如說是機廳人滿為患,拳王等熱門遊戲不消說已經聚集了一群好武之人整裝待發,小眾遊戲如泡泡龍都有兩三人圍著討論機台和GBA版幀數算法不同引致爆彈用法上的分別--這不可能啊!這種平時只有我一個認真玩遊戲其他人都過來做偷偷摸摸的事的地方就算貼出即將結業的公告也沒人來吧!況且在一旁煙癮還沒發作的老闆在一邊老神在在地和小孩玩耍,兌銀機也還活得好好的,根本不像是快要結業的樣子。

真好啊。我想起那家平日人山人海卻被加租逼走、真正承載著滿滿回憶的機廳--