The effect of trolls on Twitch Plays Pokémon

João V. Tomotani

Universidade de São Paulo; São Paulo, Brazil.

Email: t.jvitor (at) gmail (dot) com

Download PDF

In a previous paper, I presented a curious experiment of a fish playing Pokémon, made real and popular thanks to the wonders of the Internet (Tomotani, 2014). The Twitch Channel (Twitch, 2016), which sadly has been inactive for some time now, showed Grayson, the fish, playing Pokémon Red with the help of an image identification software, and was watched by millions of people (Johns, 2014). I showed that, when assuming that a fish player was the same as a random input of commands – a premise I do not find absurd – it would take quite a while to advance through a single route (although a very complex one) in the game (Fig. 1): circa 115,700 years.

troll-figure-01

Figure 1. Route 23; image taken from Tomotani (2014). The many ledges, which could make the path much more tortuous, made the Twitch Play community come up with the infamous name “Ledge Simulator”.

The peculiar premise of a fish playing Pokémon obviously derived from the original Twitch Plays Pokémon, a game of Pokémon Red where everyone watching the stream could type commands in the chat window. An IRC bot would read and execute the commands in the game. The available commands were the classic Gameboy keys: A, B, Up, Down, Left, Right, Start and Select.

Since the inputs came from rational human beings, with defined intentions and minimal coordination, supposedly the game should be less frustrating than watching a fish swimming and randomly inputting commands in the game – the key word in this phrase being “supposedly”.

The point is (besides, of course, the difficulty in coordinating thousands of people to avoid incorrect commands), not all of the people participating in the event wanted to complete the game. In fact, some of them wanted to make matters as difficult as possible for the other players, as their goal was solely to make the Twitch Plays Pokémon a frustrating experience for anyone wanting to be a crowdsourced Pokémon master. (In their “defense”, I find it hard to believe that this sort of behavior was not one of the intentions of the programmer of this game, described by him as a “social experiment”; Alcantara, 2014.) This group of people is given the name of trolls.

The impact of trolls on Twitch Plays Pokémon was so peculiar that it resulted in a curious work, where Machine Learning techniques were used to detect anomalous inputs in the game (from a base of 38 million data points), trying to identify potential trolls (Haque, 2014). The objective of the present study is to see exactly how the percentage of trolls inputting commands on Twitch Plays Pokémon affected the time for completing Route 23 in the game.

TROLLS

Trolls are creatures from Nordic and Scandinavian myths and folklore, made popular in the 20th century by pop culture, starting with J.R.R. Tolkien’s books, going through Dungeons & Dragons and Harry Potter to the thousands, possibly tens of thousands, of other novels, comics, games etc. which they inspired.

Troll is a term applied to the Giants of Norse Mythology (the Jötnar), a race that live in Jötunheimr, one of nine worlds in Norse cosmology. There is some confusion about the terms, though, as jötunn (the singular form of Jötnar), troll, þurs, and risi frequently overlap and are used to describe many beings in the legends. Some researchers point out that there are distinct classes of these creatures, but the terms are frequently considered synonyms in late medieval literature and all of them are frequently translated to English simply as “giant” (Jakobsson, 2005). In a late saga of the Icelanders (Bárðar saga Snæfellsáss; probably from the early 14th century), a passage at the very beginning claims that risi and troll not only are distinctive races, but are, respectively, at the opposite ends of the binary divide of good and evil (Jakobsson, 2005).

The Internet term “troll”, however, does not come from such creatures. The term “trolling” means luring others into pointless and time consuming discussions, deriving from the practice used in fishing where a baited line is dragged behind a boat (Herring et al., 2002).

troll-figure-02

Figure 2. Trollface, a popular internet meme based in “rage comics”. – Did you just read two paragraphs about creatures in Norse mythology that have absolutely nothing to do with this topic?

The idea of trolling always seems to be related to communication, mostly computer-mediated communication (CMC). Hardaker (2010) analyzed a 172-million-word corpus of unmoderated, asynchronous CMC to try to formulate an academic definition of trolling. After his analysis, he proposes that:

A troller is a CMC user who constructs the identity of sincerely wishing to be part of the group in question, including professing, or conveying pseudo-sincere intentions, but whose real intention(s) is/are to cause disruption and/or to trigger or exacerbate conflict for the purposes of their own amusement. Just like malicious impoliteness, trolling can (1) be frustrated if users correctly interpret an intent to troll, but are not provoked into responding, (2) be thwarted, if users correctly interpret an intent to troll, but counter in such a way as to curtail or neutralize the success of the troller, (3) fail, if users do not correctly interpret an intent to troll and are not provoked by the troller, or, (4) succeed, if users are deceived into believing the troller’s pseudo-intention(s), and are provoked into responding. Finally, users can mock troll. That is, they may undertake what appears to be trolling with the aim of enhancing or increasing affect, or group cohesion.

― Hardaker, 2010: p. 237.

The definition of “trolling” for the present study is not strictly the same, since the troll does not necessarily has the intention of portraying any good will toward the group’s goal of completing the Pokémon game. The intention of creating conflict and frustrating a group of people for personal amusement, though, is very similar. As such, we shall use a less strict definition of trolls, so that we may keep calling them such.

The percentage of people deliberately trolling on the Internet is never clear. Since trolls tend to draw too much attention, it is easy to believe they are more numerous. In the Twitch Plays Pokémon case, this was particularly true: a single input from a troll at the wrong time (or right time, from the troll’s point of view) and the avatar in the game would jump down a ledge, making many more inputs necessary for the avatar to go back to the same coordinate.

THE FIRST SIMULATION MODEL

For the present study, I wanted to know how trolls affected the time for completing Route 23 in Twitch Plays Pokémon. The first step was to develop a simulation model in VBA. A map for Route 23 composed of 305 different coordinates was generated (the same as seen in Tomotani, 2014) and the neighbors for each coordinate were defined. For each coordinate, I defined three different inputs: the “optimal route” (the command which a player wanting to finish the game would input) and two different “troll inputs”. The latter are commands that would make the route as long and frustrating as possible. I defined two different troll inputs because: (a) there were times when two commands could be equally bad; (b) trolls not always want to troll the same way; and (c) to add some variation to the routes’ heat maps presented in this analysis.

The premises to define the commands for the optimal route were:

  • Always go through the shortest path towards the objective (the door at the end of Route 23);
  • When two commands are equally good, stay away from ledges for as long as possible.

The premises to define the troll commands were as follows:

  • If you are close to a ledge you normally would not want to jump over, jump;
  • Go away from the direction you are supposed to go;
  • Only input “movement” commands (to simplify the model by not having to create simulation models for the game’s menu screen).

Once the simulation model was complete, I defined a “troll factor”, that is, the number of trolls inputting commands. Thus, the troll factor represents the percentage of players that are, in fact, trolls trying to prevent the group from completing the route.

In the simulation, we randomly decided whether the next command would be an “optimal” command or a “troll” command. The chance of the command being a “troll input” was equal to the “troll factor”. Figure 3 shows a heat map of time spent in each coordinate when the troll factor was zero. Since there is no probabilistic factor (that is, all commands made are optimal), this route is always the same: it takes 70 steps to complete this path.

troll-figure-03

Figure 3. Optimal route, when the troll factor is zero, completed in 70 steps.

Figure 4 shows a heat map of time spent in each coordinate for a simulation run when the troll factor was 10%, that is, on average one out of every ten inputs was made by a troll. In this specific run, it took 285 steps to complete the route, more than four times longer than the optimal path. When tested with a troll factor of 20%, the number of steps necessary reaches the thousands. Figure 5 is an example, where 1,011 steps had to be taken to complete the route.

troll-figure-04

Figure 4. Simulation run with troll factor of 10%, completed in 285 steps.

troll-figure-05

Figure 5. Simulation run with Troll factor of 20%, completed in 1,011 steps.

THE SECOND SIMULATION MODEL

The VBA model, though, proved inefficient when dealing with higher troll factors, constantly crashing or giving inconsistent results. As such, I decided to use a more appropriate tool, and developed a simple Discrete Event Simulation Model on the Rockwell Arena software (ARENA, 2016). This model can be seen in Figure 6. (For more information on simulations with this software, see Altiok & Melamed, 2007; and for more on Discrete Event Simulation, see Banks et al., 2009).

On this simulation model, the coordinates were indexed in a “305 lines x 4 columns” matrix in the software, where each line was a coordinate, and each column contained the possible neighbors. With a “Create” module, 100 entities were inserted simultaneously in the model, each representing a different simulation run. Each entity had an attribute named “position”, where the current coordinate of the simulation was recorded, and a “total steps” attribute, where the number of steps necessary to finish the simulation run was recorded.

troll-figure-06

Figure 6. Simulation model on Rockwell Arena.

In each step of the simulation, a “Decide” module of the Arena decided whether the next command inserted for each run was a “normal” or a “troll” one, and the “position” attribute of each entity was updated. When the current position of an entity was the coordinate for the door at the end of Route 23, the simulation was terminated and the total number of steps to finish the route was registered. At the end of the simulation, a “Read and Write” module was used to record some additional information at an Excel worksheet, such as number of steps on each cell, and number of steps on each area (more of this below).

To see how the percentage of trolls (“troll factor”) affected the number of steps, I made various simulations. For each troll factor used, I ran 100 simulations and calculated the average number of steps to complete Route 23 (it took a while for the 50% troll factor!). The results can be seen on Table 1 and Figure 7.

Table 1. Average number of steps (out of 100 simulations) necessary to finish Route 23.

troll-table-01 troll-figure-07

Figure 7. Well, that escalated quickly. (Keep in mind that the Y axis is in logarithmic scale.)

In other words, with a single troll command in every 20, it is already enough to make traversing this map twice as difficult, and when 50% of the inputs were made by trolls (well… in this case it is almost a philosophical question whether the trolls are the ones trying to prevent others from completing the game or the ones effectively trying to complete it), the number of steps necessary was more than 264,000 times greater than the optimal route.

Additionally, I divided Route 23’s map into five different areas (Fig. 8) to analyze how much time was spent in each area for each troll factor. The results can be seen on Table 2 and Figure 9. It is clear that, the greater the troll factor, the easier it is for the avatar of the game to jump over the lower ledge and into “Area 5”, where he spends most of the time. (See the Appendix for heat maps with average results.)

troll-figure-08

Figure 8. Division of Route 23 into five areas.

Table 2. Percentage of time spent on each of the five Areas for varying troll factors.

troll-table-02

troll-figure-09

Figure 9. Percentage of time spent in each of the five Areas for varying troll factors.

With these results, it is clear that trolls can be a pain whenever you are trying to conduct some nice experiment online, or have a good argument. Herring et al. (2002) speculate about why trolls (or “trollers”, as he puts it) troll, suggesting that the actions may be a result of: hatred towards people who are perceived as different or threatening by the troller (e.g., women or homosexuals); sense of control and self-empowerment when groups are targeted for their vulnerability (such as disabled people or inexperienced users); or simply because trollers enjoy the attention they receive, even (and maybe especially) when it is negative. According to Herring et al. (2002), this suggests that ignoring the troller might truly be an effective way of thwarting him/her (a.k.a. “don’t feed the troll”). Sadly, this is much harder to do in Twitch Plays Pokémon.

AND WHAT ABOUT THE FISH?

Now consider again my previous work (Tomotani, 2014), where I discussed the fish Grayson and his journey to be a Pokémon master. When you think about it, the average number of steps necessary for a simulation with 50% of trolls seems a bit underwhelming. Considering that one command was inputted every 1.5 second, the 18.492.842 steps would be made in 321 days, less than one year, while random commands made by a fish would take more than 115 thousand years.

I tried to validate this number by using my model to simulate Grayson, but it would take way too long. I adapted the model so that, instead of deciding between a “troll” and “normal” input, it chose randomly between any of the four directions (Fig. 10). After ninety minutes and 5 billion steps, the model seemed no closer to concluding its task. A simple calculation showed me it would take close to 30 days to simulate the equivalent of 115 thousand years (not that long in comparison to the 10 million years it took Earth to calculate the question to the ultimate answer).

troll-figure-10

Figure 10. Adapted model for the “random” input. Here, the two “troll inputs” and the “optimal input” from the previous model are substituted by four different commands, one for each direction.

So, I aborted the idea of simulating the whole thing, and decided to limit my simulation. I made 10 simultaneous runs, each with a limit of 1 billion steps, 50 times more than the average it took for the troll factor of 50%. After this limit was reached, the simulation would stop and record the results to show how far the simulation managed to go. Spoiler alert: not a single one managed to finish the route. Figure 11 shows a heat map for this experiment, considering the sum of the 10 simulations, a total of 10 billion steps. Figure 12 gives a closer look at the hardest area to traverse (the narrow path on Area 3), where a single input “down” means lots of backtracking.

After 10 billion steps, only once the random simulation managed to get to the “signpost” coordinate, and never getting further than that (you can see the actual signpost in Fig. 12). Table 3 shows the distribution of steps in each Area (of those five defined above) by the random simulation. More than 95% of the time was spent in Area 5, the lower part of the map.

troll-figure-11

Figure 11. Heat map for the “random” simulation.

troll-figure-12

