Juggling

My slightly random interest in juggling seems to have been revived recently by Stewart Brand who came to my school to give a talk on environmentalism and started off by showing the rather famous clip of Chris Bliss’ juggling finale (Golden Slumbers). Juggling might seem like a completely irrelevant and useless “skill”, and in many respects it is. But it seems like most of the people I know who juggle reasonably well are scientists or mathematicians (head of physics at my school, a biology teacher at my school, some guy on a poster in my maths teacher’ classroom), and there appear to be lots of fascinating parallels between juggling and maths. So in a way juggling is a unique activity combining skill, dexterity, coordination and performance with an intellectual allure irresistible to scientists and mathematicians … and for the sake of some hilarity I’ve made a Youtube vid!

Order:
1. Cascade, MM, BM, RR
2. Cascade, BB, MM, BM, MM, RR, (near drop), RR, Cascade, BB, MM, BM
3. Box
4. Improvisation

MM = Mills Mess BM = Boston Mess BB = Burke’s Barrage RR = Rubenstein’s Revenge

Siteswap notation

There’s a pretty good article explaining what this is here that also investigates the maths of juggling; it’s basically a way of writing a juggling pattern that has mathematical curiosity.

Complex Hearts AI

For some reason from the moment I heard of it, I’ve really loved the game of Complex Hearts. It’s not even that mathematical by nature–you just have to keep track of two sets of scores–but the idea of casually saying “I have -4 + 13i points” makes it an awesome game to play. So I wrote an AI for it. It’s one of the most complex (this will never get old) things I’ve ever written and it feels like a great achievement (until it epically fails against humans), so I thought I’d say something about it. It was written in C#, OOP is fairly central to its inner workings, and it uses just the four standard libraries for C# console apps (System, System.Collections.Generic, System.Linq [I did actually use Linq believe it or not. Sorting a list by value], System.Text) – I got by without using a single ArrayList!

Principles of operation

The program hinges around this single critical function GetExpectedScore(…), which attempts to determine the expected score one would accumulate after that trick if a certain card (c) is played. It’s the largest function in the program, and produces some rather convincing results. It looks at each player (p) in turn and attempts to sum the expected accumulated score from each. It does this by getting a list of point cards below the value of c, finding the probability that p has card c, arranging the point cards in order of point magnitude, then finally summing points*probabilities. It sums points by assuming each player will play the highest point card he can without winning the trick (i.e. dump the most painful card he can on you), and takes into account probabilities of being void, so there’s a sort of cascade going on. Letting P(c) be the probability p has card c, N(n) be the nth most painful card playable by p and V(n) be the score given by the nth most painful card:

ExpectedScore =
P(N(1))*V(1) +
(1-P(N(1)))*P(N(2))*V(2) +
(1-P(N(1)))*(1-P(N(2)))*P(N(3))*V(3) + …

The program sort of has two hearts, a bit like The Doctor. The first (over 200 lines) is two custom types: each player is an object, and, more importantly, the game itself is an object. This allows a trivially easy-to-implement and foolproof undo function, as well as the ability to create a duplicate game for the sake of simulations. This also includes a really primitive function for attempting to assign probabilities to players having cards (see screenshot below). It appears to be sufficient.

The second is about 350 lines of code enclosed in a region aptly labelled ‘clever stuff’. This is where the interesting functions which determine the best card to play, or the best cards to pass, all of which make use of GetExpectedScore (which itself is in this region). The best card to play is the one that has the lowest expected score determined by GetExpectedScore, and the best cards to pass are those with the highest expected scores. These tend to be high hearts, and spades of value above and including the queen.

User interface

I love console programs, and I don’t think I could have made a better UI for this using a Windows form. It’s all nicely colour coded: cyan for ‘info’, yellow for ‘notice’, red for ‘important’, green for ‘question’ and gray for ‘debug’. I even wrote a procedure to print each player’s table of card probabilities:

Click to embiggen.

Seems to work

