Browse Category

Gaming

Algorithmic Modelling – Alphabear 2

Alphabear 2 is a word game where players are given a two-dimensional grid of tiles. Some of these tiles show letters, along with timers; others are concealed and must first be exposed by using an adjacent letter in a word. Players use letter tiles (anywhere on the grid) to form a word. When a player makes a word, he/she scores points equivalent to the sum of the timers on the tiles that are used. The timers on all tiles that aren’t used then count down by 1; tiles that reach zero become unusable stone blocks.

Usually, this means that you want to form long words that incorporate tiles that have shorter timers; for example, there is a ten letter word on the above board (PEDESTALED), but it doesn’t use the F. After playing this word, the timers on the remaining letters will count down by 1; the P will now have a timer of 2, the first E 10, and so on.

However, the game does have various mechanics that mean this isn’t always the best strategy. For example, one needs to ensure that there are actually enough letter tiles to work with, and that the distribution of letter tiles allows reasonable words to be formed. The game also has players choose bears for each mission which have special abilities such as awarding additional points for certain words. Actually, in hindsight FEASTED might have been a better choice than DEADLIFTS, as I was using a bear that gives a point bonus for words ending in ED.

In addition to scoring points by making words, players also receive bonus points for the largest fully cleared rectangular area. The game identifies this for you. I’m not sure how this is actually implemented, though there are large enough boards (15 by 15?) that it’s probably not the naive algorithm of generating and testing all rectangles; where N is the width of the board that would be O(N^6). There is a DP-based approach where one can keep track of the number of stone blocks that slashes this to O(N^4) which would probably be enough. With more clever approaches it’s possible to knock the time complexity down to O(N^2) – and that’s probably optimal as any less would involve not actually reading some parts of the grid.

Most of the time, this isn’t something to worry about too much. I’m able to clear most levels with no stones at all. However, if we need to take a stone, ideally it should be as far away from the center of the board as possible (note that only the largest rectangular area counts).

Defining optimal play in general is difficult, owing to the spatial reasoning required by the largest clear area bonus, uncertainty of tiles that are yet to be revealed and sheer breadth of options when faced with many open tiles.

Before starting a round, the player has to select bears to use. Optimal decisions here largely depend on the specific challenge being played. A bear that scores bonus points for six-letter words isn’t particularly useful on a tight board where one has only a few open tiles at a time; some bears add time to timed boards, which isn’t useful if the board has no time limit. Furthermore, players select up to three bears each round; these bears can have useful synergies. In particular, I like a combination of “summon three Zs” and “score triple points for words including JQXZ (not stacking, unfortunately)”; “summon ING” or “summon ED” goes quite well with these two as well. I’ve used these to complete a mission deemed “impossible” given the strength of my bears at the time.

We can perhaps begin by focusing more narrowly on optimal play of an Alphabear endgame (where all tiles have been revealed), ignoring special abilities bears may have for now and assuming that the board has a solution. Here is an example:

From this point on, there is no more uncertainty as to what letters we have to use. Interestingly, this board shows that a greedy algorithm where one tries to play the longest possible words doesn’t work. One could begin WORKSHOPPED, leaving RAII, but this is actually an unwinnable state. There are several two-turn solutions, like ROADWORKS + HIPPIE, or WORSHIPPED + KORAI. (Obviously, this is very high-level play; I think I played SKIPPER with this board. That leaves RODIAHWO, for which I’d probably have played something like RADIO + HOW, though HAIRDO + WO is better.)

Given a multiset of pairs of letters and timers L = (l,t)^+, we want to return a suitably ordered list of words S = \left[ l^+ \right] , that satisfies the following properties:

  • legitimacy: every word s \in S is included in the game’s dictionary.
  • resourcing: words do not use tiles that aren’t in L.
  • timing: for each pair (l, t) \in L, l is used in a word before or on position t.

The above set of properties is not correctly specified without a refinement to deal with duplicate letters. There are several ways to deal with this; assuming low cardinality, one approach could be to recognise all duplicate instances of letters as separate letters, and suitably expand the dictionary to allow this. Our list is then L = \left[ (A,3), (B_1,1), (B_2,1), (E, 1) \right], and the dictionary recognises both B_1 E and B_2 E.

