mildbyte's notes tagged 'python'

Travelling murderer problem: planning a Morrowind all-faction speedrun with simulated annealing, part 3

@mildbyte 5 years, 1 month ago | programming | games | morrowind | python |

Introduction

Last time, I showed a way to generate a decent route through the quest graph as well as came up with a rough character progression that can be used to quickly complete all faction questlines in Morrowind.

Today, I'll analyse Mark/Recall and other miscellaneous transport modes, deal with an interesting Temple quest, showcase the final route and finally publish the code for the route planner.

Here's a map of the route for those of you who like migraines:

The points of interest here are joined with colour-coded lines. White is walking or flying, red is Mages Guild teleports, blue is Almsivi/Divine Intervention spells, yellow is travel by boat/silt strider and green is Recalls.

Total Recall

Mark/Recall are a pair of spells in Morrowind that allow the player to teleport around the game world. Casting Mark remembers a given place and Recall teleports the player to the last position the Mark was cast. Only one Mark can be active at a given time: casting it again removes the previous Mark.

Imagine casting Mark at the beginning of a dungeon (unlike Skyrim, Morrowind dungeons don't have a quick shortcut back to the start of the dungeon from its end) and teleporting there, or placing a Mark next to an NPC providing transport services. This could shave a considerable amount of time from the route.

There are several questions here. Firstly, given a route, what's the most efficient arrangement of Mark and Recall casts for it? Secondly, can we change the optimiser to take into account the Mark/Recall spells? The most optimal route through the quest graph might not be the most optimal when Mark/Recall spells are used.

Single Mark

For now, imagine we have already settled on a route and can only place a Mark once in the game, in fact only at one node in the quest graph (and not anywhere on the route between nodes). What's the best place for it?

Since we have a matrix of fastest node-to-node travel times, given a Mark position, at each node in the route we can decide whether we want to proceed to the next node directly or by first teleporting to the Mark and then going to the next node. Try placing a Mark at each the nodes in the route and see which one gives the fastest overall time:

def get_best_mark_position(route):
    return min(
        # can't use the mark until we've placed it
        (sum(get_node_distance(r1, r2) for r1, r2 in zip(route[:i], route[1:i]))
         + sum(
            # after placing the mark, we have a choice of recalling to it and going to the next node
            # or going to the next node directly
            min(get_node_distance(r, r2), get_node_distance(r1, r2)) for r1, r2 in zip(route[i:], route[i + 1:])),
         i, r) for i, r in enumerate(route)
    )

I ran that and found out that by far the best position for a single Mark was right at the questgiver who's standing next to the Mages Guild teleport. This makes a lot of sense: a Recall to the Mages Guild gives the player instant access to 4 cities. Coupled with Intervention spells, this lets the player reach essentially any town in the game within a matter of minutes, if not seconds.

Multiple Marks

Now, again, given a single route through the quests, let's allow the player to place multiple Marks so that they can Recall to the last one they placed.

I first tried the same idea that I did for the route optimiser: take multiple possible arrangements of Marks (basically a Boolean array of the same length as the route that determines whether, at each node, we place a Mark there or not after we visit it), mutate each one (by randomly adding or removing Marks) and score it (sum up the decreased travel costs by considering at each node whether it's better to proceed to the next node directly or via a previous Mark).

I let this run for a while but it wasn't giving good results, quickly getting stuck in local minima. A big problem with this approach was that it didn't consider placing Marks in places visited between nodes, which excluded strategies like placing a Mark at the beginning of a dungeon (while a door to the dungeon is a point in the travel graph, it isn't a point in the quest graph).

To do that, I'd have to have a matrix of best travel times between each pair of nodes in the travel graph, not just the quest graph. Given how long my implementation of Dijkstra took to create the matrix for 100 nodes, I wasn't going to get away with reusing it.

Speeding things up

Floyd-Warshall is the nuclear option of pathfinding algorithms. Instead of finding shortest paths from a single source like Dijkstra would, it finds the shortest paths between any two vertices in the graph. Not only that, but it does in \( \Theta(V^3) \), independently of the number of edges, making it perfect for dense graphs.

It took about 15 minutes to run my Python implementation of Floyd-Warshall on the coalesced 700-node graph. But this wasn't enough. I realised that coalescing vertices in the same in-game cell to a single one was giving strange results, too: for example, each node had an Almsivi/Divine Intervention edge towards the nearest Temple/Imperial Cult Shrine that has a weight considerably larger than zero (due to the fact that the central vertex for that cell was far away from the actual teleportation destination) and I was wondering if that could be skewing the route.

I hence decided to rerun the route planner on the full unprocessed 6500-node graph and rewrote the Floyd-Warshall implementation in C++. It still took 15 minutes to run it, but this time it was on the whole graph. Most of this time, in fact, was spent loading the input and writing the output matrices, since I serialised those into text and not binary.

And by that point I was on a roll anyway and rewrote the route planner in C++ as well. The Python program would now instead export the quest node distance matrix and the dependency graph to a text file. I didn't perform detailed measurements, but it definitely became a couple of orders of magnitude faster.

Adding Mark/Recall awareness to the optimizer

I tried rerunning the Mark/Recall planner on the fully expanded route (which enumerates each vertex on the travel graph) but by this point, it was getting more and more clear that simply maintaining a Mark at any Mages Guild teleporter was a really good option that was difficult to improve on.

This is a slightly trippy picture, but it's basically a contour plot that shows the average travel time (in real seconds, assuming a travel speed of about 750 units per second, which is achievable with an artifact that I'll talk about later) to any node in the quest graph from any point in the travel graph, interpolated using nearest-neighbour on pixels that didn't map to any points on the travel graph. I also added a travel cost of 5 seconds to public transport and Mages Guild teleporters. This was to account for the time spent in the game's UI as well as to nudge the optimiser into flailing less around multiple towns.

Strictly speaking, I should have actually calculated the average time at each pixel, but this picture is good enough. The colour map here ranges from blue (smallest average travel time) to green (largest). For example, Vivec (south of the game map) has the largest average travel times to any point of interest in the route. This is because the Temple of Vivec (one possible destination of an Almsivi Intervention spell) is on the other side of the city from other transport modes (boats/silt striders/Mages Guild) and so anyone near Vivec would have to first teleport to the Temple and then walk across the city to continue their journey.

On the other hand, despite being basically a wasteland, the southeast corner of the map has good travel connections: this is because a Divine Intervention spell takes the player to Wolverine Hall on the east side, right next door to the Mages Guild.

Silent Pilgrimage

There's a cool quest in Morrowind's Temple questline that involves the player completing a pilgrimage from the southernmost part of the game map to the northernmost. Sounds easy, right? Well, the only problem is that the player can't speak to anyone during the pilgrimage, which means the player can't use any public transport or Mages Guild teleports.

The honest way to do this is to actually walk or levitate the whole distance, which would take a few minutes even with Speed-increasing spells. The mostly-honest way to do this would be casting Divine/Almsivi Intervention spells in strategic places that would teleport the player part of the way between the spheres of influence of different Temples/Imperial Cult shrines. The dishonest way would be casting a Mark at the shrine during a previous visit and simply Recalling there when the pilgrimage starts.

However, the first version of the route planner wasn't really aware of that quest. I had a "Set Mark at Sanctus Shrine" graph node and a "Do the Sanctus Shrine quest" node, but the optimiser wasn't encouraged to put them close together. In the best route it had come up with, those two nodes were far apart and about 3/4 of the route was with the Mark stuck at the Shrine.

Hence, if we want to maintain a Mark at a Mages Guild, we also have to juggle that with having a Mark at the Sanctus Shrine in order to complete the Silent Pilgrimage. So the question now was kind of an inverse one: given that we can teleport to a Guild at any time (except for when the Mark is at the Shrine and so we'd get teleported there instead), what's the best route through the game quests?

I decided to produce two travel graphs: when there's a recall edge to a Mages Guild (it doesn't matter which one, since we can almost instantaneously teleport to any of them once we're there) and when there's a recall edge to the Sanctus Shrine.

The optimiser would get these two versions of the node-to-node distance matrix as well as the instructions specifying which matrix to use when. That way, it could also try to exploit the Mark in the northern part of the game map.

The best route it could come up with (not counting time spent in dialogue, combat, training or getting all required items/money at the start at the game) now took about 2500 seconds of real time, which looked quite promising.

Propylon Chambers

There's a mode of transport in Morrowind that I hadn't mentioned at all: Propylon Chambers. They're located inside 10 ancient Dark Elf strongholds that are scattered roughly in a circle around the map. Each stronghold has a Propylon Index that's hidden somewhere in the game world, and discovering a given stronghold's Index allows the player to travel to that stronghold from either of the two adjacent to it.

(from http://stuporstar.sarahdimento.com/other-mods/books-of-vvardenfell/key-to-the-dunmer-strongholds/)

Can they be useful here? After looking at their placement, it sadly doesn't seem so. Firstly, there are very few strongholds that are closer to quest objectives than ordinary towns and secondly, their Indices are often in inconvenient places (for example, the Rotheran Index is located in Rotheran itself).

But perhaps it's worth including Propylon Chambers in the route anyway? To test that, I assumed that the player has all Propylon indices from the beginning and regenerated the travel graph with the addition of teleportation between adjacent Dunmer strongholds. This would provide a lower bound on the route length and show whether there is enough time saving to make getting any of the Indices worthwhile.

Turns out, there really isn't. The best route without Propylon Chambers takes about 2500 seconds, whereas including them improves the route by only two minutes. There are a few places the optimiser decided to exploit this method of teleportation:

• When performing quests around Suran, going to Marandus and teleporting to Berandas in order to get the Boots of the Apostle in that stronghold.
• Then teleporting from Berandas to Falensarano on the eastern part of the game map to get Ring of the Wind from the cave nearby as well as (later on) deliver an item to a mine.
• Teleporting to Valenvaryon several times for easier access to the island north of the map.
• Teleporting from Hlormaren (a stronghold west of Balmora) to Falasmaryon where the Marksman master trainer lives.
• Teleporting from Berandas to Rotheran close to the end of the route to grab the Ice Blade of the Monarch (located in that stronghold).

Given that simulating actually getting the Indices would also be a pain (I'd have to keep track of the optimal travel time between any two quest nodes for when the player has any combination of indices out of \( 2^{10} = 1024 \)), I decided to skip them for now.

Opening gambit and various exploits

There are a few things that are worth doing at the beginning of the game to ensure a smooth progression through the route as well as raise enough money to pay our way through training and some faction quests.

I'd use enchantments for most of the in-game activities, including dealing damage, teleporting and movement. Enchantments are spells that can be put on equipment. They require a soul gem to produce, which determines how much charge the item will have, but enchanted items recharge over time, don't use up player's Magicka reserves and spells cast from them can't fail and are instantaneous. This means that teleporting takes a few seconds faster since we don't need to wait for the cast animation, but more importantly, casts can't be interrupted by someone hitting the player.

The items enchanted with all three types of teleportation (Divine/Almsivi intervention and Recall) are easily obtained at the beginning of the game: the first two during Edwinna Elbert's initial questline and the final one can be bought from a merchant in Caldera. I hence changed the optimiser a bit to always have these two starting nodes (Ajira and Edwinna's Mages Guild quests) at the beginning of the route and would do some more preparation as part of these before proceeding.

Dealing damage

I had played around with various ways of dealing damage to NPCs. I first thought of using Blunt weapons, since the player would have to train that skill anyway and one of the best Blunt weapons has to be acquired as a part of an Imperial Cult quest, but it still takes several swings to kill anyone with it, since the player can miss, especially at lower skill levels.

Then I remembered about the Drain Health enchantment: it reduces the target's maximum health by a given number of points. It's supposed to be used as a cheap way to weaken the enemy, but it can also be exploited. If one casts Drain Health 100pt on someone, even for one second, they will die if they have fewer than 100 hit points. Paired with a 100-point Weakness to Magicka effect, this allows for a cheap way to kill anybody with fewer than 200 hit points, which is an overwhelming majority of game characters.

Movement

Despite all the teleportation, there still is a lot of walking to be done in the game. While the character will have access to Fortify Speed potions, I only wanted to use them for long movement segments, since making enough of them to cover the whole route would take too much time.

Thankfully, there is an artifact in the game that gives the player a constant Fortify Speed effect: Boots of Blinding Speed. They boost the player's speed by 200 points (essentially tripling it) at the expense of blinding (it's in the name) the player. The blinding effect can be resisted: if the player has a Resist Magicka spell active for the split second when they put the boots on, the effect is nullified.

Moreover, levitation is important, since it allows the player to bypass various obstacles as well as avoid annoying enemies. Due to the way levitation speed is calculated (the main component is the sum of player's Speed and the levitation effect magnitude), 1 point of Levitation is sufficient for the player to start flying and it's cheaper to increase speed by manipulating the character's Speed attribute. 1 point of Levitation for about 90 seconds would be another enchantment.

Unlock, frenzy

Chests and doors in Morrowind can have a lock with a level ranging from 1 to 100. Hence, we'd need to also enchant a piece of clothing with Open 100pt.

There are quite a few times in the route where we need to kill someone who's not attacking us without attracting the guards' attention (like when doing Morag Tong assassinations before the actual quest starts). One way to do it is taunting the NPC until they attack, which takes time and needs a moderately high Speechcraft skill. Luckily, there's a magic effect for that, too. Frenzy increases the Fight rating of an NPC and 100pt for 1 second is enough to make them attack the player. When the effect wears off, they don't stop attacking and can be slain in self defence without legal issues.

Alchemy feedback loop and fundraising

When a player creates a potion in Morrowind, their chance of success as well as the potion's strength, duration and value is partially governed by the player's Intelligence attribute.

The player can also create a potion that boosts their Intelligence attribute.

Do you see how the game can be broken with this? There's no limit on how many potions the player can consume per second and there's no cap on the player's Intelligence. Hence we can have all our monetary problems taken care of by exploiting this and repeatedly creating stronger and stronger Intelligence potions to sell. Not only that, but we can also use this to create Restore Health potions that restore player's health faster than anybody can damage it as well as use the Intelligence boost to create enchanted items manually (instead of paying a specialist to do it). Finally, we can also create Fortify Speed potions that increase the player's raw speed.

There are merchants in Morrowind that restock some of their ingredients as soon as the player stops trading with them and lots of them sell ingredients for Fortify Intelligence and Restore Health potions.

We need about 75000 gold pieces to get through the game, including all training and faction quests. Luckily, there's a merchant in the game that has 5000 gold in his inventory and buys items at face value. My tests showed I needed about 150 Health potions to get me through the game, so I'd sell any extra ones to the Creeper to get me to the target number.

Fortifying player's Speed (beyond the boost provided by the Boots) is more difficult: there are only two ingredients in the game that restock and provide the Fortify Speed attribute, Kagouti Hide and Shalk Resin. However, they are quite expensive (52 gold pieces in total for the two) and also have a Drain Fatigue side effect (which makes the player lose consciousness when their Fatigue is close to zero). Hence they have to be paired with another two ingredients that have a Restore Fatigue effect.

Final route

Here's the final route that I came up with: it opens with the sequence of money-making and enchantments that I had described before and then continues with the list of things to do that was produced by the optimiser. This initial sequence took me about 28 minutes to complete and the rest of the route is located here. I also uploaded the route that assumes the player can use all Propylon Chambers here.

• Create the character (build). Steal the Limeware Platter from the Census & Excise office before leaving and pick up the Ring of Healing from the barrel on the way.
• Give the ring to Fargoth to boost relationship with Arrille. Go there, sell the platter, buy a Resist Magicka Spell, 2 Drathis' Winter Guest scrolls and an Iron Warhammer.
• On the way to the silt strider, grab the 4 types of mushrooms (needed for Ajira's first quest). Take the silt strider to Balmora.
• Join the Mages Guild, take all supplies from the chest and take the Ceramic Bowl from Ranis Athrys' table. Go downstairs to Estirdalin and make a spell of Resist Magicka 100% on Self. Hand in the first Ajira quest. Teleport to Caldera Mages Guild.
• Steal the alchemy set from the tower in the Guild as well as 1 Dreugh Wax (needed for the Seven Graces quest).
• Go north-west towards Gnaar Mok to meet Pemenie. Kill her with a combination of Thunder Fist (Nord racial power), the Drathis' scrolls and the Warhammer.
• Use the Fortify Willpower and Restore Magicka potions from the supplies chest to successfully cast Resist Magicka spell and equip the Boots. Use the Almsivi Intervention scroll to go to Ald-Ruhn.
• Go to the Mages Guild, take all supplies from the chest there.
• Buy 2 Mark scrolls from Tanar Llervi (she sells one at a time but they restock after leaving the Barter menu).
• Take Mages Guild teleport to Balmora, place a Mark while facing Masalinie Merian (Guild teleporter).
• Do all remaining Ajira quests:
  • Make sure to steal the Grand, the Large and the two Common Soul gems as well as the Platter and any other Soul Gem (needed as a donation for a Temple quest) during the second quest.
  • Flowers: Willow Anther and Heather can be bought from Ajira herself. The other two can be stolen from Millie Hastien's shop. On the way there, sell the Platter to Ra'Virr next door.
  • Sell all rewards (potions) back to Ajira to have roughly 1000 gold for the next part.
• Mages Guild teleport to Sadrith Mora, Go to Aunius Autrus in the Imperial Shrine.
• Alchemy loop time!
  • Use all money to continuously buy 10 Ash Yam, 5 Bloat and 5 Netch Leather from Aunius Autrus (should roughly end up with 260, 130 and 130 of each, respectively).
  • Use all Bloat and half of Ash Yams to make Intelligence potions, drink them all.
  • Use all Netch Leather and Ash Yams to make Intelligence potions, sell enough to Aunius to get all his money, drink the rest.
  • Go to Scelian Plebo and buy 10 Saltrice and 10 Marshmerrow 30 times.
  • Make 300 Restore Health potions with these ingredients. Sell enough Health potions to Scelian to get all his money.
• Buy Drain Blood (has the Drain Health effect) and Frenzying Touch (has the Frenzy Humanoid effect) from Uleni Heleran in the Mages Guild on the way back.
• Teleport to Balmora, Almsivi Scroll to the Temple.
• Go to Nalcarya of White Haven. Buy 1 diamond (future Thieves Guild quest) and 4 Daedra Hearts (future Temple quest), sell her enough potions to drain her of money.
• Go to Millie Hastien next door. Buy 1 Exquisite Amulet, 1 Exquisite Ring, 1 Extravagant Pants and an Extravagant Belt.
• Back to Balmora MG, buy spells from Marayn Dren: Levitate, Ondusi's Open Door, Dire Weakness to Magicka.
• Whilst still under the effect of Intelligence potions, make the following enchantments:
  • Exquisite Amulet: Weakness to Magicka 100% on Touch, Drain Health 100% on Touch (use the stolen Grand Soul Gem).
  • Expensive Belt: Levitate 1pt 90s on Self (use the stolen Greater Soul Gem)
  • Exquisite Ring: Open 100pt on Touch (Common Soul Gem)
  • Expensive Pants: Frenzy Humanoid 100pt on Touch (Common Soul Gem)
• Do hotkeying. I prefer having the Amulet on 1, Belt on 7, Ring on 8 and Pants on 9.
• Whilst still under the effect of Intelligence potions, teleport to Sadrith Mora.
• Buy 100 Shalk Resin and 100 Kagouti hide from Pierlette Rostorard (will need to sell her Health potions a couple of times in order to afford the ingredients).
• Buy 100 Hound Meat and 100 Scuttle from Threvul Serethi.
• Make 100 potions of Fortify Speed (+ Restore Fatigue) from these 4 ingredients. Alchemy should be slightly beyond 70 by this point (requirement for some Guild promotions). Hotkey Speed potions to 2.
• Recall and teleport to Caldera. Sell Restore Health potions to Creeper until have about 75000 gold. Hotkey remaining ones to 3.
• Recall, buy 6 Drathis' Winter Guest scrolls from Galbedir and buy Chronicles of Nchuleft from Dorisa Darvel, then steal a Dwemer Tube from Vorar Helas' house.
• Recall, teleport to Ald-Ruhn and do all Edwinna Elbert quests up to and including Dwemer Tube. Should be rewarded with the Almsivi and Divine Intervention amulets. Hotkey those to 4 and 5, respectively.
• Proceed as per the rest of the route.

Finally, there are several NPCs that have to be killed as part of the run and have to be damaged first before they can be killed with the Amulet, either with the Drathis' scrolls or with the Iron Warhammer/Skull Crusher when it's picked up:

• Relas Arothan has one Sanguine Item required for extra Morag Tong reputation.
• Lorbumol gro-Aglakh needs to be killed as part of the Fighters Guild questline. While he has 199 health, he has some natural magic resistance, decreasing the effect of the amulet.
• Burub gra-Bamog also has some natural resistance to Magicka.
• Orvas Dren, brother of the Duke and head of the local criminal syndicate, has to be killed as part of the House Hlaalu questline and has 250 hit points.
• Varus Vantinius is the current head of the Imperial Legion and has to be killed in a duel to finish that faction's questline.

Conclusion

I think that's it! The code to produce most of this is on my GitHub, together with the code from the previous set of articles. One day I might even actually record myself trying to follow this route, but I'm sure actually planning it out is more fun that running it.

Finally, feel free to follow me on Twitter at twitter.com/mildbyte!

Travelling murderer problem: planning a Morrowind all-faction speedrun with simulated annealing, part 2

@mildbyte 5 years, 1 month ago | programming | games | morrowind | python |

Introduction

Previously, we left off by converting the problem of finding a route that completes all faction questlines in Morrowind into the general case of the travelling salesman problem with dependency constraints. Today, we'll come up with a way to produce a good enough solution to it.

Generating a travel time matrix

There are two graphs I'm talking about here: one is the quest dependency graph from the previous part and the other one is the travel graph that I had generated back in an earlier article.

The dependency graph had about 110 geographically distinct nodes at this point, so the first order of business was creating a matrix of fastest routes and travel times between any two of those nodes, since the final route could indeed include travelling between any two points.

To do that, I used Dijkstra's algorithm: since it's an single-source-shortest-path algorithm, if I ran it for one geographical node in the quest dependency graph, I'd get shortest routes (on the travel graph) to all other points. Hence I only had to run it a hundred times.

There was a problem, though: the travel graph had about 6500 vertices and 16000 teleportation edges (that is, travelling with public transport or using an Almsivi/Divine Intervention spell: this doesn't include actual physical travel edges between points in the same cell). It took about 10 minutes to run Dijkstra for a single source, so I was looking at spending about a day generating the travel time matrix.

Hence I decided to prune the travel graph a bit by coalescing vertices that were in the same cell. For every cell (interior or exterior), I'd replace all vertices in it with a single one with average coordinates and then recalculate the cost of travelling between them:

def coalesce_cells(vertices, edges):
    # Replaces all vertices in the graph in the same cell with a single one (average location)
    vertices_map = defaultdict(list)

    for v in vertices:
        vertices_map[v.cell].append(v)

    # Calculate the average vertex for each cell    
    average_vertices = {}
    for cell, vs in vertices_map.items():
        coords = tuple(sum(v.coords[i] for v in vs) / float(len(vs)) for i in range(3))
        average_vertices[cell] = Location(coords=coords, cell_id=vs[0].cell_id, cell=vs[0].cell)

    new_vertices = set([average_vertices[v.cell] for v in vertices])

    # Group edges by average vertices they belong to
    grouped_edges = defaultdict(lambda: defaultdict(list))
    for v1 in edges:
        av1 = average_vertices[v1.cell]
        for v2 in edges[v1]:
            av2 = average_vertices[v2.cell]
            # Calculate the new edge cost
            grouped_edges[av1][av2].append((edges[v1][v2][0], get_distance(av1.coords, v1.coords) / WALKING_SPEED + edges[v1][v2][1] + get_distance(v2.coords, av2.coords) / WALKING_SPEED))

    new_edges = defaultdict(dict)
    for av1 in grouped_edges:
        for av2 in grouped_edges[av1]:
            # Replace all possible edges between the two new vertices with the cheapest one
            new_edges[av1][av2] = min(grouped_edges[av1][av2], key=lambda md: md[1])

    return new_vertices, new_edges

With this pruning, the travel graph shrunk to about 800 vertices and 2200 teleportation edges and I successfully managed to create a matrix of fastest travel times between any two nodes on the dependency graph.

Here's one of cool things you can do with such a distance matrix: use a clustering algorithm to visualize clumps in which quest points of interest are organized (the image is clickable).

For example, the top left corner of this heatmap has a group of NPCs that are all located on a set of remote islands at the north of the game map. Getting to them is a pain and takes a lot of time, hence it's worth arranging our quests in such a way so that we only have to visit there once.

Simulated annealing (genetic algorithm?)

Let's now say we have a candidate route, which is one of topological sorts of the dependency graph. We can see how long this route takes by simply adding up the cost of travel between consecutive nodes using our cost matrix.

How would we find an optimal route? Brute force won't help here. I decided to do a slightly less stupid thing: let's take a route and randomly perturb it. Sure, the route we end up with might be less efficient than it was before. But imagine we do that for tens of thousands of randomly generated routes, keeping a fraction of them that's the most efficient, randomly perturbing the best routes again and again. Eventually we'd converge on a decent route, if not the most optimal one.

The final algorithm I used is:

• Start with a pool of candidate routes: take a single topological sort and repeat it 20000 times
• Do until I get bored and terminate the optimization:
  • sort the routes by their total time, keep top 1000
  • for each remaining route:
    • generate 20 candidate routes from it:
      • pick a random point in the route and move it a random number of steps up or down
      • check the dependency graph is still satisfied, if not, try again
      • do this perturbation 30 times
  • the pool now has 20000 routes again, repeat

Of course, the actual constants can be played with and the termination condition could be better defined. Some call this a genetic algorithm (where we kind of simulate evolution and random mutations in the gene pool), some call it simulated annealing (where the magnitude of random perturbations decreases over time until the solution pool settles down). "Genetic algorithm" sounds sexier, which is why I mentioned it in this paragraph.

I left this to run overnight and in the morning came back what seemed to be a decent route through the game.

The times here were inferred from in-game travel distances, assuming the minimum walking speed of about 100 game units per second. Of course, there are potions and spells to increase the player's walking speed. In addition, this doesn't account for the time spent in the menus or actually killing whatever the player is supposed to kill.

Overall, there are some things the optimiser came up with that made me go "aha!".

I wrote a pretty printer that would take the graph nodes and expand them into an actual travel plan that uses Almsivi/Divine Intervention spells and public transport. In this fragment, for example, the route planner set up the faction questline progress just right so that all six objectives in the desolate southwest corner of the map could be completed in one go (lines 592-618).

However, there are a few problems with this route:

• It doesn't account for the uses of Mark/Recall spells. These are immensely powerful: a Recall teleports the player to the location of the last time a Mark spell was cast.
• It doesn't account for skills training in order to progress through faction quests.

Skills training

Advancement in Morrowind factions requires not only quest completion, but also skills training. I had already mentioned that while we can pay to train a skill, it can't be trained above its governing attribute.

Attributes can only be raised when the player levels up. A game character has 5 out of 27 skills as major skills (which lets them level faster and gives a flat +25 bonus to them at the beginning of the game) and 5 minor skills (which also lets them level faster, albeit not as fast as major skills, and adds a +10 bonus). The character levels up when they have gotten 10 points in their major or minor skills.

This is where it gets weird. At level up, the player picks 3 attributes to raise. How much they are raised by is determined by the skills the player had trained. For example, if they got 10 points in Alchemy (governed by Intelligence), then, if Intelligence is picked at level up, it will increase by 5 points instead of 1. However, if the player had leveled up by training 1 point in Long Blade (governed by Strength) and 9 points in Alchemy, they'll only get a 4x multiplier to Intelligence and 1x to Strength.

The player can also train skills that aren't major or minor to get enough points to boost the attribute multiplier. Let's say the player also trains 1 point in Security (governed by Intelligence) which isn't their major or minor skill. It won't count towards the 10 points required for a level up, but it will count towards the attribute multiplier calculations. Hence the player will be able to raise their Intelligence by 5.

I hence had to tactically choose my character's major/minor skills as well as the race (which gives bonuses to certain skills and attributes) in order to be able to quickly meet each faction's expectations.

Overview of factions and required skill levels

This is a list of skill levels that each faction requires in order for the player to be able to become the head of that faction. Note that this might not necessarily meet the skill requirements for the highest rank of that faction, since most factions stop checking the player's credentials during their final questlines and just promote the player to the highest rank once the questline is completed.

• Mages Guild: Alteration, Destruction, Alchemy, Enchant, Illusion, Mysticism. One skill at 70, two at 25, Intelligence and Willpower 33.
• Fighters Guild: Axe, Long Blade, Blunt Weapon, Heavy Armor, Armorer, Block; 70/25/25, Strength and Endurance 33.
• Thieves Guild: Marksman, Short Blade, Light Armor, Acrobatics, Sneak, Security; 80/30/30, Agility and Personality 34.
• Tribunal Temple: Alchemy, Blunt Weapon, Conjuration, Mysticism, Restoration, Unarmored; 80/30/30, Intelligence and Personality 34.
• Morag Tong: Acrobatics, Illusion, Marksman, Light Armor, Short Blade, Sneak; 80/30/30. Speed and Agility 34.
• Imperial Cult: Speechcraft, Unarmored, Restoration, Mysticism, Enchant, Blunt Weapon; 90/35/35. Personality and Willpower 35.
• Imperial Legion: Athletics, Spear, Long Blade, Blunt Weapon, Heavy Armor, Block; 70/25/25. Endurance and Personality 33.
• House Hlaalu: Speechcraft, Mercantile, Marksman, Short Blade, Light Armor, Security; 70/25/25. Speed and Agility 33.

Character planning

With that in mind, I decided to have Alchemy, Blunt and Marksman as high level skills. Alchemy (main skill for the Mages Guild) could be trained really quickly by making potions. Blunt was shared between 4 factions (Fighters Guild, Temple, Imperial Cult and Imperial Legion) and would have to be trained to 90. Marksman would cover the other 3 factions (Thieves Guild, Morag Tong and House Hlaalu) and trained to 80.

The other skills had to be chosen partially to cover the remaining, weaker requirements, partially so that training them would boost either Strength or Agility to 90 or 80, respectively (otherwise Blunt or Marksman wouldn't be possible to be trained). I hence decided to go for a character that starts with high Strength and a bonus to Blunt weapons and train Long Blade to boost Strength (and cover the Fighters Guild/Imperial Legion secondary skill requirement).

For Agility, I would train Block, Light Armor and Sneak. All three of those are governed by Agility and training them to required levels would result in Agility being boosted enough to allow me to train Marksman to 80.

Enchant and Mysticism would cover the secondary requirements for the Temple, the Mages Guild and the Imperial Legion.

Here's the final character sheet. The major and minor skills that she starts with are:

• Major:
  • Alchemy: 35. To be trained to 70 by making potions (main skill for MG, secondary skill for T).
  • Blunt: 40. To be trained to 90 (main skill for FG, IL, IC and T).
  • Marksman: 30. To be trained to 80 (main skill for TG, MT and HH).
  • Mysticism: 35, doesn't need to be trained (secondary skill for MG, T and IC).
  • Enchant: 35, doesn't need to be trained (secondary skill for MG and IC).
• Minor:
  • Long Blade: 25. To be trained to 45 to get extra Strength points (secondary skill for FG and IL).
  • Sneak: 15. To be trained to 30 (secondary skill for TG and MT).
  • Block: 15. To be trained to 30 (secondary skill for FG and IL).
  • Speechcraft: 15. To be trained to 25 for extra 5 Personality points (secondary skill for HH).
  • Light Armor: 15. To be trained to 30 (secondary skill for TG, MT and HH).

Encoding training in the quest dependency graph

I decided not to load up Morrowind trainer data in order to incorporate it into the route planner. Instead, I looked up the best trainers for Blunt and Marksman (since they're the only ones that will let the player reach the required level) as well as some second best ones and tried to come up with people that the player character would meet en route anyway. There were some hilarious coincidences, like Alveleg who has to be killed as part of a Fighters Guild quest but who can also train the player in Block, Sneak and Marksman up to fairly high levels.

I then added some extra nodes to the dependency graph to reflect the new training sessions:

# Training nodes
training_alveleg:
  # we're killing him as part of the FG quest and he trains Marksman (45), Sneak (42) and Block (38)
  description: Train Block x10 (up to 25), Sneak x15 (up to 30), Marksman x15 (up to 45), should get Agi 60
  giver: alveleg
training_bolnor:
  description: Train Light Armor x15 (up to 30), Marksman x5 (up to 50), should get Agility 70
  giver: bolnor andrani
  prerequisites:
    - training_alveleg
training_eydis:
  description: Train Long Blade x20 (up to 40), Blunt x30 (up to 70), Strength 85
  giver: eydis fire-eye
training_ernse:
  description: Train Blunt x20 (up to 90)
  giver: ernse llervu
  prerequisites:
    - training_eydis
training_missun:
  description: Train Marksman x30 (up to 80)
  giver: missun akin
  prerequisites:
    - training_bolnor
training_falvel:
  description: Train Mercantile x10 (should get Personality 35)
  giver: falvel arenim

They would then become prerequisites for some later quests in faction questlines:

tt_tharer_1:
  description: Get and hand in all Tharer Rotheloth quests
  giver: tharer rotheloth
  prerequisites:
    - tt_7graces_vivec
    - tt_7graces_gnisis
    - tt_7graces_kummu
    - tt_7graces_gg
    - tt_cure_lette
    - tt_mount_kand
    - tt_mawia
    - tt_kill_raxle_berne
    - training_eydis # Curate (50 blunt) to hand in Galom Daeus quest

In some cases, the requirements I added were stronger than necessary. For example, one could get promoted to Master of Fighters Guild with a Blunt skill of 80, yet it depends on a graph node training Blunt to 90. The reasoning behind it was that we don't want to visit the Master Blunt trainer more than once: if we're visiting her, we might as well train Blunt to the maximum we'll need.

Conclusion

Next up, we'll try to add the usage of Mark and Recall spells to the route as well as discuss some miscellaneous Morrowind tricks and glitches that can help during a speedrun.

Travelling murderer problem: planning a Morrowind all-faction speedrun with simulated annealing, part 1

@mildbyte 5 years, 1 month ago | programming | games | morrowind | python |

Well, not even last night's storm could wake you. I heard them say we've reached Morrowind, I'm sure they'll let us go and do a speedrun.

Jiub

Introduction

There's the famous speedrun of Morrowind's main quest that involves basically travelling to the final game location using a few scrolls and spells and killing the boss.

However, there isn't a Morrowind speedrun category where someone tries to become the head of all factions. For all its critical acclaim and its great story, most of quests in Morrowind are basically fetch-item or kill-this-person and there aren't many quests that require anything else. But planning such a speedrun route could still be extremely interesting for many reasons:

• There are 10 joinable factions in Morrowind (Mages/Thieves/Fighters Guild, Imperial Cult, Imperial Legion, Tribunal Temple and the Great Houses: Hlaalu, Redoran, Telvanni). The player can only be a member of one Great House in a playthrough, but that still leaves 8 factions to do.
• The transport system. It's not just a matter of fast travelling to certain locations like one would do in Skyrim or Oblivion. Instead travel is by several transportation modes including boats, caravans and teleportation spells that I had previously investigated. Walking is required a lot and so it's important to manage faction questlines to avoid unnecessary redundant trips to different cities.
• There are many ways to become the head of a given faction. Faction questlines use a promotion system where new questlines open up as the character attains higher ranks at a faction. Promotion is a matter of not only reputation points (awarded by quests) but also player skills and attributes.
• Some quest objectives can be pre-completed or done in a different way. For example, if the quest giver wants the player to kill someone, that someone can often be killed before the quest even starts, at which point, most of the time, the quest giver will give the player the reward anyway. However, sometimes this might not work and the player will lose out on reputation points required to unlock further questlines. Similarly, in most fetch quests the questgiver suggests where the player can get a given item, but doesn't care if it was bought in a nearby shop a few minutes ago.

So given those features, this can get really complicated. On the way to a given quest objective the player can pick up another quest or pick up an item that might be needed at some point for a quest for a different faction that they aren't even a member of. What could be an efficient route through one faction's quests might be inferior to a slower route when all factions are played through since it could be that points in that route are visited in other factions' quests anyway, and so on.

In other words, planning an efficient route through all factions would be a fun computer science problem.

A note on skill requirements and Morrowind's levelling system

There are a couple factions where the final quest can be completed immediately, but that just results in a journal entry saying that the player character is now the head of the faction (and the advancement is not reflected in the character stats). I decided I wanted to rise to the top the mostly-honest way instead.

Unlike Skyrim and Oblivion, advancement in Morrowind factions requires the player to have certain skills at a certain level. There are 27 skills in Morrowind and each faction has 6 so-called "favoured skills". Becoming head of a faction requires the player to have one of these skills at a very high level (roughly 80-90 out of 100) and 2 of them at a medium level (about 30-35).

Morrowind characters also have 7 attributes, each of which "governs" several skills. Attributes also play a role in faction advancement.

So that's kind of bad news, since in a speedrun we won't have enough time to develop our character's skills. The good news is there are trainers scattered around Morrowind that will, for a certain fee, instantly raise these skills. The bad news is that these trainers won't train skills above their governing attributes. Raising attributes requires levelling and levelling in Morrowind is a very long story. I'll get into the actual levelling strategy later.

Different routes through a given faction

I quickly gave up on scraping quest data from the game files (since most quests are driven and updated by a set of dialogue conditions and in-game scripts) and instead used the UESP's Morrowind Quests page to manually create a series of spreadsheets for each faction that included quests, their reputation gain and rough requirements.

Here's an example of one such spreadsheet:

This spreadsheet already shows the complexity of Morrowind factions. There are two intended ways to reach the top of the Mages Guild: by having enough reputation and skills to become a Master Wizard and either completing all of Edwinna Elbert's quests and challenging the current Arch-Mage to a duel or completing all of Skink-in-Tree's-Shade's quests and getting a letter from the upper management telling the current Arch-Mage to step down. I later found another way, by reaching the rank of Wizard (one rank below Master Wizard) and then talking to the current Arch-Mage about a duel, which is quicker.

Other than that, there's also multiple ways to complete a quest. Edwinna Elbert's final 3 quests requiring the player to bring her some Dwarven artifacts don't require the player to actually go to the places she recommends: the artifacts can be acquired from different locations or even bought.

Generating all possible routes through a faction

...turned out to be tricky. The first cut of this was encoding each quest in a YAML file as a set of prerequisites and required items/actions for completion. For example:

  edwinna_2:
    giver: edwinna elbert
    prerequisites:
      rank: Conjurer
      quest: Chimarvamidium 2
    quests:
      - Dwemer Tube:
          rep: 5
          completion:
            items: misc_dwrv_artifact60
      - Nchuleftingth:
          rep: 10
          completion:
            go_person: anes vendu
      ...

This encodes the start of Edwinna Elbert's advanced questline, Dwemer Tube from Arkngthunch-Sturdumz, which requires the player to have become a Conjurer in the Guild and completed Edwinna's previous quest. To complete this quest, the player needs to have the tube in their inventory (I used the in-game item ID). Completion gives the player 5 faction reputation points.

The questline continues with Nchuleftingth Expedition and to complete that quest, the player needs to go to a certain NPC (he's an archaeologist who has, as it turns out, perished). Unlike the previous quest, this action (of going to a person and interacting with them) requires us to have started the quest.

So with that in mind, we can generate a set of all possible ways to complete a guild using breadth-first search:

• set of all sequences completing the guild S = empty
• do:
  • for each sequence in S:
    • if it already completes the guild, ignore it
    • otherwise, get all possible next quests that can be done in this sequence:
      • where the quest prerequisites have been met (e.g. a previous/required quest in the questline has been completed)
      • where there's enough reputation to start a new questline
    • add each one of these possible quests to a sequence to create several new sequences
    • replace the current sequence with the newly generated ones
• until S stops changing

Combinatorial explosions, combinatorial explosions everywhere

What could possibly go wrong? Well, firstly there's an issue of ordering. If the player is juggling two parallel questlines from different questgivers, each possible interleaving of those is counted, which causes a combinatorial explosion. Secondly, routes that are strictly worse than existing routes are generated too. For example, if completing a certain guild requires us to only complete quests A, B, D and E, there's no point in generating a route A, B, C, D, E: there's no way doing D won't take extra time.

I hence did some culling by making sure that during generation we wouldn't consider a sequence if it were a superset of an already existing quest sequence. This brought the number of generated routes (subsets, really) down to a mildly manageable 300.

Is this good? Well, not really. This only accounted for which sets of quests could be completed. There was no mention of the order in which these quests could be completed (yielding probably millions of permutations), the ordering of actual actions that would complete a given quest (for example, completing a given quest could involve killing someone and that could happen even before the player character was aware of a quest) or the alternative routes (like fetching a required item from a different place or doing an extra objective to get more faction reputation).

Worse even, this was just the route generation for one faction. There were 7 more factions to do (and I had to pick a Great House that would be the quickest to complete too) and even if they didn't have that many ways to complete them, brute-forcing through all the possible routes with all factions would definitely be unreasonable.

This method also wouldn't let me encode some guild features. For example, Morag Tong, Morrowind's legal assassin guild, has several questgivers around the world, any of which can give the player their next contract. Furthermore, the reputation required for the final questline to open can be gathered not only by doing assassination contracts, but also by collecting certain items spread around the world, each yielding about the same reputation as a contract. These items can quite often be found in dungeons that the player has to visit for other factions anyway and it could be the case that doing those quests to collect these items is overall faster.

Attempt 2: a single quest dependency graph

I hence decided to drop the idea of combining all possible routes from all guilds and instead did some experimentation to find out if there are obviously quick routes through most guilds. Turns out, there were and so instead of solving a few million instances of the Travelling Salesman Problem, I could do with just one. Still impossible, but less impossible.

Quick overview of fastest routes for a given faction

In the Mages Guild, the introductory questline can be completed in a matter of minutes and yield 22 reputation points and then Edwinna's quests can be completed en route to other quest locations that will likely have to be visited anyway. Those two questgivers would bring the player character over the 70 reputation limit required to challenge the current Arch-Mage (at that point, I wasn't looking at skills training yet).

The Fighters Guild could be completed by doing all quests from one questgiver (most of which involved killing bandits in roughly the same area which can be done even before the quest begins), a couple from another one and then proceeding on to a final questline (which does have a quest requiring to bring some items to the middle of nowhere, but the alternative ending requires many more reputation points).

The Thieves Guild has some conflicts with the Fighters Guild and so the two questlines have to be carefully managed together. Almost all quests in the Thieves Guild need to be done (since doing some Fighters' Guild quests decreases reputation with the Thieves Guild), but the good news is that they share the antagonist and so after reaching a certain reputation with the Thieves Guild, finishing the Fighters Guild promotes the character to Master Thief.

Morag Tong can basically be completed in one go: after the initial contract required to join the Guild, the player collects enough Sanguine items to skip all contracts straight on to the final questline and the location of the final boss is visited twice in other guilds' quests.

Tribunal Temple starts with a mandatory pilgrimage that visits a few locations around the game map. There are several more pilgrimages as part of the questline and some of those can be completed even without having joined the faction.

Imperial Legion has a questline that takes place in a single town and requires the player to visit the location that's visited anyway in Edwinna Elbert's questline in the Mages Guild. In addition, one quest gives additional reputation with the Temple, allowing to skip one quest there.

Imperial Cult has three questlines. One of them involves fundraising and, just like in real life, the player can simply give the money to the questgiver on the spot instead of asking others for it. The other one involves fetching several powerful artifacts and visiting a couple of locations that are visited in other guilds' questlines.

After eyeballing the Great Houses' questlines, I settled on House Hlaalu. House Redoran has a way too long questline, most of the action in House Telvanni happens on the East side of the game map that mostly isn't visited in other quests and the final Hlaalu questline that leads to becoming Grandmaster can be started at an earlier rank.

Quest dependency graph

Now that I had a single route for each guild, instead of encoding each and every quest requirement and location in a graph, I opted for an easier way. Each node in a quest dependency graph would be something that's fairly quick to complete and happens in the same location. It could be a quest, or a series of quests, or the action of clearing out some dungeon that is featured in several future quests.

A node contains two things: where this node is located (for example, the in-game ID of the questgiver or an NPC in the location that the player needs to clear out or find a certain item) and nodes that the player needs to have completed before.

For example:

# Coalesced Ajira questline
mg_ajira_1:
  giver: ajira
# Edwinna's quests up until Nchuleftingth expedition, all done in one go (Dwemer tube stolen
# from Vorar Helas in Balmora, then Chimarvamidium, Skink and Huleen)
mg_edwinna_1:  # also gives Almsivi/Divine amulets
  giver: edwinna elbert
  prerequisites:
    - mg_ajira_1
mg_edwinna_2:
  giver: edwinna elbert
  prerequisites:
    - mg_edwinna_1
    - mg_edwinna_nchuleftingth
    - mg_edwinna_scarab_plans
    - mg_edwinna_airship_plans
# locations of items we need to collect to complete Edwinna's quests
mg_edwinna_nchuleftingth:
  giver: anes vendu # can discover his body before the quest begins
mg_edwinna_scarab_plans:
  giver: Khargol gro-Boguk # orc in Vacant Tower with the other copy of the plans
mg_edwinna_airship_plans:
  giver: lugrub gro-ogdum # located near the orc in Gnisis Eggmine that is also a part of the IL quest
mg_master:
  giver: trebonius artorius
  prerequisites:
    - mg_edwinna_2

In this case, the Dwarwen plans required by Edwinna can be collected even before the questline begins and then all handed in at the same time.

When talking to someone had to be done as a part of the quest, I encoded it as several nodes that depended on each other:

fg_eydis_1_start: # join FG and start first quest
  giver: eydis fire-eye
fg_eydis_1_do:
  giver: drarayne thelas # actually do the first quest
  prerequisites:
    - fg_eydis_1_start
fg_eydis_1_end: # hand the quest in
  giver: eydis fire-eye
  prerequisites:
    - fg_eydis_1_do

Here's the final quest dependency graph:

This was much better than messing around with reputation points and quest prerequisites. Any topological sorting of this dependency graph would be a valid route through the game's quests (assuming I encoded my dependencies correctly). Since each node had a fixed geographical location, I could use a pathfinding algorithm and the data from my previous project to find out the time that any given route satisfying this dependency graph (using teleportation and public transport) takes.

However, there's still a problem: there are many possible topological sortings of a given graph and counting them is #P-complete.

This is a general case of the travelling salesman problem: if here we need to find the shortest tour that visits all nodes subject to a set of dependencies (e.g. we can't visit A before we've visited C), then in TSP we need to visit all nodes without any dependencies. Having dependencies decreases our search space (in the most extreme case the dependency graph is a line and so there's only one possible route), but not by enough.

I hence had to develop some approximations to turn this graph and the matrix of travel times between its nodes into a good-enough route.

Conclusion

Next up, I'll try a couple of random approximations to solve this problem, including simulated annealing (also kind of known as a genetic algorithm). There's also the matter of planning out the player character and his/her skill development in order to minimize the amount of time we need to spend training up to get promoted in various guilds. Stay tuned!

You're probably not going to get rich in the stock market

@mildbyte 5 years, 2 months ago | python | thoughts | tech | finance |

source: XKCD

Abstract: I examine inflation-adjusted historical returns of the S&P 500 since the 1870s with and without dividends and backtest a couple of famous investment strategies for retirement. I also deploy some personal/philosophical arguments against the whole live-frugally-and-then-live-frugally-off-of-investments idea.

Disclaimer: I'm not (any more) a finance industry professional and I'm not trying to sell you investment advice. Please consult with somebody qualified or somebody who has your best interests at heart before taking any action based on what some guy said on the Internet.

The code I used to produce most of the following plots and process data is in an IPython notebook on my GitHub.

Introduction

Early retirement is simple, right? Just live frugally, stop drinking Starbucks lattes, save a large fraction of your paycheck, invest it into a mixture of stocks and bonds and you, too, will be on the road towards a life of work-free luxury and idleness driven by compound interest!

What if there's a stock market crash just before I retire, you ask? The personal finance gurus will calm you down by saying that it's fine and the magic of altering your bond position based on your age as well as dollar cost averaging, together with the fact that the stock market returns 7% on average, will save you.

As sweet as that would be, there is something off about this sort of advice. Are you saying that I really can consistently make life-changing amounts of money without doing any work? This advice also handwaves around the downside risks of investing into the stock market, including the volatility of returns.

I wanted to simulate the investment strategies proposed by personal finance and early retirement folks and actually quantify whether putting my "nest egg" into the stock market is worth it.

This piece of writing was mostly inspired by NY Times' "In Investing, It's When You Start And When You Finish" that shows a harrowing heatmap of inflation-adjusted returns based on the time an investment was made and withdrawn, originally created by Crestmont Research. They maintain this heatmap for every year here.

This post is in two parts: in the first one, I will backtest a few strategies in order to determine what sort of returns and risks at what timescales one should expect. In the second one, I will try to explain why I personally don't feel like investing my money into the public stock market is a good idea.

Simulating common stock market investment strategies

Dataset

The data I used here is the S&P 500 index. and I'm assuming one can invest into the index directly. This is not strictly true, but index tracker funds (like Vanguard's VOO ETF) nowadays are pretty good and pretty cheap.

A friend pointed me to a paper that has an interesting argument: using the US equity markets for financial research has an implicit survivorship bias in it. Someone in the 1870s had multiple countries' markets to choose from and had no way of knowing that it was the US the would later become a global superpower, large amounts of equity gains owing to that.

As a first step, I downloaded Robert Shiller's data that he used in his book, "Irrational Exuberance", and then used it to create an inflation-adjusted total return index: essentially, the evolution of the purchasing power of our portfolio that also assumes we reinvest dividends we receive from the companies in the index. Since the companies in the index are large-cap "blue chip" stocks, dividends form a large part of the return.

I compared the series I got, before adjusting for inflation, with the total return index from Yahoo! Finance and they seem to closely match the Yahoo! data from the 1990s onwards.

The effect of dividends being reinvested changes the returns dramatically. Here's a comparison of the series I got with the one without dividends (and one without inflation):

The average annual return, after inflation, and assuming dividends are reinvested, is about 7.5%. Interestingly, this seems to contradict Crestmont Research's charts where the average annual pre-tax (my charts assume there are no taxes on capital gains or dividends) return starting from 1900 is about 5%.

On the other hand, the return with dividends reinvested does seem to make sense: without dividends, the annualized return is about 4.25%, which implies a dividend yield close to the actual observed values of about 4.4%.

Another observation is that the returns are not normal (their distribution has statistically significant differences in kurtosis and skewness).

Common strategies

Lump sum investing

First, I wanted to plot the annualized returns from investing in the S&P 500 at a given date and holding the investment for a certain number of years.

The result kind of confirms the common wisdom that the stock market is a long term investment and is fairly volatile in the short term. If one invested in the late 1990's, say, and withdrew their investment in 5 or even 10 years, they would have lost about 4% every year after inflation. Only with investment horizons of 20 years do the returns finally stabilise.

Here are the distributions of returns from investing a lump sum into the S&P 500. This time they were taken from 10000 simulations of paths a given portfolio would follow (by randomly sampling monthly returns from the empirical returns' distribution). I also plotted the inflation-adjusted returns from holding cash (since it depreciates with inflation) for comparison.

What can be seen from this is that in 20 or 30 years, it seems possible to double or quadruple one's purchasing power.

I also plotted a set of "hazard curves" from those sampled distributions. Those are the simulated probabilities of getting less than a given return depending on the investment horizon. For example, there's a 30% chance of getting a return of less than 0% after inflation (losing money) for a 1 year investment and this chance drops down to about 5% for a 20 year investment. Conversely, there's a 100% chance of getting a return of less than 300% (quadrupling the investment), but after 20 years there's a 50% chance of doing so.

Dollar cost averaging

DCA is basically investing the same amount of money at given intervals of time. Naturally, such an investment technique results in one purchasing more of a stock when it's "cheap" and less when it's "expensive", but "cheap" and "expensive" are relative and kind of meaningless in this case.

DCA is usually considered an alternative to lump sum investing, but for a person who is investing, say, a fraction of their paycheck every month it's basically the default option.

I did some similar simulations of dollar cost averaging over a given horizon against investing the same sum instantly.

Unsurprisingly, DCA returns less than lump sum investment in this case. This is because the uninvested cash depreciates with inflation, as well as because the average return of the stock market is positive and hence most of the cash that's invested later misses out on those gains.

DCA would do better in a declining market (since, conversely, most cash would miss out on stock market losses), but if one can consistently predict whether the market is going to rise or decline, they can probably use that skill for more than just dollar cost averaging.

In my tests, dollar cost averaging over 20 years gave a very similar distribution to investing a lump sum for 9 years. Essentially, returns of DCA follow those of investing a lump sum for a shorter period of time.

Finally, here are the "hazard curves" for dollar cost averaging.

After a year of monthly investing we'd have an almost 40% chance of losing money after inflation and even after 20 years we still have a 10% chance. After 20 years, doubling our purchasing power is still a coin toss.

Is it worth it?

Difference in expected utility

What we have gleaned from this is that the long-term yearly return from the stock market is about 7% after inflation (but before taxes), assuming one invests over 20-30 years. Compounded, that maybe results in quadrupling of one's purchasing power (less if one invests a fraction monthly, and even less with dividend and capital gains taxes).

While doubling or trebling one's purchasing power definitely sounds impressive (especially whilst doing only a few hours of work a year!), it doesn't really feel big if you look into it. Let's say you're about to retire and have saved up $1 million (adjusted for inflation) that you weren't investing. If you were putting a fraction of that money monthly into the stock market instead you would have had $2-3 million, say. But you can live as comfortably off of the interest on $1 million as you would on $2-3 million.

And on the contrary, if you have only saved $100k, dollar-cost averaging would have yielded you $300k instead, the interest on both amounts (and in retirement it has to be risk-free or almost-risk free) being fairly small.

One could argue that every little bit helps, but what I'm saying here is that the utility of wealth is non-linear. It's kind of sigmoidal, in a way. I like this graph from A Smart Bear:

source: A Smart Bear

As long as one has enough money to get up that "utility cliff" beyond which they can live off of their investments in retirement, it doesn't matter how much is it. Conversely, saving by investing into the stock market is worth it only if one is very sure that that's the thing that will get them over the line.

Flexibility, predicting the future and barbell investing

This possible climb up the cliff comes at a cost of locking in one's capital for a large amount of time (as short-term volatility in the stock market makes it infeasible to invest only for a few years). This lock-in leaves one completely inflexible in terms of pursuing other opportunities.

One's basically treating the stock market as some sort of a very long-term bond where they put the money in at one end and it comes out on the other side, slightly inflated. There was also an implicit assumption in all these simulations that the future follows the same pattern as the past.

Returns only become consistent after 30 years with dollar cost averaging. Someone who started investing a fraction of their savings into the general stock market 30 years ago would have gotten a 5-7% annualized return. Could they have predicted this? Probably. But could they have predicted the rise of the Web, the smartphones, the dotcom boom and crash? Probably not.

I'm not saying that whatever extra money one has should be invested into Bitcoin, a friend's startup or something else. Money can also be used to buy time off (to get better acquainted with some new development or technology) or education. Is using it to buy chunks of large corporations really the best we can do?

I also like the idea of "barbell investing", coined by Nassim Nicholas Taleb: someone should have two classes of investments. The first one is low-risk and low-return, like bonds or even cash. The second one is "moonshots", aggressive high-risk, low-downside, high-upside investments. Things like the stock market are considered to be neither here nor there, mediocre-return investments that might bear some large hidden downside risks.

...so that you can do what you really love?

There's an argument that one should still save up excessive amounts of money (as investments or just cash) whilst living extremely frugally so that after several years of hard work they "never have to work again" and can retire, doing what they really would have loved to do this whole time.

One of Paul Graham's essays kind of sums up what I think about it:

Conversely, the extreme version of the two-job route is dangerous because it teaches you so little about what you like. If you work hard at being a bond trader for ten years, thinking that you'll quit and write novels when you have enough money, what happens when you quit and then discover that you don't actually like writing novels?

Paul Graham, "How To Do What You Love"

Here I am, young and retired. What do I do next? Anything? How do I know what I like? Do I have any contacts that I can rely upon to help me do that "anything"? I don't feel that toiling away somewhere, being bored for a couple of decades, so that I can then quit and be bored anyway (since I hadn't learned what makes me tick), is a useful life strategy.

Warren Buffett?

What about all those people who did become rich investing into the stock market? Warren Buffett is one of them, probably one of the most famous investors in the world. But he made his first couple of million (in 2018 dollars) working for Benjamin Graham, in salary and bonuses. In essence, if he wanted to, he could have retired right there and then.

Only then did he proceed to increase his wealth by investing (first running an investment partnership and so working with the partnership's money and presumably charging a performance fee, then through Berkshire Hathaway). None of these methods are available to someone with a personal investment account.

Conclusion

Essentially, I think that the stock market is a wealth preservation, not a wealth generation engine. Publicly-listed companies are large and stable, paying consistent and healthy dividends with the whole investment yielding a solid, inflation-beating return.

But for me? I think it's important to stay flexible and keep my options open. If someone offers me an opportunity somewhere, I don't want to say "Sorry, I have a mortgage and the rest of my money is invested in healthy companies with solid, inflation-beating returns that I can't currently sell because it's in drawdown and would you look at the tax advantages". I want to be able to say "Sure, let me give a month's notice to my landlord. Where are we going?"

project Betfair, part 8

@mildbyte 5 years, 5 months ago | programming | python | betfair | scala |

Introduction

Previously on project Betfair, we gave up on market making and decided to move on to a simpler Betfair systematic trading idea that seemed to work.

Today on project Betfair, we'll trade it live and find out it doesn't really work.

DAFBot on greyhounds: live trading

With the timezone bug now fixed, I was ready to let my bot actually trade some greyhound races for a while. I started trading with the following parameters:

• Favourite selection time: 180s
• Entry order time: 160s
• Exit time: 60s
• Bet size: £5

I decided to pick the favourite closer to the trade since I thought that if it were picked 5 minutes before the race starting, it could change and there was no real point in locking it in so long before the actual trade. The 60s exit point was mostly to give me a margin of safety to liquidate the position manually if something happened as well as in case of the market going in-play before the advertised time (there's no in-play trading in greyhound markets, so I'd carry any exposure into the game. At that point, it would become gambling and not trading).

Results

So how did it do?

Well, badly for now. Over the course of 25 races, in 4 hours, it lost £5.93: an average of -£0.24 per race with a standard deviation of £0.42. That was kind of sad and slightly suspicious too: according to the fairly sizeable dataset I had backtested this strategy on, its return was, on average, £0.07 with a standard deviation of £0.68.

I took the empirical CDF of the backtested distribution of returns, and according to it, getting a return of less than -£5.93 with 25 samples had a probability of 1.2%. So something clearly was going wrong, either with my backtest or with the simulation.

I scraped the stream market data out of the bot's logs and ran the backtest just on those races. Interestingly, it predicted a return of -£2.70. What was going wrong? I also scraped the traded runners, the entry and the exit prices from the logs and from the simulation to compare. They didn't match! A few times the runner that the bot was trading was different, but fairly often the entry odds that the bot got were lower (recall that the bot wants to be long the market, so entering at lower odds (higher price/implied probability) is worse for it). Interestingly, there was almost no mismatch in the exit price: the bot would manage to close its position in one trade without issues.

After looking at the price charts for a few races, I couldn't understand what was going wrong. The price wasn't swinging wildly to fool the bot into placing orders at lower odds: in fact, the price 160s before the race start was just different from what the bot was requesting.

Turns out, it was yet another dumb mistake: the bot was starting to trade 150s before the race start and pick the favourite at that point as well. Simulating what the bot did indeed brought the backtest's PnL (on just those markets) within a few pence from the realised PnL.

So that was weird: moving the start time by 10 seconds doubled the loss on that dataset (by bringing it from -£2.70 to -£5.93).

Greyhound capacity analysis

There was another issue, though: the greyhound markets aren't that liquid.

While there is about £10000-£15000 worth of bets available to match against in an average greyhound race, this also includes silly bets (like offering to lay at 1000.0).

To demonstrate this better, I added market impact to the backtester: even assuming that the entry bet gets matched 160s before the race (which becomes more difficult to believe at higher bet amounts, given that the average total matched volume by that point is around £100), closing the bet might not be possible to do completely at one odds level: what if there isn't enough capacity available at that level and we have to place another lay bet at higher odds?

Here's some code that simulates that:

def get_long_return(lines, init_cash, startT, endT, suspend_time,
    market_impact=True, cross_spread=False):

    # lines is a list of tuples: (timestamp, available_to_back,
    #    available_to_lay, total_traded)
    # available to back/lay/traded are dictionaries
    #   of odds -> availablility at that level

    # Get start/end availabilities
    start = get_line_at(lines, suspend_time, startT)
    end = get_line_at(lines, suspend_time, endT)

    # Calculate the inventory 
    # If we cross the spread, use the best back odds, otherwise assume we get
    # executed at the best lay
    if cross_spread:
        exp = init_cash * max(start[1])
    else:
        exp = init_cash * min(start[2])

    # Simulate us trying to sell the contracts at the end
    final_cash = 0.

    for end_odds, end_avail in sorted(end[2].iteritems()):

        # How much inventory were we able to offload at this odds level?
        # If we don't simulate market impact, assume all of it.
        mexp = min(end_odds * end_avail, exp) if market_impact else exp
        exp -= mexp

        # If we have managed to sell all contracts, return the final PnL.
        final_cash += mexp / end_odds
        if exp < 1e-6:
            return final_cash - init_cash

    # If we got to here, we've managed to knock out all price levels 
    # in the book.
    return final_cash - init_cash

I then did several simulations of the strategy at different bet sizes.

Turns out, as we increase the bet size away from just £1, the PnL quickly decays (the vertical lines are the error bars, not the standard deviations). For example, at bet size of £20, the average return per race is just £0.30 with a standard deviation of about £3.00 and a standard error of £0.17.

DAFBot on horses

At that point, I had finally managed to update my new non-order-book simulator so that it could work on horse racing data, which was great, since horse markets were much more preferable to greyhound ones: they were more liquid and there was much less opportunity for a single actor to manipulate prices. Hence there would be more capacity for larger bet sizes.

In addition, given that the spreads in horses are much tighter, I wasn't worried about having a bias in my backtests (the greyhound one assumes we can get executed at the best lay, but most of its PnL could have come from the massive back-lay spread at 160s before the race, despite that I limited the markets in the backtest to those with spreads below 5 ticks).

Research

I backtested a similar strategy on horse data but, interestingly enough, it didn't work: the average return was well within the standard error from 0.

However, flipping the desired position (instead of going long the favourite, betting against it) resulted in a curve similar to the one for the greyhound strategy. In essence, it seemed as if there was an upwards drift in the odds on the favourite in the final minutes before the race. Interestingly, I can't reproduce those results with the current, much larger, dataset that I've gathered (even if I limit the data to what I had at that point), so the following results might be not as exciting.

The headline number, according to my notes at that time, was that, on average, with £20 lay bets, entering at 300 seconds before the race and exiting at 130 seconds, the return was £0.046 with a standard error of £0.030 and a standard deviation of £0.588. This seems like very little, but the £20 bet size would be just a start. In addition, there are about 100 races every day (UK + US), hence annualizing that would result in a mean of £1690 and a standard deviation of £112.

This looked nice (barring the unrealistic Sharpe ratio of 15), but the issue was that it didn't scale well: at bet sizes of £100, the annualized mean/standard deviation would be £5020 and £570, respectively, and it would get worse further on.

I also had found out that, at £100 bet sizes, limiting the markets to just those operating between 12pm and 7pm (essentially just the UK ones) gave better results, despite that the strategy would only be able to trade 30 races per day. The mean/standard deviation were £4220 and £310, respectively: a smaller average return and a considerably smaller standard deviation. This was because the US markets were generally thinner and the strategy would crash through several price levels in the book to liquidate its position.

Note this was also using bet sizes and not exposures: so to place a lay of £100 at, say, 4.0, I would have to risk £300. I didn't go into detailed modelling of how much money I would need deposited to be able to trade this for a few days, but in any case I wasn't ready to trade with stakes that large.

Placing orders below £2

One of the big issues with live trading the greyhound DAFBot was the fact that the bot can't place orders below £2. Even if it offers to buy (back), say, £10 at 2.0, only £2 of its offering could actually get matched. After that point, the odds could go to, say, 2.5, and the bot would now have to place a lay bet of £2 * 2.0 / 2.5 = £1.6 to close its position.

If it doesn't do that, it would have a 4-contract exposure to the runner that it paid £2 for (will get £4 if the runner wins for a total PnL of £2 or £0 if the runner doesn't win for a total PnL of -£2).

If it instead places a £2 lay on the runner, it will have a short exposure of 2 * 2.0 - 2 * 2.5 = -1 contract (in essence, it first has bought 4 contracts for £2 and now has sold 5 contracts for £2: if the runner wins, it will lose £1, and if the runner loses, it will win nothing). In any case, it can't completely close its position.

So that's suboptimal. Luckily, Betfair documents a loophole in the order placement mechanism that can be used to place orders below £2. They do say that it should only be used to close positions and not for normal trading (otherwise people would be trading with £0.01 amounts), but that's exactly our use case here.

The way it's done is:

• Place an order above £2 that won't get matched (say, a back of 1000.0 or a lay of 1.01);
• Partially cancel some of that order to bring its unmatched size to the desired amount;
• Use the order replacement instruction to change to odds of that order to the desired odds.

Live trading

I started a week of fully automated live trading on 2nd October. That was before I implemented placing bets below £2 and the bot kind of got lucky on a few markets, unable to close its short exposure fully and the runner it was betting against losing in the end. That was nice, but not exactly intended. I also changed the bot to place bets based on a target exposure of 10 contracts (as opposed to stakes of £10, hence the bet size would be 10 / odds).

In total, the bot made £3.60 on that day after trading 35 races.

Things quickly went downhill after I implemented order placement below £2:

• 3rd October: -£3.41 on 31 races (mostly due to it losing £3.92 on US markets after 6pm);
• 4th October: increased bet size to 15 contracts; PnL -£2.59 on 22 races;
• 5th October: made sure to exclude markets with large back-lay spreads from trading; -£2.20 on 25 races (largest loss -£1.37, largest win £1.10);
• 6th October: -£3.57 on 36 races;
• 7th October: -£1.10 on 23 races.

In total, the bot lost £9.27 over 172 races, which is about £0.054 per race. Looking at Betfair, the bot had made 395 bets (entry and exit, as well as additional exit bets at lower odds levels when there wasn't enough available at one level) with stakes totalling £1409.26. Of course, it wasn't risking more than £15 at any point, but turning over that much money without issues was still impressive.

What wasn't impressive was that it consistently lost money, contrary to the backtest.

Conclusion

At that point, I was slowly growing tired of Betfair. I played with some more ideas that I might write about later, but in total I had been at it for about 2.5 months and had another interesting project in mind. But project Betfair for now had to go on an indefinite hiatus.

To be continued...

Enjoyed this series? I do write about other things too, sometimes. Feel free to follow me on twitter.com/mildbyte or on this RSS feed! Alternatively, register on Kimonote to receive new posts in your e-mail inbox.

Interested in this blogging platform? It's called Kimonote, it focuses on minimalism, ease of navigation and control over what content a user follows. Try the demo here or the beta here and/or follow it on Twitter as well at twitter.com/kimonote!

project Betfair, part 7

@mildbyte 5 years, 5 months ago | programming | python | betfair | scala |

Introduction

Previously on project Betfair, we ran the production market-making CAFBot in Scala, got it working, made some money, lost some money and came back with some new ideas.

Today, we'll test those ideas, look at something that's much more promising and learn a dark truth about timezones.

Sorry this took a bit too long to write, by the way, I've been spending some time working on Kimonote to add email digests to streams. The idea is that given some exporters from streams (e-mail, RSS (already works), Facebook, Twitter etc) with varying frequencies (immediately or weekly/daily digests) as well as some importers (again RSS/Twitter/Facebook/other blogging platforms) a user could create their own custom newsletter and get it sent to their mailbox (push) instead of wasting time checking all those websites (pull), as well as notify their social media circles when they put a new post up anywhere else. None of this works yet, but other features do — if you're interested, sign up for the beta here!

Shameless plug over, back to the world of automated trading goodness.

CAFBotV2 with wider spreads

Remember how in the real-world greyhound market the bot managed to have some of its bets matched despite that they were several ticks away from the best back and lay? I realised I never really tested that in simulation: I started from making the market at the top of the order book and kind of assumed that further away from there matching would never happen. Looks like I was wrong (and in fact in part 5 the bot had issues with its bets that were moved away from the current market because of high exposure getting matched anyway).

So I added (backported?) the levelBase parameter from the Scala bot into the research one: recall that it specified how far from the best back/lay the bot should start working before applying all the other offsets (exposure or order book imbalance). Hence at levelBase = 0 the bot would work exactly as before and with levelBase = 1 it would start 1 Betfair tick away from the best back/lay. levelBase = 3 is what was traded live on the greyhound market.

The idea behind this is kind of simple: if the bot still gets its bets matched even if it's far away from the best back/lay, it will earn a higher spread with fewer trades.

So, first, I ran it on our favourite horse market with levelBase = 1.

Results

Horses, levelBase = 1

It didn't do well: there were very few matches and so most of the time it just did nothing, trading a grand total of 3 times. This meant that it got locked into an inventory that it couldn't offload.

Let's run it on the whole dataset: though this market didn't work as well, in some other ones matching did happen in jumps larger than 1 tick, so those might be able to offset more liquid markets.

We're tantalizingly close to finally having a PnL of zero (the more observant reader might notice that we could have done the same by not trading at all). Let's see how it would have done on the greyhound markets, which we do know sometimes jump like crazy.

Greyhounds, levelBase = 3

Not very inspiring either. There's a large amount of markets where this wouldn't have done anything at all (since the bets were so far from the best back/lay, they don't ever get hit), and when something does happen, it seems to be very rare, so the bot can't liquidate its position and remains at the mercy of the market.

So while that was a cute idea, it didn't seem to work.

DAFBot

At this point, I was running out of ideas. The issue of the bot getting locked into an inventory while the market was trending against it still remained, so I had to look at the larger-scale patterns in the data: perhaps based on the bigger moves in the market, the bot could have a desired inventory it could aim for (instead of always targeting zero inventory).

Consider this: if we think that the market is going to move one way or another, it's okay for the bot to have an exposure that way and it can be gently guided towards it (by means of where it sets its prices). Like that, the bot would kind of become a hybrid of a slower trading strategy with a market maker: even if its large-scale predictions of price movements weren't as good, they would get augmented by the market making component and vice versa.

Carry?

I tried out a very dumb idea. Remember how in most of the odds charts we looked at the odds, for some reason, trended down? I had kind of noticed that, or at least I thought I did, and wanted to quantify it.

Those odds were always on the favourite (as in, pick the greyhound/horse with the lowest odds 1 hour before the race begins and see how they change). The cause could be that, say, people who wanted to bet on the favourite would delay their decision to see if any unexpected news arrived before the race start, which is the only sort of news that could move the market.

Whatever the unexpected news would be, they would likely affect the favourite negatively: they could be good for any of the other greyhounds/horses, thus making it more likely for them to win the race. Hence it would make sense, if someone wanted to bet on the favourite, for them to wait until just before the race begins to avoid uncertainty, thus pushing the odds down as the race approaches.

So what if we took the other side of this trade? If we were to go long the favourite early, we would benefit from this downwards slide in odds, at the risk of some bad news coming out and us losing money. I guessed this would be similar to a carry trade in finance, where the trader makes money if the market conditions stay the same (say, borrowing money in a lower interest rate currency and then holding it in a higher interest rate currency, hoping the exchange rate doesn't move). In essence, we'd get paid for taking on the risk of unexpected news about the race coming out.

Research: greyhounds

I had first started doing this using my order book simulator, but realised it would be overkill: if the only thing I wanted to do was testing a strategy that traded literally twice (once to enter the position, once to close it), it would be better write a custom scraper from the stream data that would get the odds' timeseries and simulate the strategy faster.

At that point, I realised the horse racing stream data was too large to fit into memory with the new simulator. So I put that on hold for a second and tried my idea on greyhound markets.

This chart plots, at each point in time before the race, the average return on going long (backing) the favourite and then closing our position 15s before the race begins. In any case, the favourite is picked 5 minutes before the race begins. The vertical lines are the error bars (not standard deviations). Essentially, what we have here is a really consistent way to lose money.

This is obviously because of the back-lay spreads: the simulation here assumes we cross the spread both when entering and exiting, in essence taking the best back in the beginning and the best lay at the end.

Remember this chart from part 4?

The average spread 120s before a greyhound race begins is about 5 ticks. We had previously calculated that the loss on selling 1 tick lower than we bought is about 0.5%, so no wonder we're losing about 3% of our investment straight away.

What if we didn't have to cross the spread?

Woah. This graph assumes that instead of backing the runner at the best back, we manage to back it at the current best lay (by placing a passive back at those odds). When we're exiting the position just before the race begins, time is of the essence and so we're okay with paying the spread and placing a lay bet at the odds of the current best lay (getting executed instantly).

The only problem is actually getting matched: since matching in greyhound markets starts very late (as much money gets matched in the last 80 seconds as does before), our bet could just remain in the book forever, or get matched much closer to the beginning of the race.

But here's the fun part: this graph doesn't care. It shows that if the bet is matched at whatever the best lay was 160 seconds before the race, on average this trade makes money — even if the actual match happens a minute later. If the bet doesn't get matched at all, the trade simply doesn't happen.

This does assume that the performance of this strategy is independent of whether or not the bet gets hit at all, but if that's not the case, we would have been able to use the fact that our bet got hit as a canary: when it gets hit, we know that being long this market is a good/bad thing and adjust our position accordingly.

Implementation in Scala

With that reasoning, I went to work changing the internals of Azura to write another core for it and slightly alter the way it ran. The algorithm would be:

• Run with parameters: market, favourite selection time, entry start time, entry end time, exit time (all in seconds before the race start), amount to bet.
• Subscribe to the market/order streams, get the market suspend time from the Betfair API
• At favourite selection time: inspect our local order book cache, select the runner with the lowest odds
• At entry start time: place a passive back at the current best lay odds of the given amount on the favourite.
• At entry end time: cancel remaining unexecuted orders.
• At exit time: if we have a position (as in our entry order got hit), unwind it aggressively.

I called the new core DAFBot (D stands for Dumb and what AF stands for can be gleaned from the previous posts). I wanted to reuse the idea of polling a strategy for the orders that it wished to offer and the core being stateless, since that would mean that if the bot crashed, I could restart it and it would proceed where it left off. That did mean simple actions like "buy this" became more difficult to encode: the bot basically had to look at its inventory and then say "I want to maintain an outstanding back bet for (how much I want to buy - how much I have)".

Finally, yet another Daedric prince got added to my collection: Sheogorath, "The infamous Prince of Madness, whose motives are unknowable" (I had given up on my naming scheme making sense by this point), would schedule instances of Azura to be run during the trading day by using the Betfair API to fetch a list of greyhound races and executing Azura several minutes before that.

Live trading

I obviously wasn't ready to get Sheogorath to execute multiple instances of Azura and start losing money at computer speed quite yet, so for now I ran the new strategy manually on some races, first without placing any bets (just printing them out) and then actually doing so.

The biggest issue was the inability to place bets below £2. I had thought this wouldn't be a problem (as I was placing entry bets with larger amounts), but fairly often only part of the offer would get hit, so the bot would end up having an exposure that it wasn't able to close (since closing it would entail placing a lay bet below £2). Hence it took some of that exposure into the race, which wasn't good.

Timing bug?

In addition, when testing Sheogorath's scheduling (by getting it to kick off instances of Azura that didn't place bets), I noticed a weird thing: Sheogorath would start Azura one minute later than intended. For example, for a race that kicked off at 3pm, Azura was supposed to be started 5 minutes before that (2:55pm) whereas it was actually executed at 2:56pm.

While investigating this, I realised that there was another issue with my data: I had relied on the stream recorder using the market suspend times that were fetched from Betfair to stop recording, but that might not have been the case: if the greyhound race started before the scheduled suspend time, then the recording would stop abruptly, as opposed to at the official suspend time.

Any backtest that counted backwards from the final point in the stream would kind of have access to forward-looking information: knowing that the end of the data is the actual suspend time, not the advertised one.

Hence I had to recover the suspend times that the recorder saw and use those instead. I still had all of the logs that it used, so I could scrape the times from them. But here was another fun thing: spot-checking some suspend times against Betfair revealed that they sometimes also were 1 minute later than the ones on the website.

That meant the forward-looking information issue was a bigger one, since the recorder would have run for longer and have a bigger chance of being interrupted by a race start. It would also be a problem in horse markets: since those can be traded in-play, there could have been periods of in-play trading in my data that could have affected the market-making bot's backtests (in particular, everyone else in the market is affected by the multisecond bet delay which I wasn't simulating).

But more importantly, why were the suspend times different? Was it an issue on Betfair's side? Was something wrong with my code? It was probably the latter. After meditating on more logfiles, I realised that the suspend times seen by Azura were correct whereas the suspend times for Sheogorath for the same markets were 1 minute off. They were making the same request, albeit at different times (Sheogorath would do it when building up a trading schedule, Azura would do it when one of its instances would get started). The only difference was that the former was written in Python and the latter was written in Scala.

After some time of going through my code with a debugger and perusing documentation, I learned a fun fact about timezones.

A fun fact about timezones

I used this bit of code to make sure all times the bot was handing were in UTC:

def parse_dt(dt_str, tz=None):
    return dt.strptime(dt_str, '%Y-%m-%dT%H:%M:%S.%fZ').replace(tzinfo=pytz.timezone(tz) if tz else None)

m_end_dt = parse_dt(m['marketStartTime'], m['event']['timezone'])
m_end_dt = m_end_dt.astimezone(pytz.utc).replace(tzinfo=None)

However, timezones change. Since pytz.timezone doesn't know the time of the timezone its argument refers to, it looks at the earliest definition of the timezone, which in the case of Europe/London is back in mid-1800s. Was the timezone offset back then something reasonable, like an hour? Nope, it was 1 minute.

Here's a fun snippet of code so you can try this at home:

In[4]: 
from datetime import datetime as dt
import pytz
def parse_dt(dt_str, tz=None):
    return dt.strptime(dt_str, '%Y-%m-%dT%H:%M:%S.%fZ').replace(tzinfo=pytz.timezone(tz) if tz else None)
wtf = '2017-09-27T11:04:00.000Z'
parse_dt(wtf)
Out[4]: datetime.datetime(2017, 9, 27, 11, 4)
In[5]: parse_dt(wtf, 'Europe/London')
Out[5]: datetime.datetime(2017, 9, 27, 11, 4, tzinfo=[DstTzInfo 'Europe/London' LMT-1 day, 23:59:00 STD])
parse_dt(wtf, 'Europe/London').astimezone(pytz.utc)
Out[6]: datetime.datetime(2017, 9, 27, 11, 5, tzinfo=[UTC])

And here's an answer from the django-users mailing group on the right way to use timezones:

The right way to attach a pytz timezone to a naive Python datetime is to call tzobj.localize(dt). This gives pytz a chance to say "oh, your datetime is in 2015, so I'll use the offset for Europe/London that's in use in 2015, rather than the one that was in use in the mid-1800s"

Finally, here's some background on how this offset was calculated.

Recovery

Luckily, I knew which exact days in my data were affected by this bug and was able to recover the right suspend times. In fact, I've been lying to you this whole time and all of the plots in this blog series were produced after I had finished the project, with the full and the correct dataset. So the results, actually, weren't affected that much and now I have some more confidence in them.

Conclusion

Next time on project Betfair, we'll teach DAFBot to place orders below £2 and get it to do some real live trading, then moving on to horses.

As usual, posts in this series will be available at https://kimonote.com/@mildbyte:betfair or on this RSS feed. Alternatively, follow me on twitter.com/mildbyte.

Interested in this blogging platform? It's called Kimonote, it focuses on minimalism, ease of navigation and control over what content a user follows. Try the demo here or the beta here and/or follow it on Twitter as well at twitter.com/kimonote!

project Betfair, part 5

@mildbyte 5 years, 5 months ago | programming | python | betfair |

Introduction

Previously on project Betfair, we started fixing our market-making bot so that it wouldn't accumulate as much inventory. Today, we'll try to battle the other foe of a market maker: adverse selection.

Order book imbalance

Consider the microprice from part 3: the average of the best back price and the best lay price, weighted by the volume on both sides. We had noticed that sometimes a move in the best back/lay can be anticipated by the microprice getting close to one or the other.

Let's quantify this somehow. Let's take the order book imbalance indicator, showing how close this microprice is to either the best back or the best lay: $$\frac{\text{BBVolume} - \text{BLVolume}}{\text{BBVolume} + \text{BLVolume}}$$ Can this predict price movements?

Oh yes it can. This graph plots the average move in the best back/lay quotes at the next tick (as in the next Betfair message on the stream), conditioned on the cumulative order book imbalance. In other words, the blue circles/crosses show the average move in the best lay/back quote, assuming the order book imbalance is above the given value, and the red markers show the same, but for order book imbalances below the given value.

For example, at order book imbalance values above 0.5 the average move in the best back/lay quotes in the next message is about 0.1 Betfair tick (this time I mean a minimum price move, like 1.72 to 1.73) and for order book imbalance values below -0.5 the average move in the best back/lay quotes is about -0.1 Betfair tick.

Essentially, at high negative or positive order book imbalance values we can say that there will be an imminent price move. There are several intuitive explanations to this phenomenon. For example, we can say that if aggressive trades happen randomly against both sides, the side with less volume offered will get exhausted earlier, hence the price will naturally move towards that side. In addition, if offers on a given side represent an intention to back (or lay), the participants on that side might soon get impatient and will cross the spread in order to get executed faster, the side with more available volume thus winning and pushing the price away from itself.

This effect is quite well documented in equity and futures markets and is often used for better execution: while it's not able to predict large-scale moves, it can help an executing algorithm decide when to cross the spread once we've decided what position we wish to take. For example, see this presentation from BAML — and on page 6 it even has a very similar plot to this one!

CAFBot with order book imbalance detection

This is a very useful observation, since that means the market maker can anticipate prices moving and adjust its behaviour accordingly. Let's assume that we're making a market at 1.95 best back / 1.96 best lay and the odds will soon move to 1.94 best back / 1.95 best lay. We can prepare for this by cancelling our lay (that shows in the book as being available to back) at 1.95 and moving it to 1.94: otherwise it would have been executed at 1.95 shortly before the price move and we would have immediately lost money.

So I added another feature to CAFBot: when the order book imbalance is above a given threshold (positive or negative), it would move that side of the market it was making by one tick. So, for example, let's again say that the current best back/lay are 1.94/1.95 and the order book imbalance threshold is set to be 0.5. Then:

• Order book imbalance < -0.5: large pressure from the lay side, make a market at back/lay 1.93/1.95
• Order book imbalance between -0.5 and 0.5: business as usual, make a market at back/lay 1.94/1.95
• Order book imbalance > 0.5: large pressure from the back side, make a market at back/lay 1.94/1.96

For now, I didn't use any of the inventory management methods I had described in the previous part (though there are some interesting ways they can interact with this: for example, could we ever not move our quotes at high imbalance values because an imminent price move and hence trades against us could help us close our position?). I did, however, keep the make-market-at-3-price levels feature.

Let's see how it did on our guinea pig market.

Results

So... it made money, but in a bad way. Having no inventory control made the bot accumulate an enormous negative exposure during the whole trading period: its performance only got saved by an upwards swing in odds during the last few seconds before it closed its position. In fact a 6-tick swing brought its PnL up £10 from -£6 to £4. Not very healthy, since we don't want to rely on general (and random) price moves: it as well could have stopped trading before that price swing and lost money. On the other hand, there's still the interesting fact of it having made money by generally being short in a market whose odds trended downwards (3.9 to 3.5), as in against its position.

Good news: the order book imbalance indicator kind of worked: here the same segment from part 3 is plotted, together with the bot's orders that got executed. You can see that where the old version would have had the price go through it, the new version sometimes anticipates that and moves its quotes away. In addition, look at the part shortly after 12:10 where the price oscillates between 3.65 and 3.55: since the microprice after the price move is still close to the previous level, the bot doesn't place any orders at 3.6.

However, the fact that we don't have inventory control in this version hurts the bot immensely:

Look at that standard deviation: it's larger than that of the first naive version (£3.55)!

CAFBotV2: a new hope

Let's put the insights from this and the previous part together and see if we can manage to make the bot not lose money. I combined the mitigation of inventory risk and adverse selection as follows: move the quote on one side away by one tick if either the order book imbalance is high enough or our exposure (inventory) is high enough. Effectively, if the bot would have moved its lay bet lower by 1 tick because of high negative order book imbalance (odds are about to move down) as well as because of high negative exposure (so the bot doesn't want to bet against even more), it would only move the lay bet by 1 tick, not 2.

On the other hand, let's assume there's a high negative order book imbalance but the bot has a large positive exposure. Should the bot still move its lay quote given that that quote getting hit would mean the bot would sell off a bit of its inventory? I reasoned that if the odds were about to move down, that would be good for the bot's profit (since odds going down is the same as implied probability going up, so being long benefits the bot) and in fact would allow it to offload its exposure at even lower odds later on.

So with that in mind, let's see how the brand new CAFBot does on our example horse racing market.

Look at it go. Basically a straight upwards line during the last 15 minutes and all of this while juggling its exposure back and forth like a champ. Beautiful. Let's take a look at the whole dataset.

Damn. At least it's losing less money than the version with moving the bot's quotes at high inventory values: in fact, twice as little (-£0.58 vs -£1.04).

Looking closer at what happened, looks like in some markets our fancy inventory control didn't work.

What happened here was that while the bot had a large long position and wasn't placing bets at the current best available lay, those bets were still matching as the prices would sometimes jump more than one tick at a time. The odds were violently trending upwards and so there weren't as many chances for the bot to close out its position.

How about if we get the bot to stop trading at all on one side of the book if its position breaches a certain level? While this makes the PnL distribution less skewed and slightly less volatile, it doesn't improve the mean much.

Greyhounds

Meanwhile in the greyhound racing market, things weren't going well either.

Examining the PnL closer

Back to horses again, is there some way we can predict the money the bot will make/lose in order to see if some markets are not worth trying to trade at all?

First of all, it doesn't seem like the PnL depends on the time of day we're trading.

The dataset is mostly UK and US horse races and the time is UTC. The UK races start at about 11am and end at about 7pm, whereas the US ones run from about 8pm throughout the night. There are some Australian races there, but there are few of them. In the end, it doesn't seem like the country affects our PnL either.

In addition, the money the bot makes isn't affected by the amount of money that's been matched on a given runner 15 minutes before the race start.

...and neither is the case for the amount of money available to bet on a given runner (essentially the sum of all volumes available on both sides of the book 15 minutes before the race start).

That's a curious plot, actually. Why are there two clusters? I was scared at first that I was having some issues with scaling in some of my data (I had switched to using integer penny amounts throughout my codebase instead of pounds early on), but it actually is because the UK races have much more money available to bet, as can be seen on the following plot.

CAFBotV3, 4, 5...

I also had tried some other additions to CAFBot that are not really worth describing in detail. There was the usual fiddling with parameters (different order book imbalance threshold values as well as the inventory values beyond which the bot would move its quotes) or minor adjustment to logic (for example, not moving the quotes at high order book imbalance values if getting that quote hit would help the bot reduce its exposure).

There was also Hammertime, a version of CAFBot that would move both back and lay quotes in case of high order book imbalance, in essence joining everybody else in hammering the side of the book with fewer offers. Theoretically, it would have taken a position (up to its position limit) in the direction that the market was about to move, but in practice the order book imbalance indicator isn't great at predicting larger-scale moves, so most of those trades would get either scratched out or end up as losses.

In addition, I had another problem, which is why I had started looking at whether it's possible to select markets that it would be better to trade in: submitting an order to Betfair isn't actually free. Well, it is, but only if one submits fewer than 1000 actions per hour, after which point Betfair begins to charge £0.01 per action. An action could be, for example, submitting a bet at a given level or cancelling it. Actions can't be batched, so a submission of a back at at 2.00 and a back at 2.02 counts as 2 actions.

This would be especially bad for CAFBot, since at each price move it has to perform at least 4 actions: cancelling one outstanding back, one outstanding lay, placing a new back and a new lay. If it were maintaining several offers at both sides of the book and the price moved by more than one tick, it would cost it even more actions to move its quotes. From the simulation results, running the bot for 15 minutes would submit, on average, about 500 actions to Betfair with a standard deviation of 200, which would bring it beyond the 1000-an-hour limit.

Meanwhile in Scala

Throughout this, I was also working on Azura, the Scala version of CAFBot (and then CAFBotV2) that I would end up running in production. I was getting more and more convinced that it was soon time to leave my order book simulator and start testing my ideas by putting real money on them. As you remember, the simulator could only be an approximation to what would happen in the real world: while it could model market impact, it wouldn't be able to model the market reaction to the orders that I was placing.

And since I was about to trade my own money, I would start writing clean and extremely well-tested code, right?

Conclusion

Next time on project Betfair, we'll learn how not to test things in production.

As usual, posts in this series will be available at https://kimonote.com/@mildbyte:betfair or on this RSS feed. Alternatively, follow me on twitter.com/mildbyte.

Interested in this blogging platform? It's called Kimonote, it focuses on minimalism, ease of navigation and control over what content a user follows. Try the demo here and/or follow it on Twitter as well at twitter.com/kimonote!

project Betfair, part 4

@mildbyte 5 years, 6 months ago | programming | python | betfair |

Introduction

Previously on project Betfair, we implemented a simple market making strategy and backtested it against some horse races, with disastrous results. Today, things get better.

Greyhounds

Though most of this has been done on horse racing markets, I was also experimenting on-and-off with greyhound racing. I'll be looking at those in depth later, but for now, some quick plots.

First, most action in greyhound markets happens way closer to the beginning of the race. Half of all the bets are matched less than a minute before the race starts!

In addition, the back-lay spreads are much, much wider than in horse markets. Even 2 minutes before start there can be 5 ticks between the best back and lay quote.

So how does the naive version of CAFBot do on these markets?

CAFBot results

Not that well. Looking at the odds chart for an example market, it seems like there are a lot of sporadic jumps where, sort of like in the example horse market from the previous post, the price goes "through" us (i.e. we're the last in the queue at a given price level to get our bet matched, after which that price level flips to the opposite side of the book).

Back to horses

Papers on market making

Like I had mentioned before, there are plenty of papers on market making. Despite that they're written with real-world (equity, futures etc) markets in mind, there are still a lot of things they investigate that can apply to this problem.

High-frequency market-making with inventory constraints and directional bets by Fodra, Labadie (2012) has a decent introduction to what a market maker does and what sort of controls it can have over its behaviour (together with some alarmingly large differential equations). It's based on an earlier paper: High-frequency trading in a limit order book by Avellaneda, Stoikov (2008) which had some very good presentation slides that I got some of the following ideas from. Finally, Exploring Market Making Strategy for High Frequency Trading: An Agent-Based Approach by Xiong, Yamada, and Terano has a nice overview of several market-making strategies.

Inventory risk

According to those papers, there are two risks a market maker faces. The first is inventory risk, which is what we had an issue with last time. If one side of a market maker's quotes gets executed more often than the other, it accumulates an inventory of shares (in the case of equity markets) and is no longer market-neutral (its profit is now dependent on price moves in the market).

There are two main ways to control our market maker: by specifying at what odds (or whether) it makes the market and the number of one-pound contracts it offers on each side. For example, if its exposure is getting too positive (it's backed a runner too much), it can either decrease its offers in size or offer other people to lay at higher odds, thus getting a higher premium from increasing its exposure even more. Managing inventory risk is essentially a trade-off: if we limit it to a minimum, we might miss out on earning the spread when there's not much price movement going on, whereas if we don't control it at all, we risk exposing ourselves to the market too much (having to liquidate our position in the end).

CAFBot with offer size decay

My first attempt at managing inventory risk was fairly simple: let's give the bot a maximum inventory it can have and size its quotes so that the amount it offers is scaled linearly from the full amount when it has no exposure down to 0 when it's at a maximum. For example, if the maximum amount of contracts it can offer is 10 and the maximum inventory it wants is 30:

• when it's 30 contracts short, offer 10 to buy and 0 to sell;
• when it's 15 contracts short, offer 10 to buy and 5 to sell;
• when it's neutral, offer 10 to buy and 10 to sell;
• when it's 15 contracts long, offer 5 to buy and 10 to sell;
• when it's 30 contracts long, offer 0 to buy and 10 to sell.

So, did it work?

Sort of. This is the PnL and position chart for the same market as in the previous post. It looks like the exposure management works: it's almost always bounded between -15 and +15 contracts. The profit has improved vastly (we now lose about £0.18 instead of £1.70 from the previous version), but this could be simply due to the fact that our average exposure is now smaller (on average -5 contracts) than that of the previous version (on average -65 contracts).

Running it on the full dataset we get this sad picture.

While the average profit increased, its standard deviation didn't decrease as much: the Sharpe ratio of this strategy is -0.91. To compare, the previous incarnation of CAFBot had a Sharpe ratio of -1.52 / 3.55 = -0.43.

Making a market at multiple odds

This was a small feature that I had there from the beginning, actually. The naive CAFBot from the previous post only ever has offers at two odds: the best back and the best lay. But consider this:

• Best available to back is 2.00, best available to lay is 2.02
• The prices move: best back is 2.02, best lay is 2.04
• We cancel both of our bets and replace them at the new odds
• The prices move back to 2.00/2.02. We replace our bets again.

What happened there at the 2.00 back level was that we had to cancel a bet and then replace it shortly after when the prices recovered, thus losing our position in the match queue. The addition I had was to maintain bets at several price levels: best back, 1 tick lower than the best back and 2 ticks lower than the best back (likewise for the lay side) etc. That meant, at a larger capital commitment, that the bot would still maintain its position in the queue if the prices changed for a bit. This doesn't actually require any more betting actions to do for a 1-tick move: instead of cancelling a bet at 2.00 and replacing it at 2.02 the bot would, say, cancel a bet at 1.99 and replace it at 2.02.

CAFBot with dynamic spreads

The papers also mention where to make the market as a way to control the inventory (some of them define it as a mid ± spread). Most of them use a solution to those differential equations in order to come up with an function defining the bid and ask to make a market at, but I decided not to go with that, since Betfair markets have varying granularities and spreads are usually already tight enough (in essence, anything that was more than a few ticks away from the best bid wouldn't have a chance to get matched anyway).

Instead, I used an idea from Avellaneda and Stoikov's presentation slides where their agent would move the quote by 1 tick on one side after it had accumulated a certain inventory. So, for example:

• We make a market at 2.00 best back / 2.02 best lay
• Our offer at 2.00 gets hit (we were offering to back, thus we've laid the market: we are now short)
• Instead of replacing the bet at 2.00, we now make the market at 1.99 best back / 2.02 best lay.

For my limit in this test, I used 30 contracts: with 10 contracts offered, that meant the bot would move the quote after its offer got matched 3 times on one side.

I also used the making market on several odds feature to not cancel bets unless the price moves too far away from them, placing bets at 3 levels on both sides of the book.

So, how did it do on our test market?

Results

Oooh. We finally started making money, kind of. Closer to the race beginning, as matched volumes picked up, the MTM shot up dramatically, albeit dropping as dramatically in the end. It still ended trading with about £0.60 of profit, which is pretty cool.

In addition, the average exposure was -6.6 contracts: in a market where the odds were trending down (they went from about 3.9 to 3.4, 10 ticks), the bot's exposure was against it (since the contract price, the inverse of the odds, went up) and yet it still made money. Hence the bot did manage to profit from the spread.

Finally, placing our bets on several levels helped too: on this plot, the bold green and red lines are price levels at which the bot had an offer. You can see it's often the case that a green/red line is not interrupted when the price moves slightly away from it, meaning the bot doesn't cancel a bet and lose its position in the queue. In fact, on the same market, but with only 1 bet on both sides, the bot would have made only £0.20.

Let's test it on the whole dataset now.

Not that good, actually. The Sharpe ratio is better than the previous version, but we lost more money on average. At least making a market at 3 price levels helped (below are the results for placing just 1 bet on each side).

So what happened? Let's take a look at the worst market we traded.

It's... choppy. The price is jumping all over the place and there are very few times when it doesn't move (which is where this strategy really shines). There are, on the other hand, many points where the price goes "through" the bot's bet, resulting in it having an opposite exposure to the way the price went.

Looking closer, we can see how wild this market is: in the span of 90 seconds the odds crashed from 1.80 down 10 ticks to 1.70 and then back up again. In addition, in the first 30 seconds the best back/lay oscillated between 2 levels and the bot would diligently follow it, getting executed at 1.79 and then having its position closed at the same or worse price.

So all in all, while inventory control does help the bot not place too many directional bets, it still doesn't help it make money.

Adverse selection

The second risk a market maker faces is adverse selection, the risk from information asymmetry. Someone who does cross the spread gets the benefit of choosing when their order gets executed, whereas a market maker simply posts orders and doesn't have any control over when or whether they will get hit. This creates a bias in favour of the person trading against the market maker: what if some of them are crossing the spread because they know the market is going to move, as in, they're informed traders?

Let's say there's been some sudden bad news from Apple during trading hours and people start selling Apple shares. A naive market maker that doesn't know what's happening will continue offering to buy them despite that the market clearing price will very soon move down. In the case of Betfair markets, perhaps there can be a macro-level trend (even if the trend is a self-fulfilling prophecy) that the market maker doesn't take into account and more slower traders do, thus trading in a way that perpetuates the trend.

So is there a way to protect ourselves against that? What if the bot could somehow anticipate imminent price movements that might hurt it if it has an exposure to the market and move its quotes or liquidate its position? Perhaps it can.

Conclusion

Next time on project Betfair, we'll delve deeper into market microstructure and find out that at a very micro level, markets sometimes aren't as unpredictable as we thought.

As usual, posts in this series will be available at https://kimonote.com/@mildbyte:betfair or on this RSS feed. Alternatively, follow me on twitter.com/mildbyte.

Interested in this blogging platform? It's called Kimonote, it focuses on minimalism, ease of navigation and control over what content a user follows. Try the demo here and/or follow it on Twitter as well at twitter.com/kimonote!

project Betfair, part 3

@mildbyte 5 years, 6 months ago | programming | python | betfair |

Introduction

Previously on project Betfair, we started collecting dumps of Betfair order book data from the Stream API and learned how to reconstruct series of events from those with the aim of using them to backtest a market making strategy.

Today, things get messy.

Insights into the data

As a market maker, our main source of profit should be our orders getting matched, and not us having a directional view (as in betting on which way the odds will move). Hence it's worth investigating how volumes of matched bets vary as the beginning of the race approaches.

Total matched volume

I took the total bet volumes matched on each race through time, starting from 3 hours before the race, and normalized them by diving by the final total volume just before the scheduled race start time (essentially getting the cumulative fractions of the total matched volumes). There are 24 races in this dataset: I now have quite a few more, but their recording is started much closer to the kick-off, and you'll soon see why.

As you can see, bet matching in pre-race horse trading follows a power law. About half of the total bet volume is matched 10 minutes before the race begins, and 80% of all betting happens within 50 minutes from the race start. Note this doesn't include in-play betting where I guess this gets even more dramatic.

Hence there's not much point doing market making earlier than about 15 minutes before the race. Or perhaps could it be that the reason nobody is trading is that the costs are too high?

Back-lay spreads

I plotted the average back-lay spreads through time, and it doesn't seem so. The spreads here are in Betfair ticks: the smallest one is 1 (corresponding to, say, best available back odds of 1.72 and best lay odds of 1.73, or best back at 2.50 and best lay at 2.52). Even 3 hours before the race begins, the spreads, on average, are as tight as they can be.

Design

One useful thing about way the Betfair Stream API is designed is that with the tools given to us, we can maintain a state of the order book in our program as well as our own orders. It's essentially like having the data from API-NG available to us at all times, with notifications when it gets updated.

I decided to split the market-making bot into two parts.

The core would be given the current state of the order book and output the amount of one-pound contracts that it wanted to be offering at both sides of the book, together with the odds. The core's operation would be independent of what's happening to our outstanding orders: if we already have a back bet in the book and the core of the strategy wants to be offering the same amount, then no actions would be produced.

Reconciling the core's wishes with the actual state of our orders would be the execution harness' job. Given the desired offers we wish to maintain on both sides of the book and the state of our orders, it would produce a sequence of cancellations and order placements and submit them to Betfair.

Since all of these inputs (the state of the order book and all of our orders) are actually given to us by the Betfair Stream API, this has a neat bonus of behaving in a consistent way if the bot, say, crashes: we can just start it up again and the API will helpfully give us back all our outstanding orders and positions (not that it's a good idea to blindly trust it). Polling the strategy to find out what actions it wants to perform can be done at any point in time: on a schedule or, say, whenever a new event arrives from the Betfair stream.

So the whole strategy would look something like this:

• When a new event arrives:
  • Incorporate it into our cached state of the order book and our orders (Betfair even have a guide here).
  • Give the order book to the core, request the amount of contracts it wants to offer and the odds (prices).
  • On both sides of the book, compare our current outstanding orders and what the core wants to do. For every price level, if what the core wants to offer is different from what we are offering with our outstanding orders:
    • If the core wants to offer more, submit an order placement for the difference.
    • If the core wants to offer less, take a list of our outstanding orders at that price level (since there might be several) and start cancelling them, newest first (since they're the least likely to get matched) until we reach the desired volume.

There are some operational issues with this (such as Betfair not usually allowing bet placements below £2), but this is a good general platform to build upon and definitely good enough to start simulating.

Backtester

With an order book simulator already built, augmenting it to inject strategy events is fairly easy. Let's say the simulator operates by maintaining a timestamped event queue (where the events are either placing a bet or cancelling one). We add another event type at given intervals of time (say, 100ms): when the backtester sees it, it gives the current order book and the state of the strategy's orders to the strategy, gets its actions from it and then inserts them back into the queue.

To simulate the delay between us and the exchange, the events are timestamped slightly into the future (say, 75ms) so the simulator might not get to apply player orders to the book immediately and may have to handle other orders before that.

In addition, I got the backtester to record various diagnostics about the strategy every time it polled it, such as how many contracts (actually matched bets) it owned, when its orders got matched and whether the matches were passive (initiated by someone else) or aggressive (initiated by the strategy) etc.

Meet CAFBot

There will also be a DAFBot at some point. This was a very early version. It's fairly different to what I actually ran to make the following plots, but the general idea is the same. I also moved the whole codebase to using integer penny amounts instead of floats soon after this commit.

Overview

It was time to find something to plug into the backtester. I decided to first go with the most naive approach: the core would look at the current best back and lay offers and then offer 10 one-pound contracts (recall that this results in a bet of £10 / odds) on both sides.

Since the execution harness compares the desired offers with the current outstanding bets, that would mean when the strategy was started, it would first place those two bets and then do nothing until at least one of them got fully or partialy matched, at which point it would add back to the bet to maintain the desired amount. If the market were to move (the best back/lay offers changed), the strategy would cancel the orders and replace them at the new best bid/offer.

Finally, 15 seconds before the race start, the strategy would aggressively unload its accumulated exposure (say, if more of its back bets were matched than the lay bets) by crossing the spread (and not waiting to get matched passively).

In terms of markets, I would simulate it from 1 hour before the beginning of the race, running it only on the favourite horse (the one with the lowest odds at that point).

With that in mind, I managed (after a few days of debugging) to simulate it on a few races. So, how did it do?

Backtest results

Here's a result from one race:

Well, this is not looking great.

To explain that plot, the red line is the strategy inventory, or position: how many one-pound contracts it's currently holding. For example, with a position of -170, the strategy will lose £170 if the runner we're trading wins (and £0 if it loses, but in any case we get to keep the money we got from selling the contract). The blue line is the mark-to-market of the strategy: how much money we would make/lose if we were to liquidate our position immediately by crossing the spread, like we do in the last 15 seconds before the race begins.

This is obviously just one race, but surely with an HFT strategy we would expect more consistent profit even within one race? For example, Greg Laughlin of the WSJ did a small investigation into the trading of Virtu, an HFT firm, from their abandoned IPO filings, and showed that with a 51% percentage of profitable trades and about 3 million trades a day their chance of having a losing day was negligible.

But we're not making that many trades here and so perhaps this could be a statistical fluke. It's a good thing I now have all the other race data, collected during further experiments, to check this against.

Nope. Running this against 104 races (albeit with 15 minutes of trading, since the latter datasets I collected were shorter), we can see that the bot has systematic issues and loses, on average, £1.52 per race.

So what happened in the first plot? It looks like we had a fairly chunky short exposure (betting against) throughout the trading. At its worst we were short 175 contracts, which is 17 times more than what we were offering to trade. So there was an imbalance in terms of which side of our offering was getting executed.

Investigating further...

As you can see from the odds plot, the price of the contract (inverse of the odds) trended upwards throughout the final hour before the race, with a few range-bound moves closer to the start. That explains us losing money and also kind of explains us selling too many contracts: in a trending market, there would be more matching on one side of the book, hence a naive strategy that doesn't account for that would quickly get out of balance. Or at least that's what it looks like. There are many ways to read this.

This is the previous plot, but zoomed in towards the part where we lost money the fastest. The orange line shows the best available lay odds and the blue one is the back odds (both of which are where our simulated bot also puts its bets).

The green line in the middle is the volume-weighted average price, or the microprice. It's calculated as follows: $$ \text{VWAP} = \frac{\text{BBPrice} \times \text{BLVolume} + \text{BLPrice} \times \text{BBVolume}}{\text{BBVolume} + \text{BLVolume}} $$

Essentially, if the volume of available bets on one side is bigger, then that side kind of pushes the microprice towards the opposite side. It's a good way to visualize order book imbalance and, interestingly, in that plot, sometimes a move in the actual best back/lay odds can be anticipated by the microprice moving towards one side or the other. We'll look into that later.

The crosses are the bot's orders getting executed: red means the back offer got executed (thus the bot has secured a lay bet and is now more short the market) and green means the lay offer got executed. The dots are the same, but for other people's orders.

What's strange here is that our orders often get hit shortly before there's a price move against us: for example, in the beginning, just before the best back moves from 3.80 down to 3.75 (this is still a 1-tick move), you can see several executions of the bot's back orders, with the bot quickly replacing them several times in between executions. In essence, it's sort of trying to "hold the line" against a market move, but ultimately fails and ends up with having bet against the market whilst the odds managed to move through it. Well, at least we know it's a market move in hindsight: perhaps more people could have joined the bot on its side and maintained the price.

Essentially, the bot does well during times when there's a lot of matching going on on both sides of the book and the price isn't moving. This happens, for example, for a few minutes around 12:30:

But even in this case, this doesn't look too inspiring: the initial 1-pound jump in the PnL at 12:29 is because of the odds moving up and us having a short exposure. The actual market-making part between 12:29 and 12:33 only makes about £0.10.

So in the end, looks like it's back to the drawing board.

Conclusion

Not all was lost, obviously. I had a backtesting engine, a half-working strategy (in that it didn't immediately start bleeding money) and I had an idea of what was going wrong and some possible ways to fix it. And obviously no real money had suffered yet in the making of this.

Next time on project Betfair, we'll start reading some actual papers on market making and tinkering with the bot in attempts to make it lose less money. Perhaps I'll tell about what was happening to the Scala version (that would later supposedly be a production version of this thing) as well. Stay tuned!

As usual, posts in this series will be available at https://kimonote.com/@mildbyte:betfair or on this RSS feed. Alternatively, follow me on twitter.com/mildbyte.

Interested in this blogging platform? It's called Kimonote, it focuses on minimalism, ease of navigation and control over what content a user follows. Try the demo here and/or follow it on Twitter as well at twitter.com/kimonote!

project Betfair, part 2

@mildbyte 5 years, 6 months ago | programming | python | betfair |

Probably the hardest thing about writing this will be piecing together what I was doing and thinking at the time. Keeping a development diary was a great idea, it's just a shame I started it 1/3 of the way into the project and the rest is in various commit messages.

I would never have been able to get away with these commit messages at my previous job.

In any case, I started with how everything starts: gathering data.

Attempt 1: Betfair API-NG

Good news: Betfair has some APIs. Bad news: it costs £299 to access the API. Better news: I had already gotten an API key back in 2014 when it was free and so my access was maintained.

The first Betfair API I used is called API-NG. It's a REST API that allows to do almost everything the Web client does, including getting a (live or delayed) state of the runner order book (available and recently matched odds), getting information about given markets and runners, placing actual bets or getting the account balance.

Collecting order book data

Since naming things is one of the hard problems in computer science, I decided to pick the Daedric pantheon from The Elder Scrolls to name components of my new trading system, which would be written in Python for now.

• Hermaeus, "in whose dominion are the treasures of knowledge and memory". Hermaeus is a Python script that is given a Betfair market ID and a market suspend time (when the market's outcome becomes known) as well as a sample rate. When started, it repeatedly polls the REST API at the given sample rate to get the order book contents for all runners and dumps those into a PostgreSQL database.
• Meridia, "associated with the energies of living things". Meridia reads the Betfair market catalogue (say, all horse races in the UK happening today, their starting times and market IDs) and schedules instances of Hermaeus to start recording the data a given amount of time from the market getting suspended.
• Hircine, "whose sphere is the Hunt, the Sport of Daedra, the Great Game (which I have just lost), the Chase". Hircine would be the harness for whatever strategy I would decide to run: when executed on a given market, it would read the data collected by Hermaeus and output the desired number of OPCs we wished to hold.

This was pretty much where I paused the design process: downstream of Hircine we would have some sort of a component that would determine whether to place a bet on a given market, but I didn't want to make a decision on what would happen later, since I wanted my further design decisions to be driven by looking at the data and seeing what would and wouldn't work.

I had decided to concentrate on pre-race greyhound and horse markets. Pre-race markets somehow still have dramatic odds movements (despite that there's no information becoming known that would affect the race outcome), however odds don't move by more than 1-2 ticks at a time (unlike football, where a goal can immediately halve the implied probability for some markets, like the Correct Score market). In addition, in-play markets have a bet delay of 1-10 seconds depending on the sports type, whereas for the pre-race markets the submitted bet appears in the order book immediately.

In terms of numbers, there are about 30 horse races in the UK alone on any given day (and those usually are the most liquid, as in, with a lot of bets being available and matched, with action starting to pick up about 30 minutes before the race begins) and about 90 greyhound races (those are less liquid than horses with most of the trading happening in the last 10 minutes before the race begins).

What to do next?

Now, I could either beat other people by making smarter decisions — or I could beat them by making dumb decisions quicker. I quite liked the latter idea: most high-frequency trading strategies are actually fairly well documented, I imagined that "high frequency" on Betfair is much, much slower than high frequency in the real world, and making software faster is better-defined that making a trading model make more money.

And, as a small bonus, trading at higher granularities meant that I didn't need as much data. If my strategy worked by trying to predict, say, which horse would win based on its race history or its characteristics, I would need to have collected thousands of race results before being able to confidently backtest anything I came up with. In a higher frequency world, data collection would be easier: there's no reason why the microstructure of one horse racing market would be different from another one.

The simplest one of those strategies would be market making. Remember me lamenting in the previous post that buying a contract and immediately selling it back results in a ~0.5% loss because of the bid-offer spread? As a market maker, we have a chance of collecting that spread instead: what we do is maintain a both buy (back) and a sell (lay) order in hopes that both of them will get hit, resulting in us pocketing a small profit and not having any exposure, assuming we sized our bets correctly. It's a strategy that's easy to prototype but has surprising depth to it: what if only one side of our offer keeps getting matched and we accumulate an exposure? What odds do we quote for the two bets? What sizes?

With that in mind, I realised that the way I was collecting data was kind of wrong. The idea of the strategy output being the desired position at a given time is easily backtest-able: just multiply the position at each point by the price movement at the next tick and take the cumulative sum. The price in this case is probably the mid (the average of the back and the lay odds) and for our cost model we could assume that we cross the spread at every trade (meaning aggressively take the available odds instead of placing a passive order and waiting to get matched).

Sadly, this doesn't fly with a market-making strategy: since we intend to be trading passively most of the time, we have to have a way to model when (or whether: while we're waiting, the price could move underneath us) our passive orders get matched.

How an order book works

If we have to delve into the details of market microstructure, it's worth starting from describing how a Betfair order book actually works. Thankfully, it's very similar to the way a real exchange order book works.

When a back (lay) order gets submitted to the book, it can either get matched, partially matched, or not matched at all. Let's say we want to match a new back (lay) order N against the book:

• take the orders at the opposite side of the book: lay (back).
• look at only those that have higher (lower) odds than N.
• sort them by odds descending (ascending) and then by order placement time, oldest first.
• for each one of these orders O, while N has some remaining volume:
  • if N has more remaining volume than O, there's a partial match: we decrease N's remaining volume by O's volume, record a match and remove O from the book completely.
  • if N has less remaining volume than O, we decrease O's remaining volume by N's remaining volume, record a match and stop.
  • if both volumes are equal, we remove O from the book, record a match and stop.
• if N has any remaining volume, add it to the order book.

It's easy to see that to get our passive order matched, we want to either offer a price that's better than the best price in the book (highest odds if we're offering a back (laying) or lowest odds if we're offering a lay (backing)) or be the earliest person at the current best price level. One might think of matching at a given price level as a queue: if we place a back at 1.70 (thus adding to the available to lay amount) and there is already £200 available at that level, we have to wait until that money gets matched before we can be matched — unless while we are waiting, the best available to lay odds become 1.69 and so we'll have to cancel our unmatched bet and move it lower.

So how do we use this knowledge to backtest a market-making strategy? The neatest way of doing this that I found was taking the order book snapshots that I collected and reconstructing a sequence of order book events from it: actions that take the order book from one state to the next one. Those can be either back/lay order placements (possibly triggering a match) or cancellations. If these events were to be be plugged back into the order book simulator, we would end up with order book states that mirror exactly what we started with.

However, if we were to also insert some of our own actions in the middle of this stream, we would be able to model the matching of passive orders: for example, if the best available lay at a given point in time was 1.70 and we placed an order at the better odds (for others) at 1.69, all orders in the event stream that would have matched at 1.70 would now be matching against our new order, until it got exhausted. Similarly, if a new price level was about to be opened at 1.69 and we were the first order at that level, all orders would be matching against us as well.

Inferring order book events

So I set out to convert my collected snapshots into a series of events. In theory, doing this is easy: every snapshot has the odds and volumes of available back and lay bets, as well as the total amount traded (matched) at each odds. So, to begin, we take the differences between these 3 vectors (available to back, available to lay, total traded) in consecutive snapshots. If there's no traded difference, all other differences are pure placements and cancellations without matches. So if there's more available to back/lay at a given level, we add a PLACE_BACK/PLACE_LAY instruction to the event stream — and if there's less, we add a CANCEL_BACK/CANCEL_LAY instruction for a given amount. Since we don't know which exact order is getting cancelled (just the volume), the order book simulator just picks a random one to take the volume away from.

Things get slightly more tricky if there's been a trade at a given odds level. If there's only been one order book action between the snapshots, it's fairly easy to infer what happened: there will be a difference in either the outstanding back or lay amounts at those odds, meaning there was an aggressive back/lay that immediately got matched against the order. Sometimes there can be several odds levels for which there is a traded amount change — that means an order was so large that it matched against orders at several odds. After the traded amount differences are reconciled, we need to adjust the available to back/lay differences to reflect that and then proceed as in the previous paragraph to reconcile unmatched placements/cancellations.

There was a problem with the data I collected, however: API-NG limits the number of requests to it to about 5 per second. Worse even, despite that I was making about 3 requests per second, the API would still sometimes throttle me and not give back an HTTP response until a few seconds later. This meant that order book snapshots had more than one event between them and in some cases there were way too many possible valid sets of events that brought the order book from one state to the other.

Thankfully, a slightly more modern way of getting data was available.

Attempt 2: Betfair Exchange Stream API

Unlike its brother, API-NG, the Exchange Stream API is a push API: one opens a TCP connection to Betfair and sends a message asking to subscribe to certain markets, at which point Betfair sends back updates whenever an order placement/cancellation/match occurs. Like its brother, the Stream API uses JSON to serialise data as opposed to a binary protocol. Messages are separated with a newline character and can be either an image (the full order book state) or an update (a delta saying which levels in the order book have changed). The Stream API can also be used to subscribe to the state of user's own orders in order to be notified when they have been matched/cancelled.

This was pretty cool, because it meant that my future market making bot would be able to react to market events basically immediately, as opposed to 200ms later, and wouldn't be liable to get throttled.

Here's an example of a so-called market change message:

{"op":"mcm","id":2,"clk":"ALc3AK0/AI04","pt":1502698655391,"mc":[
    {"id":"1.133280054","rc":[
        {"atb":[[5.7,5.7]],"atl":[[5.7,0]],"trd":[[5.7,45.42]],"id":12942916}]}]}

This one says that in the market 1.133280054, we can't bet against (lay) the runner 12942916 at odds 5.7, but instead can bet up to £5.70 on it. In addition, now the total bets matched at odds 5.7 amount £45.42 (actually it's half as much, because Betfair counts both sides of the bet together). In essence, this means that there was an aggressive lay at 5.7 that got partially matched against all of the available lay and £5.70 of it remained in the book at available to back, basically moving the market price.

As for the other parts of the message, pt is the timestamp and clk is a unique identifier that the client at subscription time can send to Betfair to get the whole market image starting from that point (and not from the point the client connects: this is used to restart consumption from the same point if the client crashes).

Another program had to be added to my Daedric pantheon. Sanguine, "whose sphere is hedonistic revelry, debauchery, and passionate indulgences of darker natures", would connect to the Stream API, subscribe to the order book stream for a given market and dump everything it received into a text file. It was similar to Hermaeus, except I had given up on creating a proper schema at this point to store the data into PostgreSQL (and even in the case of Hermaeus it was just the metadata that had a schema, the actual order book data used the json type). Still, I was able to schedule instances of it to be executed in order to record some more stream data dumps.

And indeed, the data now was much more granular and was actually possible to reconcile (except for a few occasions where some bets would be voided and the total amount traded at given odds would decrease).

Here's some code that, given the current amounts available to back, lay and traded at given odds, as well as a new order book snapshot, applies the changes to our book and returns the events that have occurred.

def process_runner_msg(runner_msg, atb, atl, trds):
    events = []

    # represent everything in pennies
    back_diff = {p: int(v * 100) - atb[p] for p, v in runner_msg.get('atb', [])}
    lay_diff = {p: int(v * 100) - atl[p] for p, v in runner_msg.get('atl', [])}
    trd_diff = {p: int(v * 100) - trds[p] for p, v in runner_msg.get('trd', [])}

    for p, v in trd_diff.iteritems():
        if not v:
            continue
        if v < 0:
            print "ignoring negative trade price %f volume %d" % (p, v)
            continue

        if p in back_diff and back_diff[p] < 0:
            back_diff[p] += v / 2  # betfair counts the trade twice (on both sides of the book)
            atb[p] -= v / 2
            trds[p] += v
            events.append(('PLACE_LAY', p, v / 2))
        elif p in lay_diff and lay_diff[p] < 0:
            lay_diff[p] += v / 2
            atl[p] -= v / 2
            trds[p] += v
            events.append(('PLACE_BACK', p, v / 2))
        elif p in back_diff:
            back_diff[p] += v / 2
            atb[p] -= v / 2
            trds[p] += v
            events.append(('PLACE_LAY', p, v / 2))
        elif p in lay_diff:
            lay_diff[p] += v / 2
            atl[p] -= v / 2
            trds[p] += v
            events.append(('PLACE_BACK', p, v / 2))
        else:
            print "can't reconcile a trade of %d at %.2f" % (v, p)

    # these were aggressive placements -- need to make sure we're sorting backs (place_lay) by price descending
    # (to simulate us knocking book levels out) and lays vice versa
    events = sorted([e for e in events if e[0] == 'PLACE_LAY'], key=lambda e: e[1], reverse=True) + \
             sorted([e for e in events if e[0] == 'PLACE_BACK'], key=lambda e: e[1])

    for p, v in back_diff.iteritems():
        if v > 0:
            events.append(('PLACE_BACK', p, v))
        elif v < 0:
            events.append(('CANCEL_BACK', p, -v))
        atb[p] += v

    for p, v in lay_diff.iteritems():
        if v > 0:
            events.append(('PLACE_LAY', p, v))
        elif v < 0:
            events.append(('CANCEL_LAY', p, -v))
        atl[p] += v

    return events

Parallel to this, I was also slowly starting to implement an Exchange Stream API client that would subscribe to and handle market change messages in Scala. This contraption, named Azura (whose sphere is "the period of transition and change"), would form the base of the actual live market making bot and/or any other trading strategies that would use the Stream API.

Conclusion

Next time on project Betfair, we'll start implementing and backtesting our market making bot, as well as possibly visualising all the data we collected.

As usual, posts in this series will be available at https://kimonote.com/@mildbyte:betfair or on this RSS feed. Alternatively, follow me on twitter.com/mildbyte.

Interested in this blogging platform? It's called Kimonote, it focuses on minimalism, ease of navigation and control over what content a user follows. Try the demo here and/or follow it on Twitter as well at twitter.com/kimonote!

Let's go on a treasure hunt!

@mildbyte 5 years, 10 months ago | programming | games | python | telegram | bots |

Chatbots are basically a clunky commandline interface to things that sometimes really need a custom UI.

But what if I do want to make something that uses some of the features (a GPS receiver, a camera, a microphone) that a modern phone has? I'm too lazy to write device-specific code and dig around in the intrinsics of Android/iOS APIs.

So after doing some research on modern messenger apps (I kind of fell behind on what was going on after the WhatsApp acquisition and turns out billions more have popped up since then) I stumbled upon the Telegram bot API. And it's actually pretty simple. In a nutshell, you create a bot (by messaging another bot) which gives you a token. The token is the only thing your bot needs to communicate with the Telegram servers (so no coding up handshakes or managing session keys): it makes up your REST endpoint that you can throw queries at. The connection is over SSL, so that takes care of your ISP or a kid with a WiFi dongle and Wireshark grabbing hold of your token. Bot chats aren't end-to-end encrypted though, so Telegram are still able to read whatever you talk to the bot about.

With that in mind, receiving messages is easy: just shoot a GET request at https://api.telegram.org/bot(TOKEN)/getUpdates (reference) and it will come back with a JSON-serialised list of events (message sent, message edited etc) that happened to your bot. Each one has a unique sequence number which you can use to seek around in the update log (to say get updates only starting from the last one you processed). Updates related to messages have in them a chat ID identifying your conversation with a given user -- and you include that chat ID in your POST requests to https://api.telegram.org/bot(TOKEN)/sendMessage (reference) in order to send messages back to that user.

You can also send around various other things besides text messages, like locations (latitude-longitude pairs), photos (your bot gets some links to various-sized thumbnails of the photo), contacts etc.

So I managed to write Indiana, a treasure hunt bot that comes up with a random location inside Hyde Park (well, the rectangle whose all 4 points lie within Hyde Park and yes, that means it can sometimes put the treasure in the water or in some restricted areas and I take no responsibility for you ending up there) and, when sent a location, replies back with a rough estimate of how far the treasure is. Sort of like Pokemon Go without having to lug around an extra power pack. Note you also can send the bot a manual location -- it can't distinguish between that and a physical location read from GPS (thankfully).

project Morrowind, part 7

@mildbyte 5 years, 10 months ago | programming | games | morrowind | python |

So that you don't think that the 1-year delay in posting part 6 was due to me manually drawing the population heatmaps in Paint, I finally split the code I used to produce all the plots into a set of modules and uploaded them to GitHub. You'll need the usual scientific Python stack (NumPy, SciPy, matplotlib as well as PIL) and a C++ compiler. Since I wasn't sure if it's a good idea to post the game data dump that I produced, you'll have to make it yourself: you'll need the original Morrowind.esm data file and Enchanted Editor (instructions on how to produce the dump are in the README).

With all that in mind, I've run the code end-to-end and it spit out a similar set of images to what I have on the blog, which makes me incredibly happy.

Now it's time to get back to Cookie Clicker!

project Morrowind, part 6

@mildbyte 5 years, 10 months ago | programming | games | morrowind | python |

I told you I'd be back in a year's time.

With Aryon safe back in his tower and with all inhabitants of the island maximising the efficiency of their travel, it was time to approach a new challenge and create some more pretty pictures. The next question was simple: where the hell are all the people and what do they do?

Let's try and use our cool matrix that converts in-game coordinates to coordinates on a map to its full extent and create some sort of a population heatmap. This isn't difficult to do since we already have all the pieces of the puzzle: we know where all the NPCs are located and what their occupation, race and gender are. The only problem is dealing with NPCs that are in the interior: remember how interiors are completely separate mini-worlds? This means that we can't simply infer someone's location in the exterior by taking the coordinates of the two doors and adding up an offset of the NPC from the door, since interiors often are bigger on the inside than what they look like from the outside. Since we'd only be looking at a world-scale overview, I decided not to bother with precision: the actual exterior location of an NPC is simply the location of the closest exterior door they can get to (by number of cells they have to traverse to get outside).

Armed with these tools, I went through all the NPCs in the world, getting their exterior location, and converted that location into coordinates on the map. I had a map-sized matrix where I accumulated those coordinates: the number at each pixel was the number of NPCs whose exterior coordinates fell within that square. This meant that I'd get disproportionately large amounts of people piling up at the doors of densely-populated interiors, which wasn't optimal as it was difficult to see on the image (after all, it's just one pixel) and wasn't representing the in-game reality well: after all, we are interested in the population in a given city/region and people don't really stand in one spot either, instead roaming around.

Hence I applied a Gaussian blur to my matrix so that instead of 10 people assigned to one pixel we'd be looking at something like 2.2 people on that pixel, 1.1 people one pixel away, 0.5 people 2 pixels away etc. If this feels like chopping people into parts and throwing those body parts around so they form a nice hill, it's because it kind of is.

With that out of the way, I normalised the matrix so that all values were between 0 and 1, applied one of the numerous colormaps that matplotlib has (I quite liked the one called blues) and blended it with the original map. I also toyed around with applying a transfer function to the inputs before pushing them into the colormap since I didn't like the way it looked by default -- I chose a logistic function:

\[ f(t) = \frac{1}{1 + e^{-k(t-c)}} \]

I didn't really have a methodology here: varying $k$ changes the steepness of the curve (how quickly things go from the left side of the colormap to the right side, getting brighter) and varying $c$ changes where it's centered, so I tinkered with them for each picture until it looked good.

With that in mind, let's see what we ended up with!

draw_npcs(filter_sigma=25, sigmoid_k=8, sigmoid_c=0.2, output='map_population.png') (full)

We get dark blobs in large population centres like, bottom to top, Vivec (and Ebonheart next to it), then Balmora (southwestern part of the island), Sadrith Mora (far east), Ald'ruhn (north of Balmora) and Gnisis (northwest of Ald'ruhn). There are also some minor places highlighted around -- these are either smaller settlements or larger dungeons/strongholds/shrines.

What else can we do with it? How about mapping out all the Dark Elves? Easy, just don't go through all the NPCs:

draw_npcs(filter_sigma=25, mark_npcs=[n for n in npcs if n.race == 'Dark Elf'], sigmoid_k=8, sigmoid_c=0.2, output='map_population_darkelf.png') (full)

Yes, it looks just like the population heatmap. How about seeing where they are overrepresented or underrepresented? We can divide the two overlays by one another to essentially get fractions of Dark Elves amongst the population:

draw_npcs(relative=True, filter_sigma=50, mark_npcs=[n for n in npcs if n.race == 'Dark Elf'], sigmoid_k=4, sigmoid_c=0.5, output='map_population_darkelf_relative.png') (full)

I did have to play around with the parameters for this one (increasing the blur radius and moving the centre of the sigmoid to 0.5), but we can sort of see how the Dark Elves (natives of Morrowind) are less represented in the southwestern part of the island (which is more cosmopolitan and welcoming towards foreigners) and more represented in the eastern territories as well around the Ashlander camps (which almost completely consist of them).

What else can we do? Morrowind has slavery! Let's find out where all the slaves are concentrated:

draw_npcs(relative=True, filter_sigma=25, mark_npcs=[n for n in npcs if n.class_name == 'Slave'], sigmoid_k=8, sigmoid_c=0.2, output='map_population_slave_relative.png') (full)

No blobs around big cities and towns -- which makes sense since this is a relative fraction. Instead what we have highlighted for us are random dungeons and plantations around the world where slaves are held, including Abebaal Egg Mine or Dren Plantation or some slave markets or Rotheran or Hlormaren (interestingly, for the latter the blob (west of Balmora by the sea) is west of the actual stronghold -- this is because the slaves are held in sewers from where the exit is around there).

Of course we would never use this tool for our own selfish purposes:

draw_npcs(relative=True, filter_sigma=50, mark_npcs=[n for n in npcs if n.is_female], sigmoid_k=12, sigmoid_c=0.7, output='map_population_female_relative.png') (full)

There are very few places on the island where females are overrepresented (note I set the centre of the sigmoid at 70%) -- the only one of them that's a town is Tel Mora in the northeast. That's because the councilor of that town "does not enjoy the presence of men" and all residents of that town are indeed women. Another place is Odirniran in the southeast, a Telvanni stronghold under attack by House Hlaalu. Northwest of that we have Assu with two sorceresses and north of that is Tel Uvirith -- a stronghold that gets built for the player as part of the Telvanni questline. It's disabled at the start of the game (and is invisible), but the scraper obviously didn't care about that.

Next year on project Morrowind, I promise I'll actually get around to cleaning up the source code that was used to make all this and releasing it. Promise.

project Morrowind, part 5

@mildbyte 6 years, 10 months ago | programming | games | morrowind | python |

Look what I found in my drafts folder. Welcome back to project Morrowind.

The nice visualization of where Aryon could be was very close now. I went with the stupidest approach: go through all pixels on the map, convert each one into a point in the game world and find how long it would take Aryon to get there (by using the method I mentioned previously: go through all points in the graph we know the shortest travel time to and find the one for which the total travel time (shortest time to travel to that point + time to walk from that point to the destination) is the smallest).

Except I forgot this was Python and I was going to go through, for each point on the map, about 2400 possible routes through exterior points. And there were 1650x1900 = about 3 million points. Sure, I could be smart about it and use various optimisations (like coalescing exterior points that are close enough to each other and treating them as one or exploiting the triangle inequality (as mentioned in the previous post) or looking at 2x2 blocks on the map instead of each pixel or using all 4 cores of my CPU instead of one). Or I could farm it out to a C++ program.

So I dumped the list of known exterior coordinates and times of the shortest routes to those to a file as well as the in-game coordinates of the 3-ish million points on the map I was interested in. The program would take those and spit out, for each sought coordinate, the shortest time it would take for Aryon to get there from his tower. In fact, it took 40 lines and ran in about 10 seconds. It's pretty amazing how fast you can be if you speak to the bare metal.

I then used matplotlib's contour plot to visualize the heatmap I got. I didn't manage to get it to actually overlay on the map in the map's original resolution, but the wizards were still extremely impressed and said that I should speak to them whenever I was interested in seed funding for my startup.

Picture time!

So this actually makes sense. There's a 2h circle around Aryon's home (northeast portion of the island) from where he could either walk or teleport to Wolverine Hall through Divine Intervention (an island east of Vvardenfell). Wolverine Hall has a Mages' Guild, so that means he could instantaneously get to four other major towns (a blob along the west edge of the island). So there are quite a few places he could get in 2 hours!

After that, he would have to take the Silt Strider or a boat, which would slow him down. In 4 hours he would barely be able to reach Gnisis (northwest corner of the island) or Maar Gan (the little arc at the top of the 4h contour around the main population centres). He, of course, could walk from his original location for 4 hours but he wouldn't get very far.

In 6 hours he could be anywhere on the island and in 8 he would be able to reach the northern edges of Dagon Fel, a small island north of Vvardenfell. Finally, in about 11 hours he could very possibly be having breakfast with Big Head in the most desolate corner of Morrowind. Perhaps he had some business there?

The wizards said last time they ever saw Aryon was at about 2am, so he'd been gone for almost 10 hours by that point. Luckily as we were trying to figure out if he would deliberately take the most efficient route to get as far away from his tower as possible, we heard a loud noise from a nearby wardrobe and an asleep but still alive Aryon fell out of it.

In the end, he loved my contour plot as well and hung it up on his wall. Some people say the tower steward still uses it to track down people who go missing in action during Aryon's wild parties.

Next year on project Morrowind, we'll talk about my assignment with Vvardenfell Office for National Statistics to make sense of the island's demographics.

project Morrowind, part 4

@mildbyte 7 years ago | programming | games | morrowind | python |

Welcome back to project Morrowind, in which we use technology to oppress people for our own political gains.

A couple of hungover Telvanni wizards came by to my house this Saturday morning. They went to Master Aryon's tower the night before for a round of drinks, which quickly escalated to several rounds of drinks. Long story short, Aryon managed to wander away somewhere and hasn't been seen since. Worse even, a Council meeting was supposed to take place next Monday and Aryon not attending it would be disastrous.

The wizards wondered if I could map out the locations Aryon might possibly be in so they would be able to better concentrate their agents' efforts across various cities in Vvardenfell and recover him before the meeting.

Imagining all kinds of blog posts I could write about this, I agreed.

Regenerating the graph

I first had to alter the weights between the edges on the travel graph, since in actual game time travel by silt strider or boat isn't instantaneous. But it's easy to calculate from the distance anyway: the speed of travel is in a game setting that defaults to 16000 units per game hour. For example, the distance between Seyda Neen and Balmora is about 55000 units, so if in the beginning of the game you decided to spend money on public transport instead of walking, you would get to Balmora and finish your first quest in less than 3.5 game hours.

Determining the walking time between locations also required some digging. The minimum walking speed in the game is 100 game units per real-world second and the game time by default flows 30 times faster than real time. So walking 16000 units would take about 16000 / 100 * 30 / 3600 = 1h20m of game time. As you see, this is not much slower than taking the silt strider and if you saw one you would realise why.

Obviously, if our travel NPC has "Guild Guide" in his class name, traveling with him doesn't take any time - because magic.

Having rebuilt the graph and re-run Dijkstra on it, we can easily determine how long it would take Aryon to reach any point in the game world, assuming he uses the fastest route. Go through all points in the graph we know the shortest travel time to and find the one for which the total travel time (shortest time to travel to that point + time to walk from that point to the destination) is the smallest.

There is an optimisation which I haven't done: we actually only care about points on the graph where we can get by any other route than plain walking. Consider this: if a shortest path to a point is formed by first teleporting to some point A, then walking to point B and then finally walking to point C (all in a straight line), why not walk from A to C directly (we're assuming here that Aryon can levitate and move between the points as-the-crow-flies, so any 3 points that are in the exterior follow the triangle inequality).

But of course just giving the Telvanni wizards a list of in-game coordinates would be a faux pas. They required a map, and a map I would provide. An affine map, of all things.

A quick, incomplete and mostly wrong introduction to linear algebra

The problem here is that we want to find a way to convert a pair of pixel coordinates on the game map to coordinates in the game world. Luckily, this transformation has an important property: a line between any two points on the game map is also a line in the actual world. Such transformations are called affine: they can be composed out of primitive operations like translation, rotation, reflection etc.

The good news is, they can be represented by a matrix product.

$$ \begin{pmatrix}x_{GAME} \\ y_{GAME} \\ 1 \end{pmatrix} = M \begin{pmatrix}x_{MAP} \\ y_{MAP} \\ 1\end{pmatrix} $$

So if we have a pair of map coordinates and this 3x3 matrix M, we'll be able to calculate the actual in-game coordinates, and vice versa. The third component of the vector being 1 is an ugly hack that allows us to encode translations (movement), since otherwise the vector (0, 0) on the map would map (he-he) to the vector (0, 0) in the game. More on Wikipedia.

How do we find such a matrix? Well, we can use it to transform several vectors at the same time:

$$ \begin{pmatrix}x_{GAME, 1} & x_{GAME, 2} & x_{GAME, 3} \\ y_{GAME, 1} & y_{GAME, 2} & y_{GAME, 3} \\ 1 & 1 & 1 \end{pmatrix} = M \begin{pmatrix}x_{MAP, 1} & x_{MAP, 2} & x_{MAP, 3} \\ y_{MAP, 1} & y_{MAP, 2} & y_{MAP, 3} \\ 1 & 1 & 1 \end{pmatrix} $$

And (by inverting the matrix on the right and multiplying the whole equation by it) this can be rewritten to

$$ M = \begin{pmatrix}x_{GAME, 1} & x_{GAME, 2} & x_{GAME, 3} \\ y_{GAME, 1} & y_{GAME, 2} & y_{GAME, 3} \\ 1 & 1 & 1 \end{pmatrix} \begin{pmatrix}x_{MAP, 1} & x_{MAP, 2} & x_{MAP, 3} \\ y_{MAP, 1} & y_{MAP, 2} & y_{MAP, 3} \\ 1 & 1 & 1 \end{pmatrix}^{-1} $$

Essentially, if we get 3 sets of coordinates in the game world and on the map, we can use those to recover our mapping. These 3 points also can't be on the same line because then the determinant of the matrix of map coordinates is zero and it doesn't have an inverse.

So I picked the game coordinates of 3 locations that were fairly well spread (to minimize the error) and tried to pinpoint the corresponding pixel coordinates on the map.

In the end this is the matrix I found:

$$ M = \begin{pmatrix}185.38 & -0.43327 & -126720 \\ 1.2986 & -0.018372 & 218470 \\ 0 & 0 & 1 \end{pmatrix} $$

To test it out, I plotted the three reference points I used to calculate it (in red) as well as Aryon's initial location (in blue): the exterior door to his house is located at game coordinates (85730.77, 117960.3, 5081.284) which he matrix mapped to (1147.33, 555.21).

I can see your house from here! (the actual map comes from http://thegamersjournal.com/rpg/pc/morrowind/maps/map_rendered_m.jpg)

This edition of project Morrowind was overdue by about two months, so I sadly have to stop here. But next time I'll definitely tell you how we managed to track Aryon and save the Telvanni council from collapse.