I’ve test run it a couple of times with actual games, though personally playing the other three players slightly invalidates the testing! The AI seems to make good decisions and appears surprisingly good at not picking up points, hence doing pretty well for itself in my opinion! Apart from some interesting encounters involving code that looks like it was written while drunk (my code is normally pretty terrible) and functions I defined but never finished coding resulting in very strange happenings (“just make it return ’1′ for now, I’ll code it later”), I’ve needed to add minor caveats here and there, such as taking into account the cards currently on the table when evaluating the probability of winning the trick and the points currently on the table when evaluating the expected score from winning that trick, and taking into account the player’s current score when deciding which card to play.

Test run. The two previous players have played the Ace of Spades (AS) followed by the Queen of Spades (QS). The player has two spades from which to choose (JS and KS). The AI recognises that although KS beats QS, potentially winning unwanted points, it realises any spade played will be beaten by AS with probability 1, so the expected accrued score from each card is 0 + 0i.

Limitations

The AI doesn’t know about shooting, or, more importantly, the existence of the 10 of clubs. I really don’t know how to incorporate that into the current structure which is a real pity considering that’s in a way the entire point of having complex scoring (otherwise you’d just have two separate sets of scores to keep track of which have nothing to do with each other). I have yet to code in the rule about breaking hearts, though it’s pretty unlikely to lead with hearts anyway considering that would tend to result in picking up points (unless you play 2H or something). It is also extremely defensive: it assumes every other player is attempting to screw it over, and consequently doesn’t bother trying to screw other players over at all. Perhaps I should include a constant that decides the aggressiveness of the program – the AI will choose to play the card that most screws over another player (c) provided that c’s expected score is no higher than a certain value, or no higher than a certain fraction of c’s value, or something. Additionally, the algo for working out expected scores is actually wrong – it makes an underestimate because it doesn’t use Bayes’ Theorem (though it’s still quite good). I should implement an improvement soon.

British Informatics Olympiad Finals at Cambridge

I’ve just got back from the British Informatics Olympiad finals (they chose the top 14 in the country to take this – I was an experimental error) which took place at Trinity College in Cambridge. Despite a fairly epic fail, I thought the weekend was quite productive and I’ve definitely acquired better skills from the only formal or otherwise training in programming the contestants were (strongly) encouraged to undertake. More photos can be found on my Flickr photostream.

Night shot of housing

As always with such activities, the people there shared many interests, and since programming is (at St Paul’s anyway) an interest few people take vaguely seriously, it was a particularly unique weekend for me in that I could talk about Dijkstra’s Algorithm without getting suspicious sideways glances and a general awkward diffusion of human density away from myself… Pretty much all the people there were doing double Maths and were very much into it, and even at a school like St Paul’s one probably wouldn’t be able to mention the Collatz Conjecture and have every person in the room nod and begin elucidating their own hypotheses on where the proof will (if ever) eventually come from (e.g. graph theory, number theory, computing etc). One of the people who had a big hand in organising and managing the whole affair (Tom), seemed to know a great deal about Physics, Maths and computing and the night before the olympiad he and a few of us had a long argument about string theory, something unheard of even in Physics lessons at school. Tom also seemed to know my maths teacher from helping him set ridiculously hard BMO questions at some point in the past (I think I can just about forgive him for doing that). The atmosphere was also quite singular since geek humour actually worked, and maths and physics jokes got a higher laugh:groan ratio than usual; though I couldn’t help facepalming when, while collecting in papers, Tom remarked ‘all your papers are belong to us’.

I think I probably did get quite a bit out of this whole experience. Since being invited to the finals I’ve been constantly prodded to complete USACO training challenges which are combined with a form of structured training / algorithmic tutorial thing which gives users formal training of algorithms. This training is actually the only time I’ve ever been ‘trained’ in programming and I’d been sort of making things up on the fly since I started programming (in visual basic…) back in Colet Court – I didn’t actually know what a greedy algorithm was until this year, and my understanding of even what algorithms are was still sketchy when I took the BIO for the second time (last year). So by going through a beginners through intermediate algorithms training course was definitely useful for me and I now approach problems more analytically rather than just trying to convince a compiler to automatically do what I would personally do if faced with a problem (no, not give up straight away and watch a film instead). I have to say though that despite its utility I acquired a few bad habits from it. Since for each assignment infinite attempts are allowed, I tend not to actually test programs against anything other than sample data and submit it, hoping something that can solve a specific case will probably work with all other cases. Inevitably it tends not to work first time and rather than sitting down and debugging it, I take the test data and just try to make the program work for that by doing silly things like making loops slightly longer or incrementing variables by 1 randomly. USACO helpfully also provides the full answers for test data. I have to say though that the grading system on USACO is impressive – after you submit a solution the backend code automatically compiles and runs the program for each test case and grades its answer. Inspired, I’ve now got something vaguely similar set up on my Debian server (albeit requiring both FTP and SSH connections to sort of do everything manually).

