I posted yesterday about using classic deterministic strategy games like Reversi (aka Othello) as a test bed for voting systems. The problem is that the experiment I described is actually quite hard to coordinate.

After some refinement of the idea I came up with the following randomization strategy for producing a game that, over enough runs, will produce something not totally dissimilar from this experiment.

The initial idea is to use a voting mechanism which can be repurposed into a variety of systems. I don’t know if this system has a name. I refer to it as gin ranking for historical reasons (I initially started using it on types of gin for a blind taste testing). It’s very simple: You first assign grades to everything, you then put the items in each grade in a strict order of preference.

This can then be turned into a vote in a variety of ways because it provides both grades and a strict ordering of the candidates: You can use a condorcet system, you can use approval voting on anything >= a certain grade, you can use range voting, you can use majority judgement, etc. So we don’t have to decide just yet what voting system we’re going to use (more on this later).

But we can also use this ranking in a single player game. Here is how you play Randomized Ranked Reversi:

It’s played on a normal reversi board with the normal reversi rules. All that is changed is that you may be started in an arbitrary board position and the way you make your move.

Your turn consists of being presented with a list of options for moves. I still don’t have a good sense of whether providing the list of all possible moves will be an overwhelming number. If is, you get presented a random subset.

You gin rank this set of moves. A move is then randomly selected based on your rankings. The exact mechanism doesn’t matter terrible – all that matters is that if you ranked A better than B you should be more likely to get A, and if you graded A better than B you should be significantly more likely to get it.

Your opponent can either be an AI or another player. For our purposes it will be an AI.

This gives a strong incentive to get your vote correct in all the particulars – ranking something well makes it likely to be picked, ranking something badly makes it less likely, and your grades then influence those probabilities even more strongly.

How do we use this game to run the previous experiment?

Well, the idea is we make a slight simplification and ignore history. All we care about is a board position (including whose turn it is) and the votes by users on moves from that position. So every play of the random game is a contributing a vote.

At any given time we have a population of people playing the game and a set of board positions we’re interested in the answer to. The goal is to get a minimum number of votes on each interesting board position.

When a new player starts they are given a random board position that we are currently interested in gathering more votes for. They then play randomized ranked reversi against an opponent who behaves as follows:

1. If there’s a move I could make that would put the player in a board position I’m currently interested, make that. If there is more than one, pick the one which currently has the most data already gathered
2. If there are existing votes for my position, pick one at random (preferring ones in which the player won) and run the RRR algorithm to pick a move from that
3. Fall back to some fairly dumb AI. Might even just pick a move at random

We can now use this to answer the experiment I previously proposed, as long as you restrict yourself to voting strategies that can be applied to gin ranking. You do it as follows:

In order to play a game as strategy X with N voters, you proceed as follows:

If we are in a state where we have M votes for that state we do one of three things:

1. If M is >= N, we sample a subset of size N from M (with or without replacement? Not sure), run the strategy on that sample and play the winning move
2. If M is < N but still pretty large we generate a population of size N by sampling with replacement and run the strategy
3. If M is too small, we submit it to our players as an interesting board position and get them to fill it out. We pause the simulation until they have done so.

What are the benefits of doing it this way?

• has much lower coordination costs – people don’t need to wait for the other people in their group to vote in order to make progress
• by not imposing a voting system up front you get a lot more reuse out of the data
• It might actually be fun to play. I suspect playing the real version of the experiment would be a nightmare slog of waiting for other people to finish voting
• If you institute some sort of leader board as an incentive to win, the players are given a fairly strong incentive to vote honestly and accurately

The main downside is that it suffers badly from sparsity of data – I expect 90% or more of positions in a given game will be unique. There are a lot of valid reversi boards. I don’t know how many, but I expect it to be on the order of 2^100. The fact that the valid moves are quite constraining and people will tend to make similar decisions should help, but I don’t know how much. It might be possible to help this by steering some subset of the players randomly assigned moves towards boards we want, but you can only do that so much before people cotton on and it starts to distort the results.

