Network Algorithmics by Varghese

I skimmed Network Algorithmics by George Varghese (2005). This book presents common tricks used at the OS, hardware, and architecture levels to prevent network bottlenecks. Here are 15 principles listed on the first page.

Number	Principle	Example
1	Avoid obvious waste	Zero-copy interfaces
2	Shift computation in time
2a	Precompute	Application device channels
2b	Evaluate lazily	Copy-on-write
2c	Share expenses, batch	Integrated layer processing
3	Relax system requirements
3a	Trade certainty for time	Stochastic fair queuing
3b	Trade accuracy for time	Switch load balancing
3c	Shift computation in space	IPv6 fragmentation
4	Leverage off system components
4a	Exploit locality	Locality-driven receiver
4b	Trade memory for speed	Processing, Lulea IP lookups
4c	Exploit existing hardware	Fast TCP checksum
5	Add hardware
5a	Use memory interleaving and pipelining	Pipelined IP lookups
5b	Use wide word parallelism	Shared memory switches
5c	Combine DRAM and SRAM effectively	Maintaining counters
6	Create efficient specialized routines	UDP checksums
7	Avoid unnecessary generality	Fbufs
8	Do not be tied to reference implementation	Upcalls
9	Pass hints in layer interfaces	Packet filters
10	Pass hints in protocol headers	Tag switching
11	Optimize the expected case	Header prediction
11a	Use caches	Fbufs
12	Add state for speed	Active virtual circuit list
12a	Compute incrementally	Recomputing CRCs
13	Optimize degrees of freedom	IP trie lookups
14	Use bucket sorting, bitmaps	Timing wheels
15	Create efficient data structures	Level-4 switching

Diablo 3 - item sets

Modern item games like Diablo 3 (D3) use a mechanic called sets: when used together, certain items unlock particular bonuses. For example in D3, Litany of the Undaunted increases attack speed, The Wailing Host increases crit chance, and used together they give 15% extra gold from monsters. Item sets is an old mechanic - the Diablo 2 expansion already had some in 2001.

Sets in D3 are a great mechanic for at least two reasons. First, sets let developers encourage the use of certain skills. Since the bonuses from set items nearly always provide more damage than regular non-set items, players use them. For example, the Marauder set for Demon Hunters requires the use of sentries, a skill that would not be used otherwise because its AI for picking a target is unpredictable. Second, set items are a great mechanic also because they give players a goal. When I dropped my first set item and saw the set bonuses, I immediately wanted other items in the set.

Sudden increase in power

End-game starts after reaching level 70. Reaching level 70 by yourself takes roughly 15 hours. Difficulty from then on can be measured by the Greater Rift (GR) level your character can reach. Set bonuses are so powerful that they make your character jump multiple GR levels at once. For example, going from 5 set items to 6 can double your character's effective damage or toughness, and make you reach 5 or 6 GR levels higher. This explains why the Ring of Royal Grandeur, which reduces the number of items needed for set bonuses by 1, pretty much a wild-card for all your sets, is such a game-changer. These sudden increases in power sometimes surprise players, but I think each bump makes them suddenly feel very powerful. Interestingly, back in 2013, sets used to be as good as non-set legendary items.

Vague descriptions or hidden mechanics?

The descriptions of D3 set bonuses are often vague, and require the player to check the forums and Youtube videos for details. Here are two examples.

Marauder set

This is a Demon Hunter set. The 2-piece bonus is straightforward: it gives 500 dexterity (on top of the approximately 500 dexterity already contributed by each set piece).

The 4-piece bonus makes the Companion skill call all possible companions (instead of only one). Do passive effects from the Companion skill (e.g. the boar increases life regeneration) apply as well? And do all active effects trigger when I use the skill? The answers are not written in the description, but people figure it out quickly by trying.