I don’t have a good way of finding an optimal solution; I suspect the problem is actually NP-complete; it feels like SAT or 3SAT may be reducible to this problem, though I haven’t worked through the details. Nonetheless, there are several search heuristics we can try. Clearly, on a given turn we must use everything which now has a timer of 1. Also, although this board is an example of why you don’t want to be greedy, in general it probably makes sense to do some kind of ordered backtracking, where one expands the most promising nodes first. I can imagine an A* search could actually work well, though finding an admissible heuristic could be hard.

There’s a fourth property we want as well:

  • optimality: the score produced by the words is maximal.

Going back to our sample board, WORSHIPPED and KORAI will score one more point than ROADWORKS and HIPPIE, because there is one fewer timer tick. In general, we want to minimise the number of timer ticks by playing longer words upfront where possible, as this reduces the number of timers that are still ticking. Once one has devised a feasible solution, it may make sense to perform some iterative optimisation by seeing if it’s possible to bring letters forward. Of course, that approach may get us stuck in a local optimum. I could see some kind of iterative hill-climbing algorithm from the top-n admissible solutions (as found by our ordered backtracking) yielding decent results.

Unfortunately my vocabulary and anagram skills are far from good enough to handle the required complexity, especially under time pressure. Most of the time, successfully playing every letter on the board is enough to complete the mission’s objectives. Interestingly, it looks like the game wasn’t really programmed to deal properly with successfully using every letter but failing the mission. The game claims that there’ll be an additional reward on the reward screen when identifying the board as clear; yet, there is no reward screen as the mission was failed.

Algorithmic Modelling – Codenames

Codenames is a board game designed by Vlaada Chvatil which tests communication. The game is played with two teams; each team splits itself into clue-givers and guessers.

There is a board of 25 cards, each with one (or more) words on them. Of these cards, 9 are owned by the first team, 8 owned by the second team, 7 are neutral and one is the ‘assassin’.

The clue-givers attempt to communicate to the guessers which cards are owned by their team. This is done by giving a one-word clue followed by the number of cards N corresponding to the clue. The rules establish some bounds on allowed associations (for example, ‘sounds like’ clues are not allowed).

I don’t know how much time went into selecting the words to appear on individual cards, but there are certainly many words in the deck that can be interpreted in many ways, which makes the game fun. For example, I can think of quite a number of ways to clue BOND (COVALENT for unambiguity; DURATION, ASSET or DEBT for the debt; JAMES, AGENT or SEVEN or even at a stretch something like CASINO for the character; FRIEND or FRIENDSHIP; STREET or TUBE; CONTRACT, PROMISE or WORD for the idea of a promise; ADHERE or CONNECT, among others). Which one I might pick would depend on the other words on the board.

Guessers then identify up to N+1 cards they think their team owns. This can be based on the entire history of clues given, not just the previous clue. These cards are guessed one at a time; a team is only allowed to make further guesses if they guess ‘correctly’ one of their team’s cards. Teams may refrain from making all guesses.

The game ends either when all cards owned by a team are revealed (that team wins), or if a team reveals the assassin (that team loses).

In practice, clue-givers will need to consider all cards, not just the ones their team owns. The penalty for ‘failure’ varies; the assassin is an instant loss, and revealing a card owned by the other team is also bad. For example, with the cards APPLE, BANANA and GRAPE it would be very tempting to declare (FRUIT, 3) as a clue; yet, if KIWI is owned by the other team (or worse, is the assassin) it might be dangerous.

However, if the other team has already revealed that KIWI is theirs (e.g. with another clue, maybe SOUTH or BIRD) then the FRUIT clue becomes safe. Thus, pre-computing a strategy at the beginning of the game (e.g. by partitioning the eight or nine clues owned into several logical groups while avoiding other words) may not be optimal.

I tend to consider making an effort to win to be a key part of games, and thus what moves may be considered good also often depends on the state of the game. For example, if the opposing team has just one card left, I will give a broader clue that may have more tenuous links in a ‘do or die’ effort to finish on this turn. A less extreme example would be attempting weaker links if behind, or perhaps playing slightly more conservatively if ahead.

