MapReduce for MMOs

MapReduce is a powerful tool to parallelize batches of computations. MMOs may sometimes have to run batches, but from what local game companies tell me, nobody in the game industry is currently using MapReduce. I guess, this is mostly due to studios not knowing what to do with it. Here are some examples.

Business intelligence

Basic metrics such as weekly play time or stop rate can give a rough perspective of the retention of an MMO. These metrics can be estimated with a couple SQL queries on dumps of the production database(s). It starts taking more time and effort to distinguish accross server shard, faction, race, or class. Still, a SQL script running for a few hours can do the job. Fancier analyses such as machine learning or social network graphs explorations take even more time and effort. MapReduce can be used to tune machine learning algorithms through Mahout, and even to process graphs (Google's Pregel also seems interesting for parallel processing of graphs: the Pregel version of PageRank takes 15 lines of code).

Detecting bots, hacks, or gold farmers is not as straightforward, but I think it is doable. First, the typical deviant behaviors have to be determined and made explicit by humans. For instance, speed-hackers send too many messages per second to the server, while gold farmers interact with less players, but more intensely, than normal players. Then, detecting deviant behaviors can be a machine learning classification or a graph parsing problem. In both cases, MapReduce can help.

Game-specific

Matchmaking and ladder: Some pre-calculations or updates to parameters of the ladder and match-making algorithms could be done offline by a small MapReduce cluster. A player's skill is unlikely to change much in 12 hours, so a cron task could run the job twice a day. According to Josh Menke from Blizzard, matchmaking involves gradient descent or Gaussian Density Filtering. Not sure whether Mahout supports GDF, but gradient descent is supported.

Tuning and balancing can take days for system designers. MapReduce could do that automatically: each mapper job is given a particular set of system parameters: player 1 has skill A (cost x SP and inflicts y damage) and skill B (cost z SP and heals w HP), player 2 has skill C (...) and skill D (...). Mappers run a few hundred Monte-Carlo simulations of a player 1 versus player 2 match with a fixed set of parameters (player1:A,B; skillA:x,y; skillB:z,w; ...). When done, mappers pass average statistics (win/loss ratio, average amount of gold at the end of the match, ...) of the 100 matches to reducers who sort them. The interesting configurations for balance are those with a win/loss ratio close to 50%. Naturally, this brute-force way of balancing assumes a proficient AI, and designers will still have to tweak the configurations returned by MapReduce so that they feel fun.

Practical concerns

Engineering detail: MMOs have hundreds of shards, but really only one MapReduce cluster should be needed. Each shard could send its jobs to the MapReduce cluster when it needs them done, and wait asynchronously for the MapReduce answer on a particular port. If the MapReduce job uses data from the production database, producing a daily dump may induce a temporary extra load on the shard's database machines, but this should be fine during empty hours.

MapReduce can be a double-edged sword if overused. Exploring the parameter space of learning algorithms too aggressively may lead to less accurate models.

Edit: Some people have been using MapReduce for analytics: mogade's platform and keighl have been using it through mongodb, but it's more of an engineering constraint (scatter-gather queries in a nosql DB to build a ladder board) than an analytics or machine-learning endeavor.

Quests - Howard 2008

Quests: Design, Theory, and History in Games and Narratives by Jeff Howard, in 2008.

History of quest games

Year	Game	Innovations
1974	DnD	GM as referee, quests taken from Celtic, Norse, and Arthurian mythologies.
1976	Adventure	on computer, first RPG, network play
1983	King's Quest series	cut scenes, music, multiple endings, optional puzzles, and side-quests.
1985	Ultima IV series	virtues, colors, and classes are related
1986	Zelda series	quest status screen shows the player's progress, first action-adventure game.
1999	EQ	proliferating tasks rather than a single main quest
2004	WoW	lore quests, the never-ending war theme is a bleak scenario not particularly conductive to meaningful gameplay: failing a quest is not problematic.

Intro

Campbell's "Hero's Journey" consists of separation, initiation, and return. The individual builds himself, as found in medieval romances. In games, the initiation phase is lengthened and repeated, since it has most action.

A quest is an action that is meaningful to a player. It's also called a "mission" in games with a modern setting.

Ludologically, a quest has goals and consists of searching a functional meaning: a key opens a door, therefore the player should look for a door. A sword kills monsters, therefore the player is expecting to encounter enemies soon. Once meaning is found, the quest is over.

Narratologically, a quest has a story. The story and the lore motivate and immerse the player in the task.

But actually, meaningful quests come from striking a balance between too much action and too much narrative, while keeping in mind the big picture of the game's meaning. Except for XP and loot, why is that quest important to the player? What satisfaction does the player get by doing that quest? Here are some clues:

• Impact on the world: achievement, gaining power, learning about the lore, altering political or moral balance, or changing relationships with NPCs
• Back story: motivation to learn what happened before or what is going to happen after the quest is over.
• Lore: themes and ideas encoded within the world, such as religion, politics, landscape, objects, or challenges. "The world itself is the puzzle", and the player shows his opinions by playing the game.

Symbols should be tied to game mechanics. For example, in Ultima, completing a quest requires understanding the world's allegorical meanings: some colors are associated to a class and a quality (red = warrior = valor). Obtaining a part of a relic should open a door or provide a new power

In the end, the player may quest to make the plot progress, improve his avatar, or to try out fun gameplay. Ideally, a quest should combine the three, but it gets tricky in games where the player is allowed to pursue quests in the order he wants.

Spaces

Both macro and micro levels should guide the player towards the general direction to go to. Both should create a sense of progression and convey a meaning by their layout.

Micro level: balancing exploration and challenge. Tiered spaces such as towers or crypts are easy to navigate: traveling towards the highest or lowest level ensures challenges and rewards. Mazes with a sort of structure also work. There should also be disorientation elements such as traps, secret doors, or dead-ends, as well as obstacles standing between the player and his goal.

Macro level: quest hubs. Hubs are known and relatively safe places such as cities or campgrounds where the player is given quests and has to return to complete them. Hubs are surrounded by several quest locations. WoW has breadcrumb quests to encourage exploration, but no main quest; that makes the world seem disconnected and episodic. See the Morrowind map: the player starts on the periphery of the world, and travels clockwise from hub to hub until Ghostgate at the center of the map for the final encounter.

Dreams within games create initiatory spaces: the avatar can be changed into an animal, a ghost, or an older self, but remains controlled by the player, increasing the sense of immersion in the non-dream game world.

Characters

Cf Propp's dramatis personae at the beginning of theater scripts: characters are not defined by their traits, but by their actions: villain, donor, helper, or hero.

Dialog: keep it short, and let players have choices. yes/no selections are too simple: add a reason to add meaning. Example: NPC says "Take this money as a reward to save my kids". Player should not simply be given "OK", or "accept"/"refuse", but rather "I don't need money to save kids" (which shifts the player's alignment to lawful good) or "You don't have to give me the money - I'm going to kill you myself" (evil, and eventually summons the guards).

One quest per NPC is rare in modern RPGs.

Quest types

Name	Description
fetch	find an object and return it to an NPC
delivery	give an object to an NPC
dungeon crawl	go to certain points of a dungeon - and get loot on the way
escort/protect	usually an NPC, but could be a fellow player too
kill/combat	the most loaded with meaning: killing a peasant is very different from killing a demon. Opponents have to be obstacles to the plot

Objects

Most objects that the player collects are useless (sold to NPCs for money) or functional (healing potion, armor). But certain objects can motivate quests if they are:

• needed but missing,
• loaded with symbols,
• relatively powerful,
• fun to use (eg cast a random skill),
• with a distinct appearance (eg the Tatoos of Planescape Torment)

Sometimes, these objects only are MacGuffins: they are unimportant in themselves but motivate and unfold the plot.

The rod of seven parts: make a story from the whole and powerful artifact, break it apart, and spread the pieces around the world. The story follows naturally, and the players discover the meaning of the quest gradually. It also encourages exploration. Micro-level example: the 3-headed flail from the De'Arnise Hold in Baldur's Gate 2 requires the player to fully investigate the whole castle, and not just go directly to the boss.

There are varieties of ways the player can get an object: looted, forged, stolen, summoned by a sacrifice, or found in a chest at the bottom of a cave. But the way the player gets in possession of an object should give clues about using that object. Examples: a mace loot from a giant should require lots of strength. Frostmourne, given by the Lich King to trick Arthas the paladin, is obviously cursed.

Challenges

Tie the quest presentation to the world map and the log book. The logs of completed quests must give clues about the next quests or where to find them.

Conflicting goals make interesting choices. For example, in Ultima IV, the avatar gains compassion points by not killing 'good' characters, and gain valor points by never backing down from a fight. Interesting choice arises when the player is attacked by a 'good' character. [But what the player chooses (ie the player's opinion) differs from why he was given the choice in the first place (ie the meaning of the game).]

See also: hero's journey.