Algorithmic Modelling – Touhou Project 11 (Subterranean Animism)

The Touhou Project is a series of “bullet hell” shoot-em-up games. In these games, the player controls a character within a 2D plane and needs to dodge large quantities of bullets. These games tend to be fairly difficult, testing players’ reflexes and in some cases logic as well (for example, many patterns are aimed at or relative to the player’s position; misdirecting such patterns can be useful).

I wouldn’t say my reflexes are very good. Nonetheless, good progress can be made using careful resource management; players are given tools in the form of lives (extra chances after getting hit) and bombs (single-use abilities that clear the screen and deal damage to enemies). The eleventh installment of the series is called Subterranean Animism (SA), and I’m choosing to look at it for this post because it is widely regarded as the hardest game in the series to clear on normal difficulty. For most of these games (on normal), I can just sit down, play the game, dodge bullets and win. There were two exceptions – the fifteenth entry Legacy of Lunatic Kingdom (but even then that only took about five attempts), and SA. SA required a nontrivial amount of planning – I had to learn some of the specific patterns, and also chose a shot type I wouldn’t normally pick.

I generally play Touhou games on normal with an aim to complete the game on a single credit; this is called a “1 Credit Clear” or 1CC. I’m generally somewhere in between difficulties; I’m fairly comfortable with Normal in most cases, but Hard is hard (the game also has an even harder Lunatic mode). I’ve successfully completed 1CCs of most of the games in the series on Normal, and a few of the easier ones (7, 8, 10) on Hard. SA was the toughest game in the series for me to 1CC; it is also the last one I did, at least from installments 6 through 16.

Resource Management

Touhou games usually start the player with two spare lives; this is true in SA as well. However, the bomb mechanic is different from other games, which give the character a fixed number of bombs per life. In SA, players sacrifice some of their shot power when using a bomb. A character’s shot power usually ranges from 0.00 to 4.00; this is increased by collecting powerups when fighting stages or bosses. Firing off a bomb costs 1.00 shot power (and cannot be done if one is below 1.00). This can be frustrating, as some patterns become more than proportionally harder if the player’s shot power is low. When a character is hit, she (the games feature an all-female cast) will drop powerup items such that shot power will be reset to at least 2.25 (higher if shot power was at least 3.00). There is an exception – if it is the character’s last life, a full powerup item will drop that sets shot power to maximum.

The game also has mechanics for earning additional lives. In SA, boss enemies have a staged health-bar with multiple patterns; if the player defeats a pattern within the time limit and is not hit, a life fragment will drop; five life fragments result in an extra life. Bombs are allowed.

A Touhou game is divided into six stages; typically stages 1 through 3 are mostly a non-event for me. That said, for SA, the boss of Stage 3 has a few fairly nasty attacks. Most of my aforementioned “blind” or casual 1CCs involve racking up large stocks of lives and bombs on these stages, and then utilising these aggressively in the later stages. We can see this on SA, as well as on what is often regarded as one of the easier entries in the series, Imperishable Night (IN); the first death on SA is at the end of stage 4 while that on IN is at the end of stage 5. That said, I’m actually already failing to dodge patterns as early as stage 3 or 4. It’s important to be willing to use bombs to deal with difficult patterns, as they are much easier to recover (by subsequently picking up powerup items) in SA. This becomes even more important in other games like IN, where bombs that are unused when a player is hit just go away.

Character Selection

Touhou games usually give the player a choice of multiple player characters, and sometimes for each character different weaponry. Typically, different characters have different movement speed and possibly some other advantages or disadvantages, like having a smaller hit-box or extra bombs. In terms of weaponry, players may select from different normal shots and bombs, which usually have balanced trade-offs. For example, one may pick a homing shot which does less damage but can hit enemies anywhere on the screen, or a shot that only shoots straight ahead but does more damage.

Earlier, I mentioned being able to sit down and just play the game; in most cases this involves the main character of the series, called Reimu, who usually (and in SA) has relatively slower movement and a small hit box. I also normally use her homing shots for a first playthrough, even though I usually prefer straight shots after I get more comfortable with the game. These don’t quite exist in SA.

Apart from slightly different shooting and movement mechanics, many Touhou games also feature a medium to late stage boss (often on Stage 4) which adapts her patterns to the player’s character selection. This is on full display in SA as well; the Stage 4 (out of 6) boss has a relatively easy warm-up battle that is static, before reading the player character’s mind and creating patterns from that (which differ depending on the character and shot type).

Most of the time, the different variants of patterns the boss uses are quite balanced. However, this isn’t the case in SA and thus influenced my selection. Although I find ReimuA (with straight shots) is best equipped to handle the Stage 5 and 6 bosses, the Stage 4 fight one has if one makes this choice is extremely difficult, I’d say possibly even harder than the later bosses. Pictured above is Double Black Death Butterfly; it isn’t apparent from the picture, but some of the butterfly bullets are rotating inwards (and so one needs to dodge bullets possibly coming from behind as well). I thus picked ReimuB (which has a weakly homing shot, a relatively easy Stage 4 fight and a special ability to gather powerups from anywhere on the screen) for my 1CC.

Learning the Patterns

Of course, even with careful resource management it’s unlikely that one can perform a 1CC if one’s dodging skills are too far below the bar. While some of the patterns are random and/or based mainly on reflexes, others have a certain trick to them that makes the pattern a lot easier once figured out. With experience, one can figure out common elements and ways to deal with them (for example, a stream of bullets fired at the character’s position; move slowly, but to change directions make a sudden quick movement to open up a gap in the stream) – this drives most of the “sight-read” clears.

In a sense, good resource management is less critical (consider that one can completely ignore the resource system if one can reliably dodge every single pattern in the game) if one can dodge the patterns. That said, it’s actually possible to clear one these games even if one is quite poor at dodging them, if one makes good use of the resources one has.

Learning German 1: Ich lerne jetzt Deutsch

When I was in middle school and high school, I struggled a lot with learning both English and Chinese. In the end, I performed reasonably well in the relevant summative assessments (I obtained a 6 in English A1 SL and 7 in Mandarin B SL for my IB certificate), but it was always a struggle. I don’t think I struggled particularly with understanding or writing as far as English was concerned; I had more difficulty with decoding literary devices and interpreting poems and related themes. I found learning Chinese challenging, perhaps because I didn’t speak or listen to it much at home, and also because all other lessons were conducted in English.