Another thing I’ve always wanted to do was learn C++ as every linux package seems to require compilation with g++, so C/C++ seems to be the language to learn. Since the BIO Finals required code in C/C++ or Delphi (that nobody used, surprise surprise) I was forced to learn a new language, and after discovering the awesomeness of pointers, I have an incentive to endure the confusion and use some really cool programming features (at the risk of corrupting random critical data in the system memory).

And as always with a visit to Cambridge, I got to see more of the college and living quarters. I have to say, the Corpus rooms were more spacious though assuming a specific comparison is representative of a more general comparison would be displeasing to my stats teacher.

And of course since the BIO is sponsored by Lionhead Studios (gaming company) we got to meet a representative and should find obtaining work experience there much easier.

So anyway, here’s what I remember from the itinerary:

Day 1
Erroll and I arrived at Trinity only to be told we had to be at the porters of Burrell College on Grange Road, which is somehow related to Trinity. After a bit of a trek we arrived, Pauline-style, fashionably late. We were shown our rooms, were provided with food and were shown the computer rooms where we got used to our environments. It was actually a very simple question on summing squares repeatedly (up to 2^63 times) – all we had to do was notice there was a repeating sequence – but the unfamiliar environment and unfamiliar method of file input (fscanf in <stdio> as opposed to fin >> in <fstream>) made me do all sorts of stupid things. I think after three months of USACO challenges in C++ I think I still prefer C# / Java as languages. Perhaps it’s got something to do with compilers (my 2003 MS C++ compiler at home goes kaput randomly).

Day 2
The brain uses an insane amount of energy when working hard and doing olympiads was even suggested (as a joke) as a means of weight loss. For this reason an awesome breakfast was bestowed upon us, consisting of baconey, eggy, toastey goodness. The morning papers were both written, the first being on Turing Machines and the second on emotion/sentiment detection in text. This was actually probably the most enjoyable part of the contest – the questions on turing machines were a bit like a mix of maths, logic and electronis (involving truth table like things and train track systems etc). It was also the only bit I could actually seem vaguely competent doing – an education in maths and electronics probably helped me.

The afternoon was when the hardcore competitioning kicked in with a whopping five-hour paper consisting of four questions (the best people completed two questions). I’ll talk about those later, but I failed quite epically, only managing to write a program to solve a question for about half the test data. It also transpired I’d spent all my time on the hardest question, and that although I saw immediately an algorithm that Dr Forster said worked, my implementation was total crap. Later that evening I managed to think up a linear time program to solve the same problem which when I mentioned it the next morning was apparently the best solution Dr Forster had thought of. I still blame C++ :P

After the olympiad I attempted to take some night photography with a tripod which is apparently banned. Oops. We all then went to dinner at Ask and got quite stuffed up before being asked to eat more in the chill room afterwards.

Day 3
Today was mostly free time in which Erroll, I and another person we met spent our 2 hours of free time pulling newspaper, broadband adverts and IR spectra printouts out of a pool table in an attempt to get the balls out. Our efforts included using mobile phones as endoscopes to get a better view of the inside of the machine, using wire coat hangers as hooks to reach the newspaper and peering inside the machine to aid our end. We were eventually thwarted as we concluded our over-zealous table tilting had resulted in the balls falling out of the mechanism entirely and ending up unretrievably on the bottom of the table. For future reference: pool table lock picking doesn’t work with coat hanger wires.