Mathematically modelling Codenames can be tough. We can try modelling the game state as a tuple (O, E, N, x, h, f_O, f_E) where O, E, N are sets of the remaining clue words our own team has, words the enemy team has, and the neutral words, x is the assassin, h = (t,w,n)^+ is the history of the game, and f_O and f_E are preference functions of the form h, w, n, O, E, N, x \rightarrow P, returning an ordered list O \cup E \cup N \cup \lbrace x \rbrace. (t, w, n) is a clue meaning that a given team gave a clue word and hinted that some number of cards was relevant. This already abstracts two difficult parts away – ordering the clues, and determining how many of the top preferences to pick.

I think the preference functions need to take into account previous clues from both teams; if a previous clue could clearly have corresponded to two words and I picked the wrong one, it might be fairly high on the list even if unrelated. Similarly if this scenario happens to the opposing team, I would probably avoid the word that would blatantly be theirs.

The notion of degree of confidence also isn’t captured as well in our ordering; going back to the fruit example, having a clear ordering would imply that clues for less than 4 items could reliably result in correct guesses (if we knew that APPLE was by a small margin the best pick, we could safely and confidently give (FRUIT, 1) to clue it, which seems wrong). One could imagine modelling these with selection probabilities, though things would be even more complex.

The above representation still seems computationally difficult to work with. The evolution of the preference function as one moves from one state to another is unclear (so in that representation it is fully general), making lookahead difficult. It doesn’t seem like a greedy choice is always best; for example, given eight clues that are reasonably divisible into four pairs, a clue for 4 words taking one element from each pair might be a bad idea if the other words can’t easily be linked.

We can proceed by simplifying the preference functions; a simple approach could be that for each w, n each team has a persistent preference function that returns an ordered list of O_0 \cup E_0 \cup N_0 \cup \lbrace x \rbrace. The preference functions during the game then return the subsequence of that list that contains strictly the words still left in the game. This of course doesn’t take into account past information or clues from the other team.

With this, we can attempt to solve the game using standard techniques; assuming that the vocabulary of clues is bounded (let’s say it must be from the Linux dictionary), a game state is winning for the current team if there exists some word for which the preference function returns everything in O as a prefix. A state is losing if all moves in that state produce a state which is winning for the opposing team.

We can generalise this to a simple probabilistic model as well; the preference ‘functions’ instead return a discrete random variable that indicates either guessing some word or passing. A simplified model could then, at the start of the game, assign weights to each candidate indicating the relative probability that candidate would be selected. These can be normalized to account for a pass probability. As words are removed from the board, the probability of the remaining words being selected scales (we can imagine a simple rejection-sampling where we discard words that aren’t actually on the board any more).

The algorithm for the probability that we get a win from a given state is then slightly more complex (though I think still reasonably covered by standard techniques).

On Deckbuilding Games and Slay the Spire

Deckbuilding is a genre of games where players start with a (usually) standard deck of cards and then improve it over the course of the game. This can involve acquiring new cards that are usually more powerful than the initial set of cards and/or synergise in better ways, upgrading existing cards, or even removing cards that are weaker or less relevant so that one is more likely to draw the (better) remaining cards.

These games typically offer some replayability because the sequence of decisions one may have on how one can improve one’s deck differs from game to game; what it means for a deck to be successful can also vary depending on what the other players are doing.

Slay the Spire is a player-versus-environment RPG where combat is driven by a deckbuilding mechanic; players start with simple offensive (Strike) and defensive (Defend) moves plus possibly a few class-specific cards. The combat is turn-based. On a player’s turn, the player draws 5 cards. Cards have an energy cost, and players initially have three energy per turn to play as many cards from their hand as they want. Of course, there are cards and other mechanics that can be leveraged to obtain additional card draws or energy. Players are also shown their opponents’ next moves, which allows for some degree of planning; a simple example of this could be deciding to eliminate a specific monster in a group, because it is about to attack.

In terms of gameplay, the start of the game does feel relatively rudimentary as the player always has the same or a similar deck. However, each time a player defeats a group of monsters, he is given the option (but not the obligation) to add one of three cards to his deck.