The 6-piece bonus reads: Sentries cast your equipped Hatred spenders. After trying it out, I realized that sentries have a different rate of fire for each spender: Cluster Arrow (massive area damage) seems to happen only every 5 shots, whereas Elemental Arrow (small multi-target damage) the rest of the time. Looking at high-level Demon Hunters, most wear Tasker and Theo, which increases the attack speed of your pets by 40-50%. Are sentries pets? (Yes!) And how can I make my sentries use Cluster Arrow more often? (You can't!) Theorycrafters figured it all out by analyzing game frames one by one and sharing their findings. But is the average player supposed to read the forum to improve their character?

Zunimassa set

This is a Witch Doctor set. The 2-piece bonus gives 250 intelligence and grants 30 Mana per Kill. Is it only when my character performs the killing blow on a monster? Does it also work when it's one of my pets? Does it also work when it's another player?

The 4-piece bonus reads: Your Fetish Army (FA) lasts until they die. This is straightforward, and it made me think about the passive skill Fetish Sycophants (FS). FS seems to combo well with FA: When you hit enemies with your spells, you have up to a 10% chance to summon a dagger-wielding Fetish to fight by your side for 60 seconds. There are several problems with this apparent FA-FS synergy.

First, why the up to? What makes the rate be less than 10%? That is where theorycraft comes to the rescue. The community found out that one can have at most 15 active FS at the same time. So the rate of FS trigger is 10% until 15, at which point it becomes 0%. The description of FS should also mention this cap of 15.

A second problem is the easy confusion between the two types of fetishes. 1) Witch Doctors can have many pets: a Gargantuan, zombie dogs, FA fetishes, FS fetishes, and mimics. FA and FS are both fetishes, so intuitively, they must benefit from the same bonuses. 2) Why excluding FS from the 4-piece bonus when the effect from the Carnevil helm applies to both FA and FS? 3) The distinction between FA and FS is not for game balance: in practice, it's very easy to maintain 15 FS active all the time by speeding through monsters.

Why so vague?

I can see several reasons:

• Practicality: the developers want to be able to modify the bonus (through hotfix or patch) without modifying the description.
• Brevity: a precise description may require too much space in the item tooltip.
• Practice: figuring it out by trial is more visceral than by just reading the description.
• Theorycraft: explaining everything spoils the fun of theorycrafters.

Uselessness, sub-optimality, and combinatorics

Some sets are clearly underpowered compared to others. The Witch Doctor Invoker set and the Demon Hunter Shadow set are only useful when your character gets hit. Sadly, in D3, the best defense is offense: the goal is to kill monsters quickly enough that they don't kill you. Therefore these sets end up never being used (except the 2-piece Shadow set in hardcore mode, maybe?).

The Natalya set is not useless, but rather suboptimal. Both the 2-piece and 3-piece bonuses increase damage slightly and enhance mobility (more discipline means more Vaulting). The 4-piece bonus reduces the cooldown of Rain of Vengeance by 2 seconds for each enemy you kill. RoV has a base cooldown of 30 seconds, and does 1000% area damage for 5 seconds, so the set seems very interesting. In practice however, it is difficult to keep monsters grouped in an area for 5 seconds. So while some players use the 2- and 3-piece bonus, nobody cares about the 4-piece bonus. I wonder if the set would be more used if the cooldown was reduced by 2 seconds for every enemy hit (instead of killed).

ArcheAge boasts 120 classes, but it's only because players can pick 3 skill trees among 10, ie C(10,3) = 120 different combinations of skill trees. I don't think that all combinations are efficient, but ArcheAge achieves such diversity simply by leveraging combinatorics on 10 coherent sets of skills. In D3, a player using a Demon Hunter can pick 6 active skills among 24, so that's a total of C(24,6) = 134k different builds. Add to this that each active skill has 4-5 runes, and that there are also another 4 passive skills (5 if we count the Hellfire Amulet) to pick among 18. That's billions of combinations! Yet the only sustainable Demon Hunter builds actually played are minor variations around the same 6 skills. That is because the Marauder set forces players to pick these skills. Moreover, I really liked combining multiple 3- and 4-piece sets together, but the 6-piece Marauder took all the spots. I wish D3 had 1) more 4-piece sets and fewer 6-piece sets, and 2) combinations between sets, not just between sets and legendary items (e.g. Marauder and Tasker and Theo)

Diablo 3 - the item game

In item games, the main goal of players is to continuously upgrade their gear. Diablo 3 (D3) is the perfect example: kill monsters in order to drop better gear in order to kill monsters faster. Bungie just released Destiny, an item-game FPS budgeted with half a billion dollars. Yet Destiny could learn from Diablo 3. So here are some thoughts about the item game in D3.

Prevent farming ...