I’m not sure if this has had a negative effect on my preference for language learning, though to some extent I certainly associate this with stress and difficulty. Nonetheless, about two months ago I decided to start learning German a bit more seriously.

I downloaded the Lingvist app after a colleague recommended it to me. The app performs pretty aggressive vocabulary drills – it’s been useful for plugging basic gaps and discovering new words. According to the app, I’ve learned about 1100 words; the app allows you to learn at most an additional 20 per day, though that’s usually enough to keep my hands full. I’ve been using up this quota most days.

However, the app doesn’t cover the principles underlying grammar, and of course the ability to train listening, speaking or writing is somewhat limited. I thus took an opportunity at work to start more formal lessons, which should help me get better at these skills. The teacher, Katja, has been great – I do understand a fair bit more now, and (hopefully!) sound better and clearer when I speak. I’ve found the lessons to go at a pretty decent pace; they can be demanding, but I like that.

Why German specifically? Firstly, it is a practical choice. German is relatively widely spoken especially considering the countries I might consider moving to, or at least plan on visiting for holidays in the future (which would include Germany and Switzerland).

Secondly, I’ve certainly picked up a few words from my time in Zurich, mainly “Ich spreche kein Deutsch” and how to navigate shops (imagine someone knowing that Rechnung means invoice or Insgesamt means total, but not knowing words like Vater – father – or Tschüss – goodbye), so I’m not exactly starting from zero in terms of vocabulary, even if my knowledge of the grammar and fundamentals may be lacking.

Finally, I find the way words are constructed or varied quite pleasing. I recently came across the word Nachfolger in Lingvist, which means “successor”; the parts mean “after” and “follower”. I’ve come across quite a number of words where the meaning makes sense considering the components, which is nice – Zeitpunkt (point in time) or Verantwortung (responsibility, but Antwort means answer – in a sense of being answerable for something) come to mind.

I anticipate that the grammar may be quite difficult to pick up – declension is considerably more prevalent in German than in English, where tricky cases are mainly in the pronouns, or Chinese. Gender for nouns that don’t obviously seem to have a biological or possibly identity gender is often arbitrary – for example, tables are male, flasks are female, and babies are neuter! In English, he and she are rarely used outside of these ‘clear’ cases (there are a few exceptions, e.g. ships or countries are sometimes feminine, though it generally still feels more natural to me to use ‘it’).

Grammatical cases seem to be another sticky point; articles and adjectives may be written differently depending on whether a noun is the subject or object.  Das ist ein alter Drucker means ‘that is an old printer’, but I’d write Ich habe einen alten Drucker for ‘I have an old printer’ (printers are masculine). However, if I was talking about a lamp (feminine), I would have to write Das ist eine alte Lampe.

Furthermore, sentence structure is different. English and Chinese generally follow subject-verb-object ordering in a sentence. However, German features V2 order, where the verb usually must come second, but other than that things are more relaxed. For example, Every Saturday I read a book is fine as a sentence in English; 每个星期六我读一本书 would work in Chinese. However, the straight translation Jeden Samstag ich lese ein Buch is not OK in German; the verb has to be in position two, so it would have to be Jeden Samstag lese ich ein Buch (or Ich lese ein Buch jeden Samstag, or Ein Buch lese ich jeden Samstag depending on what is intended to be emphasised).

My formal knowledge of grammatical structures within English is also fairly lacking, even though I think I am able to differentiate between grammatical and ungrammatical sentences in English. I had to refresh myself on what an infinitive was during the German course. German also has quite a few more constructs (e.g. accusative and dative cases) which will take some getting used to. Nonetheless, I’ve enjoyed learning so far, and plan on continuing to learn it, hopefully to at least a B1 level.

17:9 (Q2 2019 Review)

This quarter felt particularly tough for me, for various reasons. I remember being tasked as a 16-year old back in middle school to, for a philosophy class, write an essay on the meaning of life. I don’t remember the content of that essay particularly well; I remember that I took an existentialist approach to the problem. Essentially, it is up to oneself to create some semblance of meaning. I think I found the quarter more draining than normal because I was confronted with situations that made me re-evaluate some of the underlying principles I use to guide my decisions.

I’m still on the AtlasDB team. The transactions2 project I’ve been driving has finally been (mostly) completed. It has been almost nine months since this started, and it’s the largest and probably the most difficult project I’ve done professionally. I see quite a few parallels with MCMAS-Dynamic (though transactions2 is probably theoretically easier but more difficult in terms of implementation). There’s always a bit of burnout after launching these large projects, perhaps because of the substantial time and effort invested in them.

Looking forward, the lead stuff now means that I’m helping with scoping and guiding work on pretty much all the major things the team is doing – which also means that for a change I’m not actually directly leading an individual project. I’ve also continued to interview and (I hope) further refine my skills – I like the debugging facet and have kept plugging away at it.

I normally write a healthy section on finance, but it hasn’t featured as prominently this quarter. I normally update my tracker spreadsheets twice a month, on the 10th and 25th, but I missed the 10th June update completely. It’s perhaps a reflection on the importance of different things; as much as I would like to champion financial responsibility or support the FIRE movement, there are many more important things once one’s affairs are mostly in order. This was a pretty normal quarter in terms of saving and spending – there were many things that felt luxurious as I holidayed in Belgium and Japan, but a good chunk of that was prepaid in Q1. Investments seemed to pretty steadily push their way higher up the charts (I’m up a few percentage points); this is probably in part due to a fall in Sterling, though.

One thing that got more serious for me this quarter was learning German – or, as I should say, Ich lerne jetzt Deutsch. It’s a privilege to take lessons at Palantir and the instructor is excellent; besides that, I’ve also been using Lingvist (a flash-card app) to expand my vocabulary. I’ve found the grammar to be quite challenging; the myriad ways in which nouns and adjectives get declined is not something my past experience with English or Mandarin helps with very much. I often use strange mnemonics to keep track of noun gender (such as little Bobby Tables for der Tisch, a Brutalist town centre for das Zentrum, and Minnie Mouse for die Maus). Ich habe leider keine Konfidenz auf Deutsch zu schreiben – that is, I unfortunately don’t have the confidence to write in German (beyond simple phrases and isolated statements).