The options that come up in the first few rounds will typically shape how the deck develops. For example, while most cards can be upgraded once only, there is a specific card called Searing Blow that may be upgraded multiple times; eventually, it can develop into a card that costs 2 energy but yet deals far more damage than Bludgeon, a 3 cost card that deals pure single-target damage. It is a viable strategy to build a deck around this, eliminating other cards from the deck so that one draws it on every turn; there are cards like Double Tap (which, for 1 cost, doubles another attack) that can further enhance this type of deck.

Conversely, I frequently play in a style which relies on combining cards that give a constant strength bonus to all attacks along with cards that attack multiple times for small amounts of energy. That said, some degree of flexibility is important, as the choices given to the player will be different on different plays; being wedded to a single strategy can be dangerous, as specific key cards may not be available.

Players can also acquire relics which further influence game mechanics; these can simply provide boosts (such as “every 10th attack does double damage”), make certain styles of gameplay more attractive (“the third Attack card you play each turn boosts your Dexterity by 1 for the rest of the combat”) or even significantly change game mechanics (“retain your hand rather than discarding it” or “if you empty your hand, draw 1 card”). These are random (and apart from at the shop / rewards from winning boss battles, players aren’t really given options here) so, as before, planning on specific relics becoming available is also typically not a good solution.

Winning the game unlocks a new-game-plus mode called ascension; players start at Ascension 1, which increases the rate at which elite enemies spawn. Winning the game on Ascension 1 unlocks Ascension 2, which applies the restrictions of Ascension 1 and makes normal enemies do more damage. This increases incrementally up to Ascension 20. I’ve got up to 16 on one of the characters. At high levels there’s not very much room for error; I have had a 10 win-streak without Ascensions, but struggle with high Ascensions quite a bit. I think I tend to force my deck to fit a certain mold perhaps too early on; this can get scuppered if I subsequently am unlucky.

Another challenge a player can take on, as with many other games, is speed-running, or attempting to win quickly. Playing fast (as shown in the screenshot above) limits one’s time for decision making. For example, I normally plan my entire route through the map for each level at the beginning of the level, but that of course takes a bit of time. A normal, more relaxed game can easily take 30-40 minutes, especially if I’m playing with a relatively less aggressive build.

I’ve played the game for about thirty hours or so. It has been enjoyable, and the Defect character (an automaton that manipulates a queue of orbs) is particularly fun, if difficult to use. In terms of educational value I think the game demands a decent intuition of probability, as well as understanding how cards may work together. There are some synergies that are explicit or clear, but others are often less obvious and require some thought/experimentation.

Colour Rush (Board Game: FUSE, Kane Klenko)

While I’m not sure I would go the full length to say that efficiency is the highest form of beauty, I’d certainly say that I can find efficiency to indeed be beautiful. In controlled environments, I enjoy testing my own efficiency (typing tests, programming and Sudoku competitions, competitive Sims). Many of these environments feature elements of uncertainty, meaning that managing probabilistic outcomes is key to being efficient (in Sudoku bifurcation can sometimes be faster than reasoning through complex logical chains; in a programming contest, you might luck out on some buggy or sub-optimal algorithm actually passing all test cases anyway). I’ve recently enjoyed a challenging game which has probability management at its core.

FUSE is a real-time dice game from designer Kane Klenko. Players play bomb defusal experts who are trying to defuse bombs; this is represented by rolling dice and placing them on ‘bomb’ cards to match constraints. The team rolls some number of dice, and then allocates them to the cards, incurring penalties if some of the dice cannot be allocated. The game itself has a hard time limit of 10 minutes, so quick thinking is encouraged as players get more turns (and thus more rolls of the dice).

The dice are almost standard six-sided dice; interestingly, I noticed that it was not the case that opposite faces of each die added up to seven (2 was opposite 4 and 3 opposite 5, for some reason). The dice come in five colours (red, blue, black, yellow and green), and there are five dice of each colour. Card constraints may involve numbers, colours or both, and vary widely in the difficulty; easy cards have requirements like “two dice matching in either colour or number” or “A – B = 2”, while more difficult ones can involve building a six-die pyramid where each die is a specific colour. The bombs are rated in difficulty from 1 to 6, skipping 5.

Some bombs also introduce ordering constraints, requiring players to build a tower or pyramid (and players are not allowed to build unsupported structures). There is also a dexterity element here, as the penalty for knocking over a tower or pyramid is losing all progress on that card.