After an inventive method of going round (in three dimensions) a gate without a keycard I and a few others got to the main Trinity college. The tension was apparently high as they announced the IoI competitors though I didn’t notice; my expectations were clearly low as I had just organised three weeks’ work experience with Microsoft at the same time as the finals. What was nice though was that we got very cool 4GB memory sticks with ‘British Informatics Olympiad’ on them, and we were issued with compulsory free games and ‘Introduction to Algorithms’. I already had the book and had in fact brought it to the contest in order to seem vaguely intelligent with no real intention of looking at it.

My room

The questions

I’ve put thumbnails of scans – click to enlarge. I cut out my retarded scribblings.

Desperate Measures

This is the one I half did, and also the hardest. You’re given a cross section of a polygon and are supposed to divide it into triangles using only given vertices. In the question the polygon is the cross section of a cave tunnel…

My initial (and apparently correct) thought was to cut off all the bits sticking out of the polygon (i.e. turn them into triangles and ignore the outside points) and end up with a convex polygon and subsequently just a triangle in the middle; sort of repeatedly going round the polygon chopping off bits. My second (and apparently better) thought was to go from left to right joining up points, an algorithm that runs in linear time.

River

This is apparently the easiest question: a river (= straight line) of up to length 2^31 kilometres (the unit was some amusing invented thing but I can’t remember what it was) can be split up in one of up to 1000 (=n) ways into n unequal segments (= up to 1000 different sections using up to 1000 different partitions). The question was to split it into n segments so that each different segment is a segment described in a different partition and there’s no overlap of partitions. OK that’s a crap explanation – the scan does it better.

I didn’t actually look at this which is a pity – it was the easiest. When I looked at it before going to bed that night I managed to come up with an algo straight away which would have worked in O(n^2 ish) – the biggest case would have taken about a second to run. Pity I saw 2^31 and immediately moved on when actually doing the competition.

All work and no play

The scan says it all. It was a really annoying question because I started working on it about an hour before the end. I wrote an efficient O(n) algo for finding how many ways there are of making n in such a way, had an amazing pascal’s triangle/combinatorics thing going, and was about to write it when I realised it all got screwed up by the blocks only going up to 10. Unable to repair my program, my final submission only worked up to n=10 (needs to work up to n=64). I might also have forgotten to change the output method from console to file output. Meh.

Spies

I couldn’t think of an efficient way of doing this (not even in the evening though I was very sleepy by then) and am certainly not going to attempt it again until I have lots of free time, i.e. summer. This was the second hardest.

๏̯͡๏﴿

Higher or Lower

DPG came up with an interesting way to engage our interest (or maybe burn time as Christmas drew near) while teaching us about trends down groups and periods in the periodic table: he got us all to play the famous (I think) game of ‘higher or lower’. The rules are simple: A card is placed on the table (or stuck to the whiteboard) face up, and the players have to guess whether the next card, drawn at random, is higher or lower than the one on the board. If you get it wrong, you’re out of the game. If you’re right, you stay in for the next round. The last one remaining wins of course. Most of the mathematically pretentious members of the class (like me) naively played very strictly by the rule of maximising the probability of winning at each round: the risk-averse lot. On the other hand, the riskophiles were partial to going ‘lower’ on the 4 of Spades. Originally I thought it’s always better to play by my method: to long cards lower than 8 and short cards higher than a 8 (for the sake of nomenclature, rather than saying going ‘higher’ or ‘lower’ on a card, I’ll say to ‘long’ or ‘short’ the card – it’s a _bit_ shorter). I didn’t win a single round, but some of the members of the class willing to take risks won one or two mars bars (yes that was what we were playing for…). So what’s going wrong? Does Maths not work?

I eventually came to realise the flaw in the original model I came up with: I thought all that matters is the probability of winning at each round and completely neglected to consider the other players. Eventually I worked out it might sometimes be better to go short on a low card if nobody else is shorting it: there is value in avoiding the crowd. If very few people take the same position as you on a card, if you are correct, you have fewer people to compete against in subsequent rounds so have a higher chance of winning. Cursing myself for having been so stupid and missing out on a mars bar (well, not quite) I set about doing some Maths.