I travelled quite a bit this quarter, balanced between work and leisure. I visited Boston for the Palantir puzzlehunt. I also visited Singapore for Daniel’s wedding, and Brussels and Tokyo for holidays. It can be quite expensive, but I’ve been finding I need a bit more relief from the pressures of work and general administration than normal. I enjoyed these trips, to some extent in spite of very packed schedules. The Brussels and Japan trips were mainly food-focused (though the Musical Instruments Museum and Sankei-en Garden, respectively, were also standouts; I think we spent about two or three hours in each of these places, but if I was on my own I could imagine spending the whole day there). Satou Steakhouse (teppanyaki), Ginza Tamai (a restaurant specialising in sea eels, or anago) and even the somewhat more humble Toriyoshi (grilled chicken skewers or yakitori, and fried chicken or karaage) were all excellent. I’d like to go back, schedule allowing; I had a really good time.

This quarter also features a fairly large number of bank holidays in the UK, meaning that I had a number of three-day weekends (and four, in the case of Easter). I’ve started to take more interest in enjoying these extended holidays by trying to do different things (as opposed to focusing on reading, logic puzzles or things along those lines). It seems like I end up going on longer walks, and staring at coffee cups in cafes; past me would have decried this as a waste of money – and while I intellectually can’t deny that it is frivolous, I do still enjoy this.

In terms of logic puzzles, the WPF Sudoku and Puzzle GPs are almost over. The seventh round of the Sudoku GP ended last week, and it felt absolutely brutal (I scraped 325 points and a 98/414 rank). It wasn’t my worst round (that was the fourth round), but in round 4 I made steady progress while breaking a few puzzles while this time I struggled to tackle the puzzles at all. I had two good rounds in between (round 5: 51/502; round 6: 57/476). I had two decent rounds for the Puzzle GP – I’d say I’m weaker there, and I ranked a reasonable 90/384 in round 4 and 83/383 in round 5; conversely, round 6 was an absolute mess for me though and I ranked 207/349, which is my first sub-median score in a good while!

I played a lot of Slay the Spire in Q1 but this slowed down; in fact I haven’t spent very much time at all on computer games this quarter. I didn’t play very much in the way of board games as well, though I distinctly remember a Pictionary session where I managed to guess CURRY off a bunch of lambda expressions, and a few Codenames Duet clues – an AIRBASE, 3 clue for MESS, FLAG and APRON which landed perfectly, and a game which went wrong when I tried to be smart and gave a STEEL, 5 clue for a bunch of vaguely metal-related words not noticing that BEAM was an assassin – or rather, noticing that it was there, but having my mind filled with images of laser or wireless signal beams.

Musically I’m not sure where things were going this quarter. I did listen to more instrumental pieces. A good number of these were piano-focused, both classical (like Liszt’s Hungarian Rhapsody No. 2) and relatively modern (like Rush A and other entries in that series). Some of these also come from video games (like Fantastic Light, Ancient Flowers from the Touhou series). A common theme here might be speed – many of these pieces are very fast. Perhaps I find music to be an outlet for dissatisfaction when things are not going quickly enough.

On the flight back to Singapore, in between rounds of Tetris I listened to Calum Scott’s debut album Only Human. I think I recognised his name from his Dancing On My Own cover, though I really don’t watch much TV or listen to the radio so I didn’t know what kind of music he produced. It was mostly very listenable, though a bit on the heavier side (I guess in my opinion at least this fits his voice much better, though).

I particularly enjoyed three of the tracks on the album, though I think only one of them can reasonably qualify for my song of the quarter. The opener If Our Love Is Wrong is well put together, though more specific to Scott’s situation; the closer Not Dark Yet (a Bob Dylan cover) works well but is a bit too dark for me to enjoy – which is probably the point. My winner is the much more straightforward You Are The Reason; it’s a clean and well-executed piano ballad that seems to carry a certain gravitas. The line in the chorus about fixing what one has broken also appeals to me; I think if I look back at the songs I’ve chosen, failure and subsequent correction is a pretty common theme (e.g. Starting Over, These Days, Back from the Edge). Scott’s vocal line does get pretty difficult to follow, but it makes sense given the subject matter.

Death by Cubes (Algorithmic Modelling: Pandemic)

“So the probability we lose is 2/3, multiplied by 5/23, or 10/69. It’s pretty much a 6 in 7 shot.”

I met a friend for dinner and board games a while back, and one of the games we played was Pandemic. Designed by Matt Leacock, the game is themed around managing and discovering cures for diseases before they spread across the world.

Diseases are modelled using cubes, and they spread across a network of cities (which are nodes in a graph). On players’ turns, they perform actions to contain the spread of diseases, research cures for these diseases or share knowledge with other players. After they are done with their actions, players draw cards from an infection deck, where each city (node) is represented once. For each card, players need to add a disease cube of the city’s colour to the city. For example, considering a simplified network:

  • If D is drawn, one yellow cube will be added to D. Similarly, if E is drawn, one red cube will be added to E; if F is drawn, one blue cube will be added to F.
  • A city is allowed to have a maximum of three disease cubes of each type; if a fourth cube of the same type needs to be placed, an outbreak happens. Instead of placing the fourth cube, all connected cities receive one cube of the relevant colour. For example, if C is drawn, a blue outbreak occurs in C, and one blue cube is added to both B and F.
  • The rules on having at most three cubes of each type still apply when placing additional cubes, meaning that outbreaks can cause chain reactions. For example, if A is drawn, a red outbreak occurs in A. This causes one red cube to be added to B, D and E. However, B already has three cubes, meaning that a chain outbreak occurs in B; this causes one red cube to be added to A, C, E and F.
  • This looks like it would loop infinitely, but there is some mercy; in a given chain reaction, each city may only outbreak once. Thus, instead of adding a red cube and triggering an outbreak again in A, no red cube is added.

The game ramps up steadily in pace, by increasing the infection rate (number of cards drawn) over time. Players lose the game when the eighth outbreak occurs, when they need to place disease cubes but can’t (these are component-limited), or when the deck of player cards runs out.

Separately, the goal of the game is to research a cure for each of the four diseases in the game, which requires collecting data on the spread of the diseases. There is a deck of player cards which contains twelve city cards associated with each disease; players need to collect five of them (in one player’s hand) and bring them to a research station. This can be tricky, as players draw cards independently, and giving cards is restricted (I can only give you a card if we’re both in the one city that is associated with that card, and if it’s my turn). At the end of each player’s turn, players draw two cards from this deck (if they can’t, the game is lost).