I’ve only played solo or in a team of two. Playing solo, a player draws and rolls three dice at the beginning of his/her turn, and then allocates them to a pool of four active cards, possibly placing multiple dice on a single card. At any time (except towards the end of the game), there are four active cards and five cards in a ‘market’ ready to become active when an active card is completed.

I’ve been able to complete the single-player “Elite” difficulty (getting through 23 cards in 10 minutes) about half of the time if playing with a random mix of 27 cards, and have done it (once in ten attempts or so) if playing with cards drawn from the most difficult sets (i.e. all the level 6s and 4s, with all remaining cards being level 3s).

I made some simple tactical observations regarding card constraints. For example, there is a level 2 card requiring three numbers that sum to 11. If I have a free choice of a number to play there, I would play as close to 4 as possible (considering that two dice most likely sum to 7).

I think the main strategy in solo play involves ensuring that one’s cards don’t end up having conflicting demands, as far as possible. For example, consider the following set of cards.

This is an awful situation to be in, because apart from one space for a 1, all of the cards here demand high numbers to start. Four decreasing numbers only admits a 4 or higher (and even then, I find starting that card with a 4 very restrictive as it forces 3-2-1); the 15 sum only admits a 3 or higher (and then forces 6-6; I usually play one six and then on a later turn find a pair adding to 9). Misaligned numerical constraints can be painful; misaligned colour constraints might be even worse because colours are sampled without replacement (well, until card(s) are cleared or penalties are incurred). There is a level 4 card that demands four dice of the same colour, which I try not to pick up.

There are many cards that have rather specific requirements (e.g. a specific colour and number); I tend to try to carry one or maybe two of these at a time, while trying to ensure the rest of the cards cycle regularly. The penalty for a unused die involves re-rolling it, and then removing a die that matches in terms of colour or number (if possible).

Although the game only lasts ten minutes (or less, if the deck is cleared in time), I’ve found it to be highly addictive, especially difficult runs on the elite difficulty. I’d expect times to vary quite widely as it’s a dice game, though I’ve noticed that I run out of time with between one and three cards from the end most of the time. I’ve never counted, but it wouldn’t be unreasonable to average fifteen seconds for a turn, and to some extent things average out over 120 selections and rolls. As mentioned above, I think a key part of solo FUSE strategy involves managing interactions between the requirements of active cards.

Minor criticisms would include some disconnect in the difficulty of the cards. I find that most of the level 6s are less luck-dependent than some of the lower level cards, like the level 3 “any 5, a yellow die, and a green 2”. More bizarrely, the ‘6-5-4 pyramid’ card in the photo above is only level 2, though it’s considerably more restrictive than the ‘sum to 15’ card also in the photo (level 3). There might be a case for a more permissive card being rated higher if the cost of verifying correctness is higher (e.g. ‘three digit prime number’), but I don’t think adding three numbers introduces much overhead.

The ceiling for individual card difficulty also isn’t very high. The highest stacks are of height 5 (with very loose constraints) and pyramids of height 3 (using six dice). I’d imagine there would be scope to define some level 8 cards that might use seven or more dice and/or require combinations that are stricter or more complex, like a six-die pyramid where each die not placed on the ground level must equal the sum of the two dice directly underneath it, or even something like this:

I’ve played this with a friend from Imperial as well. With two players, each player has two active cards, four dice are rolled and each player must take two dice. We only played up to the standard difficulty. I’d like to play this with a bigger group, though; communication gets much trickier, and also with two I am able to maintain sufficient context in my head to compute a good allocation of four dice across two sets of two cards. With five, there are 10 active cards, which would probably be unreasonable to keep track of.

In summary, I’d highly recommend this game based on my solo/pair experiences. I’ve probably had about twenty to twenty-five playthroughs in total, and have enjoyed it thoroughly even though I generally don’t enjoy real-time games. Each run is short, but can generate an adrenaline rush, and the difficulty level is highly configurable so it should be possible to find a level that works well. I might even extend the game with some custom “hard mode” cards (this can be done by getting opaque sleeves so the backs are indistinguishable). I haven’t yet had the opportunity to play with a larger group, which should bring new and interesting challenges too.