In D3, like in D2, the drops are completely random: with a few exceptions, nearly any item can drop from any monster or wreckable object (e.g. jars). The odds are just higher for harder monsters, and way lower for wreckable objects. The exact drop rates are secret (except the 10% legendary drop rate from Kadala). This secrecy has led to various rumors and tinfoil hat theories about how loot can be influenced.

D3 has, or used to have, farming spots such as the Decaying Crypt, but they were mostly for XP, not for drops. In D3, farming boss monsters actually brings fewer drops than farming normal or elite monsters. This contrasts with Diablo 2, where players were grinding bosses like Baal or Diablo for XP and loot. So in a way, the grind in D3 is less boring than in D2.

... Yet allow farming

As of October 2014, there are 2 exceptions to what I just wrote: 1) bounty rewards like RoRG or Helltrapper, and 2) Hellfire Amulet.

The RoRG was introduced in February 2014. It is a mandatory item to reach the game's highest difficulty levels. Players have to camp Act-1 bounties to get one with good rolls. To farm as quickly as possible, players join co-op games to split farm: instead of spending 15-20 minutes completing the 5 bounties together, they each complete a bounty in 5 minutes. I am surprised that the developers did not see it coming: split farming is very clearly not how we want players to play the game. Yet nearly a year later, they still have not changed the bounty system.

The Hellfire Amulet is not as mandatory compared to the RoRG. But its bonus is so useful that all of the top players have it. Farming it is somewhat more fun than farming for RoRG, since it is a quest in itself: a) hunt for the 4 Keywardens on the game's largest maps to obtain 4 keys, b) combine the 4 different keys into a portal, c) kill 2 super bosses at once, a somewhat more difficult task than the Keywarden hunt, and d) combine 4 super bosses' loots to obtain a Hellfire Amulet.

The Reaper of Souls expansion

From launch in May 2012 until the retirement of the Auction House (AH) in February 2014, players were mostly buying their gear from the AH, and sometimes grind-crafting it. They nearly never dropped it themselves. Legendary weapons had 7-8 affixes. After the AH retired, Loot 2.0 arrived, and the expansion Reaper of Souls (RoS) shortly after that. Legendary weapons now have 4 primary and 2 secondary affixes. Secondary affixes do not matter much (e.g. more XP when killing a monster), so RoS drastically reduced the item entropy.

The expansion also reminded me of Blizzard's somewhat elegant solution to a common MMO problem. Most MMOs in the early 2000s had the same problem: players who have been playing for a year have too much of a head start compared to players who have been playing for 3 months. New players are hopeless, especially in PvP situations. World of Warcraft solved this problem with what I call expansion gating: WoW vanilla capped the character level at 60 and item level at 92. Until the first expansion came out to increase these two caps, players were gated there. The advantage of expansion gating is that it gives the same chance to old and new players. The main drawback (if any) is mudflation. Diablo 3 is no different: level-70 items have twice more DPS than level-60 items. Thus when the expansion launched, players threw away all the gear they had acquired before.

Few links to other end-game activities

Item games have a great loop, but it is not enough in itself. D3 launched in May 2012. The Auction House (AH) launched in May 2012 too, so players could play two games in one: the action RPG and the auction game. Note that you did not need to play the aRPG to play the auction game, but you did need to buy gear off the AH to play the aRPG well. Had it been the opposite, I think the game would have been much better.

In July 2012, the developers realized that the item hunt is just not enough for a long-term sustainable end-game. Since launch, the game also allowed players to hunt for achievements and start new characters (in softcore or hardcore). In August 2012, the developers added the leveling up grind through 100 Paragon levels. Every Paragon level increased the chance to drop an item and the amount of gold dropped by 3%. In February 2014, Paragon levels became infinite, and the 3% bonus was removed. Clans and communities were also added in February 2014. Since August 2014, players can compete on the greater rift leaderboards, and start new seasonal characters (in softcore or hardcore). Interestingly, the item game is completely independent of all other end-game activities (except the AH and the original 100 Paragon levels increasing magic find and gold find). In other words, the item game of Reaper of Souls could be directly copied into another game without having to also copy the other activities.

Ken Lobb FDG 2014 keynote

Ken Lobb designed Golden Eye and Killer Instinct in the 90s. Here are notes from a keynote he gave at the FDG 2014 conference.

Having an extensive knowledge of games is mandatory for game designers, because they provide a common vocabulary to talk about games.