The deck of player cards also contains a few special event cards which help players, and more interestingly several Epidemic cards which are disruptive. The number of Epidemic cards to include is variable (4 are used in an easy game, 6 for a difficult one). When an Epidemic card is drawn, players resolve a three-step process:

  1. “Increase”: The infection rate marker moves along its track, possibly increasing the infection rate (number of infection cards to draw at the end of each player’s turn). This begins at 2, but eventually becomes 4.
  2. “Infect”: There is a sudden wave of disease in a new city. Players draw the bottom card of the infection deck, and the city in question receives 3 disease cubes of its colour. The usual Outbreak rules apply, though thankfully only one Outbreak occurs even if the city already has two or three cubes.
  3. “Intensify”: The infection discard pile is shuffled (including the just-revealed card from the bottom of the infection deck). These cities are likely to suffer from more disease soon, especially since this happens as part of players drawing cards (before the infect phase of the current player’s turn).

Going back to the initial calculation, we were on the second last turn of a game with six Epidemic cards, five of which had already been drawn. There were three cards left in the player deck. We already had seven outbreaks occur, meaning that one more would lose the game. However, we had also cured three diseases, and the Medic which I was playing was sitting in a research station with all of the cards to cure the last disease on the next turn. Furthermore, my friend who was playing the Operations Expert held the One Quiet Night Event card, which allows skipping of the Infection phase.

Thus, the only risk of losing was drawing the last Epidemic card, and then in the Infect step revealing a city on the board which already had disease cubes of its colour (from outbreaks in adjacent cities). These events draw cards from separate decks, so their probability should be independent.

The first term is easy – there were three player cards remaining, one of which was the last Epidemic card, so there would be a 2/3 chance we would draw it. For the second term, we looked through the infection discard pile, which at that time had 24 cards (along with Sydney, which we removed from the deck using a special event card). There were thus 23 unseen infection cards; six of them corresponded to locations on the board which had disease cubes. On my friend’s last turn, we were able to defuse one of these locations, leaving a final loss probability of (2/3) * (5/23).

It turned out that we got lucky as we didn’t draw the Epidemic card, and even then the card at the bottom of the deck would have been safe. I wasn’t initially keen on doing too much of the calculation, figuring that clearing one risky place was easy but two was hard, but my friend (who is a statistician) decided to go ahead with the calculation.

On Set Collecting

When I hear the word ‘set’, the first thing I think of is the computing data structure, and then the mathematical construct that that data structure is trying to model. Essentially, a set is an unordered collection of distinct objects. I’d probably then think of the Egyptian deity before thinking of the card game, or failing at a contract in bridge. That said, we recently had some interesting discussions about the card game over lunch at work.

The game consists of a deck of 81 distinct cards which each show a number of shapes. Each card has four attributes, and each of these attributes can take on three values – number of shapes (one, two or three), colour (red, purple or green), shading (shaded, striped or unshaded) and shape (diamond, rounded rectangle, ‘S’).

Initially, twelve cards are dealt to the table; players compete in real-time to identify a set of three cards where, for each attribute, the cards are either all the same or all different. The player collects these cards, and the dealer replenishes the cards on the table.

It is possible that no set is possible with twelve cards. In physical games, the dealer will, after a while, deal three more cards to the table if no one can identify a Set. We were playing on an app, though; this app waits for players to claim that there is no set available, and penalises players if they make an erroneous claim. More often than not, even though all of us were looking carefully at the board, we were too quick to declare no-set with 12 cards. However, we had one round where even with 15 cards (after one declaration of no-set), no one found anything. After a long while, someone pressed the no-set button, and indeed there wasn’t a set!

After the game, discussion turned towards finding the maximum number of cards where no set was possible. We quickly settled on 16 as a lower bound; this is possible if you only use two of the values for each of the four attributes (e.g. by throwing out all cards that have three symbols, are red, are shaded or are diamonds). Now it becomes impossible to perform matches along any attributes being different, since you need one occurrence of each of the three values; also, because cards are unique there is no set of three cards where all four attributes are the same (that would be three copies of the same card). This arrangement has 2^4 = 16 cards.

Going beyond this is tricky, mainly because the number of possible groups of cards you have to pick from is large. There are 81 ways of selecting the first card, and 80 ways of selecting the second. The third would have 78 ways, since there is one specific card that won’t go with the first and second. However, later on you can’t just deduct one card for each already selected card; for a simple counterexample, suppose I have already selected:

  • (1) one red shaded diamond
  • (2) one green shaded rectangle
  • (3) one green shaded S

Now suppose I try and add the card (4) with one red shaded rectangle. This means that the card with one purple shaded rectangle would now become ineligible for selection, because it would form a set with (2) and (4). However, we have already eliminated this card from consideration, because it would form a set anyway with (1) and (3).

I turned to writing a quick program here. This is a standard algorithm based on depth-first search.

  • Each card is represented as a vector with four components.
  • There is an initial set of 81 vectors created.
  • To guide our search, whenever we consider adding a card to a working set, we iterate over the elements of the existing working set and determine which cards would, together with the new card, create a set. This relies on an observation that for any pair of (distinct) cards, there is one and only one card that would form a set with the first two. We then prune these set-creating cards from the search tree.

This found sets of size 17 quite quickly, but knowing that the bound was 20, I knew that wasn’t good enough. There were several implementation tricks that I used to help speed up the search.

  • This search is easily parallelisable; each branch of the search tree may be explored in parallel. A simple implementation (and what I used) could rely on Java’s parallel streams when doing the recursion, for instance. The orchestration around keeping track of the best answer needs a few small changes to be thread-safe, of course.
  • If the goal is merely to find some set of size 20, then we can exploit the symmetry of the problem and fix the first card to be any card (I used 0,0,0,0), since any cap set could be re-expressed as one that contains 0,0,0,0 by permuting the assignment of attributes to variable values. There may be more clever symmetry to exploit here than what I did.
  • Computing the last element of a set involves a bunch of jumps, branches and math; the result of this computation is deterministic, and can be cached so that it can be reused along different branches of the search tree. There’s probably something more clever I can do regarding overlapping sub-problems (this improves the runtime only by a constant factor).