Taking Risks on Rotations

I haven’t owned a gaming console since the Playstation 2, mainly because I’ve found PCs to be sufficient for my own purposes and I don’t do very much gaming in the first place. I already have a pretty good PC for some of my own work (such as programming and some image/video editing I’ve done in the past). Nonetheless, I do enjoy watching a few YouTube channels which feature playthroughs of games with commentary, and I’ve certainly seen a lot of news regarding Nintendo’s latest console, the Switch.

One of the launch titles for the console, 1-2-Switch is a minigame collection which largely serves to demonstrate the capabilities of the Switch’s controllers (or “Joy-Cons”). The controllers have buttons, motion sensing capabilities, a camera (“Eating Contest”) and some kind of precise vibration (“Ball Count”). Most of the minigames seem simple and somewhat fun, as well as relatively balanced (in fact most games don’t really feature a way for players to interfere with one another – several others also have players’ roles over the course of the entire minigame being largely symmetric). There are a few that seem unbalanced (“Samurai Training” – assuming equal probability of success the first player has a greater probability of winning), though there was one that was clearly unbalanced in favour of the second player, that being “Joy-Con Rotation”.

The game invites players to rotate their controller about a vertical axis as much as possible, without otherwise disturbing it (e.g. by tilting the controller) too much. Scores are measured in degrees of rotation, with “unsuccessful” turns (e.g. too much alternative movement) scoring 0. Players get three rotations in turn, and then the score from their three turns is added up. In a sense this gives the second player an advantage; on his final turn he needs to know how much to rotate the controller to win, and should aim for precisely that. The problem we’re analysing today is then: how do we make a decision on how much of a rotation to attempt if we’re the first player, and how much of an advantage does the game give the second player (at least as far as the final turn is concerned)?

Let’s make a couple of simplifying assumptions to this:

  • Let X_i be a continuous random variable over [0, \infty) and some is. The probability mass function of the X_i, f_{X_i}(x) are assumed independent, continuous and tending to zero as x tends to infinity. Furthermore, for a given value of x representing the number of degrees player i attempts to rotate the controller, we are successful iff X_i \leq x.
  • We assume scores are continuous (in the actual game, they’re only precise down to the degree).

Now, assuming we aim for a given rotation x, the probability of a win is then approximately f_{X_1}(x) \times (1 - f_{X_2}(x)), which we seek to maximise. Thus, for a simple example, if the X_i are exponentially distributed with parameters \lambda_1 and \lambda_2, we then seek to maximise the function

g(x) = (1 - e^{-\lambda_1x}) \times e^{-\lambda_2x}

This can be minimised, and yields a solution of x^* = \frac{1}{\lambda_1} \log \frac{\lambda_1 + \lambda_2}{\lambda_2}; this gives the first player a winning probability of

\left( \dfrac{\lambda_1 + \lambda_2}{\lambda_2} \right)^{-\frac{\lambda_2}{\lambda_1}} \left( \dfrac{\lambda_1}{\lambda_1 + \lambda_2} \right)

So if both players are equally skilled in terms of rotation ability (that is, \lambda_1 = \lambda_2) then the first player wins with probability of just 0.25. Furthermore, we can find out how much better player 1 needs to be for an even game (that is, the value of k for which \lambda_1 = k\lambda_2); we formulate

(k+1)^{-\frac{1}{k}} \left(\dfrac{k}{k+1}\right) = 0.5

which works out to about k = 3.4035. If this player went second, however, he would have an over 0.905 probability of winning!

The multiple trial case is interesting, especially because it seems like the problem does not demonstrate optimal substructure; that is, maximising the probability you win for a given round doesn’t necessarily mean that that’s the correct way to play if going for more rounds. For a simple (if highly contrived) example; let’s suppose we play two rounds. Player one can (roughly) make rotations up to 50 degrees with probability 1, 200 degrees with probability 0.3, and more than that with probability 0. Player 2 can make rotations up to 49 degrees with probability 1, 52 degrees with probability 0.6, and more than that with probability zero. To win one round, you should spin 50 degrees (win probability: 0.4); but to win two, if you spin 50 degrees twice, your opponent could spin 52 once and 49 once (leaving a win probability of 0.4); going for 200s and hoping for at least one success gives you a win probability of 0.51.