I still don’t know if I actually care enough to implement this, but in this incarnation it sounds like an interesting enough project that I might at some point.

Pozorvlak has an interesting blog post spawned by this rant by Vinay Gupta.

The TLDR is that he wants a concrete strategic plan for how you would run a government ministry whose goal it was to promote dancing, getting high and fucking.

Whilst I’m a very boring person who only has a more than passing interest in one of the three (no prizes for guessing which), I’m sufficiently megalomaniacal to believe that obviously I should be put in charge. So here’s an outline of my plan to utilize the forces of central planning and bureaucracy to get the population both high and laid.

I’m leaving aside the question of whether this is a good idea. This post will focus on how I would do it rather than whether we should do it.

Getting High

Decriminalization

It’s pretty hard to be in charge of Getting High if it’s illegal to get high. So let’s fix that.

Step 1 is to simply decriminalize the consumption of drugs. Don’t care what it is – if you want to put it in your body that’s ok with us.

The sale of drugs is another matter. A lot of drugs are very harmful. And a lot aren’t. I would form a department of the government whose goal was to research in an objective manner the effects of various drugs and to determine which should be made legal and which should remain banned due to adverse individual or social effects. It will also be responsible for quality control standards on all drugs sold.

I’m going to go out on a limb here and say that I expect to very quickly decriminalize the use of both Marijuana and MDMA. I’ve pretty limited knowledge of the subject, but based on a little bit of reading I feel semi-confident in saying that these are probably not substantially worse for you than already legal drugs like alcohol, caffeine and cigarettes and that their use is sufficiently widespread that keeping them illegal would basically be no more than a fiction anyway.

Licenses for the sale of alcohol would be extended automatically to include licenses for the sale of other legal highs (perhaps not all of them? I don’t know). Whilst bars and stores would not be required to sell them, we would hope they would do so and would run a marketing campaign to encourage it.

Ensuring quality and price

The second government institution I will form is in charge of flagrantly and maliciously interfering with the free market like a damn liberal hippy. It’s responsible for the producing of legal highs. It will produce a cheap, high quality instance of all legal drugs (including alcohol, cigarettes and caffeinated beverages as well as currently illegal drugs). These will be sold at a profit, but profit margins will be kept deliberately low and production will be tax free. Additionally all profits will be ploughed back into the ministry budget.

The goal here is to basically undercut the competition. By ensuring a steady supply of cheap but decent drugs you force the market to compete on quality rather than price. As well as making sure good drugs are affordable to all it has the nice feature of making it quite difficult for the existing criminal elements to compete.

Dancing

My plan for dancing (which incidentally should also improve our quality metrics on getting high and fucking) is to institute a series of certifications for clubs and bars.

These certifications will have three incentives attached:

1. Tax breaks
2. Discounts on government highs
3. Marketing: The ability to say you are government certified in various ways. A/B testing will be performed to determine the effectiveness of various different phrasings of the certifications on custom. e.g. Out of “The Man thinks we’re awesome!” and “Government certified not-a-shithole” which is likely to be more effective?

Certification criterion will include but not be limited to the following:

1. Enjoyment, as measured by our expert (and socially diverse) panel of random club and bar samplers (official job title: “I have the most awesome job ever”)
2. Cleanliness
3. Safety
4. Inclusivity (price of entry, obnoxious bouncers, etc)
5. Cost
6. Spaciousness

Each of these cause the club to accrue points, and points mean pri- err. certifications. Each certification level requires a minimum score from each of the categories and a total score across all of them.

The certification levels will be kept deliberately unbounded so you can always reach a higher level of certification. The first time a new level of certification (e.g. the first club to reach certification level 10) is reached, the government will sponsor a massive party in the relevant venue in celebration. It may also be worth sponsoring parties in other high quality venues from time to time.

Additionally, specific facilities are encouraged and come with their own certifications, subsidies and rewards. These include:

• On site medical facilities (nothing too extreme, just basic care for if you’ve injured yourself or had too much of something)
• Chill out rooms for people who want a break or want to go take something a bit more relaxing
• Rooms available for rent (this is actually a good idea regardless of whether you want to encourage sex. Sex will happen, and this helps make sure it’s in a safe place)

There will also be a separate scheme providing free contraceptives in clubs, regardless of their certification level.

Additionally, the government will perform regular surveys about access to clubs. In areas where there is an indication of a high unmet demand (or an unwillingness of the existing venues to meet government certification standards) we will subsidize the creation of clubs designed to meet a high level of quality. Similar to our production of drugs, these will be run in a tax free low profit manner for which the profits will be returned to the ministry budget.

Fucking

This is the hard one. So to speak.

Hopefully the increase in dancing and getting high will lead to a greater amount of fucking. But the simple fact of the matter is that the people most in need of the solutions we hope to offer in this space are the people least likely to willingly avail themselves of them.

In the interests of exploring solutions to this problem we will found the department of “sex is awesome” education. It will explore solutions to this problem.

The primary tool of this department will be Science. I would be extremely surprised if anyone actually knows what works here. Different things need to be tried to see what works.

First, we need to start with educating the children. Hangups about sex start young, and need to be addressed then. A/B testing will be performed to determine the optimal way to get teenagers talking to adults about sex in a comfortable no-judgement manner. Schools will be provided with at least one councellor whose job it is to address any questions they have. Parents who are uncomfortable with these goals for their children will be kindly invited to go practice the goals of this department with themselves.

For the generations for whom the damage is already done the problem is more difficult. I don’t have a good solution right now, other than that we should fund research on how to deprogram people of some of their more negative attitudes, so I’m going to pass on it for the moment. Hopefully everything so far is enough to trigger social change and that will gradually improve peoples’ attitudes as a whole.

Mini conclusion

I’ve actually more or less convinced myself that most of this is a good idea in the course of writing this. I’m not sure the details work, but I suspect where they don’t it’s merely in need of modification rather than outright dismissal.

Edit: I’ve realised I’ve not answered a lot of the questions from the original post. I’ve largely been focused on policy.

How do you measure your department’s effectiveness?

There are a couple obvious things to measure.

Firstly, we measure the results of certification. If an increased level of certification does not lead to an increase (or at the very least a non-decrease) in popularity we are doing something wrong.

We measure sales of our brands of drugs vs other ones. If we’re not selling well then something is wrong with our strategy and we should fix that.

We conduct random polls of people to find out what they think of us.

How do you recruit and train new DDGHF staff, and what kind of organisational culture do you try to create?

This is a tricky one. There are two types of personality type we need here: We need people who are really good at organizing things and people who are really inclined to party.

I would be inclined to focus on the former more than the latter – the goal here is to get the nation to party, not to get our department to. The main things I would do to offset this are quite simply to impose from on high not taking ourselves too seriously and to throw regular parties to break any ice that might form.

How does the new broom affect other departments?

Well, the effect on Justice is obviously quite a big deal due to the changing laws on what’s criminal.

I have a sneaking suspicion it might do some interesting things to tourism. Not sure why.

Already mentioned the changes to education. It’s probably confined to those.

I have absolutely no idea what it’ll do the the economy. It basically just throws all the dice up into the air to see where they land.

Not sure beyond that.

How do we manage diplomatic relations with states that are less hedonically inclined?

Invite them around to a party? It depends who they are and what their objections are.

One concern is trade sanctions. A ready supply of legal drugs makes us in danger of becoming part of the illegal drug trade in other countries. The easiest solution is to make export of drugs illegal even though their domestic sale is legal.

I don’t expect countries will outright ban their citizens from visiting us: cf. Amsterdam.

What are the Party Party’s policies on poverty, the economy, defence and climate change?