This was sufficient to get the tool to spit out many sets of size 20, though I unfortunately didn’t churn through every possible selection, so this doesn’t show that 20 is an optimum.

Notes from a Nervous Engineer (2019 Q1 Review)

I think the first time I came across the concept of a scarcity mindset (where one approaches problems believing resources are finite) when I was around 14 or so. This was in The 7 Habits of Highly Effective People. To quote Covey:

Most people are deeply scripted in what I call the Scarcity Mentality. They see life as having only so much, as though there were only one pie out there. And if someone were to get a big piece of the pie, it would mean less for everybody else.

Covey recommends its counterpart, the abundance mindset, which is the idea that there are enough resources out there for everyone. That said, I don’t buy in to the idea of abundance being superior, because resources and opportunities often are scarce. I’d bring in the Bruce Lee “I fear the man who has practiced one kick 10,000 times” quote here; bearing scarcity in mind forces prioritisation, and that if done well is really useful. This may be dangerous, but I’d hazard that scarcity can lead to fear that one is stagnating. This, if managed well, can drive one to, to use Covey’s terms, aggressively “sharpen the saw” (pursue self-improvement) as well.

There are sides of the scarcity mindset that are certainly dark. There is a danger of casting things that are not zero-sum games as zero-sum games. Aggressively focusing on scarcity can lead to excessive stress and blind short-term optimisation (manifesting in things like money dysmorphia as described in this Guardian article). I’m also somewhat guilty of this, but it can lead to hoarding. That said, in my experience a scarcity mindset is often unfairly tarred and feathered – it indeed can often be dangerous, but it has its uses.

Software Engineering

Things changed direction; I expected to move off AtlasDB, but instead became the tech lead (admittedly with a bit of dithering and some convincing from other storage experts – and a few non-storage ones too). My responsibilities have changed somewhat in that I have been spending more time maintaining context and reviewing code. I don’t think there are benchmarks, but I suspect the amount of individual development work that I do is still high relative to other TLs (in any case it’s a spectrum – I’ve worked with one in the past who did more work than I did).

I also got started on studying Designing Data-Intensive Applications after recommendation from some engineers whom I respect. Having spent almost two and a half years on AtlasDB, most of the material is not particularly new to me – that said, this would have been an excellent read when I just started on the team. I’d recommend the book for people working with distributed systems (even if they’re not necessarily working directly on distributed systems – e.g. if doing support).

Finances

With Brexit looming, the pound has been extremely volatile. I was a bit of an uneasy Remainer during the 2016 referendum. In any case, the way things have panned out since has sent me very firmly in the Remain direction now. I’d say my exposure to sterling cash is at relatively low levels. I tend to be somewhat risk-averse, and although GBP is probably undervalued, the danger of no-deal is there.

I haven’t been tracking the markets very closely; from what I remember things went up in January (after getting smashed at the end of December) and then have mostly gone sideways. It’s also coming to the end of the 2018/2019 tax year; I’ve seen the ISA ads around, though not so many for ‘use your capital gains allowance’ which is something I should look at this week.

Expenses-wise, Q1 has been awkwardly high; some of this is because of one-off expenses for activities that’ll actually take place in Q2 (travel and holidays). My overall savings rate is still decent, as income was higher because of bonuses.

Travelling

I had just two trips out of the UK this quarter, and interestingly both were to visit specific friends in the context of specific events. I went back to Singapore in January for Isaac’s wedding – that was a very short trip as I only had close to a day or so to actually spend with family. The other trip was to Zurich for a weekend trip in February to meet Stan.

Hobbies

The logic puzzle train has been chugging along. I took part in most of the WPF Sudoku and Puzzle GPs, though I missed one round of the puzzles as I was in Zurich that weekend. I’ve always been stronger at sudoku and it shows – I’m on overall rank 60/774, with rankings 82/599, 139/598 and 47/541 in the three rounds. I thought round 2 went pretty well, though I broke an easy Classic Sudoku and, more significantly, a (I think still easy) Braille Sudoku that was worth a lot of points. Round 3 was good – all three of the ‘weird’ variants at the end were disposed of quickly. For puzzles I’m on overall 167/557, with rankings of 102/434 and 93/405 in the two rounds I participated in. We’ll see how Sudoku Round 4 goes, though I think it went poorly for me.

I’ve been reading a fair bit too – some readers may recognise that the title of this post is inspired by Matt Haig’s Notes on a Nervous Planet. I first came across his earlier work Reasons to Stay Alive randomly in a Popular bookshop in Singapore late last year, when waiting to meet a friend. I found the book pretty captivating, though I didn’t buy it then – instead, I placed an order for the book to be delivered to me in London. Both of the books held my interest; the former was raw and pretty compelling, while the latter is more familiar territory for me and I think I could to some extent identify with his perspectives.

I also found James Clear’s Atomic Habits to be a very practical read; I’ve been following his emails for a while. I appreciated the principled approach the book presents. He first establishes that things that become habits tend to be obvious, attractive, easy and satisfying; he then explores how to influence behaviours to increase or decrease how much they show each of these traits.

General Thoughts

It’s been a stressful quarter; there has been a lot of change at work, unease in my financial situation, and discontent with things in general. Perhaps this is something worth thinking about; there’s a passage near the end of Notes on a Nervous Planet on diminishing returns, where Haig observes that many people have tendencies to repeatedly move the goalposts when successful. For me, “be good at math” became “top my class in math”, then “top my cohort in high school in math” (I failed this one, though unexpectedly got Physics instead), then “get a first at Imperial”, then “get the first at Imperial”… “with a 90 average”… “while running a club and working part time 20 hours per week”. Similarly, “be a good dev”… can quickly spiral into “with patents”, “building large features”, “be a principal engineer” and so on. It’s important to maintain perspective as to whether the repeated escalation of these goals is something one really wants to do.

There’s usually a song I associate with each quarter. This time around I’ve been listening a fair bit to Drunk Me by Mitchell Tenpenny. He’s a country artist and I don’t listen to country very much, but this is pretty much a straightforward pop song. There are some awkward metaphors in there, but generally I find the production pleasant, and the A4s he hits in the chorus are nice enough. The message involves giving up habits that are likely to lead the singer back to his ex, which is a pretty logical response.