Perverse Incentives

gametheory

I do watch a couple of Let’s Plays on YouTube, and one game that a couple of channels have been playing is Trivia Murder Party from the Jackbox Party Pack. I’ve found the format to be interesting and relatively well-designed for building tension, though there are a few weird edge cases because of how the rules are laid out.

The final round has rules as follows:

  • One player is in the lead (the player with the fewest number of spaces left to the finish line).
  • Players are presented with a category, and need to decide if objects presented fit that category or not. The player in the lead has two objects; other players have three (this is a rubberbanding measure used to encourage them to catch up).
  • For example, a category could be “Asian Countries” with objects Russia, Shanghai and the USA. In this case players should only select Russia (Shanghai is a city, and the USA is in North America).
  • For each object correctly classified, players advance one space on the board. No penalties are issued for objects that were incorrectly classified.
  • The player with the lead moves first. If he is across the finish line, he wins (independent of what non-leading players do).
  • In the event of a tie, the highest ranked player (based on the previous rounds) who is not in the lead takes the lead. Furthermore, all tying players apart from the new leader (including the old leader, if relevant) move back 1 space.

One strategy of playing the final round, and an arguably sensible one is to always try and answer the questions to the best of one’s ability. Yet, the aforementioned rubberbanding mechanism means this isn’t always optimal – suppose you’re playing against an incredibly knowledgeable opponent who implements the maximising strategy. Furthermore, suppose you’re in the lead, with 5 spaces to go before finishing, while your opponent has 7. Then, consider:

  • If you advance 2 spaces, you’ll have 3 spaces left to go whilst your opponent has 4. Then, no matter what you do, your opponent will take the lead on your next turn, and you’ll lose.
  • If you advance 1 space and your opponent advances 3, you’ll both be at 4 spaces to go. Because of the tie rule, he leads and you get pushed back one space. This brings you to (5, 4). Now, as a non-leader advance 3 spaces; no matter what happens you retake the lead. Finally, advance 2 spaces and win.

We can generalise this to solve the two-player case, by considering what is a winning position – in the case where both players have very strong trivia knowledge, but the opponent always advances the maximum number of spaces.

  • (1, n), n \geq 2 is clearly a winning position. Simply advance and exit.
  • (2, n), n \neq 1 is also winning for the same reasons (and (2, 1) is losing).
  • (3, n) is a bit more interesting. n \leq 2 is clearly lost. But (3, 4) is actually lost too, because that becomes (2, 1) or (3, 1) after one turn, both of which are losing positions.  (3, n), n \geq 5 and greater are won; advance to (1, n-3) and win.

Having considered a few cases, we can use what’s called induction to determine the rest of the winning positions. What this means is that we are defining winning positions in terms of whether other positions are winning. This can be dangerous if we produce circular definitions, but the relationships we use here are well-founded in that we maintain that the total number of spaces left to go for both players always decreases, for each of the sub-problems we look at.

We thus say that a position (p, q) is winning, if and only if any of the following are true:

  • p = 1, or p = 2, q \neq 1.
  • p > q + 1 and at least one of (p-3, q-2), (p-2, q-2) and (p-1, q-2) is winning.
  • p = q + 1 and at least one of (p-3, q-1), (p-2, q-2) and (p-1, q-2) is winning.
  • p = q - 1 and at least one of (p-1, q-3) and (p, q-3) is winning.
  • p = q - 2 and at least one of (p-2, q-3) and (p, q - 3) is winning.
  • p = q - 3 and at least one of (p-2, q-3), (p-1, q-3) and (p + 1, q-3) is winning.

We can derive a similar inductive rule for cases where one always maximises the number of answers: for each of the “at least one of” choices, always pick the first option. We can then consider when the (probably) “intended” strategy of trying to answer to the best of one’s knowledge fails to be optimal. In terms of implementation, the inductive definition above swiftly lends itself to a dynamic-programming implementation, whether “top-down” or “bottom-up”.

I’ve only considered the 2 player case because it’s relatively simple to analyse… things get substantially more complex once we go beyond that, especially factoring in the tiebreaking rules based on first-round performance. In practice, given that the questions can be difficult and unpredictable, at least for me it would probably be too risky to try to take a dive like this – but I can see this becoming relevant if expert players played this.