Figure 12. Closer look at the most critical part of the map, a narrow path on Area 3. The number on each coordinate represents the number of steps taken on that coordinate (the “###” represents very large numbers).

 Table 3. Steps taken in each area in “random” simulation.

troll-table-03

As such, the conclusion of my previous work that a random input of commands to complete the game is not a productive approach seems valid. This might be a possible explanation to the deactivation of the Fish Plays Pokémon channel, so that Grayson could focus his energy in activities that make better use of his skills.

REFERENCES

Alcantara, A.M. (2014) Twitch Plays Pokémon: a social experiment from its creator. Mashable, available from: http://mashable.com/2014/02/ 28/twitch-plays-pokemon/#5nL.FQX07sq3 (Date of access: 11/Sep/2016).

Altiok, T. & Melamed, B. (2007) Simulation Modeling and Analysis with ARENA.  Academic Press, Waltham.

ARENA. (2016) Arena Simulation Software. Available from: https://www.arenasimulation. com/ (Date of access: 17/Sep/2016).

Banks, J.; Carson II, J.S.; Nelson, B.L.; Nicol, D.M. (2010) Discrete-Event System Simulation, 5th ed. Prentice Hall, Upper Saddle River.

Haque, A. (2014) Twitch Plays Pokemon, Machine Learns Twitch: unsupervised context-aware anomaly detection for identifying trolls in streaming data. Available from: https://www. albert.cm/dl/twitch_paper.pdf (Date of access: 19/Sep/2016).

Hardaker, C. (2010) Trolling in asynchronous computer-mediated communication: from user discussions to theoretical concepts. Journal of Politeness Research 6(2): 215–242.

Herring, S.; Job-Sluder, K.; Scheckler, R.; Barab, S. (2002) Searching for safety online: managing “trolling” in a feminist forum. Information Society 18(5): 371–384.

Jakobsson, A. (2005) The Good, the Bad, and the Ugly: Bárðar saga and its Giants. Medieval Scandinavia 15: 1–15.

Johns, S. (2014) 20,000 anxiously watch a fish play Pokemon on Twitch TV. Available from: https://www.neowin.net/news/20000-anxiousl y-watch-a-fish-play-pokemon-on-twitch-tv (Date of access: 17/Sep/2016).

Tomotani, J.V. (2014) The infinite fish playing Pokémon theorem. Journal of Geek Studies 1(1–2): 1–8.

Twitch. (2016) Fish Plays Pokemon. Available from: https://www.twitch.tv/fishplayspokemon (Date of access: 17/Sep/2016).


ACKNOWLEDGEMENTS

I am grateful to Henrique M. Soares for proposing this nice topic to study, as well as for suggestions and comments.


ABOUT THE AUTHOR

João Vitor Tomotani is an engineer who likes to make strange models. He refuses to acknowledge any Pokémon game after the Gold/Silver generation.


APPENDIX

troll-figure-a1

Figure A1. Heat map for the average of 100 simulation runs with a troll factor of 5%.

troll-figure-a2

Figure A2. Heat map for the average of 100 simulation runs with a troll factor of 10%.

troll-figure-a3

Figure A3. Heat map for the average of 100 simulation runs with a troll factor of 20%.

troll-figure-a4

Figure A4. Heat map for the average of 100 simulation runs with a troll factor of 30%.

troll-figure-a5

Figure A5. Heat map for the average of 100 simulation runs with a troll factor of 40%.

troll-figure-a6

Figure A6. Heat map for the average of 100 simulation runs with a troll factor of 50%.

Table A1. Number of total steps on each coordinate for the 100 simulations for varying troll factors (since the table is quite large, please click on the image to see a better resolution).

troll-table-a01


Check other articles from this volume

The strongest starter Pokémon

Bruno L. Carli

Independent researcher, Curitiba, PR, Brazil.

Email: brunolcarli (at) gmail (dot) com

Download PDF

Earlier this year, an article entitled “Which is The Most Offensively Powerful Starter Pokémon?” (Codd, 2016) caused great controversy on the Internet among players and fans of the Pokémon franchise. This article compared the three classical starter Pokémon, based on the anime, and concluded that Charizard was the strongest one.

The present work aims to analyze and discuss the data presented by Codd (2016) regarding the following issues: (1) Does his anime-based data coincide with the game mechanics? (2) Can his study be applied to metagame prospects? (3) Is Charizard really the most “powerful” Pokémon in-game?

ABOUT POKÉMON

Pokémon™ is an entertainment franchise, created by Satoshi Tajiri in 1995, that started with video games, but now includes an anime, a trading card game, clothing and several other products. Needless to say, the main products of the franchise (the games and anime) caused a large impact in recent pop culture.

The first products to be released were the “twin games” Pokémon Red and Pokémon Green, in 1996 in Japan. These games were later (in 1998) released worldwide as the Red and Blue versions for Nintendo’s Game Boy console. (As a side note, in celebration of its 20 years of existence, earlier this year the Pokémon Company released a website containing a timeline of their products).

On TV, Pokémon was first released in Japan in 1997 with the episode “Pokémon – I Choose You” (released in the United States only in 1998; Wikipedia, 2016), triggering wide public attention. The franchise is now successful worldwide, attracting millions of fans and players of all ages, ethnic groups and social classes, and the games are often regarded extremely seriously by the players.

CODD’S THEORY

Codd (2016) concluded in his article that Charizard (the last form of the starter Charmander) was the most powerful of the three initial options (the grass-type Bulbasaur, the fire-type Charmander and the water-type Squirtle; Fig. 1). To reach this conclusion, Codd based his work on “data” provided by the anime, specifically (for Charizard) in the episode “Can’t beat the heat!” (aired 17/Feb/2002), from which he estimated variables such as weight (body mass), height and width of the Pokémon. Through a series of calculations, all very well-founded in Physics, Codd determined that the offensive power of Charizard is well ahead of its competitors.

Codd’s calculations are in fact quite accurate and may be applicable to the anime. But it behooves us a little analysis regarding the applicability of his results to the game. At the very start of his article, Codd states:

At the start of each Pokémon game, the player is given a choice of starter Pokémon. The options are almost always a choice between a fire type, a water type and a grass type. In most ways the most iconic of the starter Pokémon across all Pokémon generations are the original three; Charmander, Squirtle and Bulbasaur, which will fully evolve into Charizard, Blastoise and Venusaur respectively.

― Codd (2016: p. 1), my highlight

Therefore, the first sentence of this quotation makes it clear that the author refers to the games, with its challenging proposition of having to choose one of three possible options to continue. In the same paragraph Codd says:

Each of these Pokémon also have a signature move, one which is closely linked to them through the course of the anime and the games. For Charizard this is Flamethrower, for Blastoise this is Hydro Pump and for Venusaur this is Solar Beam.

― Codd (2016: p. 1), my highlight

Thus, the author establishes an intrinsic connection between anime and game. From this point on, he starts his analysis based on the size and proportions of the starting Pokémon gathered from the anime. Despite this, the authors surmises that his calculations may be applied to the game. The discordance between Codd’s arguments and the games is based on a simple fact: he used estimates and variables that are not true (or accounted for) in the native mechanics of the game, being thus irrelevant in determining the offensive capability of a given Pokémon. In the game,

Each Pokémon has six major Stats, which are as follows: HP, Attack, Defense, Special Attack, Special Defense and Speed. HP means ‘Hit Points’ and represents health (‘amount of vitality’) of a Pokémon. When it suffers damage, a numerical value is calculated by the game, and the result is subtracted from the current HP. When HP reaches zero, the Pokémon faints and is out of action.

― Vianna Sym (2015: p. 26), my translation

In the games, Pokémon are defined by certain features, among which are the above-mentioned Stats. Each Pokémon has a given number of points assigned differently to its Stats, making it tough, agile or strong. HP represents the Health Points (or Hit Points) of a Pokémon, and from the work of Codd (2016), it is understood that a Pokémon that is “powerful” is the one with the highest chances to take the opponent’s HP down to 0 more effectively.

Thus, to estimate how powerful a Pokémon is, one should not base his/her calculations on features estimated from the anime, but rather analyze the Stats distribution of a given Pokémon as it appears in the game. This study takes into account the Stats of each of the starting Pokémon to more thoroughly analyze how powerful each can become, that is, how much damage a Pokémon can cause in a battle.

 CASE STUDY

Let’s first set the game to be any of the so-called “Gen I” versions (Pokémon Red, Blue, Green or Yellow), released between 1996 and 1998. In these versions of the game, there were less Stats, only: HP, Attack, Defense, Special and Speed (also, there were no mega-evolutions). The distribution of stats between the starting Pokémon (in their last form) can be seen in Figure 1.

Pokestarters - Fig 1

Figure 1. Base stats of (from top to bottom) Venusaur, Charizard and Blastoise in Gen I. Source of the tables: Serebii.net. Original artwork of the Pokémon by Ken Sugimori; available through Bulbapedia.

By comparing the so-called Base Stats of the three starting Pokémon (from Fig. 1), we get the chart shown in Figure 2. This gives us a broader view of the Stats distribution of each Pokémon, distinguishing their higher and lower attributes. If we add up all the Base Stats of each Pokémon, we obtain a grand total score of Stats points (Fig. 3). From Figure 3, it can be seen that all three Pokémon sum up to the same value: 425 points. In the first versions of the games the Stats were kept in a balance during the development of these three Pokémon. Thus, the sum of Base Stats alone is not enough to show which starter is the strongest. There’s more to consider.

Pokestarters - Fig 2

Figure 2. Chart comparing the Base Stats of the three starters in Gen I.

Pokestarters - Fig 3

Figure 3. Sum of all Base Stats values of each starter Pokémon in its final form (Gen I).

Using the Base Stats, we can estimate the possible amount of damage (measured in hit points, or HP; Vianna Sym, 2015) that a Pokémon can cause with one of his moves. This is in fact based on a complex calculation depending on several variables, such as the attacking Pokémon’s level and offensive Stat and the opponent’s defensive Stat, alongside some occasional bonuses. By default, the formula is expressed as (Vianna Sym, 2015):

Pokestarters - Equation1where “Level” is the current character level of the attacking Pokémon, ranging between 1 and 100; “AttackStat” is the Base Attack Stat or Special Stat (depending on the kind of move, Physical or Special, used) of the attacking Pokémon; “DefenseStat” is the Base Defense Stat or Special Stat (again, depending on the kind of move used) of the opponent; “AttackPower” is the power of the move used (this is pre-defined in the game and each move has its own power value), where a greater value represents a greater damage output; “STAB” is an acronym for “Same-Type Attack Bonus”, which means that if the move used has the same type as that of the Pokémon using it, it increases in 50% (STAB = 1.5; otherwise, STAB = 1); “Weakness” is applied depending on whether the chosen move is super effective on the opponent (this variable can assume values of 0.25, 0.5, 1, 2 or 4, depending on the type of the move and of the defending Pokémon); “RandomNumber” is simply an integer assigned randomly by the game, ranging from 85 to 100.

Other in-game factors may cause changes in damage output, for example: weather effects (rain and sunshine), and the so-called “buffs” and “de-buffs”, which are respectively temporary increases and decreases in the Pokémon’s Stats caused by moves such as Agility, Dragon Dance, Swords Dance etc. Weather effects were not yet present in the first versions of the game, so they will not be considered in this study. Moreover, to keep the analysis simple (not to say feasible), increases/decreases in Stats will also not be taken into account. The calculations here use only the Base Stats of the Pokémon in question and the set Power value of the moves. Weakness will also not be applied.

Codd (2016) considered the “signature moves” of the starting Pokémon as: Solar Beam for Venusaur (grass type), Flamethrower for Charizard (fire type), and Hydro Pump for Blastoise (water type).

The Power of each of these moves can be seen in Figure 4, alongside other data: “Battle Type” is the type of the moves, which in this case are the same as the types of the starter Pokémon (so STAB = 1.5); “Category” refers to whether the move is a Physical Attack or a Special Attack (all are Special and thus use the Base Special Stat); “Power Points” (PP) represent the number of times that the move can be used; “Power Base” is the Power of the move (used in the equation above); “Accuracy” refers to the probability of success in hitting the opponent (in %).

Pokestarters - Fig 4

Figure 4. From top to bottom, the moves Solar Beam (formerly rendered as “Solarbeam” or “SolarBeam”), Flamethrower and Hydro Pump, showing their in-game Power values and type (in Gen I). The symbol in the “Category” entry means that the moves are all Special Attacks. Source: Serebii.net.

CALCULATING THE DAMAGE

To calculate the damage dealt by each of the starter Pokémon with their signature moves, I used a virtual calculator available at Smogon University, the “Pokémon Showdown”. (Smogon University is a community dedicated to the competitive world of Pokémon games, giving the players some useful tools.) The moves have the Power values shown in Figure 4 and the defending Pokémon will be a Chansey (see Fig. 5 for Base Stats), which is neutral (that means, neither weak nor strong) towards the starters and their signature moves. All Pokémon are considered to be Level 100.

Pokestarters - Fig 5

Figure 5. Base stats of Chansey in Gen I. Source of the table: Serebii.net. Original artwork of the Pokémon by Ken Sugimori; available through Bulbapedia.

By putting all the values in the Pokémon Showdown calculator, we have:

  • Venusaur (Solar Beam): Note that the Gen I version of Solar Beam is not present in the Pokémon Showdown database, so I used the Gen II version instead (the Power is the same). The damage output falls in the interval 125 to 147 points, which represents 17 to 20% of Chansey’s total HP. Venusaur needs to land 5 blows to knock out its target.
  • Charizard (Flamethrower): The damage output falls in the interval 90 to 106 points, which represents 12 to 15% of Chansey’s total HP. Charizard needs to land 7 blows to knock out its target.
  • Blastoise (Hydro Pump): The damage output falls in the interval 113 to 133 points, which represents 16 to 18% of Chansey’s total HP. Blastoise needs to land 6 blows to knock out its target.

Just in case, these numbers were checked on another calculator, built by myself (Pokémon Damage Calculator; Carli, 2016). An algorithm was developed based on the damage equation from above, translated in some programming languages (available at: https://github.com/brunolcarli/pokeDamageCalc) and then translated into APK format so it can be installed on any mobile device running on Android (Fig. 6) or Windows operating systems. Feel free to download the app at: https://build.phonegap.com/apps/1824036/install. The results were very similar (Fig. 6): 127 to 144 points of damage for Venusaur’s Solar Beam; 84 to 98 points of damage for Charizard’s Flamethrower; and 106 to 122 points of damage for Blastoise’s Hydro Pump.

Pokestarters - Fig 6

Figure 6. Screenshots of the Pokémon Damage Calculator app (Carli, 2016: v. 1.0.0, running on Android OS), showing the maximum damage output for Venusaur’s Solar Beam (left), Charizard’s Flamethrower (middle) and Blastoise’s Hydro Pump (right).

Organizing all these numbers (from both the Pokémon Showdown and the Pokémon Damage Calculator) in a chart (Fig. 7), it is possible to clearly see the minimum and maximum damage each of the initial Pokémon can inflict, with their signature moves, against a neutral target. It can be seen that Charizard is actually the Pokémon that causes the least amount of damage, while Venusaur can deal the greatest amount of damage. Thus, Venusaur can be regarded as the “most potent” starter if we are referring to the sheer amount of damage caused.

CONCLUSION

The present study thus shows that Codd’s (2016) analysis is not applicable to the game itself, since it is not based on the variables and values present in the game mechanics. Also, as shown above, Venusaur and not Charizard is the “most potent” starter considering just the raw amount of damage it can cause. However, this is true only for a single attack in a single round of battle (which is important for the so-called “one-hit knockout”). Of course, as every player knows, one should not think that damage output alone makes a Pokémon more effective in battle. The game has much greater complexity and we would be reducing it to nothing if we just consider maximum damage. For instance, Solar Beam is a move that needs to spend 1 turn of the battle recharging, while both Flamethrower and Hydro Pump can be used every round. Furthermore, there are other factors, like Hydro Pump having an accuracy of 80% (meaning it misses one out of every five times) and Flamethrower being able to leave the defending Pokémon with the burn status condition. However, this is a matter for another day; for now, Charizard has lost its crown.

Pokestarters - Fig 7

Figure 7. Simple chart showing the maximum (red) and minimum (blue) points of damage each of the starters can inflict with their signature moves (Solar Beam for Venusaur, Flamethrower for Charizard, and Hydro Pump for Blastoise). The chart takes into account the values obtained by both the Pokémon Showdown and the Pokémon Damage Calculator.

REFERENCES

Bulbapedia. (2016) The Community-driven Pokémon Encyclopedia. Available from: http://bulbapedia.bulbagarden.net/wiki/Main_Page (Date of access: 08/May/2016).

Carli, B.L. (2016) Pokémon Damage Calculator, version 1.0.0. Available from: https://build.phonegap.com/apps/1824036/install (Date of access: 23/Apr/2016).

Codd, T. (2016) Which is the most offensively powerful starter Pokémon? Journal of Interdisciplinary Science Topics: https://physics.le.ac.uk/jist/index.php/JIST/article/view/153/94 Date of access: 23/Apr/2016).

Pokémon Company. (2016) Pokémon 20th Anniversary. Available from: http://www.pokemon20.com/en-us/ Date of access: 23/Apr/2016).

Pokémon Showdown. (2016) Pokémon Showdown! BETA. Available from: https://pokemonshowdown.com/damagecalc/ (Date of access: 23/Apr/2016).

Serebii.net. (2016) Serebii.net – Where Legends Come to Life. Available from: http://www.serebii.net/index2.shtml (Date of access: 23/Apr/2016).

Smogon University. (2016) Competitive Pokémon Community. Available from: http://www.smogon.com/ (Date of access: 23/Apr/2016).

Vianna Sym, Y. (2015) A Arte do Pokémon Competitivo. 2 ed. Available from: http://1.pokeevo.net/topic/8946178/1/ (Date of access: 23/Apr/2016).

Wikipedia. (2016) Pokémon. Available from: https://en.wikipedia.org/wiki/Pok%C3%A9mon (Date of access: 23/Apr/2016).


Check other articles from this volume

Using Unmanned Aerial Vehicles in Search & Rescue Operations

João V. Tomotani

Universidade de São Paulo; São Paulo, Brazil.

Email: t.jvitor (at) gmail (dot) com

Download PDF

TECHNOLOGY IN VIDEO GAMES

In video games, technology has always played an important part (as technological advancements, futuristic technology, lost technology…), often taking a major role in games: the titans in Titanfall, the portal gun in Portal, the metal gears in Metal Gear, and all sorts of armor, equipment and gadgets in Metroid, Crisis, Halo, Batman, Call of Duty etc. This is not a surprise, given that the public of such video games has always been highly connected with the latest technology. Also, while being futuristic and sometimes exaggerated, technological representations in games always try to remain close to real-world tech and science, in order to meet demands for “realism” in games.

In this context, robots (and other automated equipment) have also been widely featured in many games. These devices, though, always have military and war purposes. Besides all the games mentioned above, we have the laptop gun in Perfect Dark, JACK in Gears of War and all the machines in the Final Fantasies. When taking part in search operations, robots are used either for protecting something/-one/-where or for surveillance and repression: the UAVs (Unmanned Aerial Vehicles) in several shooters, the Monokumas in Danganroompa, the 1984-esquee tech from Freedom Wars etc.

This view of technology is pretty much one-sided, overshadowing their possible applications in more humanitarian scenarios, such as using UAVs in “Search & Rescue” (SAR) operations. Although shooting stuff is the core and fun of many games, I think it is worthwhile to explore the more “pacifist” side and to show gamers what this technology is really capable of. After all, the use of UAVs in SAR operations is already a reality.

HUMANITARIAN LOGISTICS IN DISASTER RELIEF OPERATIONS

Modern humanitarian logistics operations originated during the Nigerian civil war, in the conflict of Biafra, which unfolded after an attempted military coup in the 1960s. This conflict was the first in which large-scale humanitarian operations were conducted (Blecken, 2010). Since then, such operations started to be carried out systematically, and humanitarian organizations have often seen their objectives and principles collide with those of other interested parties. The principles of humanitarian operations (humanity, impartiality and neutrality) were established because of the necessity to position themselves between the two opposing sides of any conflict, and now serve as a guide for all humanitarian organizations (Blecken, 2010).

The basis of humanitarian operations is the belief that individuals affected by crises have the right to life and dignity, and thus are entitled to assistance. The Sphere Project (2011), where several organizations set minimum standards for humanitarian assistance, defines the right to life with dignity as: the right to live free of treatments and punishments that are cruel, inhuman or unworthy. As such, the central ideas of humanitarian operations are: the right to life when it is threatened and taking necessary measures to save lives and reduce suffering.

Humanitarian Logistics is a relatively new academic field, but the number of contributions in the area have increased steadily in recent years (see Leiras et al., 2014, for a thorough review).

Wassenhove (2006) defines a disaster as a “break”, something that physically affects a system, threatening its priorities and objectives. Disasters can be classified either as natural or “man-made”. Likewise, they can be classified as having a sudden or slow onset. Examples of natural disasters with sudden onsets are earthquakes and hurricanes, while examples of natural disasters with slow onsets are hunger and drought. Examples of man-made disasters with sudden onsets are coups and terrorist attacks, while slow onset man-made disasters are political crises and refugee crises (Wassenhove, 2006).

Traditionally, four stages are defined in Operations Management in disaster scenarios: mitigation, preparedness, response and recovery (Wassenhove, 2006; Tomasini & Wassenhove, 2009). SAR operations are those conducted in the response phase, aiming to find and provide relief to the greatest number of people in the hours after the disaster, trying to maximize the survival chance of victims (Hoyos et al., 2015). Tsunemi et al. (2015) emphasize the importance of agility in such operations, as statistical studies show that the rate of survival of, for instance, trapped victims in collapsed buildings, plummets within 72 hours of the moment of disaster.

UAVs are able to act autonomously in dynamic and complex environments and thus, are used predominantly for military purposes, such as intelligence gathering, surveillance and reconnaissance (Gupta et al., 2013). This is, of course, what is reflected in video games. However, there has been increasing interest in using UAVs for SAR operations, since they are able to quickly reach areas of difficult access and to quickly build a network of information and communication among the affected areas (OCHA, 2014; Meier, 2015). This is particularly relevant given that the travel speed within a region affected by disasters such as floods or earthquakes tend to be greatly reduced (Yuan & Wang, 2009).

SAR operations have particular difficulties, such as the uncertainty of the time required to inspect different regions and the uncertainty of the number, amount and location of victims. Thus, traditional methods of routing and scheduling may be insufficient to define the best way of working with UAVs. The present study is divided in three parts: (a) a brief review of the literature on the use of UAVs for SAR operations; (b) an evaluation of how different heuristics (in particular the “sweep method” of Ballou, 2006) stack up against the uncertainties of said operations; and (c) the proposal of improvements in heuristics to adapt them to the specificities of SAR.


Heuristic: Sometimes, an exact (or “optimized”) solution to a problem cannot be mathematically guaranteed or would take too much time and resources to be calculated. Many times, though, an approximate solution is acceptable for such problems. A procedure that can produce a practical, though not perfect solution, is a heuristic (Henderson, 2009).


UAVs IN SEARCH & RESCUE OPERATIONS

Tsunemi et al. (2015) classify rescue operations in three types: (1) search operations in a wide area, conducted immediately after the disaster to assess its scale and impacts; (2) search operations in a narrow area, for obtaining more specific information of affected sites discovered by the type-1 search; and (3) pinpoint search operations, which physically access the sites from type-2 search to locate/rescue victims. Constant communication between the search teams and the HQ, as well as using real-time information to update them, is clearly necessary in all three search types (Huang et al., 2013).

Irrespectively of the types above, works usually distinguish between two kinds of SAR operations, according to the area in which they take place: urban and non-urban (or wild). SAR operations in wild areas are searches for people lost in deserts, mountains or any other sparsely populated natural environment. Most works dealing with SAR operations (particularly those that involve UAVs) are interested in these environments (e.g., Goodrich et al., 2007; Cooper & Goodrich, 2008; Lin & Goodrich, 2009; Lin et al., 2010; Morse et al., 2010; Molina et al., 2012; Karma et al., 2015). For SAR operations in urban areas, there are additional challenges, such as searching through debris and clearing roads (Chen & Miller-Hooks, 2012). However, not many works focus on urban settings (e.g., Jotshi et al., 2009; Ko et al., 2009; Chen & Miller-Hooks, 2012; Huang et al., 2013).

Chen & Miller-Hooks (2012) point that, although there is an extensive literature that addresses the management of emergencies, few studies propose optimization techniques for SAR operations: Jotshi & Batta (2008) present a search heuristic that minimizes the time to find a single stationary entity on a given area; Jotshi et al. (2009) bring solutions for dispatching and routing emergency vehicles in urban settings when roads have been compromised; and finally Chen & Miller-Hooks (2012) themselves propose a multistage stochastic programming algorithm for urban settings, increasing the efficiency of the operations and highlighting the importance of communication between the search teams.


Stochastic programming (or optimization) is a framework that allows the modeling of uncertainty in the input data, in contrast to deterministic optimization, which does not. In some complex cases, the inherent uncertainty of data, coupled with the evolution of such data over time, leads to a sequential optimization-under-uncertainty model (Casey & Sen, 2005), where data is input through a series of stages. Such problems are called multi-stage stochastic programming.


As for the use of UAVs in SAR operations, several works have already tackled different problems, ranging from building communication networks to improving images obtained by the UAVs’ sensors (e.g., image recognition and infrared). In a UAV-based SAR operation, there are four critical personnel roles (Goodrich et al., 2007; Cooper & Goodrich, 2008): (1) the commander responsible for managing the search; (2) the UAV operator; (3) the UAV’s sensor operator (it’s better to have a different person than the UAV operator for this); (4) the ground search team.

Ko & Lau (2009) built and tested an autonomous UAV for urban environments, which could circumnavigate debris and search for the heat signatures of survivors. Despite this line of research being still on its infancy (Lin et al., 2010), their focus have already changed a little. As a consequence of recent technological advances (mainly in electromechanical systems, communication technology and control theory), many proposals now focus on multiple cooperative robots, known as “swarms”. Swarms have many benefits over regular UAVs, such as: robustness against failures (other robots can continue the search if one has problems), increased flexibility in reorganizing as the mission progresses, and economies of scale (Çayurpunar et al., 2008; Waharte et al., 2009).

Regardless of UAV type, the way the search is in fact conducted is the crucial point and it depends on the algorithms used. Lin & Goodrich (2009) proposed and algorithm that considers the priority of the search regions (those most likely to have survivors), in order to define the search routes for the UAVs. Murtaza et al. (2013) proposed a similar algorithm, but using a partially observable Markov decision process method.


A very interesting (and geeky) work was conducted by Megalingam et al. (2012). They proposed the design of a rescue robot with a human-like upper-body that is controlled through gesture-based imitations, acquired through the Microsoft Kinect, a motion sensing input device developed originally for the Xbox 360 video game consoles (and later for Windows PCs and the Xbox One).

Would it look something like this maybe? (Nintendo’s R.O.B.; image by Evan-Amos, 2012, taken from Wikimedia Commons).


Waharte & Trigone (2010) tested three types of algorithms (greedy heuristic, heuristic based on attraction/repulsion potentials, and heuristic based on partially observable Markovian decision process) through simulations, and found that estimating the best search paths through the sharing of information between UAVs reduced the duration of the operations, albeit at a high computational cost. They also concluded that there are several important aspects to be met, such as the quality of the sensors, energy constraints, environmental hazards and communication restrictions between UAVs. Regarding the latter, Asadpour et al. (2012) point out that the communication capability of conventional UAVs is insufficient for the large volume of data required for SAR operations, such as images and videos. They thus proposed hybrid networks made with smartphones and ground stations. Environmental dangers are also quite problematic, as shown by the work of Karma et al. (2015), since they may incur on reduced visibility (thus making detection difficult) or severe damage to the usually fragile UAVs.


A Markov decision process is a model for sequential decision making when under uncertainty, in situations where outcomes are partly random and partly under control of the decision maker (or agent), considering both short-term outcomes of current decisions and opportunities for making decisions in the future. The partially observable Markov decision process is a generalization of the Markov decision process, and considers that the decision maker cannot directly observe the state of the system. Since the true state is hidden, the agent must choose actions based on past actions and observations, composing scenarios of possible state distributions (called belief states).


FORMULATION OF THE PROBLEM

As I mentioned above, here I intend to evaluate how different heuristics (in particular the “sweep method” of Ballou, 2006) stack up against the uncertainties of SAR operations, also proposing improvements for them. Therefore, I need to insert some of the difficulties present in real-life SAR operations. Thus, the problem formulated has the following characteristics:

  • The maps where the search occurs are generated randomly, with random x and y coordinates being assigned to a defined number of regions (search sites). The maps can have 50, 100 or 500 regions. For the present study, it was decided that the coordinates may vary from (-3) to (+3), and the travel time between two regions is equal to the distance between them in the stipulated coordinated plane.
  • A command base for the SAR operation is defined on the map at a random position. The base is the starting point of the UAVs’ routes. For this study, it was decided that the basis of the coordinates could range from (-1.5) to (+1.5). An example of a map, with the search regions, can be seen on Figure 1. The application for the map generation was developed in VBA, and its interface can be seen on Figure 2.

Fig 1

Figure 1. Example of a search map with 50 search locations (blue dots) and the command base (red diamond). The travel time between two points is directly proportional to the distance between them.

Fig 2

Figure 2. Interface of the map generator.

  • The search is conducted by five UAVs. A maximum flight range is set for each vehicle, after which it must return to the base before leaving again (immediately) on the next route. It was decided that the flight range for all UAVs is (30).
  • Each search location has a known “search complexity”, randomly assigned. Places with greater complexity require larger times to complete the search. In this study, it was decided that the complexity (search time) could be (1), (2), (3) or (4), with respective probabilities of being assigned (40%), (30%), (20%) or (10%).
  • Each search location has a known probability of containing a victim, randomly assigned. The total number of victims is unknown. In the present study, it was defined that the likelihood of a location having a victim could be (10%), (30%), (60%) or (90%), with chances of (30%), (20%), (20%) or (30%), respectively.
  • For testing the various heuristics, four instances were generated for each map scale (50, 100 and 500 search regions).

HEURISTICS TO SOLVE THE PROBLEM

For solving the proposed scenarios, two heuristics were developed, prioritizing areas where victims are most likely to be found (similar to the works of Lin & Goodrich, 2009, and Murtaza et al., 2013). After the initial results, a third hybrid heuristic was proposed. The interface developed in VBA, for the simulation of the heuristics can be seen on Figure 3.

Fig 3

Figure 3. Simulator interface.

“Greedy” Heuristic

The first heuristic proposed is the “greedy”, which takes into account the distance to the search areas, the complexity of the search operation and the probability of finding a victim, to compose a prioritization factor. Each UAV calculates the factor for all regions that have not yet been searched, and goes towards the region with the highest factor. The greedy heuristic is said to be “myopic”, because it does not have long-term vision. Three different factors were tested to evaluate how the “distance” and “probability of victim” parameters affected the quality of the solution: one that considers only the shortest time to come and inspect the regions (1/T); one that considers the shortest time and the square of the probability of finding a victim (1/T*P2); and one that takes the shortest time, and the fifth power of the probability of finding a victim of (1/T*P5).

“Sweep” Heuristic

The “sweep” heuristic is a simple and known vehicle routing algorithm, capable of solving a variety of problems rapidly and with relatively small average error rate (around 10%; Ballou, 2006). In this method, a line is drawn from the point of origin, and this line rotates on a defined direction. Search locations through which the line passes are the ones which will compose a route, the rotation stops when the length of the route equals the flight range of the UAV. Finally, prioritization logic is applied for all locations that compose this route, in order to define the route sequence. Because of this two-stage process, Ballou (2006) points out possible problems in the formation of routes, such as the non-compliance of flight range restriction.

In the present problem, prioritization logic applied in the second stage was the likelihood of a location having victims, with locations of greater probability being visited first. It should be noted that the “sweep” method implemented has a major constraint for the proposed problem, because the routes are generated complete one at a time, and assigned to a UAV, so that the last search sites tend to be visited by a single vehicle (for being part of the same route), and thus allowing for idle vehicles (those that have completed their own routes). This restriction is most noticeable for problems with few locations.

Hybrid Heuristic

After the first tests of the algorithms, it was found that the “greedy” heuristic quickly finds the first victims, but are slow to find all of them. Meanwhile the “sweep” method quickly finds all the victims, but is not so effective in the first moments of the SAR operation, which are the most critical. Because of this, a hybrid method was implemented, where the first routes are generated by “greedy” heuristics and the later routes are generated by the “sweep” method. For this problem, in scenarios with 50, 100 and 500 search sites, a greedy heuristic is used until time instances of 10, 30 and 90 respectively.

RESULTS AND DISCUSSION

The simulation results can be seen on Tables 1 to 3, showing the average time needed to find the indicated percentage of survivors.

Table 1. Results of the simulation for the different algorithms (with 50 search locations), showing the average time needed to finish.

Table 1

Table 2. Results of the simulation for the different algorithms (with 100 search locations), showing the average time needed to finish.

Table 2

Table 3. Results of the simulation for the different algorithms (with 500 search locations), showing the average time needed to finish.

Table 3

The “greedy” heuristics that prioritize the probability of finding survivors had good results for the early stages of the operation, while the “sweep” method is more efficient in finding all survivors in the shortest possible time. This becomes more evident with the routes generated by each method (Fig. 4., the “sweep” method creates more efficient routes). Hybrid algorithms, in turn, use the “greedy” strategy for finding many survivors in the early moments of the search, switching to the “sweep” strategy later on in order to find all the victims faster. Figure 5 shows an example of comparative results for a specific scenario.

Fig 4

Figure 4. Example of routes generated by different algorithms for a scenario with 50 locations.

Fig 5

Figure 5. Example of the results of the different algorithms for a scenario with 500 locations. The “greedy” 1/T*P2 and 1/T*P5 had the same result, so only the latter is shown.

CONCLUSION

SAR is an essential part of humanitarian operations, and the use of UAVs for this purpose is already a reality. Still, few studies have focused on search algorithms for using UAVs and even fewer have considered the complexity and uncertainty of real-life problems. This work is a first attempt to tackle this problem.

The results provided by the simulations of the hybrid model were very promising, and the balance between “greedy” and “sweep” heuristics appear to be a good solution to meet conflicting objectives. The time spent for each algorithm during a hybrid approach can be calibrated according to the characteristics of the explored area. However, the model has a large number of complex parameters, being difficult to calibrate. A next step would be to test such model in real-life scenarios to assess the sensitivity of such parameters.

Perhaps the most obvious constraint on the proposed solutions is the lack of communication between UAVs. A more intelligent system of communication between different vehicles allows a more coordinated search (Çayurpurnar et al., 2008) and would probably show even better results, particularly in scenarios with many search sites. An idea would be to develop an UAV control simulator, where the “players” could communicate or not with each other, and the differences in performance could be analyzed systematically.

Another constraint presented in the work is the binary nature of the presence of victims on search sites. One possible improvement would be the use of Poisson distributions to set the number of victims for each location, which would affect the dynamics of prioritization factors, making the model more complex and closer to real-life scenarios.

Finally, we must remember that almost no video games include such a humanistic view on technology as SAR operations (unless it is for rescuing the main hero, of course). Although agreeing that combat, war, conflicts and violence are an important (and fun!) part of games, it is also nice to remember the positive impact brought by technological advancements, and that such education through games is always possible.


ACKNOWLEDGEMENTS

I am grateful for the suggestions from Dr. Adriana Leiras, Dr. Irineu de Brito Jr. and João Gilberto Sanzovo (USP), which greatly improved the text.


REFERENCES

Asadpour, M.; Giustiniano, D.; Hummel, K.A.; Egli, S. (2012) UAV networks in rescue missions. Proceedings of the 8th ACM International Workshop on Wireless Network Testbeds, Experimental Evaluation & Characterization: 91–92.

Ballou, R. H. (2006) Gerenciamento da cadeia de suprimentos / logística empresarial. Bookman, Porto Alegre.

Blecken, A. (2010) Humanitarian Logistics: Modelling Supply Chain Process of Humanitarian Organizations. Haupt Verlag AG, Berna.

Casey, M.S. & Sen, S. (2005) The scenario generation algorithm for multistage stochastic linear programming. Mathematics of Operations Research 30(3): 615–631.

Çayirpunar, O.; Tavli, B.; Gazi, V. (2008) Dynamic Robot Networks for Search and Rescue Operations. Proceedings of the EURON/IARP International Workshop on Robotics for Risky Interventions and Surveillance of the Environment: 1–9.

Chen, L. & Miller-Hooks, E. (2012) Optimal team deployment in urban search and rescue. Transportation Research, Part B, 46: 984– 999.

Cooper, J. & Goodrich, M. (2008) Towards combining UAV and sensor operator roles in UAV-enabled visual search. Proceedings of the 3rd ACM/IEEE International Conference on Human Robot Interaction: 351–358.

Goodrich, M.A.; Cooper, J.L.; Adams, J.A.; Humphrey, C.; Zeeman, R.; Buss, B.G.  (2007) Using a Mini-UAV to Support Wilderness Search and Rescue: Practices for Human-Robot Teaming. Proceedings of the IEEE International Conference on Safety, Security and Rescue Robotics: 1–6.

Gupta, S.G.; Ghonge, M.M.; Jawandhiya, P.M. (2013) Review of Unmanned Aircraft System (UAS). International Journal of Advanced Research in Computer Engineering & Technology 2(4): 1646–1658.

Henderson, H. (2009) Encyclopedia of Computer Science and Technology, Revised Edition. Facts on File, New York.

Hoyos, M.C.; Morales, R.S.; Akhavan-Tabatabaei, R. (2015) OR models with stochastic components in disaster operations management: a literature survey. Computers & Industrial Engineering 82): 183–197.

Huang, A.; Ma, A.; Schmidt, S.; Xu, N.; Zhang, B.; Meineke, L.; Shi, Z,; Chan, J.; Dolinskaya, I. (2013) Integration of Real Time Data in Urban Search and Rescue. Northwestern University. Available from: http://www.ccitt.northwestern.edu/documents/Integration_of_real_time_data_in_urban _search_ and_rescue.pdf (Date of access: 16/Dec/2015).

Jotshi, A. & Batta, R. (2008) Search for an immobile entity on a network. European Journal of Operational Research 191(2): 347–359.

Jotshi, A.; Gong, Q.; Batta, R. (2009) Dispatching and routing of emergency vehicles in disaster mitigation using data fusion. Socio-Economic Planning Sciences 43(1): 1–24.

Karma, S.; Zorba, E.; Pallis, G. C.; Statheropoulos, G.; Balta, I.; Mikedi, K.; Vamvakari, J.; Pappa, A.; Chalaris, M.; Xanthopoulos, G.; Statheropoulos, M. (2015) Use of unmanned vehicles in search and rescue operations in forest fires: Advantages and limitations observed in a field trial. International Journal of Disaster Risk Reduction 13: 307–312.

Ko, A.W.Y. & Lau H.Y.K. (2009) Intelligent robot-assisted humanitarian search and rescue system. International Journal of Advanced Robot Systems 6(2): 121–128.

Leiras, A.; Brito, I. Jr.; Peres, E.Q.; Bertazzo T.R.; Yoshizaki H.T.Y. (2012) Literature review of humanitarian logistics research: trends and challenges. Journal of Humanitarian Logistics and Supply Chain Management 4(1): 95–130.

Lin, L. & Goodrich, M.A. (2009) UAV intelligent path planning for wilderness search and rescue. International Conference on Intelligent Robots and Systems: 709–741.

Lin, L.; Roscheck, M.; Goodrich, M.A.; Morse, B.S. (2010) Supporting wilderness search and rescue with integrated intelligence: autonomy and information at the right time and the right place. Proceedings of the 24th AAAI Conference on Artificial Intelligence: 1542–1547.

Megalingam, R.K. & Mahadevan, A.P.K.A. (2012) Kinect based humanoid for rescue operations in disaster hit areas. International Journal of Applied Engineering Research 7(11): 1–5.

Meier, P. (2015) UAVs and humanitarian response. In: New America (Ed) Drones and aerial observation: New Technologies for Property Rights, Human Rights and Global Development. A Prime, Washington, D.C.

Molina, P.; Colomina, I.; Vitoria, T.; Silva, P.F.; Skaloud, J.; Kornus, W.; Prades, R.; Aguilera C. (2012) Searching lost people with uavs: the system and results of the close-search project. International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences 39-B1: 441–446.

Morse B.; Engh, C.; Goodrich, M. (2010) UAV video coverage quality maps and prioritized indexing for wilderness search and rescue. 5th ACM/IEEE International Conference on Human-Robot Interaction: 227–234.

Murtaza, G.; Kanhere, S.; Jha, S. (2013) Priority-based coverage path planning for Aerial Wireless Sensor Networks. Proceedings of the 2013 IEEE 8th International Conference on Intelligent Sensors, Sensor Networks and Information Processing: 219–224.

OCHA. (2014) Unmanned Aerial Vehicles in Humanitarian Response. OCHA Policy and Study Series 10: 1–15.

Sphere Project. (2011) The Sphere Project: Humanitarian Charter and Minimum Standards in Humanitarian Response. Practical Action Publishing, UK.

Tomasini, R.; Wassenhove, L.V. (2009) Humanitarian Logistics. Palgrave Macmillan, London.

Tsunemi, Y.; Ishii, T.; Murata, M. (2015) Imaging solutions for Search & Rescue Operations. NEC Technical Journal 9(1): 90–93.

Waharte S. & Trigoni, N. (2010) Supporting search and rescue operations with UAVs. International Conference on Emerging Security Technologies: 142–147.

Waharte S.; Trigoni, N.; Julier, S.J. (2009) Coordinated search with a swarm of UAVs. SECON.

Wassenhove, L.N.V. (2006) Humanitarian aid logistics: supply chain management in high gear. Journal of Operational Research Society 57(5): 475–489.

Yuan, Y. & Wang, D. (2009) Path selection model and algorithm for emergency logistics management. Computers & Industrial Engineering 56(3): 1081–1094.


Check other articles from this volume

Modeling and analysis of a Zombie Apocalypse: zombie infestation and combat strategies

João V. Tomotani

Universidade de São Paulo; São Paulo, Brazil.

Email: t.jvitor (at) gmail (dot) com

Download PDF

Humanity can be quite creative when it comes to thinking up of interesting and fictional ways of being completely annihilated by (and also of ways of romancing) fantastical monsters. Though most people tend to believe that humanity’s intelligence and sense of self-preservation will make us find creative ways to overcome nature’s challenges, it is also believed that man will inevitably be creative in eventually deploying its own demise. In the present work, I will focus on one of the most popular apocalyptic themes of modern pop culture, the zombies.

Ogg (2011) comments how, in modern times, the zombie genre has evolved from a cult to a highly popular theme, estimating its monetary worth as over 5 billion dollars. Zombies are present in movies, books, comics, video games, television series, various toys and products, and even have their own parades.

The zombie apocalypse, though, should not be treated so lightly. After the initial hype, a zombie infestation is likely to bring some problems to civilization as we know it. As such, I believe that there is not sufficient work focusing on zombies and/or how to survive their potential threat. (Though most people tend to believe that a zombie attack is unlikely, the effects of such attack would be relevant; thus, it should be better understood.) Here is presented a discrete-time model of a zombie apocalypse where some parameters are used to control the combat strategies deployed against the infestation.

LITERATURE REVIEW

According to Brooks (2003), a zombie is a reanimated human corpse that feeds on living human flesh (or just brains, depending on the reference). Through a list of recorded attacks, Brooks suggest that zombies might have been in existence since 60.000 BCE (though such record is doubtful to say the least).

The stories about zombies probably originated in the Afro-Caribbean system of Vodou (or voodoo), where people were described as being controlled by a powerful sorcerer. The movie White Zombie, from 1932, is widely considered the first zombie movie, but it was the 1968 movie Night of the Living Dead that made the walking dead theme truly popular, giving birth to the zombie genre. Contemporary zombies are depicted as mindless monsters that do not feel pain and have nothing but appetite for human flesh, wandering aimlessly intending to kill/eat (and, consequently, infect) people. For more information, interesting references are Brooks (2003), Munz et al. (2009) and Fobiya et al. (2013).

Some works were recently published focusing on zombie outbreaks. These books focus on self-defense and organization of the population against zombies, or against other humans after the zombie outbreak inevitably happens (Brooks, 2003; Fobiya et al., 2013).

A seminal work by Munz et al. (2009) proposed a mathematical model of a zombie outbreak. The authors used a structure known as an “Epidemic Model” for their work. Epidemic models are simplified means of describing the transmission of communicable disease through individuals, the earliest mathematical modeling of the spreading of diseases being carried out in 1766 by Daniel Bernoulli (for more info, see http://en.wikipedia.org/wiki/Epidemic_model).

After the work of Munz et al. (2009), many others developed their own models: Calderhead et al. (2010), Idu & Oladele (2010), Flanagan (2012), Blais & Witkowski (2013). These models differ from each other on some of their premises. Munz et al. (2009), for instance, considered four different scenarios: (1) the SZR scenario, where the population consisted of susceptible (or “normal”) humans (S), zombies (Z), and removed individuals (R; humans that died naturally or zombies that were destroyed); (2) the SIZR scenario, where a “latent infection” stage was added (I), where the individual took time before becoming a zombie; (3) the SIZRQ scenario, where a quarantined area (Q) was created to contain both infected individuals and zombies (the flowchart of this last model can be seen on Figure 1); (4) the model with treatment, where a cure for the infection could be developed quickly, in a way that a treatment would be able to revert a zombie to its normal human self. The models of Munz et al. (2009) are similar to the well-known SI / SIS / SIR epidemic models (for more information, see Allen, 1994), where the population may consist of susceptible, infected and removed individuals (the removed are those that cannot be infected again).

Zombie - Figure01
Figure 1. Flowchart of the SIZRQ model. Reproduced from Munz et al. (2009).

Both Calderhead (2010) and Idu & Oladele (2010) reproduced the SZR model. The former shows the difficulties in estimating parameters for predicting the outcome of a zombie outbreak, while the latter presents a hypothetical scenario where the dead could resurrect as normal humans in order to offer analogies with different kinds of studies (such as allegiance to political parties).

One of the biggest limitations of the model presented by Munz et al. (2009) was the fact that the destroyed zombie could always be “resurrected”. Both Flanagan (2012) and Blais & Witkowski (2013) thus proposed a model where the zombie could be permanently removed. The model with permanent removal presented by Blais & Witkowski can be seen in Figure 2.

Zombie - Figure02
Figure 2. Model where individuals can be susceptible (S), temporarily removed (R), zombie (Z) or permanently removed (X). Reproduced from Blais & Witkowski (2013).

All the previous works showed that the zombie outbreak would have quite bad consequences for the human species, resulting on the extinction of the susceptible population. Most works also showed that the infection would act so fast that the natural birth and death rates would be pretty much irrelevant for the purposes of the simulation. Finally, the previous authors worked with the simulation paradigm of System Dynamics (SD), one of the earliest paradigms that works with “rates”, “levels” and “feedback loops” (for more information, see Pruyt, 2006).

I believe that a scenario where the human population becomes extinct is quite bad, and that simulation models should be less fatalist when treating such themes, proposing combat strategies instead of only showing the results of an outbreak. As such, I will present a simulation model based on the Discrete-Event Simulation (DES) paradigm where some combat strategies will be explored, with the intention of developing the best course of action.

THE SIMULATION MODEL

First, a “map” where the infection takes place is defined (Figure 3). The map is a square with side length m. Inside the map, a square area with side length c is defined as the human colony. Inside the human colony, another square with side length \mu*c  is defined as the “safety” area, where \mu is a “safety factor” between 0 and 1. Finally, the size of an “event cell” is defined as e. The event cell is where the events (encounters) of the simulation take place.

Inside the map, a number  of humans and  of zombies are randomly placed. The humans are distributed inside the colony while the zombies are distributed outside of it.

The simulation model is based on the Discrete-Event Simulation (DES) Paradigm. In the System Dynamics (SD) Paradigm mentioned above (used by all the previously cited authors), the infestation is modeled as a system of nonlinear equations, which causes a complex behavior of feedbacks that are continuous in time. The DES, in turn, focuses on the discrete events that cause changes on the states of the system, considering that no changes occur between events. One of the advantages of the DES is that, since no change occurs in the system outside of the events, the simulation can directly jump in time from one event to the next, usually running faster than the corresponding continuous simulation.

A great advantage of adopting the DES instead of the SD Paradigm for this simulation is that it is easier to insert and analyze nondeterministic factors on the equations, such as the chances of a susceptible human being infected by a zombie on an encounter. It also becomes possible to simulate phenomena that follow probabilistic distributions, making them more realistic (and susceptible to chance).

Zombie - Figure03
Figure 3. Map of the simulation model.

On this model, I considered that the events happen in “turns”. On each turn, the following sequence of events happens:

  1. Humans move on the map;
  2. Zombies move on the map;
  3. The event cells that have individuals inside them are defined;
  4. The encounter inside each event cell is simulated;
  5. The status of each individual is updated;
  6. Turn restarts.

On this model, zombie infection was treated as a disease that only affects living beings, not as an act of necromancy. The disease is transmitted through contact with an infected individual. Six different categories of individuals were defined for my simulation: susceptible humans (S), active zombies (Z), inactive zombies (I), destroyed corpses (X), trained humans with weapons ( W ), and trained humans with vaccines (V). All humans start as susceptible humans. The difference between inactive zombies (I) and destroyed corpses (X) is that the latter are permanently removed from the simulation (killed), while the former can be cured back to human form, or reanimated as active zombies.

The movements of humans and zombies have the following rules:

  1. If the human is inside the safety area of the map, he/she moves randomly in any direction;
  2. If the human is outside of the safety area, he/she moves randomly with a slightly higher probability of returning to the safety area;
  3. Zombies always move randomly in any direction;
  4. Inactive zombies and destroyed corpses do not move.

After all the individuals have moved, the event cells that will be simulated are defined. Each cell that has at least one individual inside will simulate the following events.

(1) All humans have a chance of becoming a zombie, where the chance of this happening is:

P_{Z} =i *((1-( \frac{1}{1+5*n_{Z} } ))-(1- \frac{2}{1+ n_{S}+2*n_{V}+3*n_{W} } ))

Where:  i = infection rate; n_{Z} = number of zombies inside the same event cell as the human;  n_{S} = number of susceptible humans inside the same event cell as the human;  n_{V} = number of trained humans with vaccine inside the same event cell as the human;  n_{W} = number of trained humans with weapons inside the same event cell as the human.

With this equation, it is possible to see that the higher the number of zombies in the same event cell as the human, the higher the probability of him/her being contaminated. Likewise, the higher the number of humans in the same event cell, the lower the probability of him/her being contaminated. It is also possible to see that trained humans with vaccines and weapons have a greater influence in the probability than simple susceptible humans.

As an example, the chance of a human being contaminated if he is alone with one zombie on the same cell is 83.3%. If there are two zombies, the probability goes to 90.9%. If there is only one zombie and one trained human with a weapon, the probability is only 33.3%.

(2) All zombies have a chance of being “cured”, “defeated” (become inactive) or completely destroyed:

The probability of a zombie being cured is calculated as:

P_{C1} =h*(1- \frac{1.5}{1+ n_{V} } )

Where:  h = cure rate.

The probability of a zombie being completely destroyed is calculated as:

P_{X1} = \frac{(1- \frac{1.9}{1+ n_{S} + n_{V} + 2.8*n_{W} } )}{2*n_{Z}^{2}}

And the probability of a zombie being “defeated” (becoming inactive) is calculated as:

P_{I} = \frac{(1- \frac{1.9}{1+ n_{S} + n_{V} + 2.8*n_{W} } )}{n_{Z}^{2}}

(3) All inactive zombies have a chance of being reanimated as zombies, cured, or being completely destroyed:

All inactive zombies have a probability r of being reanimated if they are on the same event cell as another active zombie, where r is defined as a reanimation rate.

The probability of an inactive zombie being cured is calculated as:

P_{C2} = \frac{(1- \frac{1}{1+ 3*n_{V} } )}{1+2*n_{Z}^{2}}

The probability of an inactive zombie being completely destroyed is calculated as:

P_{X2} = \frac{(1- \frac{1}{1+ 0.3*n_{S} + 6*n_{W} } )}{1+2*n_{Z}^{2}}

Four other important parameters for the simulation are: the time necessary for training and equipping humans to fight zombies and the percentage of the population that will be trained and equipped (respectively, T_{W} and \alpha_{W} ); and the time necessary for developing a cure and the percentage of the population that will be trained to administrate it (respectively  T_{V} and \alpha_{V}). After the first case of contamination (first susceptible human becomes a zombie), it takes a time T_{W} for the authorities to train and equip the population with weapons, and a time T_{V} to do the same with the vaccines.

One important point is that every zombie that is cured comes back as a susceptible human. It is considered that all equipment he had before being infected is lost, and he is no longer capable of fighting with the same efficiency after the contamination.

The objective of the simulation is to define the best strategy to contain a zombie infestation, considering:

  1. Which is the ideal size of a human colony;
  2. Once the first case of contamination is discovered, how quickly must the population be trained and equipped with weapons;
  3. Which is the best setup of weapons / vaccines to ensure the survival of as many humans as possible.

SCENARIOS AND RESULTS

Once the model was finished, some scenarios were defined to test it.

I conducted many simulations, trying to understand how each parameter affects the results. One limitation found in the model is its high instability due to the stochastic events (more about this limitation is discussed on the next section). Because of this problem, the conclusions that can be drawn from the model are limited. I present here only the most relevant simulations conducted, and will further discuss their implications on the next section.

Firstly, some parameters were stipulated at the beginning of the tests and were not changed in any scenario. The infection, cure and reanimation rate were fixed respectively as 1.0, 1.0 and 0.8. The map and cell size were fixed respectively as 100 and 4, the number of individuals was stipulated as 8,000 and the initial number of zombies was defined as 12. Finally, the “safety factor” was defined as 0.9.

It is interesting to note that in no scenario zombies stayed inactive for long, being either reanimated, destroyed or cured very quickly.

On the first scenario (Figure 4), the time necessary to train and arm 20% of the population was defined as 500 turns after the first infection. The time necessary to develop the vaccine and train 30% of the population on how to use it was stipulated as 2,000 turns after the first infection. The colony side length was defined as 40 (40% of the map size).

As a result, humans were extinct after around 20,000 turns, with close to 6,500 individuals being destroyed and 1,500 zombies remaining at the end. After the zombies “invaded” the human colony, the infection began to spread quickly. Once the population was trained and armed, the rate of infection got slower and the rate of zombie destruction got higher. Once the population was equipped with vaccines, the number of susceptible humans slowly rose for a while. Humanity’s demise was that the zombie infestation had already gotten out of control, with way too many zombies. Since a cured zombie comes back as a simple susceptible human, the number of humans that were equipped with weapons or vaccines slowly went down and humanity was overrun by zombies.

Zombie - Figure04
Figure 4. First scenario. – Infection rate: 1.0. Cure rate: 1.0. Reanimation rate: 0.8. T_{W}: 500. \alpha_{W} : 0.2. T_{V}: 2,000. \alpha_{V} : 0.3. n: 8,000. z: 12. m: 100. c: 40. e: 4. \mu: 0.9.

On the second scenario (Figure 5), the colony side length was reduced to 24. As a result, humans became extinct sooner, after around 10,000 turns, with close to 3,500 individuals being destroyed and 4,500 zombies remaining. Since humans were restricted to a smaller area, it is reasonable to assume that the infection spread more quickly after the zombies invaded the colony.

Zombie - Figure05
Figure 5. Second scenario. – Infection rate: 1.0. Cure rate: 1.0. Reanimation rate: 0.8. T_{W}: 500. \alpha_{W} : 0.2. T_{V}: 2,000. \alpha_{V} : 0.3. n: 8,000. z: 12. m: 100. c: 24. e: 4. \mu: 0.9.

On the third scenario (Figure 6), the colony side length remained 24, and the time necessary to arm the population increased to 1,000 turns. As a result, humans became extinct very quickly. Once the population was trained and armed, the number of zombies was already overwhelming and there was nothing to be done. Humans became extinct after close to 1,000 turns and more than 7,500 zombies were left at the end.

Zombie - Figure06
Figure 6. Third scenario. – Infection rate: 1.0. Cure rate: 1.0. Reanimation rate: 0.8. T_{W}: 1000. \alpha_{W} : 0.2. T_{V}: 2,000. \alpha_{V} : 0.3. n: 8,000. z: 12. m: 100. c: 24. e: 4. \mu: 0.9.

On the fourth scenario (Figure 7), the percentage of the population trained and equipped with weapons went up from 20% to 25%, and the time necessary to do so returned to 500 turns after the first infection. As a result, the initial surge of contamination was partially contained, with a peak of close to 2,000 zombies at the time the vaccine was distributed (lower than in the previous scenarios). Similarly to the first scenario, though, the zombies slowly managed to contaminate humans equipped with weapons and vaccines, resulting, once again, on the extermination of humanity after close to 20,000 turns.

Zombie - Figure07
Figure 7. Fourth scenario. – Infection rate: 1.0. Cure rate: 1.0. Reanimation rate: 0.8. T_{W}: 500. \alpha_{W} : 0.25. T_{V}: 2,000. \alpha_{V} : 0.3. n: 8,000. z: 12. m: 100. c: 24. e: 4. \mu: 0.9.

At this point, I was starting to get worried that humanity might not manage to survive a zombie apocalypse. As such, I started developing scenarios with more aggressive anti-zombie policies, where vaccines would be distributed more than once among the population. Also, I returned the colony size to 40.

On the fifth scenario (Figure 8), the percentage of the population trained and equipped with weapons went back to 20%, and the time necessary for this was kept at 500 turns after the first infection. After an initial time necessary to develop the vaccine and train 30% of the population on how to use it stipulated as Tv1 = 2,000 turns after the first infection, a second time of distributing vaccines was stipulated as Tv2 = 6,000 turns. For my despair, though, humanity was once again exterminated after a long battle. The zombies were close to be eradicated after 18,000 turns, but slowly regained the upper hand.

Zombie - Figure08
Figure 8. Fifth scenario. – Infection rate: 1.0. Cure rate: 1.0. Reanimation rate: 0.8. T_{W}: 500. \alpha_{W} : 0.2. T_{V1}: 2,000. \alpha_{V1} : 0.3. T_{V2}: 6,000. \alpha_{V2} : 0.3. n: 8,000. z: 12. m: 100. c: 40. e: 4. \mu: 0.9.

Finally, a sixth and last scenario (Figure 9) was created. Deciding to defeat the zombies at all costs, four moments of vaccine distribution were stipulated at turns 2,000; 6,000; 10,000; and 15,000. Finally, humanity managed to eradicate the zombies, but with the loss of 3,000 lives.

Zombie - Figure09
Figure 9. Sixth scenario. – Infection rate: 1.0. Cure rate: 1.0. Reanimation rate: 0.8. T_{W}: 500. \alpha_{W} : 0.2. T_{V1}: 2,000. \alpha_{V1} : 0.3. T_{V2}: 6,000. \alpha_{V2} : 0.3. T_{V3}: 10,000. \alpha_{V3} : 0.3. T_{V4}: 15,000. \alpha_{V4} : 0.3. n: 8,000. z: 12. m: 100. c: 40. e: 4. \mu: 0.9.

CONCLUSION

Herein, a mathematical model of a zombie outbreak was successfully developed and tested. With the results of the simulation, it is possible to draw the following conclusions (Table 1 summarizes the main results).

Zombie - Table01
Table 1. Summary of each scenario.

The size of the human colony impacts significantly the results of the outbreak, which varies according to the colony’s organization. Unless the human settlement is capable of organizing itself quickly and efficiently to combat a zombie attack, the model recommends that you run away from highly populated areas if you want to survive. This conclusion is compatible with the study made by Alemi et al. (2015). Similarly, Brooks (2003) identify urban centers as one of the most dangerous places to be when zombie outbreaks start. Since the objective of the present study is to preserve humanity, not individual survival, I believe it is important that urban centers be better prepared for outbreaks, to respond accordingly when they happen.

The model also suggests that it is important to react to a zombie infestation as quickly as possible to contain the initial outbreak, avoiding a “point of no return”, when the zombies slowly gain ground over the remaining humans. Initially, I believed that the model would be interesting to show the tradeoff between weapons (killing the zombies) and vaccines (avoid killing zombies while trying to cure them). It became evident, however, that zombies are quite dangerous when not quickly taken care of, since their numbers can grow exponentially. If humans want to survive, containing the initial wave of zombies with weapons is unavoidable (interestingly, this topic was never touched upon in previous works).

In addition, I believe that the model has room for many improvements and is far from ideal if we want to actually develop anti-zombies combat strategies. One idea is to use yet another simulation paradigm, namely the “Agent Based Modeling” (ABM), which is much more recent than the SD and DES. The ABM is useful to simulate interactions of autonomous individuals acting according to simple rules. With such model, it would be possible to further develop human actions and strategies, for example: making humans walk in groups (preferably with one armed individual) and having a better logic in the direction of their movements.

Another problem with the model is that it is highly unstable and sensitive to modifications on its parameters, since most events are stochastic (from movement of the individuals on a big map, to the outcome of the encounters) and a different result of each event has a great and chaotic impact on the rest of the simulation (for instance, having two armed humans become zombies instead of none on an encounter). As such, most of the conclusions presented here should be approached carefully and, for that reason, I did not dare to present a curve of the impact of each parameter.

Most importantly, further work must be conducted to better define the parameters of the simulation. I do not have sufficient data to estimate the chances of a human being infected by a zombie upon an encounter, nor do I know how long it would take to develop a cure for the zombification. It is also quite possible that the impact of being trained and having a weapon in a zombie apocalypse is being overestimated on my model, since I probably would be quite unsettled if an undead was trying to eat my flesh.

REFERENCES

Alemi, A.A.; Bierbaum, M.; Myers, C.R.; Sethna, J.P. (2015) You Can Run, You Can Hide: The Epidemiology and Statistical Mechanics of Zombies. Quantitative Biology. Cornell University Library. Available from: http://arxiv.org/abs/1503.01104 (Date of access: 15/May/2015).

Allen, L.J.S. (1994) Some Discrete-Time SI, SIR, and SIS Epidemic Models. Mathematical Biosciences 124: 83–105.

Blais, B. & Witkowski, C. (2013) Zombie Apocalipse: An Epidemic Model. Available from: http://terpconnect.umd.edu/~jzsimon/hlsc374/ref/Blais+Witkowski-handout-2013.pdf (Date of access: 06/May/2015).

Brooks, M. (2003) The Zombie Survival Guide: Complete Protection from the Living Dead. Three Rivers Press, New York.

Calderhead, B.; Girolami, M.; Higham, D.J. (2010) Is it safe to go out yet? Statistical Inference in a Zombie Outbreak Model. Available from: http://www.strath.ac.uk/media/departments/mathematics/researchreports/2010/6zombierep.pdf (Date of access: 06/May/2015).

Flanagan, K.M. (2012) Zombie Attack! An Introduction to Quantitative Modeling. National Center for Case Study Teaching in Science. University of Calgary, Alberta, Canada. Available from: http://sciencecases.lib.buffalo.edu/cs/files/zombie.pdf (Date of access: 06/May/2015).

Fobiya, A.; Ottoni, A.; Pazos, D. (2012) Protocolo Bluehand: Zumbis: Seu guia definitivo contra os mortos e os vivos. Nerdbooks, Curitiba.

Idu, E.I. & Oladele, R.O (2010) An Epidemic of Zombie Infection: A mathematical Model. Available from: https://www.unilorin.edu.ng/publications/oladelero/Zombie_paper.pdf (Date of access 27/Mar/2015).

Levin, S.A.; Greenfell, B.; Hastings, A.; Perelson, A.S. (1997) Mathematical and Computational Challenges in Population Biology and Ecosystems Science. Science, Vol. 275(5298): 334–343.

Munz, P.; Hudea, I.; Imad, J.; Smith, R.J. (2009) When zombies attack! Mathematical modelling of an outbreak of zombie infection. In: Tchuenche, J.M. & Chiyaka, C. (Eds.) Infectious Disease Modelling Research Progress. Nova Science Publishers, Hauppauge. Pp. 133–150.

Ogg, J.C. (2011) Zombies worth over $5 billion to economy. Available from: http://www.nbcnews.com/id/45079546/ns/business#.VRW2gvnF8pk (Date of access: 06/May/2015).

Pruyt, E. (2006) What is System Dynamics? A Paradigmatic Inquiry. In: Größler, A.; Rouwette, E.A.J.A.; Langer, R.S.; Rowe, J.I.; Yanni, J.M. (Eds.) Proceedings of the 24th International Conference of the System Dynamics Society. System Dynamics Society, Nijmegen. Pp. 102.


Check other articles from this volume

The munchkin dilemma

João V. Tomotani

Universidade de São Paulo; São Paulo, Brazil.

Email: t.jvitor (at) gmail (dot) com

Download PDF

As most of you might have already guessed by the title, I am a nerd. As such, a relatively large part of my life was invested in hours of playing video games, reading nerdish stuff and playing tabletop role-playing games (RPGs).

RPGs should not be confused with board games, card games or board wargames. RPGs require players to “create fictional personas (…) within the rules and genre specified by the game, and then collectively engage in protracted storytelling” (Williams et al., 2006). As such, though the dungeon master might give some rules, background information and create a whole world for the players to explore, playing RPGs and creating your character is quite an open experience, where the player can and should use his/her creativity to have as much fun as possible together with the other players.

My experience with RPGs is mostly restricted to the Dungeons & Dragons system (D&D), which is probably the most famous tabletop RPG in the world. It was created in 1974 by Gary Gygax and Dave Arneson and, through the years, had many revisions of the rules, with new editions being published. Literally hundreds of books (Wikipedia, 2014) with new rules and classes were written to expand the ever-growing options for the players and dungeon masters. Also, D&D is remarkably less controversial than Storytelling RPG systems, with fewer parents blaming D&D for some sort of small disorder their children have, like a tendency to murder goats, summon cosmic horrors or whatever.

On a D&D game, players form a group of adventurers (or party) and embark on a journey for wealth and glory. Inside a world created by the dungeon master, the players are free to explore dungeons, destroy castles, build cities, save princesses and be awesome. Obviously, this never happens, as players inevitably ends up doing stupid actions which usually gets them (and everyone near them) killed; but this is the fun of RPG, probably.

One can divide a typical D&D game in different stages. There are moments when the party is exploring a forest, gathering information in the middle of a big city, furtively invading a well-guarded castle or fighting a horde of beasts. The party, thus, usually have different characters with different roles to fulfill each task (or not, since teamwork usually is not part of the average D&D party). Battles are inevitable and an important mechanics of the game, with whole chapters of the rule books devoted to it. Because of all the above, some players end up reading lots of books to find nice abilities and build a good and useful character. Being a hopeless nerd, of course I’ve done that.

THE MUNCHKIN DILEMMA

Today, I will present what I like to call the “Munchkin Dilemma”.

The word munchkin originated with the famous “The Wonderful Wizard of Oz” novel (often called simply “The Wizard of Oz” on the numerous reprints and the 1939 movie, which, by the way, recently made 75 years), written by Lyman Frank Baum in 1900. Munchkins are the natives of the Munchkin Country, and were originally said to be about Dorothy’s height. On the famous movie adaptation, though, the Munchkin Country was called “Munchkinland”, and the munchkins were depicted as being much shorter than the other Oz residents, being played by either children or adults with dwarfism. The word munchkin ended up entering the English language due to the popularity of the movie, as a reference to small children, dwarfs and anything of small stature, much like the Oompa Loompas.

In RPG jargon, however, munchkin is a pejorative term used to depict the “power player”, meaning the player who tries to make optimized characters, using the many different books to conceive the most efficient, overpowered killing machine instead of a character fun to play with. I guess the reason they are called munchkins is because they play like children, though it would make a lot more sense if it was because they like to play with dwarves. They are despised by the other serious and mature adults who play RPG.

There is a lot of prejudice associated with this term, of course. I expect no one likes making an useless character, but I guess that players that for some reason want to play with monks or bards tend to feel bad when a wizard does their job (much) better, and then they start complaining about not wanting to make a “power” character because they prioritize the roleplaying part of the game (they should be happy, though, since they are true to the uselessness of their characters). A card game created in 2001, where the player’s objective is to get to a high level while preventing the opposing characters of doing the same, was named Munchkin with the intent of making fun of such playing style (it is a great card game, by the way).

Munchkin_Imagem01
“And my axe!” Art by Todd Lockwood. Image taken from: Dungeons & Dragons Player’s Handbook (3.5 ed.).

Though there are many ways one player can be a munchkin, most of the times the munchkin’s objective is simple: to be a damage dealing, powerhouse chucknorresque machine. And to do so, he wants to have the strongest class, with the best configuration of feats and the strongest weapon.

Usually, the best way to do so is with a complex combination of many classes, or with a cleric or wizard. An optimized fighter, for example, might fight with a spiked chain and use the Improved Trip and Improved Disarm feats to become a very strong, overpowered and forever alone hated fighter.

Munchkin_Imagem02
Cover art of the Munchkin card game, by Steve Jackson Games. Image taken from: http://www.worldofmunchkin.com/game/

With all that in mind, I decided to create my own version of the Munchkin Dilemma D&D 3.5 edition, which I will try to answer here. The dilemma is stated as: “Which of the basic classes from the D&D Player’s Handbook v.3.5 (Cook et al., 2003a) is the best melee class when it comes ONLY to one-on-one combat? No multiclassing, no dips, no fancy stuff, just blood, death and violence.”

The dilemma may be rewritten as: “Which class should I take if I want to kick some monster ass?”

SIMULATION PROCESS

In an attempt to answer one of humanity’s most pressing questions, I decided to create characters with the melee classes from the Player’s Handbook, at different levels, with normal progressions (focusing on being strong at 1×1 combat) and equipment that corresponds to their expected treasure. The characters would then be tested against each other to see which one would have the best victory/defeat rate.

The first classes chosen were: Fighter, Barbarian and Ranger. Though the morphed Druid is said to be the strongest melee, it is also: (1) not a usual munchkin class; (2) difficult to simulate because of the many resources (wild shape strategies, such as grappler, trampler and defender; animal companion; spells). So I decided to leave druids for later. At first, I wanted to add the Rogue just to see how well it would fare, but at lower levels he wouldn’t be able to use the keen rapier + telling blow combo and at higher levels he would likely face fortified armors, so it wouldn’t make sense. I added the Monk just for the fun. The Paladin and the Cleric were not chosen at first because they were either too specific against some enemies or way too complicated to simulate. The levels chosen were: 1, 6, 12, 20. Though it makes absolutely no sense to have a level 20 pure melee Fighter with a two-handed sword, I stipulated that there would be no multiclassing for the first experiment. The race for all characters was decided as human, so no one would have any obvious advantage.

The fights are 1×1, with each character starting close to each other (avoiding charges and strategies of allowing the opponent to attack first and later using full attacks).

The ability scores for each character were decided by using the “Elite Array” distribution suggested on the Dungeon Master’s Guide (Cook et al., 2003b: p. 169). The distribution of the scores is 15, 14, 13, 12, 10, 8 among the abilities, whichever way the player wishes. The abilities and the extra ability points gained on levels 4, 8, 12, 16 and 20 were chosen according to the classes’ strengths. Similarly, the feats were chosen in accordance to the classes’ characteristics. The money for each level was also taken from the Dungeon Master´s Guide (Cook et al., 2003b: p. 135), with the exception of the 20th level, where a random large amount of money was chosen (usually, a lot of the money at this stage goes to other random stuff not really necessary for battle).

Also, there are different strategies the fighter might have. He can be the typical sword & board user, the two-handed weapon user, or the two weapons user. All three were considered in this study. The stats of each characters, as well as the feats chosen, are displayed on Table 1.

Munchkin_Imagem03
Table 1. Character stats. I decided to leave it small because no one will read it anyway.

Some considerations and strategies were assumed for the character building (the characters’ detailed information, relevant for combat, can be seen on Table 2–7):

  • The sword & board fighter is mainly a defensive character. His strategy consists of not being hit (with the Combat Expertise feat) and using his superior BAB to get some attacks each turn. He will use his money on good shield and armor, decent weapon and rings of protection and/or amulets of natural armors. Each turn, if no attacks connect, he will slowly reduce the BAB penalty spent on Combat Expertise;
Munchkin_Imagem04
Table 2. Fighter (sword & board).
  • The two-handed sword fighter uses power attacks with his great sword, trying to do the most damage possible each turn. His money will be heavily invested on a powerful weapon and strength boosters. If some money remains, he might get a decent full-plate and a flying shield. Each turn, if no attacks connect, he will slowly reduce the BAB penalty spent on the Power Attack feat;
Munchkin_Imagem05
Table 3. Fighter (two-handed sword).
  • The two-weapon fighter uses the “two-weapon fighting” feat tree, and tries to hit as many attacks as possible each turn. Pretty much all his money will go to his expensive weaponry;
Munchkin_Imagem06
Table 4. Fighter (two swords).
  • The barbarian rages as soon as he can and uses the same strategy as the two-handed sword fighter. The Leap Attack feat is pretty much default for the barbarian, so I felt like he needed to have it even though there are no charges in the simulation. His money is better spent on weapons and damage / HP boosters, since there is no point in getting a good light/medium armor for a raging barbarian. He always use maximum points for the full attack no matter what;
Munchkin_Imagem07
Table 5. Barbarian (with rage, +6 level 1 and 6, +8 level 12, +10 level 20).
  • The ranger was a big question mark. I decided right away to ignore the animal companion and go for the Distracting Attack variant or something, but had some doubts as for the favored enemy, which could turn out to be a bit overpowering for this simulation. I decided that he should have the favored enemy “humanoid (human)” since this is a common choice among players and is an important characteristic of the ranger (not having it would make this class way inferior on this competition). The favored enemies were chosen in order of my preference: arcanist (1st), undead (2nd), human (3rd), construct (4th), elemental (5th). The ranger spells were replaced by the Champion of the Wild variant from Complete Champion (Stark et al., 2007: p. 50). His money will be spent similarly to the two-weapon fighter;
Munchkin_Imagem08
Table 6. Ranger, two swords (favored enemy human: +2 lvl 12, +4 lvl 20).
  • Though the monk was included just for fun, I had some problems on creating the character. Since this is an all-out damage battle, I excluded feats of disarming and tripping, which are great (though the monk is never great, thanks to his horrible BAB). So, to make things fair, I used some feats from the Tome of Battle book, which we usually don’t use because of the overpower stuff in there. Since the monk suffers from MAD (Multiple Ability score Dependency; damn, the monk is horrible), his money is spent on items for pretty much all abilities. One good equipment for the monk would be the Monk’s Belt, but it takes away the monstrous Belt of Battle. Damn monk, I hate thee.
Munchkin_Imagem09
Table 7. Monk (considering 100% flurry of blows and Snap Kick on level 20).

SIMULATION VS. ANALYTICAL ANALYSIS

I decided to use a simulation method instead of analytically solving probability equations, because doing it analytically takes an absurd amount of time, since the number of combinations are enormous. To exemplify, I tried to make the Barbarian vs. Fighter (two swords) level 1 fight analytically. The terrible result is shown on Tables 8–11. The problem is that each attack has three possible outcomes (hit, miss or critical), the two-swords fighter, for instance, generate 2 to the third power possible outcomes with each attack. When considering more attacks and more health points, the number of combinations grow considerably. Imagine a fight of a level 20 monk against a level 20 ranger: the monk’s 7 attacks and the ranger’s 8 all have three possible outcomes. Considering the total HP, it is possible for the ranger to hit the monk 11 times without defeating him, while the monk can hit the ranger 14 times without defeating him. After the fighter’s second attack, I decided to extrapolate the results previously found to the remaining rounds. I believe I got close enough to the answer, but it took some effort. Thus, the barbarian defeats the two-swords fighter more than 4 out of 5 times.

Munchkin_Imagem10
Table 8. Combat data.
Munchkin_Imagem11
Table 9. Battle begins. Notice how each branch where the fighter survives after a barbarian attack results in other 8 branches, with 8 possible fighter outcomes.
Munchkin_Imagem12
Table 10. Fighter’s second attack.
Munchkin_Imagem13
Table 10. Fighter’s second attack (cont).
Munchkin_Imagem14
Table 11. Extrapolating the results and final result.

RESULTS

In this section, I will present the results of the simulation (which was made in VBA), as well as some considerations regarding critical aspects of D&D combat. For each fight, I will present what was the winning percentage of each build, the average percentage of remaining Health Points of the winner, the average number of rounds it took for the winner to defeat the opponent, and how many times the winning party had the initiative of the fight. Each table shows the result of a build against each of the other builds. The information shown are:

  • Number of victories and percentage of victories: out of 1000 fights, how many were won by each build;
  • Remaining HP and percentage of remaining HP: on average, how much HP this class had left in the fights it won;
  • Average number of rounds: on average, how many rounds it took for this class to win the fights it won;
  • Initiatives won and percentage of initiatives: out of 1000 fights, how many had this build winning the initiative roll;
  • Winning with initiative: how many fights this build won AND had the initiative.

Also, henceforth, the sword & board Fighter, the two-handed sword Fighter and the two-weapons Fighter shall be called, respectively, S&B Fighter, THS Fighter and TW Fighter.

LEVEL 1

On level 1, it is possible to see that the Barbarian had little trouble dominating all the other builds, with winning percentages higher than 70% against any opponent and an average of less than two rounds to finish a combat. This result is not unexpected, since the Barbarian acquires the very strong Rage ability on level 1. The Ranger and the Monk, on the other hand, performed poorly against all the opponents, and had a technical draw when faced against each other. This result also is not unexpected, since both classes have low hitting rates at the first level – the Monk’s flurry of blows is still underdeveloped and the Ranger does not yet acquired his first Combat Style class ability (two-weapon fighting).

In the middle of the pack are the three fighter builds. The S&B Fighter, with his high armor class, managed to defeat the TW Fighter and the THS Fighter, while the TW Fighter defeated the THS Fighter. The three fights were relatively close. Table 12 shows the detailed results of the fights.

Also, it is interesting to compare the results of the simulation with the ones calculated analytically on the first part. It was calculated that the Barbarian would defeat the TW Fighter more than 80% of the time, while in the simulation, it is seen that the Barbarian would win around 70% of the time. This difference shows that some of the simplifications adopted in the first part were probably incorrect.

Table 13 shows some averages and consolidated results. It is interesting to see how having the initiative impacts the outcome of the fights. The Ranger and the Monk had most of their wins when they had the initiative, while the Barbarian had a very low number of defeats when having the initiative.

Munchkin_Imagem15
Table 12. Results of the fights for the level 1 builds.
Munchkin_Imagem16
Table 12. Results of the fights for the level 1 builds (cont.)

 

Munchkin_Imagem17
Table 13. Some consolidated results for the level 1 combats.

LEVEL 6

On level 6, once again the Barbarian defeated all the opponents. This time, though, he had a much harder time against all the Fighters, and the THS Fighter in particular. By level 6, the Fighter builds gained a lot of feats, mainly the Weapon Specialization, Power Attack, Power Critical and Improved Initiative ones, which made them considerably stronger. The S&B Fighter and the THS Fighter did very well against the other classes, and had a technical draw when they fought against each other.

The Ranger and the Monk, on the other hand, dragged terribly behind the other classes. The Ranger’s strongest resource in a fight lies with her Favored Enemy ability and, for this simulation, this ability is only acquired against humanoid (humans) on level 12. The Monk suffers because of his lower Base Attack Bonus; by level 6, all the other classes have acquired their second attack, while the monk still has only one (without considering the flurry of blows). The detailed results can be seen on Table 14.

Table 15 shows again some averages and consolidated results. Compared to the level 1 combats, the ones on level 6 took much longer due to the increase in Health Points, without much damage dealing improvement (which usually comes with stronger equipment at higher levels). The builds that did better at level 6 were the ones that were capable of consistently dealing high damage with few attacks (THS Fighter and Barbarian), instead of many, easier-to-miss attacks and low damage.

Once again, the initiative had a lot of impact on the results of the fights. The only outlier would be the Ranger who won most of her fights without the initiative (though most of them were against the monk).

Munchkin_Imagem18
Table 14. Results of the fights for the level 6 builds.
Munchkin_Imagem19
Table 14. Results of the fights for the level 6 builds (cont.).
Munchkin_Imagem20
Table 15. Some consolidated results for the level 6 combats.

LEVEL 12

On level 12, once more the Barbarian defeated all opponents without much trouble. Most of the merit can be given to a much higher number of Health Points, and mainly to the much higher damage output per round of the build (Greater Rage, Gloves of Strenght +4, Collision Weapon, Boots of Speed), which reduced his average number of rounds to finish a combat to less than two. In fact, at this stage the equipment starts playing a much larger role on the combats, allowing all classes to finish their fights in a much shorter time.

The Ranger, once again, struggles to win even a small number of fights. The favored enemy ability is still underdeveloped and the two weapons are very expensive to upgrade. For this reason, the TW Fighter also does very poorly on this scenario where equipment is so relevant.

The Monk, on the other hand, performs surprisingly well (I definitely did not expect the Monk to win a single fight!). Thanks to a fully developed Flurry of Blows and the Monk’s Belt, he is capable of dealing a lot of damage to builds with low Armor Class, losing badly only to the S&B Fighter and the Barbarian.

Finally, the S&B Fighter convincingly defeats the THS Fighter and all the other opponents but the Barbarian. Thanks to stronger equipment, the S&B Fighter is capable of defeating the opponent quickly, while keeping a very high Armor Class. The detailed results can be seen on Table 16.

Table 17 shows again the averages and consolidated results. The fights are much shorter thanks to the increase on damage output with the better equipment. It is clear that the initiative factor becomes even more impacting than in the two previous scenarios. A high percentage of the fights won by the Ranger and the Monk are when they have the initiative. This effect is also a consequence of the higher damage output.

Munchkin_Imagem22
Table 16. Results of the fights for the level 12 builds.
Munchkin_Imagem23
Table 16. Results of the fights for the level 12 builds (cont.).
Munchkin_Imagem24
Table 17. Some consolidated results for the level 12 combats.

LEVEL 20

Finally, on level 20, the Barbarian is once more completely dominant. With a monstrous amount of Health Points and damage output, he easily defeats all other classes and completely destroys the S&B Fighter, who is incapable of dealing enough damage.

The S&B Fighter, though completely defeated by the Barbarian, overpowers all the other classes through consistent damage and very high Armor Class. The TW Fighter and the Ranger, with enough money to equip themselves, perform very similarly, defeating both the Monk and the THS Fighter.

The Monk, once again, is crushed by the other classes. The Monk’s interesting feats and abilities are not enough to deal with increasingly powerful weapons and armors. The detailed results can be seen on Table 18.

Table 19 shows the averages and consolidated results. The fights are still short, with high damage output by all classes. The information of the consolidated results were used to generate the three graphics presented on Figures 1–3.

Once again, the initiative factor is more important than in the previous three scenarios. Most of the fights won by the Ranger, Monk and TW Fighter happened when they had the initiative, while the Barbarian almost did not lose when she had the initiative.

Munchkin_Imagem26
Table 18. Results of the fights for the level 20 builds.
Munchkin_Imagem27
Table 18. Results of the fights for the level 20 builds (cont.).
Munchkin_Imagem28
Table 19. Some consolidated results for the level 20 combats.

 

Munchkin_Imagem21
Figure 1. Number of builds defeated.
Munchkin_Imagem25
Figure 2. Total fights won.
Munchkin_Imagem29
Figure 3. Average number of rounds taken to defeat the opponent.

CONCLUSION

First and foremost, I find it important to state clearly that the combat is but a small part of the D&D game. Though it might be tempting to create an efficient character for battles, there are many different ways a character can be truly powerful, useful and, most important of all, fun to play with. Secondly, 1×1 melee combats are (thankfully) rare in D&D games. Most battles involve many characters and enemies, making them much more fun and challenging, requiring some amount of team work, planning and creativity. Thirdly, even on 1×1 melee combats, only going for full attacks is not that common. Characters can (and should) have different tactics that involve disarming, tripping, sundering or any other resource that allow them to overpower the opponent. Having said that, this small simulation shows some interesting points.

The Barbarian is clearly the strongest build of the ones simulated when considering raw power. The high attack bonus and damage output surpass the most solid defenses, while the enormous amount of Health Points protects against the fiercest attacks. The Barbarian is clearly superior to the THS Fighter, when it comes solely to melee fights.

Monks, Rangers and TW Fighters, builds that use a large number of attacks, have trouble against defensive characters, since many of the attacks do not connect. On the other hand, they can consistently defeat characters with low Armor Class, making them interesting choices against Wizards and other spellcasters.

The most interesting finding of this simulation, though, is the increasing impact of the initiative on the melee combats, when considering the possibility of a “full attack”, as the characters grow stronger.

Due to powerful items such as Boots of Haste and Belt of Battle (or, even better, spells such as Haste or Righteous Wrath of the Faithfull), winning or losing the initiative can be more important than a careful planning of the attack or the careful creation of a character. This might not be relevant in situations where, as stated above, many characters are fighting at the same time, but it can be a problem when 1×1 melee fights affect the whole outcome of the adventure.

As such, some adaptations of the initiative rule may be interesting when such fights are necessary (gladiator fights, generals meeting in the battlefield, among others). One interesting alternative is the one presented by the Shadowrun system (Hardy et al., 2013) where, instead of rolling initiative once for all your actions of the round, you roll initiative to define an “initiative gauge”. The character to act is the one with the highest “initiative gauge” and each action taken depletes this gauge by some amount.

With the release of D&D 5th edition, many changes were made, including combat rules. Soon enough, I shall play it to give my take on it!

REFERENCES

Cook, M.; Tweet, J.; Williams, S. (2003a) Dungeons & Dragons Player’s Handbook: Core Rulebook 1 v3.5. Wizards of the Coast, Renton.

Cook, M.; Tweet, J.; Williams, S. (2003b) Dungeons & Dragons Dungeon Master’s Guide: Core Rulebook 2 v3.5. Wizards of the Coast, Renton.

Hite, K. (2009) Rough Magicks. Pelgrane Press, London.

Hardy, J.M.; Brozek, J.; Croteau, R.; Dynna, M.; Goodman, P.; King, R.; Large, A.; Oratz, D.; Pavao, A.; Ratkovich, S. (2013) Shadowrun, 5th ed. Catalyst Game Labs, Lake Stevens.

Stark, E.; Thomasson, C.; Louve, R.; Marmell, A.; Astleford, G. (2007) Complete Champion. Wizards of the Coast, Renton.

Wikipedia. (2014) List of Dungeons & Dragons rulebooks. Available from: http://en.wikipedia.org/wiki/List_of_Dungeons_%26_Dragons_rulebooks (Date of access: 01/Sep/2014).

Williams, J.P.; Hendricks, S.Q.; Winkler, W.K. (2006) Gaming as Culture – Essays on Reality, Identity and Experience in Fantasy Games. Oxford University Press, Oxford.


cover vol1(1-2)
Check other articles from this volume

The Infinite Fish Playing Pokémon Theorem

João V. Tomotani

Universidade de São Paulo; São Paulo, Brazil.

Email: t.jvitor (at) gmail (dot) com

Download PDF

THE INFINITE MONKEY THEOREM

I will start by presenting this little famous theorem. The Infinite Monkey Theorem states that if you have a monkey hitting keys at random on a typewriter keyboard for an infinite amount of time, eventually it will end up reproducing some famous text, like the complete works of William Shakespeare, The Lord of the Rings, or the very article you are currently reading (the process used to write this article is not that far from it, actually).

This is the sort of theorem that clearly became famous because of its funny name. And, while I do find the name amusing, the theorem itself is also quite interesting; well, at least more interesting than the real-life experiment that the University of Plymouth decided to do, which remarkably showed that a monkey with infinite time would probably be able to defecate infinitely and destroy an infinite amount of typewriters (BBC News, 2003). Also, for some reason, friends of mine tend to state the Infinite Monkey Theorem as having an infinite amount of monkeys with an infinite amount of typewriters, instead of the infinite time stuff. Though this would solve the small problem of having to find an immortal monkey, maybe an infinite amount of monkeys would also pose a problem (for more information, you can read “what would happen if you were to gather a mole (6×1023) of moles” from Randall Munroe, 2014) – let me simply say that this would make Planet of the Apes a lot more literal.

In any case, recently a small event reminded me of the Infinite Monkey Theorem. I am talking, of course, about Grayson Hopper, and his quest to become a pokémon master. Grayson is a fish who rose to absolute stardom after his owners decided to make him play Pokémon. By swimming in his aquarium, Grayson’s position is detected by a camera and a command is sent to the game. You can follow his play on Twitch. Not much is going on right now (or ever).

Grayson is trying to prove by himself that, through a generator of random movements and a lot of time, one should be able to finish a game like Pokémon, which you can play by pressing only one button at a time and not having to rely on timing or stuff like that. I mean, if a ten year old boy can do it, why can’t a fish?

And what the Infinite Monkey Theorem states is that he can do it, right? The fish might very well be able to beat the game in his lifetime, since a really large number of combinations of buttons will be generated, and one of them MUST be the correct one. Well, meet Route 22 (Fig. 1).

Fish_Imagem1
Figure 1. Why, hello there, Route 22. Image taken from: Pokémon Gold/Silver/Crystal.

From now on, I will consider that all of you had a childhood and are thus capable of following the game mechanics.

Route 22 could be called the nightmare of random walking (for more information on random walking, or “why a drunk always come back home while a drunk bird may be lost forever because of extra dimensions and stuff”, see Math Explorer´s Club, 2009). The game mechanics of one-side-crossing-only ledges clearly makes this route goddamn awful. Also, Grayson tends to stay still for some seconds on the same area of the aquarium, thus repeating the same command a lot (a “down” command one time more than necessary can be fatal here). So, is it impossible?

Only one way to find out…

THE INFINITE FISH PLAYING POKÉMON SIMULATION MODEL

To simplify, let’s say that the movement of the fish in the aquarium is a random process that can be categorized as a Markov chain. A Markov chain is one of the simplest stochastic processes, where the next entry in the chain depends only on the current position (or state), and not on the history of entries (this lack of history is called the Markov property). The random walk is an example of a Markov chain. Though the movement of the fish depends on the history (usually he will keep swimming on the same direction), let’s not waste time trying to model this further, because time is precious and we wouldn’t like to waste it on useless stuff like a useless model.

Grayson’s aquarium is divided into nine squares (Fig. 2). Each square has a specific command, with one exception, the “randomize!” command, which randomly chooses one of the other eight. Let’s consider that one command is chosen after every second.

Thus, the Markov chain describes a process where the random walker is on a position among nine, and has a random probability of going to any of the nine positions (including staying on the same one) after one second.

Fish_Imagem2
Figure 2. Grayson’s aquarium and control scheme. Screenshot taken from: Twitch – Fish Plays Pokémon.

The matrix that gives the probability of transition to each of the states in a Markov chain is called the transition matrix. The transition matrix can be dynamic or stationary in time. For example, giving the fish more food would make it dynamic, with a higher probability of him going to the surface of the aquarium. But let’s consider a stationary matrix for simplicity.

After watching Grayson playing Pokémon for 2 minutes (boy, that was fun!), I generated some numbers for the transition matrix (Table 1). I decided that the probability of him staying still in the same position for one second would be 80% in any of the positions (though I must say that it is probably much higher). Also, I considered that the probability of him going to an adjacent area was higher than crossing the aquarium from one instant to the other. Since the position of the commands changes over time on the twitch play, I decided to generate them randomly and leave them as such. Admittedly, the fish spends a lot of time near the surface, but let’s not focus on the details since the randomization of the commands also contributes to the randomization of the process.

Fish_Imagem3
Table 1. Position matrix.
Fish_Imagem4
Table 2. Probabilities of the transition matrix.

By multiplying the transition matrix by itself a number “n” of times, you can find the accumulated transition probabilities after n events. For instance, if I multiply the matrix by itself twice, I will have the probabilities of Grayson transiting between two states after two seconds.

Since the transition matrix is stationary, aperiodic (no time limitations from transiting from one state to the other) and has no recurrent state (states with probability of 0, transition state, or 1, absorbing state), it is also said to be ergodic, that is, the system has the same average behavior over a long period of time. Multiplying the matrix by itself 128 times, I get to the following matrix (Table 3).

That is, the probability of Grayson being in one of the states after a long period of time is not dependent on his initial state, only on the transition matrix. Looking at this matrix, I can see that the probability of the fish spending some time on the center of the aquarium is slightly higher than on the edges, given the numbers I decided for the transition matrix. Since the distribution among the states is quite similar, I am happy with the transition matrix chosen. After modeling the fish movement, it was time to model the map of Route 22 (Fig. 3).

Fish_Imagem5
 Table 3. Transition matrix after 128 seconds.
Fish_Imagem6
Figure 3. Modelled map of Route 22.

   As can be seen on Figure 3, for each coordinate on the map, a number was attributed. This number states movement restrictions or other characteristics. Coordinates with the number “1” have no movement restriction, while coordinates with the number “3” has restrictions with the “up” direction, and coordinates with the number “2” have no restrictions, but the “down” direction skips a square. Once again, to simplify the model I considered that Grayson cannot go to the right of the map, leaving the area of Route 22.

The green area is the “wild grass” area. I decided to count the steps taken on “wild grass” areas to estimate how many pokémon battles Grayson would face in his epic quest. The probability encounter formula, according to Bulbapedia (2014) is defined as P = x / 187.5, where x is the encounter rarity variable. Considering a common encounter rate (x = 8.5), Grayson should face S*0.05 battles, where S is the number of steps taken on wild grass.

The desired results are the number of total commands necessary for Grayson to arrive at his destination. Other interesting results are the number of battles and the number of commands given while in “paused” state.

As a limit of commands (thus, time), at first I thought that the simulation should go no longer than the average life span of a goldfish. Considering a life span of 25 years, this would be the same as 788,400,000 seconds/commands (if he keeps pressing the A or select button, or moving while on paused state, it still counts as a command for the simulation).

This number of commands, though, is unreasonably high and would probably only increase the entropy of the universe. So, I decided to just let it run for a couple of minutes and see what would happen after the equivalent of one day for the fish.

The model was written in VBA and the program ran on my personal computer.

RESULTS AND DISCUSSION

The results are as follows:

  • Number of steps to complete: 86400 (1 full day, didn’t complete, ended in coordinate 14 x 18);
  • Number of steps on “wild grass” areas: 351;
  • Estimated number of battles: approximately 18;
  • Number of steps taken on paused state: 47796.

Thought I only simulated the equivalent of one “fish day”, whenever I stopped to watch the simulation, it was clear that the character in-game was struggling to get out of the lower part of the map. It was expected, almost inevitable, for Grayson to spend most of his time randomly walking around the 76 coordinates that composed this artificial cage (with only one way out, coordinate 13 x 34, and many ways in); more than 99% of the time was spent there. Positioning the character right in front of the exit and moving “up” twice was a very specific command that happened only twice during the simulation, with the character going back right after. Also, more than half of the commands were given while on paused state.

A DIFFERENT APPROACH

The greatest limitations of the study above are the short simulation time and the fact that the simulation was run only once. Considering how the stochastic process of the fish swimming impacted the results, it would be necessary to run the simulation dozens of times to achieve better and more valid results.

With that in mind, I now propose a different take on The Infinite Fish Playing Pokémon experiment. Instead of simulating the random process of a fish swimming, I will propose some simplifications in the previous model, so that the problem can be solved on a deterministic way. Though the simplification will reduce considerably how well the model represents reality, the results presented will offer valuable information on the magnitude of the problem.

EXPLANATION OF THE NEW APPROACH

On my first attempt to model the Fish Playing Pokémon, I considered that the movement of the fish in the aquarium was a random process which could be represented as a Markov chain. Since the position of the fish in the aquarium was considered a Markov process, this stochastic process was what defined which command was sent to the Pokémon game.

Since the probability of each command being chosen depended on the position of the fish in the aquarium, the modeling of the Pokémon game was a complex process that needed simulation.

This time, I will simply ignore the position of the fish and consider that the command sent to the game is a completely random process, with each of the directional commands having the same probability of being chosen. This way, the movement made on the game depends only on the current position of the character in the map, that is, the game itself can now be modeled as a Markov chain. With this simplification, the probability of the character being in each position can be defined on a deterministic way.

IMPLEMENTATION

Once again, the first step is to attribute a number to each coordinate in the map, and define which the possible movements for them are. There are 305 different possible coordinates in Route 22 (Fig. 4). Considering four possible commands, each command has a 25% chance of being chosen.

Fish_Imagem7
Figure 4. Route 22 with coordinates.

If the chosen command is impossible to be made, the character stays on the same coordinate. For example, if the character is on square 305, there is a 25% chance of him going to coordinate 267, 25% of going to 304, and 50% chance of staying in the same place. These probabilities, as stated, do not vary.

Having defined the coordinates and the possible movements, I can define the transition matrix. Since I have 305 possible positions, the transition matrix will be a 305 x 305 matrix (Figure 5). From each position, the character can do, at most, 4 different movements. That way, at least 301 movements will have a zero (for instance, the probability of going from position 127 to 29 in a single step is zero).

By multiplying the transition matrix by itself a number “n” of times, you can find the accumulated transition probabilities after n events.

Another simplification adopted is that the end of route 23 is not an absorbing coordinate, that is, if the character arrives at the end, it is possible for him to go back. This simplification is necessary for the transition matrix to be ergodic, and thus stabilize after a long period of time.

Fish_Imagem8
Figure 5. An example of a small subset of the transition matrix.

Multiplying the matrix by itself 64000 times (since there were many coordinates, it took a while for the probabilities to stabilize), I get to the matrix shown in Figure 6. This stabilized matrix shows that, after a long time, the probability of the character being in each coordinate does not depend on the starting point. This is true because of the ergodic property of the system. When stabilized, it is said that the system achieved stationary regime.

Fish_Imagem9
Figure 6. A small part of the transition matrix, after 64000 commands.

 RESULTS OF THE DIFFERENT APPROACH

Another way of interpreting the stationary regime matrix is that, instead of the probability of the character being in each state, it represents the percentage of time the character will spend in each of the 305 coordinates. That way, it is possible to calculate how many iterations are necessary, on average (after achieving stationary regime), for the character to pass through a defined coordinate.

The probability of the character being in coordinate 29, thus, is 4.11*10-13, that is, a little more than 0.000000000041%. If we divide 1 by this probability, we see that, on average, we would need 2.43*1012 iterative steps to pass through coordinate 29.

Since each command (or step) is made every 1.5 seconds, this number of steps would take around 115.700 years to be made. This time should be at least doubled, if we considered the possibility of the commands that are not movement commands (the “A”, “B” and “Pause” commands).

Interestingly, the percentage of time spent in the lower part of the map (coordinates 230 to 305) is 96.36%, and the time spent in the initial part of the map (up to coordinate 92) is 99.42%.

 CONCLUSION

What are the odds of the universe taking form as it did? What are the odds of you being conceived? These questions were made many times by many different scientists from different areas. Binazir (2011) shows through an interesting chart, which went viral on the internet, that the odds of you existing are the same as two million people throwing a trillion-sided dice and all of them getting the same result. As usual, the best answers are from Douglas Adams (1979), who shows that the whale and the bowl of petunias are not impossible as you initially thought, just as impossible as anything else.

The more specific the event, the more impossibly low are the odds of it happening.

This study only started as a joke, but the more I thought about it, more it made sense in this world of impossible improbabilities happening.

Grayson will clearly never finish this game, not before the heat death of the universe. He probably won’t even get close to the Safari Zone, from where he would never come out as well anyway. But maybe, only maybe, something impossible might happen, and the fish might be able to achieve his impossible dream of becoming a Pokémon master.

REFERENCES & FUTHER READING

For more information on Markov chains, queue theory and lots of Operations Research concepts, read: Winston, W.L. (2003) Operations Research: Applications and Algorithms, 4th ed. Cengage Learning, Boston.

Adams, D. (1979) The Hitchhiker’s Guide to the Galaxy. Pan Books, London.

BBC News. (2003) No words to describe monkeys’ play. Available from: http://news.bbc.co.uk/2/hi/3013959.stm   (Date of access: 14/Aug/2014).

Binazir, A. (2011)  What are the chances of your coming into being? Available from: http://blogs.law.harvard.edu/abinazir/2011/06/15/what-are-chances-you-would-be-born/ (Date of access: 14/Aug/2014).

Bulbapedia. (2014) Tall Grass. Available from: http://bulbapedia.bulbagarden.net/wiki/Tall_grass (Date of access: 14/Aug/2014).

Math Explorer’s Club. (2009) Random walks. Available from: http://www.math.cornell.edu/~mec/Winter2009/Thompson/randomwalks.html (Date of access: 14/Aug/2014).

Munroe, R. (2014) What If?: Serious Scientific Answers to Absurd Hypothetical Questions. Houghton Mifflin Harcourt, Boston.

Twitch. (2014) Fish Plays Pokémon. Available from:  www.twitch.tv/fishplayspokemon (Date of access: 14/Aug/2014).


cover vol1(1-2)
Check other articles from this volume