I’ve been sober
‘Cause there ain’t no hangover like you girl
“Baby, can you come over?”
I always find those words at the bottom of a hundred proof

I don’t drink much alcohol, though I do drink quite a bit of coffee and chocolate. In a sense, my ‘alcohol’ would be activities or behaviours I find addictive that are likely to lead to ruin or negative consequences. This could include things like obsessive fear over how the markets are doing or how Brexit is going, or spending time procrastinating. I don’t think there is an object of spite here, unlike in the song, but nonetheless the idea that one may find value in cleaning up one’s life is something I can get behind.

Algorithmic Modelling – Achievement Hunting (Slay the Spire, Part 2)

Many modern video games feature an achievements system. Achievements are typically awarded for completing specific tasks; typically achieving all of these requires doing substantially more than just what is required to finish the game. In many cases, it’s not even possible to complete all of the achievements on one playthrough.

In a previous post, I wrote about Slay the Spire, an RPG where combat is driven by a deckbuilding mechanic. The game also features an achievements system. I finished getting 100% completion on these achievements this week – this took quite a long time. If I wanted to start from the beginning and accomplish these as quickly as possible, I would need to plan carefully. The main issue here is that achievements are not independent. For example, there are chains of achievements where the final achievement subsumes all previous ones (e.g. “have 99 block, have 999 block” or “unlock ascension mode, finish ascension 10, finish ascension 20”). Furthermore, some achievements can be achieved using the same strategy (e.g. “play 25 cards in a single turn” and “defeat a boss before it takes a turn”, which can both be achieved by building an infinite combo). Other achievements can often be significant handicaps (e.g. “beat the game with a deck that has no uncommons or rares”, “beat the game with only 1 relic”) and I thus think it’s a lot harder to combine these with other achievements.

The game is played in distinct runs, and a majority of the achievements involve performing specific feats on individual runs. We can model this by identifying strategies that unlock one or more achievements. If we try to use the fewest number of distinct approaches, this becomes what’s called a set cover problem. There are achievements A = \lbrace 1, 2, \ldots N \rbrace and strategies S = \lbrace S_1, S_2, \ldots S_M \rbrace with each S_i being non-empty and a subset of A. We also require that \bigcup_{i=1}^M S_i = A, otherwise not all achievements are achievable. The goal is to identify some set of strategies we need to deploy S' \subseteq S such that \bigcup_{s' \in S'} s' = A. Trivially, picking everything is possible, but it’s very unlikely that that’s going to be minimal.

This problem is known to be NP-hard; the decision version (does there exist a solution using k strategies or fewer?) is NP-complete. Clearly, we can obtain a solution that is worst-case exponential in |S| \times |A| by iterating through each possible subset of S, checking if it satisfies the criteria and remembering the best solution we’ve seen so far. There’s a little dynamic programming trick we can do to memoise partial achievement states (e.g. I can get to the state where I have the first 8 achievements and no others using two runs with one strategy but three with another; I’ll always pick the first). This achieves a solution exponential in |A| but linear in |S|, which is an improvement. We can also try to pre-process the input for A and S a little, by eliminating any achievements that are subsumed by harder achievements, and by eliminating any strategies that are strictly dominated by others.

If this is unacceptable, we can either try to use approximation algorithms (for example, a standard ‘greedy algorithm’ which picks the subset with the most outstanding items doesn’t always fare too poorly). We can also attempt to leverage constraint solving systems; these don’t deal with the exponentiality of the problem directly, but they often have good heuristics to deal with this.

That said, this isn’t a very good model, as some strategies are riskier to implement than others. For example, it may be theoretically possible to combine “beat the game with one relic” and “beat the game without uncommon or rare cards”, but that seems unlikely. For example, if each of these individually has a 1% chance of being completed but attempting them together has just a 0.1% chance, doing the achievements separately will take an expected 200 runs while the combined approach has an expectation of 1000.

A natural extension to this is to consider the weighted version of the problem. We change the formulation slightly, so each strategy has a weight w_s and we seek to minimise the total weight of the strategies we pick. If we assign a strategy a given probability of success p, since runs are (mostly) independent, the expected number of runs it takes to attain a successful outcome would be 1/p following standard geometric distribution results. The dynamic programming based algorithm still works if we keep track of weights instead of number of sets.

This is better, but there are still a few issues with the model. Firstly, partial successes haven’t been considered in this model; we might try a risky strategy for three achievements and fail, but still complete two of them. We could try to account for these by figuring out some kind of state transition between achievement states – it wouldn’t be a set cover problem any more. We would be building some kind of a discrete-time Markov chain on-the-fly.

Modelling this as a set cover problem also seems to imply that our algorithm is offline; that is, it formulates a strategy and then executes it. However, Slay the Spire has a significant luck element, especially if one is trying for specific achievements, and thus an offline algorithm doesn’t work so well. For example, one achievement requires “play 10 shivs on a single turn” and another “have an enemy reach 99 poison”; the cards and relics that support these are quite different, and depending on what cards are offered as the game progresses, one achievement or the other could become easy or nigh-impossible. If both achievements remain to be unlocked, it seems suboptimal to commit early on.

Algorithmic Modelling – The Game: Extreme

I had a weekend break in Zurich to meet up with a friend who works there. We often play board games when we meet, so I brought Hanabi and FUSE (very compact games, suitable for travelling – especially since I almost always travel HLO) but my friend was thinking of getting something different. We thus headed down to a game shop, and picked up The Game: Extreme (Board Game Geek).

The rules are fairly simple. There is a deck of 98 cards – one copy each of the integers from 2 to 99, inclusive. Players will have some number of cards in their hand (eight for a solo game, seven for 2 players), and play them to the table; the game ends in a loss if a player must play, but is unable to (or if all cards are played, which is a win). It is a cooperative game; players all win or lose together. The rulebook also mentions a half-win if players finish with ten cards or fewer remaining.

There are four communal piles that players can play cards to. On two of these, cards played should be numerically increasing; on the other two, they should be numerically decreasing. However, one may also go against the direction of a pile – this can only be done if the jump is exactly 10. Thus, for example, if an increasing pile has a 57 on top, one may play a 59 (increasing) or a 47 (ten less), but may not play a 49 (not increasing, and not ten less). Of course, if a player has both the 59 and 49, the player may play the 59, after which the 49 becomes legal.

