## Wednesday, February 29, 2012

### non-injective power mapping

Suppose $p$ is a prime and $f(a) = a^m$ is defined for $a$ that are relatively prime to $p$, then prove that $f$ is injective if and only if $m$ does not divide $p-1$.

Labels:
fermat,
injective,
Number Theory,
prime

## Tuesday, February 28, 2012

### Musings: rpg combat tuning part 1

After discussions with a few friends about the necessity of holy trinity in RPG (tank, dps / damage per second, healer), I began to wonder if it's possible to design a combat system such that the group doesn't need a tank, dps, or healer. Don't get me wrong, the concept of holy trinity will always be there, but would it be possible to design a system such that the need of a dedicated tank, dedicated healer, or dedicated dps is not needed, or can be variable?

The motivating use case is that in WoW, the standard group composition is 1 tank 3 dps 1 healer (1-3-1). What about 1-2-2? It certainly can work, as long as there's no enrage timer, hard or soft. But what about 1-4-0? It almost certainly won't work. 0-5-0 is even worse. This alone puts some constraints on the nature of group composition, is that you need a dedicated tank, a dedicated healer, and the rest can be dps or healers. The second tank probably won't help that much. Furthermore, each player much squarely choose to be a tank, a dps, or a healer. No double-classing, no double dipping skill points (talents). Thus, you can't have a group that's comprised of, say, 1.5 tank, 2.5 dps, and 1 healer. My goal of this musings is to allow a more creative group composition and that they'd be seriously viable to complete the dungeon. Within reason. (0-0-5 will never work no matter how you put it). To add into your curiosity, there are youtube videos of 10 blood death knight killing a heroic raid boss in Firelands when the content was current (seriously, search it).

To formalize the goal of this article, here are the basic principles:

With that in mind, let's look into the most basic version

Basic Version

First some assumptions:

Now, in the world of perfect tuning, if the gear and skill level of the group is "just right", the boss would die right when the tank dies (or is left with 1 hp). Now, assuming that the configuration is $1-(n-2)-1$, this would translate to:

$$\frac{H}{(n-2)d} = \frac{T}{b-h}$$

The LHS represents the time it takes for dps to burn the boss down, and the RHS represents the time it takes for the boss to kill the tank. $b-h$ represents the incoming damage by the boss after being mitigated by the healer.

Now, suppose that this boss is also killable with $1-(n-3)-2$ configuration, we have additional constraint:

$$\frac{H}{(n-3)d} = \frac{T}{b-2h}$$

Solving both equations, we have $b = (n-1)h$ and $H / d = T / h$. Furthermore, as long as those two relations are satisfied, for any real number $0 \leq k \leq n-1$ we have:

$$\frac{H}{(n-k-1)d} = \frac{T}{b-kh}$$

This means that as long as you have one tank, the number of healers can be any number from zero to $n-1$, and the rest is dps. Note that $k$ doesn't have to be an integer, which gives credence to our assumption as having "1-2.5-1.5" composition or whatnot. Here, $k$ represents the number of healers.

The required relations are then:

1. $b = (n-1)h$. This means that hps of a healer is not a match to the hps of the boss. The tank HP WILL go down steadily throughout the fight, which means that the fight must be sufficiently long otherwise RNG will be too prominent in the fight. Moreover, a short fight won't be fun for everyone.

The length of the time is $H/d(n-k-1) = T/h(n-k-1)$. In order for this fight to be long, then $H/d = T/h$ must be a large quantity. In other words, boss hp is large compared to player dps and consequently, boss dps is small compared to tank hp.

This is the first radical departure from the Wow model: slow early fight assumption. If we want the fight to last 50 seconds with $1-(n-2)-1$ configuration, then the tank health is roughly 50 times $b$. There is no danger of tank dying randomly in the middle of the fight, and damage cannot by spiky. The danger of wipe only comes towards the end when the tank seems to be low on health versus dps trying to burn the last of the boss.