The Mathematics

Let n be the number of different card ‘levels’ in the heirarchy (e.g. 2, 3, 4 … King, Queen, Ace). Normally n=13 since suites don’t matter.

Assumption #1:

I start by assuming the heirarchy system is transitive, i.e. if a 3 is higher than a 2 and a 4 is higher than a 3, then a 4 is higher than a 2. Then we can number these levels 1 to n: e.g. J=10, Q=11, K=12, A=13. I’m basically renumbering the sequence 2, 3 … Q, K, A as 1, 2, … 13.

Let x be the level of the current card that people are playing on. So if the card is a King, x=12

The probability (p) of the next card being higher than x is (n-x)/n and that of the next card being lower (p’) is (x-1)/n. If I were using my original naive method, I’d stop here and at each round work out this probability. If p > p’ I’ll long the card, otherwise I’ll short it. However I need to factor in the other players.

Assumption #2:

This is where I make my second main assumption which is more important and tenuous: I assume that the probability of winning in the end is 1/m where m is the number of players left in the game at that point. This is essentially assuming that every player left in the game has the same probability of winning.

Let h be the number of players who long the card.

The probability of winning (w) if you long the card is p*(1/h)
The probability of winning (w’) if you short the card is (1-p)*(1/(m-h))

Now we have a better method of assessing which way to go. Since you can wait and see how many other people go high/low on a card before deciding on your own position, this method can work. However a bit more work needs to go into this: calculating this probability is a somewhat difficult task: as it turns out,

w = (n-x)/n*(1/h)

which can’t be done in a short amount of time (I certainly can’t sub values in and get a result very quickly – the dividing by h will always turn out to be a mess since it’ll always be like 13 or 7 or something inconvenient), and the second formula is much worse. One way of making this formula easier is finding how many people would have to long a card for the probability of winning with a long position to be equal to that with a short position (where w = w’): a sort of ‘equilibrium point’ at which it’s equally good to go long as short. w = w’ so

(n-x)/n*(1/h) = (1-(n-x)/n)*(1/(m-h))

Which simplifies to:

h/m = (n-x)/n = p

This is incredibly nice: the percentage of people going high has to equal the probability that going high wins for w to equal w’. In retrospect it was sort of obvious I was going to end up with this anyway but it’s good to see it mathematically. This formula is nicer for me because I find proportions and ratios much easier to think about:

h : m = (n-x) : n

If the card is a 8, x = 7.

h : m = 6 : 12

Even better, if we call the number of players who go low on a round h’:

h’ / m = (x – 1) / n = p’
h’ : m = (x-1) : n = 6 : 12

Now that we can quickly calculate h, the number of players who ‘should’ go long, and/or h’, we can work out whether too many people are going long or low. If more people are going long than h, we go short. If more people are going short than h’, we go long. Simple!

Problem?

Some people might notice that h is on the bottom of the fraction in the expression for w and may express concern that h may be 0, and thus the probability of winning if you go long is infinity! I think this doesn’t matter because if you do go long, h becomes 1 and w turns into something sensible.

Game #2

With the assumptions I’ve made, I can also assess a secondary branch of the game that DPG created to spice things up a bit: he gave us the option of guessing the exact value of the first card to be put on the board. If you play this game, if you guess right you win immediately. If wrong, you lose and are out of the game before it even begins. Let’s examine this version. Clearly the probability of winning (k’) is 1/n. If you play the main game, at the beginning the probability of winning (k) is 1/m by assumption 2. The decision of which game to play is thus fairly obvious. For my class, k’ = 1/13 and k is about 1/15. The alternative would have been a good option after all, despite my gut instincts!

Meh this is pointless

Ultimately this is probably a flawed model since assumption #2 is most likely wrong but it does highlight the importance of considering the entire game before launching into playing it by some naively constructed strategy like I did… Perhaps the next step would be to try to model how the rest of the class behaves with some sort of probability distribution and come up with a formula for what to do without seeing what everyone else is doing. Or assumption #2 should be reconsidered. Maybe some system of card counting should be factored in, just for fun! But all that takes effort…

Higher or Lower?