One can probably write some search-based algorithm to figure out what the best possible outcome is for a given hand and individual pile, or even set of piles given some fitness function. There’s also a straightforward dynamic programming optimisation, and for certain classes of fitness functions there might be better principles one can leverage.

Players must typically play two cards on their turn, though they may play more (for example, if they have a chain of cards that involves several reverse jumps) while there are still cards in the deck; once that is emptied, they only need to play one. Once they have played all of their cards, they draw back to their hand size and play passes to the next player.

The Extreme version adds special effects to some of the number cards. These may either restrict the current player’s turn (requiring that they stop immediately, play exactly three cards, or immediately cover up the card that was played) or affect all players while they are exposed (requiring players keep quiet, play all the cards in their turn to the same pile, not do reverse jumps or only draw 1 card at the end of their turn). Apart from the stop card, all of these make the rules for playing more restrictive (and thus I’d say this is somewhat harder than the base game).

The solo game doesn’t generally seem too difficult as one can plan and execute sequences of reverse jumps without interference from others. The keep-quiet special effect no longer really matters, and the stop cards actually become positive as they allow for drawing cards back up earlier. I’m not sure how one might formulate an algorithm for determining optimal moves, but I can generally see the following principles:

  • Play the minimum number of cards needed per turn, and then draw back up. This lets you see more options, which is useful. Normally in a multiplayer game you may want to play more than the minimum to ensure that no one interferes with your plan, but in single player no one will anyway.
  • Plan and aggressively use reverse jumps. These often get thwarted in multiplayer games (you might draw a card that allows a reverse jump, but someone might need to play on the relevant pile before it gets to your turn).

Playing with more than one player gets trickier, as communication between players is permitted but precise numerical information is not. I would say things that imply precise numerical information (e.g. “I can jump this pile”) are also bad. There are edge cases which are probably acceptable (e.g. “it makes no difference to me; which of these would you prefer I play to?” with an up-65 and down-67 suggesting I hold the 66). Still, talk of “small/large jumps” and actively saying “stop” after interesting cards are played is very useful.

Cooperating well involves looking ahead to other players’ turns as well; it’s not always optimal to, on each player’s turn, individually minimise “damage” to the piles. There have been times where being forced to jump a pile by 30 or so, I’ve encouraged my teammate to play more cards there since it would be destroyed on my turn anyway. We only played with two players, but I imagine the dynamics get more interesting with larger groups.

The Game: Extreme is a very light game; while there is some minor logic involved it’s not particularly complex. It’s fairly fun and witnessing successful chains can be enjoyable; the special effect cards can also cause annoying obstacles (while blocking reverse jumps is probably the most damaging, the keep-quiet one is interesting as it changes the game for a while). It’s certainly a fun thing to play while passing time and discussing other things, and hard enough to provide a good challenge without being frustrating.

Evolving Robots to Cut Stocks: A Coding #10YearChallenge

Ten years ago, I was in high school. I had some experience with coding, mostly through computer science lessons in school; I did Computer Science HL for the IB diploma programme, which had a sizable Java component. As part of the IB programme, students need to write an extended essay, which is basically a research paper.

I worked on Application of Evolutionary Algorithms to Solve the One-Dimensional Cutting Stock Problem. There are two terms to unpack here. First, “evolutionary programming” is a biologically inspired heuristic for solving optimisation problems. The idea is that we first randomly generate a pool solutions that are feasible. We then create ‘related’ solutions by permuting the existing solutions in some way, assess their quality using a function and then replace the old population by selecting randomly from the old and new, with bias towards better solutions. In this way, the theory is that the population of solutions increases in fitness/quality over time.

Second, the “cutting stock problem” is an operations research problem in manufacturing, where raw materials are supplied in finite sizes (e.g. rolls of paper) and one needs to cut them to fixed specifications. The assumption here is that it’s not possible to glue together parts that don’t correspond to any request to fulfill one – any pieces that are too small are lost (this is called ‘trim loss’).

In hindsight this seems decently ambitious for a high-school project. I did well, and got an A (which is the highest grade for these), though I remember how long it took me to write a (in hindsight absolutely terrible) working implementation.

Implementation

The project was implemented in Java, which the IB programme focuses on in its Computer Science course.

Looking back at how my code was structured, it was rather unsurprisingly amateurish and messy. There were just four source files for the entire project, including one 700-liner. That said, there was some semblance of organisation, at least in the sense of abstraction and factoring out logical units into functions. The main loop body of the runOneIteration() method I had was just four statements that ran the major steps of the evolutionary algorithm – clone the current generation, perform mutation, evaluate the new generation’s fitness, select the next generation.

My Java knowledge was poor at the time. Some of this was not knowing about the possibility of using external libraries – I had my own implementation of deep copying objects. Some of this wasn’t even external libraries; I had implementations of median-of-three quicksort and the Fisher-Yates shuffle, which seems unnecessary (these are Collections.sort() and shuffle() respectively).

I seem to have had near zero knowledge of the Collections APIs. I also used a lot of primitives and arrays of primitives, which made things hard to read. This could be argued as having better performance (by avoiding function calls, boxing when performing math and so on), but there wasn’t such a discussion in the paper or comments anywhere, so I’d chalk it up to lack of knowledge.

For an example, we can look at the implementation of a deep-copying routine I wrote back then.

If I was to review this code, there were quite a few things I’d highlight:

  • I’m not sure Java serialization and deserialization is the best way to do this. The general serialize/deserialize approach makes sense, but there are more user-friendly and performant serialization libraries out there. I’d probably use Jackson now.
  • There are no tests! Amazingly I didn’t have any automated tests for my implementation at all. (Contrast with MCMAS, where one of the first things I did when working on that codebase was introducing an automated test framework.)
  • Swallowing exceptions and returning a potentially null object seems like an error-prone pattern. I’d prefer to have clients check for errors by catching (possibly unchecked) exceptions, rather than checking if the reference is null.
  • The ObjectOutputStream can be leaked if writeObject() or flush() throws. We should use something like try with resources (though at the time that didn’t exist – in that case we would put close() in a finally block).
  • The class is a utility class, but it has a public constructor (default in Java). It’s silly, but someone could instantiate instances of this class, which shouldn’t be allowed.
  • Using Object directly for the return type can be troublesome, especially since we know the object that’s being returned has the same type as the input.
  • The reason we have to assign null to obj on line 3 is because it may not be assigned when referenced on line 21. If we wanted to keep this contract (don’t throw, and return null on failures) we can avoid this by returning in.readObject() directly in 13 and null directly in the catch blocks, which is probably more readable.
  • This is not a fair criticism in 2008 (as the feature in question was introduced in Java 7), but nowadays if we want to handle different types of exceptions in the same way we should use the multi-catch syntax to be concise.