2. $H/d = T/h$, or equivalently $H = Td/h$. The quantity $Td/h$ cannot be arbitary. It is a function of player gear and skill that's intended for that fight. The boss needs to be tuned such that his hp $H$ satisfies that relation. The boss damage $b$ is tuned to be $b = (n-1)h$. The values of $T,d,h$ themselves are not pegged one way or another. Their relative values are only important in PVP (eg, to determine the burstiness and length of average 1v1 game).

Corner case: if the configuration is $1-0-(n-1)$, the boss dps matches healer's hps exactly, so the tank won't die. But since none of them does any dps, the boss won't die either. While this is not a kill, it's not a wipe either, and it's consistent with our definition of well-tuning.

Now, if there are no tanks, we could argue that the players themselves becomes the tank. The collective health pool of healers and dps can be combined to become the "tank." The challenges here is that players must be good enough to taunt off each other just at the right time. Also, the effectiveness of the dps or healer that's currently being hit by the boss is reduced (e.g., spell pushback, hit/expertise requirement from the front, etc). As long as the average health pool of a player is well above $T / n$, the fight is still reasonably-tuned. Note that we're talking about effective health. So even if an average player has, say, 60% the hp of a tank, they won't have the same amount of armor mitigation, magical resistance, damage reduction cooldowns, avoidance, etc. Assumption of $T/n$ isn't that far-fetched assuming $n$ is not too large.

Now, if we have $2-(n-3)-1$, the equation becomes:

$$\frac{H}{(n-3)d} ? \frac{2T}{b-h}$$

which simplifies to $4 ? n$. In other words, if $n = 4$ then the fight is still equally tight-tuned, but if $n > 4$, then the fight is under-tuned (the boss dies well before tank dies). This is where the model breaks down. In fact, the more tanks there are, the more the fight is under-tuned. This is because the presence of the second tank greatly increases the tanks' collective health pool, but the loss of dps doesn't compensate enough.

More radically, if we have $(n-1)-1-0$, the fight is greatly under-tuned, albeit extremely boring, while $2-0-(n-2)$ is severely under-tuned (because no matter how small incoming damage is reduced to, there is still zero group dps but a finite number of collective health pool).

In essence, the model's main weakness is this: In the presence of multiple tanks, a healer is a liability compared to a dps.

There are several ways we can correct this situation, which we shall visit in future articles:

Another thing to note is that we didn't address how difference in mitigation from tank to tank would factor into healing. For example, if tank A has 10k hp with 50% damage mitigation, and tank B has has 5k hp with 75% damage mitigation, they both have 20k effective health. But tank B is far preferable to healers. We can easily rectify this situation by imposing that all tanks will have similar amount of health and mitigation. Wow somehow achieves this via harsh diminishing return curves for parry, dodge, and armor. The rest of our equation is still valid with this restriction.

The motivating use case is that in WoW, the standard group composition is 1 tank 3 dps 1 healer (1-3-1). What about 1-2-2? It certainly can work, as long as there's no enrage timer, hard or soft. But what about 1-4-0? It almost certainly won't work. 0-5-0 is even worse. This alone puts some constraints on the nature of group composition, is that you need a dedicated tank, a dedicated healer, and the rest can be dps or healers. The second tank probably won't help that much. Furthermore, each player much squarely choose to be a tank, a dps, or a healer. No double-classing, no double dipping skill points (talents). Thus, you can't have a group that's comprised of, say, 1.5 tank, 2.5 dps, and 1 healer. My goal of this musings is to allow a more creative group composition and that they'd be seriously viable to complete the dungeon. Within reason. (0-0-5 will never work no matter how you put it). To add into your curiosity, there are youtube videos of 10 blood death knight killing a heroic raid boss in Firelands when the content was current (seriously, search it).

To formalize the goal of this article, here are the basic principles:

- To clarify, we are not trying to improve upon WoW or any other RPG combat systems out there. Rather, we are trying to come up with a new system from scratch. A few games such as Guild Wars 2 claimed that it IS possible to alleviate the need of a dedicated tank, but they still need a healer (if I'm reading the beta reviews correctly).
- We are not concerned with what's fun to play or not. Ok maybe we are, but that's a secondary issue that might be revisited in future articles. Part of what makes current RPG so fun is that sense and element of danger that RNG can screw you off or reward you handsomely. As you shall see, in the system that I designed, the effect of RNG is greatly minimized. Any element of fun should come from the encounter design and not the combat system design itself.
- In part 1 (this article), we shall concern ourselves with a pure tank-and-spank style game (Patchwerk style). Anything that deals with movement, environmental damage, adds, etc, would unnecessarily complicate the calculation.
- Furthermore, we're assuming that players are reasonably intelligent. That is, they won't put all their skill points into tanking perks and play as a healer, while wearing dps gear. We're assuming that all players will wear roughly equivalent gear and play equivalently well.

With that in mind, let's look into the most basic version

Basic Version

First some assumptions:

- Each group is comprised of $n$ people.
- DPS: tank and healer does zero (negligible) dps, and all dps does $d$ dps. This would mean that the tank would have some other mechanisms to keep the boss aggroed. One possible solution is that a taunt is permanent until further overwritten (or until tank is dead). The boss does $b$ dps.
- HPS (heal per second): tank and dps does zero self-hps. Health does not regenerate in combat. Healer does $h$ hps. The boss does zero hps.
- Health: The tank has $T$ effective health, and the boss has $H$ effective health. The rest of the players' health should be irrelevant for this version.
- No built in enrage timer, soft or hard.

Now, in the world of perfect tuning, if the gear and skill level of the group is "just right", the boss would die right when the tank dies (or is left with 1 hp). Now, assuming that the configuration is $1-(n-2)-1$, this would translate to:

$$\frac{H}{(n-2)d} = \frac{T}{b-h}$$

The LHS represents the time it takes for dps to burn the boss down, and the RHS represents the time it takes for the boss to kill the tank. $b-h$ represents the incoming damage by the boss after being mitigated by the healer.

Now, suppose that this boss is also killable with $1-(n-3)-2$ configuration, we have additional constraint:

$$\frac{H}{(n-3)d} = \frac{T}{b-2h}$$

Solving both equations, we have $b = (n-1)h$ and $H / d = T / h$. Furthermore, as long as those two relations are satisfied, for any real number $0 \leq k \leq n-1$ we have:

$$\frac{H}{(n-k-1)d} = \frac{T}{b-kh}$$

This means that as long as you have one tank, the number of healers can be any number from zero to $n-1$, and the rest is dps. Note that $k$ doesn't have to be an integer, which gives credence to our assumption as having "1-2.5-1.5" composition or whatnot. Here, $k$ represents the number of healers.

The required relations are then:

1. $b = (n-1)h$. This means that hps of a healer is not a match to the hps of the boss. The tank HP WILL go down steadily throughout the fight, which means that the fight must be sufficiently long otherwise RNG will be too prominent in the fight. Moreover, a short fight won't be fun for everyone.

The length of the time is $H/d(n-k-1) = T/h(n-k-1)$. In order for this fight to be long, then $H/d = T/h$ must be a large quantity. In other words, boss hp is large compared to player dps and consequently, boss dps is small compared to tank hp.

This is the first radical departure from the Wow model: slow early fight assumption. If we want the fight to last 50 seconds with $1-(n-2)-1$ configuration, then the tank health is roughly 50 times $b$. There is no danger of tank dying randomly in the middle of the fight, and damage cannot by spiky. The danger of wipe only comes towards the end when the tank seems to be low on health versus dps trying to burn the last of the boss.

2. $H/d = T/h$, or equivalently $H = Td/h$. The quantity $Td/h$ cannot be arbitary. It is a function of player gear and skill that's intended for that fight. The boss needs to be tuned such that his hp $H$ satisfies that relation. The boss damage $b$ is tuned to be $b = (n-1)h$. The values of $T,d,h$ themselves are not pegged one way or another. Their relative values are only important in PVP (eg, to determine the burstiness and length of average 1v1 game).

Corner case: if the configuration is $1-0-(n-1)$, the boss dps matches healer's hps exactly, so the tank won't die. But since none of them does any dps, the boss won't die either. While this is not a kill, it's not a wipe either, and it's consistent with our definition of well-tuning.

Now, if there are no tanks, we could argue that the players themselves becomes the tank. The collective health pool of healers and dps can be combined to become the "tank." The challenges here is that players must be good enough to taunt off each other just at the right time. Also, the effectiveness of the dps or healer that's currently being hit by the boss is reduced (e.g., spell pushback, hit/expertise requirement from the front, etc). As long as the average health pool of a player is well above $T / n$, the fight is still reasonably-tuned. Note that we're talking about effective health. So even if an average player has, say, 60% the hp of a tank, they won't have the same amount of armor mitigation, magical resistance, damage reduction cooldowns, avoidance, etc. Assumption of $T/n$ isn't that far-fetched assuming $n$ is not too large.

Now, if we have $2-(n-3)-1$, the equation becomes:

$$\frac{H}{(n-3)d} ? \frac{2T}{b-h}$$

which simplifies to $4 ? n$. In other words, if $n = 4$ then the fight is still equally tight-tuned, but if $n > 4$, then the fight is under-tuned (the boss dies well before tank dies). This is where the model breaks down. In fact, the more tanks there are, the more the fight is under-tuned. This is because the presence of the second tank greatly increases the tanks' collective health pool, but the loss of dps doesn't compensate enough.

More radically, if we have $(n-1)-1-0$, the fight is greatly under-tuned, albeit extremely boring, while $2-0-(n-2)$ is severely under-tuned (because no matter how small incoming damage is reduced to, there is still zero group dps but a finite number of collective health pool).

In essence, the model's main weakness is this: In the presence of multiple tanks, a healer is a liability compared to a dps.

There are several ways we can correct this situation, which we shall visit in future articles:

- We can give tanks and healers some nontrivial dps, so that a group without any dps still has chance to kill the boss. Consequently, the healer dps must be nerfed a little bit so that a group of $0-0-n$ or $1-0-(n-1)$ can still wipe.
- We can make multiple tanks composition a little bit less effective. For example, the boss could gain an increased dps buff if he kills someone or is taunted.
- An alternative to nerf multi-tanks: only the FIRST tank gets an hp of $T$, but subsequent tanks' hp won't be as high. This could be achieved via an npc that the MAIN tank talks to before the fight, that increases the main tank's hp from normal to $T$, and only usable once. This is less elegant, but is viable, and somehow similar to Thrall's buff in Ultraxion encounter.

Another thing to note is that we didn't address how difference in mitigation from tank to tank would factor into healing. For example, if tank A has 10k hp with 50% damage mitigation, and tank B has has 5k hp with 75% damage mitigation, they both have 20k effective health. But tank B is far preferable to healers. We can easily rectify this situation by imposing that all tanks will have similar amount of health and mitigation. Wow somehow achieves this via harsh diminishing return curves for parry, dodge, and armor. The rest of our equation is still valid with this restriction.

## Tuesday, February 21, 2012

### Maximal non-intersecting boat tours

In a country, there are $n$ islands, and each island has exactly one port. A travel agency is planning a series of boat tours where it would employ a number of boats that start and end on these ports. They must obey these rules:

1. Each tour starts and ends at the same port and does not stop at any other port. That is, each tour is a loop that passes through exactly one port.

2. No two tours may intersect each other, except at ports.

3. For two distinct tours A and B, either A must circle an island that B doesn't, or B circles an island that A doesn't. By "circling" an island we mean: the region created by the tour contains the island.

Assuming that all islands have non-zero area and all boats are treated as points, what is the largest number of tours that can be run at the same time?

Solution

Answer: $2n$

First we will show an arrangement of $2n$ tours that satisfy the given constraints, and then we shall show that it is the largest attainable number.

For each island, have a tour that starts at that island and circle it closely to the shore so that we don't greatly alter the shape of the island. Altogether, there are $n$ of such tours.

Then, label the island $I_1, \dots, I_n$. For each $i = 2, \dots, n$, have a tour that starts at $I_1$, circles $I_1, \dots, I_i$ and comes back to $I_1$. There are $n-1$ such tour. Finally we can have a tour that doesn't circle any island. In total, there are $2n$ tours.

The proof for maximality is similar to our construction. There can be at most one tour that doesn't circle any island, and there can be at most $n$ tours that circle exactly one island. Now we show that there are at most $n-1$ tours that circle multiple islands. Let's call a tour that circles multiple islands a "complex" tour.

Suppose $T_1$ and $T_2$ are both complex tours and both circle an island in common $I_1$. Furthermore, WLOG, we can assume that $T_1$ circle an island $I_2$ that $T_2$ doesn't. We assert that $T_2$ must be inside $T_1$. Otherwise, the possibilities are either $T_1$ is inside $T_2$, which is impossible since $T_2$ doesn't contain $I_2$, or that they are disjointed, which is impossible because they both contain $I_1$, or that they intersect. There must be at least two points of intersection, but they can only intersect in ports and they each can stop in oneport only, also impossible. Thus, we have just proved the following statement:

Given two complex tours, either they are disjoint or one is inside the other.

From here, it's matter of induction to show that there can be at most $n-1$ complex tours given $n$ islands. Take the smallest complex tour $T$ that does not contain another complex tour. $T$ circles at least two islands, and any other complex tour either contains $T$ or is disjoint from $T$. So as far as other complex tours are concerned, we can regard $T$ as an island on its own, thereby reducing the number islands by at least 1. Since there are now at most $n-1$ "islands", then there are at most $n-2$ complex tours. Altogether with $T$, we have at most $n-1$ tours.

1. Each tour starts and ends at the same port and does not stop at any other port. That is, each tour is a loop that passes through exactly one port.

2. No two tours may intersect each other, except at ports.

3. For two distinct tours A and B, either A must circle an island that B doesn't, or B circles an island that A doesn't. By "circling" an island we mean: the region created by the tour contains the island.

Assuming that all islands have non-zero area and all boats are treated as points, what is the largest number of tours that can be run at the same time?

Solution

Answer: $2n$

First we will show an arrangement of $2n$ tours that satisfy the given constraints, and then we shall show that it is the largest attainable number.

For each island, have a tour that starts at that island and circle it closely to the shore so that we don't greatly alter the shape of the island. Altogether, there are $n$ of such tours.

Then, label the island $I_1, \dots, I_n$. For each $i = 2, \dots, n$, have a tour that starts at $I_1$, circles $I_1, \dots, I_i$ and comes back to $I_1$. There are $n-1$ such tour. Finally we can have a tour that doesn't circle any island. In total, there are $2n$ tours.

The proof for maximality is similar to our construction. There can be at most one tour that doesn't circle any island, and there can be at most $n$ tours that circle exactly one island. Now we show that there are at most $n-1$ tours that circle multiple islands. Let's call a tour that circles multiple islands a "complex" tour.

Suppose $T_1$ and $T_2$ are both complex tours and both circle an island in common $I_1$. Furthermore, WLOG, we can assume that $T_1$ circle an island $I_2$ that $T_2$ doesn't. We assert that $T_2$ must be inside $T_1$. Otherwise, the possibilities are either $T_1$ is inside $T_2$, which is impossible since $T_2$ doesn't contain $I_2$, or that they are disjointed, which is impossible because they both contain $I_1$, or that they intersect. There must be at least two points of intersection, but they can only intersect in ports and they each can stop in oneport only, also impossible. Thus, we have just proved the following statement:

Given two complex tours, either they are disjoint or one is inside the other.

From here, it's matter of induction to show that there can be at most $n-1$ complex tours given $n$ islands. Take the smallest complex tour $T$ that does not contain another complex tour. $T$ circles at least two islands, and any other complex tour either contains $T$ or is disjoint from $T$. So as far as other complex tours are concerned, we can regard $T$ as an island on its own, thereby reducing the number islands by at least 1. Since there are now at most $n-1$ "islands", then there are at most $n-2$ complex tours. Altogether with $T$, we have at most $n-1$ tours.

Labels:
boat,
Combinatorics,
differential geometry,
Geometry,
induction,
island,
topology

## Wednesday, February 8, 2012

### A Divided Kingdom

A kingdom has the shape of a convex $n$-sided polygon $A_1 \dots A_n$. The King owns a castle at point $O$ in the interior of the kingdom, and he has $n$ princes, $P_1, \dots P_n$. They are each given a castle at the vertices of the polygon, so that prince $P_i$ has a castle precisely at $A_i$. The area $OA_iA_{i+1}$ is called the province $i$.

One day, a strife breaks out in the kingdom and each prince declares independence from the King. As a result, each province is divided into one or more vassals, each of which is shaped like a triangle. (Note that each province is a triangle to begin with, so some of the more stable province do not necessarily break apart into multiple vassals). At the vertices of these triangles, a citadel (a smaller castle) was erected.

Each castle and fort then declares an allegiance to King or one of the princes while following these rules:

1. Each castle declares allegiance to its original owner. That is, castle at $O$ keeps its allegiance to the King and castle at $A_i$ keeps its allegiance to prince $P_i$.

2. Each citadel that lies in the province border declares allegiance to either one of the owner of the castles at the endpoints of the province border. For example, a citadel that lies in the line $A_1 A_2$ may declare allegiance to prince $P_1$ or $P_2$, and a citadel that lies in the line $OA_3$ may declare allegiance to either the King or prince $P_3$.

3. Each citadel that lies in the interior of a province declares an allegiance to either one of the owner of the castles at the vertices of the province. For example, a citadel that lies in the province 1 may declare allegiance to either the King, prince $P_1$, or prince $P_2$ (because province 1 is the triangle $OA_1A_2$).

Now, with all citadels and forts having declared allegiance, each vassal's ownership is resolved as follows. Note that each vassal is shaped like a triangle, so it has precisely three citadels or castles on the vertices. If two or more of those citadels or castles declare allegiance to an entity, then the vassal is owned by that entity. For example, if a vassal has vertices declaring allegiance to $P_1, P_2, P_1$, then that vassal is owned by prince $P_1$.

A vassal whose vertices declare allegiance to three different entities is then left in a constant state of war. Prove that the number of such vassals is $n+2k$ where $k$is a non-negative integer.

One day, a strife breaks out in the kingdom and each prince declares independence from the King. As a result, each province is divided into one or more vassals, each of which is shaped like a triangle. (Note that each province is a triangle to begin with, so some of the more stable province do not necessarily break apart into multiple vassals). At the vertices of these triangles, a citadel (a smaller castle) was erected.

Each castle and fort then declares an allegiance to King or one of the princes while following these rules:

1. Each castle declares allegiance to its original owner. That is, castle at $O$ keeps its allegiance to the King and castle at $A_i$ keeps its allegiance to prince $P_i$.

2. Each citadel that lies in the province border declares allegiance to either one of the owner of the castles at the endpoints of the province border. For example, a citadel that lies in the line $A_1 A_2$ may declare allegiance to prince $P_1$ or $P_2$, and a citadel that lies in the line $OA_3$ may declare allegiance to either the King or prince $P_3$.

3. Each citadel that lies in the interior of a province declares an allegiance to either one of the owner of the castles at the vertices of the province. For example, a citadel that lies in the province 1 may declare allegiance to either the King, prince $P_1$, or prince $P_2$ (because province 1 is the triangle $OA_1A_2$).

Now, with all citadels and forts having declared allegiance, each vassal's ownership is resolved as follows. Note that each vassal is shaped like a triangle, so it has precisely three citadels or castles on the vertices. If two or more of those citadels or castles declare allegiance to an entity, then the vassal is owned by that entity. For example, if a vassal has vertices declaring allegiance to $P_1, P_2, P_1$, then that vassal is owned by prince $P_1$.

A vassal whose vertices declare allegiance to three different entities is then left in a constant state of war. Prove that the number of such vassals is $n+2k$ where $k$is a non-negative integer.

Labels:
coloring,
Combinatorics,
Geometry,
invariance,
route,
tesselation,
topology,
triangulation

Subscribe to:
Posts (Atom)