Among Us as an Operations Research Problem

1. The Among Us Game

Among Us is a game of teamwork and betrayal that develops in a spaceship with a crew of astronauts. There are two types of players: crewmates and impostors. The game’s objective depends on whether the player is an impostor or a crewmate. If the player is an impostor, the primary goal is to sabotage the spaceship or eliminate all other members of the crew. If the player is a crewmate, he or she must achieve one of two goals: finish all the tasks in the spaceship or point out all the impostors.

1.1. The Spaceship

The game can be played in one of four available spaceships: The Skeld, MiraHQ, Polus, or The Airship. Although each map has its particularities, the concept is quite similar. Because The Skeld (Figure 1) is the most popular spaceship, it is described in detail, whereas the other spaceships have similar characteristics.¹

The central point of the spaceship is the cafeteria. In fact, the game starts with all the astronauts (crewmates and impostors) there. The cafeteria has a unique and special feature: a panic button that any astronaut can press to perform an emergency call. The remaining blue areas represent the spaceship’s zones where the crewmates must execute tasks. The impostors can then feign that they are completing a task but are not allowed to execute them.

The spaceship has certain perks available depending on the player’s affiliation, in addition to the aforementioned tasks. Crewmates can see footage of the security cameras and a log of the players’ movement. Impostors can sabotage certain essential equipment (oxygen depletion and reactor meltdown) and use vents to hide or to move to another vent without being seen.

1.2. General Gameplay

Usually, Among Us is played online or on a local server with friends. The game is supposed to be played under absolute silence except for in-game trials. After the game starts, each astronaut is free to move to whichever place in the spaceship they want. Crewmates can start their chores, and impostors can start their sabotages. Moreover, impostors can eliminate crewmates. The eliminated crewmate is allowed to finish his/her tasks as a ghost but cannot participate in other activities.

All noneliminated players have a meeting if one of two things happens: a player detects a dead body and calls the meeting, or a player pushes the panic button in the cafeteria. Impostors are allowed to call the meeting as well. This reunion is paramount to the game because it is the only opportunity for the crewmates to discharge an impostor from the spaceship. In the meeting, astronauts that are still alive are allowed to communicate to expose who they think is an impostor. This discussion is often verbal if the game is played on a local server or between friends. If this game is played online with strangers, it is performed on a chat platform provided by the game.

After the time to discuss who is an impostor runs out, the remaining players are allowed to vote. They can vote for a player, skip the vote or simply do nothing. If a player has more votes than any other option (including skip), the player is ejected from the ship. Nothing happens if there is a tie or the majority of votes are skips. Regarding the competitive settings of the game, the game does not confirm whether the ejected player is an impostor.

The game ends if:

• The crewmates finish all the tasks. The crewmates win.

• The crewmates eject all the impostors. The crewmates win.

• The number of crewmates is equal to the number of impostors. The impostors win.

• A life-threatening sabotage is not fixed on time. The impostors win.

Although each game host can decide the proportion the game is usually played with one impostor if the total of players is eight or below and with two impostors otherwise. The maximum number of players is 15.

One of the strategies available to crewmates is to avoid being alone in a room with an impostor because it can result in the elimination of the former in an isolated place without witnesses. Because the game is often played among friends, the strategies of the impostor can sometimes be predicted. These strategies are often derived from knowing the location of an impostor within a time window. As such, visiting other places where tasks must be completed when the impostor is elsewhere can represent a competitive edge in the game.

2. Proposed Educational Activity

We present two different activities to be developed in an introductory optimization course: one is to be played in a session, and another is to be used as coursework. The coursework activity is presented more formally because it is ready to be delivered to the students. On the other hand, the activity to be performed in a session must be directed by the lecturer.

The students are expected to know about the game. They can download it (free in Google Play and Apple App Store) such that they understand the game’s dynamics. If this is not possible, a tutorial on the game can be presented.²

The appendix of this teaching note includes a larger map of The Skeld.

2.1. Game to be Played in a Session

The game to be played in a session has two phases:

Phase 1: The students are divided into smaller groups (three to five students per group). Each group receives a map of The Skeld and a distance matrix. Then, they are provided a set of tasks to be performed, as well as the time required in each area.

The students are informed that they are crewmates and must design a route starting from the cafeteria to perform all tasks and return to the cafeteria in the least time possible. Moreover, in order to eliminate symmetry, students are asked to visit the MedBay area first.

Moreover, they must guarantee that MedBay is the first visited area. This is to eliminate symmetry. The route must be designed considered the distance matrix given in Table 3.

Phase 2: The students are informed that there is an impostor in the spaceship! Because of the elimination of some of their crewmates, they have learned about the impostor’s whereabouts.

Now the challenge for the students is similar to the initial one, but there is a new condition. They must avoid meeting the impostor in an area. The optimal solution for the TSP is not feasible. If the route is not changed, they will meet the impostor in the reactor, storage, shields, and navigation areas.

The lecturer can use this challenge to introduce the concept of disjunctive constraints. To solve this limitation, the crewmates must decide if they visit an area prior to or after the impostor. Two new considerations must be taken into account when the impostor’s whereabouts are contemplated. First, the crewmates can stay idle in an area after performing the task (they can wait until the impostor moves). Second, the objective function can change because adding the times of movement and the times to perform the tasks do not include the idle times in an area.

2.2. Coursework Exercise

You are a crewmate on a spaceship called “The Skeld.” At the moment, you are in the cafeteria. Based on recent events, you know that there is an impostor inside the spaceship. It is your priority to avoid an encounter with the impostor. You have these pending tasks (Table 1):

Table 1. Tasks to be Performed

Your unjustifiably eliminated crewmates have given insights into the areas that the impostor will visit. The information includes the time within which the area is visited (Table 2):

Table 2. Impostor Whereabouts

Table 3. Distance Matrix

Moreover, you also know that the first task to be performed is to check your vital signs.

This is the time to go from one area to another (in minutes).

You must:

1. Identify a feasible solution to the problem using a heuristic method. Suppose there is no impostor on the ship. You may use the Evolutionary Excel Solver as an alternative. Describe the heuristic strategy used to identify your solution.

2. Formulate a mathematical model to visit all the nodes where tasks must be performed. Solve the mathematical model and describe the optimal route. Assume that there is no impostor on the ship. The student is encouraged to read Orman and Williams (2007) to understand how the problem can be formulated better.

3. Formulate a mathematical model to visit all nodes where tasks must be performed without encountering the impostor. Solve the mathematical model and describe the differences with respect to the previous solution.