A Software Engineer’s Perspective on Shenzhen I/O

I had some opportunity to have a bit of a break over the Christmas and new year period, and James recommended this title to me about a month ago or so, so I thought I’d give it a shot. It’s essentially a kind of competitive hardware programming game – you’re given a task to complete, and the challenge is to build a circuit exhibiting the specified behaviour. Of course, in practice this is wrapped in a pretty fun if frivolous story. To do this, you have to arrange various components on a circuit board, such as microcontrollers (which allow some form of assembly programming), bridges, logic gates, etc. The verification interface (pictured in the screenshot) definitely reminds me of Quartus II.

I did some x86-64 assembly programming during my first year at Imperial, and thus initially hit a bit of a snag (I kept typing in commas between operands, for a bit wondered why cmp, jne or shl weren’t valid commands, and also tried to perform arithmetic operations with both source and destination registers – you have to use an accumulator). It didn’t take too long to figure things out, though.

I’d say the first puzzle which got tricky was this one (there was an earlier one on using a greedy algorithm for coin change which might have been a bit tricky too):

  1. You will receive a signal on a non-blocking IO channel that consists of three packets. The first indicates the location to which you must move a robot using a motor, the second indicates the number of pulses to clean the plants at that location (?) and the third indicates the number of pulses to spray them with nutrition.
  2. To control the robot, you have to use its motor. Fire a signal of 100 for one pulse and then pull back to 50 to move the robot forward (increasing numbers); fire a signal of 0 for one pulse and then pull back to 50 to move it backward (decreasing).
  3. The clean and feed steps must be done for precisely the correct number of cycles.
  4. (Implicit) You may assume that there’s no overlap in signals (i.e. the robot will always have finished its feed steps before it gets another packet).

To add to the challenge, the microcontrollers have limited amounts of memory, and thus our programs have to be pretty short. As tasks grow more complex, we need to break them down into smaller pieces; we then end up needing to define protocols between the components. For example, for the above problem, the workflow is as follows:

  1. The “main” (first) module, upon receiving a packet, dispatches the target location to the second module and then blocks until said second module has sent a signal back.
  2. The second module compares the robot’s current and target locations, and submits commands to a third module (the one in the top right hand corner) to drive the robot to the target.
  3. The third module simply drives the motor to move the robot one step forward on a 0 input, and back on any other input.
  4. Once the robot is in the right location, the second module signals back to the first, unblocking it.
  5. The first module reads the rest of the packet and executes the clean and feed steps appropriately.

While this is of course different from what most software engineers will be doing in practice, I think it is not unreasonable to use this as part of teaching computer architecture and/or assembly (hello first-year Imperial students!). I think the game does teach a couple of useful ideas.

  1. Abstraction. This becomes critical for some of the larger problems. Quite a number of the tasks I’ve completed so far have involved developing protocols that use message passing between two or three modules.
  2. Optimisation can be painful. Most of the time the cleanest factoring is not going to give you the best score, to say the least; I think most users will experience some pain rewriting assembly to fit in fewer lines and/or run with fewer instructions.
  3. Complex conditional structures and gotos. You can use jumps, but those tend to be expensive; it thus becomes pretty common to use nested tests (teq, for example, checks if its two operands have equal value). Tests set a three-valued flag; instructions can be preceded by “+” or “-” to be run only if the flag is set to true or false respectively. Rather nastily, the flag can be set to neither as well (there is a tcp instruction that indeed writes the three-valued output to the flag!)
  4. A reminder to consider edge cases. For the Coin Change circuit, the test cases did include a case with exact change, as well as a case where only the largest coins were needed. I’m not sure if the robot test cases included anything too sneaky beyond no movement being required.

Highly recommended; in addition to all the fiddly circuitry there’s also a pretty cool card game that’s a strange hybrid of FreeCell and Spider Solitaire. I’d give this a 9 out of 10, easily. That said, I think people with no prior programming experience would find the learning curve very steep. The game does pretty well at introducing some useful constructs via suitably contrived tasks (there was one on the ROM module, one on the I/O expander, and one about using the digits of an integer as flags) to help mitigate that, though.