Probably that you shouldn’t have elected a one policy party if you care about this sort of thing.

I’m assuming they’re unlikely to be pro a large defence budget. Poverty is bad because it interferes with peoples’ ability to party. I refer you to my prior political ranting as to what I’d do about that.

Climate change is bad. It’s hard to dance with wet feet. Let’s sort that out.

So, do you remember Hammer Principle? That thing Mike and I did about two years ago?

Well, it’s still around. It even gets a fair bit of traffic. It averages about 100 unique visitors a day, which isn’t nothing, and every now and then reddit or hacker news remember it exists and the world briefly descends on it.

Which makes it pretty embarrassing how much we’ve been neglecting it. It’s largely just been trucking along, doing its thing, and we’ve been cheerfully ignoring it. It had a few bugs, but it basically worked and people liked it so we weren’t that worried.

We briefly tried to do a relaunch last year when the one year anniversary came up, but we got trapped into a “REDESIGN ALL THE THINGS” plan and it ended up floundering. Too much work to get back to where we started.

But not this time! Mike has been getting very excited about The Lean Startup recently, so when we got interested in doing some more work on Hammer Principle we decided to do it that way. We’ve not been terribly strict about it, but we’ve started measuring some things and making little tweaks in response to that.

To be honest the main benefit for me has been the instant feedback. Not even from the measuring so much (though it’s surprisingly addictive), just the fact that we’re iterating in small changes and features. It’s nice to see rapid progress on it again, and it motivates us to do more and to make yet more rapid progress.

Here are some of the things we’ve done:

• Tweaked the URL schema. Not exciting for you, but google analytics and subdomain based grouping were not friends which made it hard to tell what’s going on (all old URLs should now redirect to new ones. Tell me if they don’t or you find broken links we’ve missed
• New navigation bar between nails. It was a little hard to tell due to the aforementioned issues with old URL schema, but as far as we could tell basically no one navigated between nails. If you came for the programming languages you were unlikely to stay for the databases. This is an attempt to fix that, and it seems to be helping
• Redesigned the colour scheme. The old one was a bit garish – it kinda made sense at the time, but as we added different colours for different nails it made much less
• Added random assertions to the home page, giving people examples of the sort of fact the system throws out
• Complete redesign of the comparison pages. More on this in a moment

The comparison page is the one that excites me the most. Partly because it’s the biggest change, partly because I thought the old ones were a bit shit, but mostly because I think the new ones are really quite cool.

The old comparison pages were basically a list: The top 10 statements people thought each item was better at than another. This lead to a lot of conclusion because they looked like they were suggesting these statements were empirically good for that language when that often wasn’t the case (when you’re comparing assembler and C for “this language would be good for a web project” you know you’re in trouble). It also wasn’t very informative.

The new ones however give you much more information about the breakdown between the two sides, and with less of an implication that either are good for it. It also gives you more data about what’s going on in a reasonably easy to digest way. I think the overall result is a much clearer picture of the differences between the things you’re comparing. Try comparing Ruby and Python, Git and Mercurial or Judo and Aikido.

Hopefully this is just the start. We’re building up a list of things to try and experiments to run and the result should be a variety of changes coming in the near future.

This is another post brought to you by the school of the bloody obvious. Or at least it should be, but despite having implemented a trivial variation on this data structure before it still took me far too long to remember it existed.

My previous use case was the original version of IntAllocator in the rabbitmq Java client API (it’s an internal class used for allocating channel numbers). In looking it up I’ve noticed that it no longer does, for reasons that do make sense, but those reasons don’t apply for my current use case (basically the new version uses an internal bitset, trading space for time. RabbitMQ only needs to allocate one of these, and the range isn’t that large, so trading space for time is completely acceptable).

My current use case was for building separation graphs for metric spaces. Part of an algorithm I’m playing with requires keeping a candidate list for each element: That is, a list of elements which might be > t away but we’re not sure. This needs to not take up O(n) space when the answer is “the whole set” and we need to be able to remove elements from it efficiently. Hence the constraints in the title.

The resulting structure is basically a range compressed bitset built out of a balanced binary tree. It works as follows:

A node in the tree may be either empty, an inclusive range represented by its endpoints or a split around a pivot of m such that the left hand side of the tree contains elements <= m and the right contains elements > m. We enforce the invariants that neither child of a split may be empty, and that ranges must have endpoints which admit at least one element.

Allocating an entire range is then just a matter of creating a range node holding two integers, i.e. O(1).

Deleting an element is harder, but not much.

• Deleting an element from an empty node does nothing.
• Deleting an element from a range has three distinct cases:
  1. If the element is not contained within the range, do nothing
  2. If the element is one of the endpoints, decrement or increment the relevant endpoint. If this results in the range being empty, replace this with an empty node
  3. If the element is internal to the range, split this range around its midpoint and delete from the split instead
• Deleting an element from a split is even more straightforward: You determine which child the element should belong in and delete from that. If this results in that child being empty, replace this node with the other child.

Notes

• I’ve put together a Haskell implementation to demonstrate the algorithm
• There are at least two sensible ways to split a range. You can either do it around the element being deleted (which guarantees you’ll not have to recurse – you just allocate a split and two new ranges) or you can do it around the midpoint of the range. The former is cheaper but can result in the tree becoming unbalanced, the latter guarantees you’ll never need more than log(n) levels of recursion but also means most of the time you’ll use log(n) levels of recursion. You could also implement a hybrid where you split around the deleted point unless you’re below a certain depth in the tree, but I’m not sure it’s worth the added implementation cost
• It is useful for split nodes to keep track of the smallest interval containing them as you can then shortcut if the element to be deleted lies outside that interval
• You can also implement deleteRange efficiently (I think in O(log(n), though there’s a detail I haven’t checked there). This is left as an exercise for the interested reader
• When I implemented IntAllocator I added a cache for this: A bounded size stack which you pushed elements to delete onto. When the stack grew full you sorted it into ranges and deleted the ranges all at once. There was a specific reason for this that doesn’t apply (sometimes you wanted to say “pop an element, any element” and that came from the stack if it was non-empty), but this might still be a useful thing to do for imperative versions of this code (it’s a bad idea for pure ones)

We had our housewarming party last night, and I’d made this as food. A friend asked me for the recipe, and I was surprised it wasn’t already on here due to it being one of my standards, so I’m now fixing that.

I should warn you that this recipe is largely a lie, in that the details change every time I make it. This is the version I made last night though (well, this is a halved version of that).

Ingredients

• 1 white onion
• A smallish knob of fresh ginger
• Fresh chilli to taste (depends on type of chilli and spiciness you want. Do use fresh rather than dried though)
• One medium butternut squash
• One can chickpeas
• One small can of coconut cream
• A bit of sugar
• Quite a lot of salt
• Quite a lot of garam massala
• Plenty of sunflower oil

I can’t really give precise measurements on the salt and garam massala because I was adding them continuously throughout until I got the taste right. My guess is several tea spoons of salt and several table spoons of garam massala.

Cooking

1. Dice the ginger, onion and chilli finely.
2. Peel the squash and cut it into roughly 1cm cubes
3. Fry the ginger, onion and chilli with salt and sugar until the onion starts to go transparent
4. Add the squash and garam massala. Mix it all up thoroughly and fry for a little bit longer
5. Add boiling water until the squash is nearly covered. Allow to simmer for a while, stirring occasionally
6. When the squash is starting to go soft, add the coconut cream. Continue simmering and stirring
7. Eventually the squash should be breaking up, causing the sauce to thicken. Once it’s starting to taste nearly cooked, add the chickpeas and continue simmering

At this point it’s basically ready to serve whenever, but it improves significantly by leaving it to cook on a low heat for longer. Also, keep tasting it whilst it’s cooking and add more salt and garam massala to taste.