In the late 80s, teams rolled their own tools. Nowadays, AAA teams still have the not created here problem and waste a lot of time reinventing the wheel. That's why indies using Unity or Unreal can save on costs and take a bite at AAA.

The most important tool in game development is the game build, because it is how the game improves, little by little. Next comes the schedule, ie what to do next. Finally comes the spec and docs, because they change all the time. Microsoft has the process mastered. In fact, Microsoft is too good at planning: they always ship what they speced, and not exactly what they should create. The industry in general, and Microsoft in particular, sign games that cost way too much money.

Difficulty: games have shifted from lose vs win, to win vs big win vs epic win. now in call of duty, high kd ratio is winning. dying is not too bad. before in golden eye, die means restart whole 10min level. now, focus on positive reinforcement rather than punishment.

Major game design issues:

• Tutorials are hard to build right. Should players be reminded of mechanics they may already know, or should they instead be taught from scratch? The Zelda series have great tutorial design: they simply give the player the tool, and teach by giving more and more difficult challenges that require using that tool. Achievements can also encourage a particular behavior.
• Cheating is OK. 90% of Xbox players are also on a second device when they play. Players use Youtube, watch Twitch, and look for cheats and FAQs all the time. Procedurally-generated or randomized content can curb this practice down, but a real solution may involve the game itself showing tips or videos from the players who passed an obstacle to those who are stuck.
• Making a game noticed on app stores/platforms is difficult. Advertising and charts do not target particular players. Word of mouth is more effective, but how does it start? Maybe app stores could recommend games to hardcore players, which would trickle them down to their friends? [This may have an answer: according to Wooga, it takes $250k to reach the first spot on the App Store]

Diablo 3 - Randomized content

A lot of game content in Diablo 3 is determined randomly. Arguably, more randomness means more diverse content and therefore players less likely to become bored by repetition. But randomness also has drawbacks.

Maps

Maps are generated somewhat procedurally. Some elements like the map borders remain constant, but events and dungeon entrances are picked randomly among a pool and placed randomly in predetermined places.

Maps like The Den of the Fallen sometimes have loops, which is annoying: players kill monsters on their way, but when they realize they have been looping around, they go back on their way without any monsters to kill. It is a waste of time. A solution could involve using heuristics to prevent loops.

A Greater Rift (GR) is a dungeon in which players race against time. The higher the level of a GR, the tougher its monsters. GR is a competitive activity: leaderboards show the teams who achieved the highest GR levels. Problem: the GR map is picked randomly; sometimes it is a maze, sometimes it is linear, and sometimes it has loops. The randomness does not make for a fair competition. One solution would be to remove maze maps from the selection. Another solution would involve keeping the map and monsters constant, and make one leaderboard per map. It would be pretty much like a racing game.

Elite affixes

Elite monsters can have up to 5 affixes. Affixes have 3 categories: crowd-control such as Vortex, defensive such as Extra health, or offensive such as Desecrator. These affixes are picked randomly, with a couple heuristics making sure that an elite can have at most one crowd-control affix and at most one defensive affix. Some affixes such as Invulnerable Minions were so annoying that they were removed from the game altogether.

Still, some combinations remain more deadly than others. For example, elites combining Molten (they burn where they walk on), Fast, and Horde (create 8-10 Molten and Fast minions) are the bane of melee characters.

Gear

In the original Diablo 3 (also known as D3v for Diablo 3 vanilla), loots were completely random. For example, a Wizard could drop a mace only Barbarians can use. Enters the Auction House (AH for short): the Wizard sells the mace on the AH and, with the money received for it, buys a better wand from the AH. Trading through the AH worked well from launch in May 2012 until August 2012 when the designers realized that the AH can short circuit the natural pace of item drops, making the game feel less rewarding for some players. Indeed, players could obtain second-best gear in only a couple days, play for a week, get bored for not progressing, and leave the game. Conclusion: completely-random loot with an AH for trading does not work.

Loot 2.0 landed in the game just before the Reaper of Souls expansion. Loot 2.0 has 3 parts: 1) little to no exchange between players (to prevent gold farming), and no AH, 2) loot is targeted to the player, ie Wizards only drop Wizard gear, and 3) the Mystic lets the player reroll an attribute on any piece of gear. Six months after the release of the expansion, this has been holding fine.