Algorithms

The cutting stock problem is difficult (it’s in FNP, and the decision version of “is there a better solution than some number of stocks” is NP-hard), hence heuristic-based algorithms like this seem reasonable. The mutations I used then were swaps, which probably makes sense for this problem as it preserves feasibility (the orders can’t be changed).

The algorithm was probably a bit too greedy in terms of how much it prioritised already-good solutions. I’m not sure if I had heard of the words simulated annealing then, but I interestingly seem to have suggested something like it when discussing possible future work! Those words weren’t mentioned anywhere in the essay and the paragraph in question has no references, so it might well have been a thought from first principles.

The approach of selecting stocks with high wastage to swap pieces from is initially effective in reducing trim loss; yet, this also caused the algorithm to converge at local optima frequently. Conversely, selecting stocks with low wastage to swap pieces from seems to encourage the algorithm to search for the global optimum, though this may require significant amounts of time. A conditional approach, more biased towards swapping stocks with more wastage at the beginning than at the end might prove effective.

Documentation

The obvious difference was that this was written in Word while nowadays I’d almost certainly use Latex for a document like this. Some of the formulas were awkwardly typeset, and rather frustratingly there wasn’t a consistent theme to the diagrams (I see Arial, Calibri, Times New Roman and LM Roman!)

There were some fair points that I made then; for example, the algorithm is flexible with resource constraints, in that terminating at any point will spit out a feasible solution, and much of the gain is obtained early on.

Conclusion

More generally, it’s good to see that things have changed, and that there has been real and significant improvement. I’m often frustrated about my learning and development as an engineer, and in the moment it’s often hard to see any improvement. Yet, viewed over a larger time-scale, across the Imperial degree (shout-out to Software Engineering Design), multiple internships and a battery of research papers and patentable work, things have improved quite a fair bit, which is somewhat gratifying.

Boundary of Lines and Gradients

In The 7 Habits of Highly Effective People, Stephen Covey introduces the notion that things we encounter in life may be classified as irrelevant or relevant to us (whether they are in our circle of concern), and then of the things that are relevant, whether they are things we can influence (hence circle of influence).

This idea is introduced in the context of arguing that highly effective people are proactive. The book claims that there’s a risk that one spends too much time focusing on things within one’s circle of concern, but external to one’s circle of influence. By definition, these can’t be meaningfully changed by one’s actions, so one logically should not focus on these; yet, there is a tendency for one to index too heavily on these, perhaps because they are worrying to look at.

I remember some concern over my work visa application process when I was still studying at Imperial; at the time, the UK Migration Advisory Committee was actively reviewing the Tier 2 scheme with a specific focus on post-study work. Obviously, that was within my circle of concern, but was out of my circle of influence. I was quite concerned about it then, and spent a good amount of time researching how Tier 2 visas looked like and what changes might have occurred.

I also took positive action to hedge these risks (which was within my circle of influence). This included investigating opportunities elsewhere, restricting my internships to places that were willing and able to sponsor Tier 2 visas, and trying to be “so good they can’t ignore you”. Looking back, I think the hedging was valuable; poring over visa rules was less so.

So far, so good. However, there is some difficulty in applying this idea. Two challenges I’ve thought about recently are accurately identifying the boundaries of one’s circle of influence, as well as figuring out when one should exercise one’s ability to influence things in one’s circle of influence.

In terms of identifying boundaries, one may incorrectly identify things as within one’s circle of influence, owing to overconfidence or excessive optimism – a classical example being what other people, especially other people we don’t know choose to do. The inverse would be identifying things as outside from fear; I’ve done this before in terms of some aspects of how I’d been investing my free time (in particular, a commitment to over-studying).

Errors in both directions may also stem from ignorance; for example, one may (correctly) think that the spot GBPUSD exchange rate is mostly not in one’s circle of influence, and then extend that to say that the number of pounds one must pay for a known upcoming dollar expense is out of one’s circle of influence (wrong; forward contracts and other hedging methods exist).

Some authors make further distinction between things one can influence and things one can control, which usually implies personal ability to decide the outcome (for example, one can control one’s own decisions, but can probably only influence another person’s behaviour). I find this a fairly useful distinction to make.

We then move to figuring out if things within our circle of influence are actionable. They can be, but aren’t always. For example, I’ve thought about how to insulate my portfolio from the storms of Brexit and the recent market turbulence. On one hand, my asset allocation is clearly within my circle of influence. I can sell everything and go to cash (or, if one’s worried about the pound, to the US dollar or yen). I’d say it’s even stronger than that – it’s something I can directly control in that I know I am able to execute the relevant transactions if I want to.

Yet, I don’t necessarily know how changes in my asset allocation will affect the returns I will get and the risk I’ll be taking on. I can make some estimates based on past distributions, but those will suppose that at least to some extent past performance is indicative of future returns; there might be ‘black swans’ which can mess with this and by definition are not foreseeable (and thus outside of my circle of influence). In a sense, I know I can change things, but I don’t know as well what impacts my changes will actually have; there is also a cost to implementing changes (both in terms of tax and dealing fees). Making repeated portfolio changes that individually make sense if one thinks one can significantly influence returns or risk could turn out being very costly.

A variant of this is that we may loses sight of actions we should probably take that contribute towards progress on a goal in our circle of concern, even if we (correctly) identify it as mostly outside our circle of influence. This might include the broader state of the economy, environment or public health – it’s probably reasonable to think of these as not things we can directly influence, but that shouldn’t be a reason to ignore them altogether. These behaviours should be accounted for by related things within our circle of influence, possibly at a finer resolution (e.g. “I will continue to work, earn, invest and spend” because I am concerned about my own personal economy and living standards), but they might not necessarily be.

I agree that we should focus our energies on things that we can influence; that said, we need to be careful to identify these correctly (or for things that are large, identify what we can influence), and also to be aware that being able to influence something doesn’t mean we should.