Older blog entries for Bram (starting at number 81)

Extending protocols is very simple. You have a base level of functionality which is the core of the protocol, and a way of adding new information which is ignored in the current implementation. When later implementations are made, they can use the extra space to do protocol negotiation and use new features if both sides support it.

Well, duh. Unfortunately most people can't seem to grok this very basic concept.

For example, http 1.0 has quite nice extensible straightforward protocol negotiation built in, using headers, and a 1.0 client or server is very easy to implement. Rather than keep on adding optional features to 1.0 declared in headers, http 1.1 has now been created, and the push is to make everything run 1.1 (of course, the version number is an opaque string which there are no clear guidelines on how to parse and deal with). http 1.1 is a bloated mess, with all kinds of 'required' features, many of which aren't, and won't be, implemented properly in practice. This engineering debacle hasn't stopped certain people from claiming that they're 'creating the technology to enable the future internet' though.

Telnet has some basic protocol negotiation hacked in, which is used by competently written protocols like kerberos and srp. Unfortunately ssh, among many other problems, is its own protocol, forcing the end user to be aware of yet another TLA. ssh version 1 was hacked together amateurishly for a variety of forgiveable reasons, so ssh2 was created to fix its problems. ssh2 has succeeded in having embarassing crypto breaks less frequently than ssh1, but the engineering decision was made that since it was done wrong the first time, it would keep being done wrong the second time, and it still doesn't work as a negotiated protocol on top of telnet. (Just because you're running a telnet server doesn't mean you have to accept sessions which are unencrypted. In fact telnet is very nice in making it possible to put up a human-readable error message when that happens.) Unsurprisingly, a very large fraction, if not the majority, of all remote terminal sessions still use unencrypted telnet.

The quality of phone reception has been limited by bandwidth for a while now. Since calls pass through multiple intermediary machines, it isn't possible to magically flip a switch and have all phone reception get better. However, if I'm speaking to someone two doors down on the same exchange, there's no reason we should be stuck at the old quality. It would be fairly straightforward to create a new voice quality format which only turned on if the entire line of equipment (including the end phones) supported it. This would require innovation by the telcos though, who account for their phone switching equipment as depreciating over the course of forty years, so don't expect it to actually happen. Phone reception will only get better when people switch to using voice over IP.

Trust Metrics

Paul Crowley came up with a nice trust metric. Unfortunately this one will sometimes cause someone's certs to not work at all if they cert more people, creating a strong artificial disincentive to certification. I've figured out a way of fixing this, and fixing the performance problems which result. Rather than pontificate about it at length, I'll just post example code, which is quite terse and straightforward.

# certs is {node: [certed nodes]}
def rank(seed, certs):
    already_selected = {}
    numhits = {}
    for key, value in certs.items():
        numhits[key] = [0] * len(value)
    def rank_single(current, passed):
        if passed.has_key(current):
            return None
        passed[current] = 1
        if not already_selected.has_key(current):
            return current
        cs = certs.get(current, [])
        numhit = numhits.get(current, [])
        nexts = [(numhit[i], i, cs[i]) for i in xrange(len(cs))]
        nexts.sort()
        for garbage, i, next in nexts:
            result = rank_single(next, passed)
            if result is not None:
                numhit[i] += 1
                return result
        return None
    result = []
    while True:
        next = rank_single(seed, {})
        if next is None:
            return result
        result.append(next)
        already_selected[next] = True

MineSweeper

MineSweeper3D is cool.

I would like to have a minesweeper engine which calculated the exact probability that each not yet revealed cell had a mine in it. This could be done reasonably for large boards using a neat memoization trick where you go a row at a time. Even better would be to make it so that each cell you clicked on didn't have a bomb in it, but your cumulative probability of winning got multiplied by the chances that there was a mine in that cell. In the end, your score would be the log of your winning probability. That would be fun to play, and very interesting to implement.

Life Patterns

Computer searches for life patterns have been going on for the last two decades and the results are quite astounding. I'm particularly enamored of the wickstretchers. Unfortunately I can't seem to find a pattern file for the wick stretcher which leaves a single diagonal line of cells.

Jacob Moorman contacted me after my last post about difficulties with SourceForge. The problems I have are being worked on, as detailed on this page. It appears that the problems will be resolved within a short enough time frame that switching to another CVS would cause more pain than it would alleviate (but not by a large margin). brondsem links to several other project hosting facilities.

Spam Stopping

I was talking with clausen and we came up with some interesting ideas for spam stopping.

Rubik's UFO

I came up with a nice solution to Rubik's UFO.

Busy Beaver Numbers

There's some very interesting recent work on busy beaver numbers. Computing bb(5) may be possible.

Sourceforge's CVS has been terrible recently. I would like to move BitTorrent's hosting somewhere else. Ideally to a place which is already hosting other things, has been doing so for a while, and is free.

I need the following -

• A CVS repository, with ViewCVS, globally available anonymous CVS, the ability to set up new accounts, and access control. This should go without saying, but CVS should update immediately, which sourceforge isn't doing any more. It should also be possible to easily download a whole repository tarball.

• Mailing lists which support moderation with more than one moderator, make the archives available online, do a reasonable job of keeping people from harvesting addresses, and give me easy access to the list of subscribed addresses so I can easily move it elsewhere later if necessary.

• Download hosting, which allows new files to be easily published and taken down, tracks download stats, and can be linked to with a simple hyperlink (unlike sourceforge's redirection crap). This is currently about 40 gigabytes a day.

Anyone who would like to volunteer or suggest resources please mail me.

Random Picking

An interesting problem came up in BitTorrent development. There are n things, some of which pass and some of which don't. We would like to do a scan over all things and stop at the first one which passes. We could scan from the beginning, but that would lack an another property we want which is that each acceptable thing should have about an equal probability of being picked.

Scanning could be done randomly but that involves generating lots of random numbers, which can be very slow. I came up with a neat trick. Arrange the n objects into a list, pick an s less than n at random and a d less than n and relatively prime to n at random, then scan through (s + d * i) % n for each i < n.

What is the maximum possible bias towards or away from a particular object this technique can have? I think it works fine in practice.

Algorithm obfuscation

I realized the other day why my attempts to come up with simplistic invariants for circuit satisfiability problems were going absolutely nowhere.

Consider some algorithm for solving some problem. We will now generate an equivalent algorithm which is only slightly slower but whose operation is completely obfuscated. Select a secure hash function (we assume there are infinitely many of these, and they cannot all be summed up simply). Memory will instead of containing bits in the unobfuscated algorithm instead contain a single plaintext counter and many (count, bit) pairs. Whenever writing to memory, instead of writing out the bit you would have increment the counter by 1, then store (count, hash(count)[0] xor mybit). Memory can be read out by computing hash(count) xor memvalue. This completely and thoroughly obfuscates memory, to the point that I've decided to give up looking for a simple invariant to prove an absolute lower bound on runtime. Ah well.

Due to technical difficulties, I lost some mail from last week.

Apache and BitTorrent

There's some interesting discussion as to whether Apache will come with the BitTorrent mimetype already configured.

New Puzzle

I came up with a new puzzle.

Snail Racing

I saw a very cute board game in a store the other day. It features a racetrack which six different colored snails move along. There is a single six-sided die to roll. All snails start at the beginning line, and a snail to move forwards is repeatedly selected by die roll. The game ends when a snail crosses the finish line.

It's clearly meant for very young children, and the box says that players try to guess which snail will win in the end, and it's a family game with no winners and losers. Natuarally, I immediately noticed that it would make a great prop for a cutthroat gambling game.

Snail racing, a game for two players.

Both players start by putting a fixed ante into the pool. Before each die roll, both players write down an amount of money. The amounts they wrote down are then revealed, and they each put the amount they wrote down into the pool. The player who wrote down the larger number (determined by coin toss in the case of a tie) gets to put a single token on a snail of their choosing. A snail is then advanced by die roll, and play continues with another round of writing down numbers. When a snail wins, all the money in the pot is divided among the two players proportionately to how many tokens each of them had on that snail.

Hexagonal Game Rules

There was an error in my analysis of game winning positions given in my last entry. Before explaining what the error was and why I've made a slight rules change, I'd like to recap the rules, since they're now considerably more understandable.

Game is played on a hexagonal board with hexagonal cells. Players alternate placing pieces of their color. At the beginning, one player puts down the first piece and the other player decides which color they want to play.

A player wins whenever they make any of the following configurations:

1. A single group which touches four or more edges

2. Two separate groups, one of which touches three adjacent edges and one of which touches three edges not all adjacent, and which share exactly one edge between them.

3. Two groups each of which span three edges and a third group which spans two non-adjacent edges not connected by either of the other two. The third group may touch more edges as well.

These rules are straightforward, and force there to be no draws. They also make winning require clear board domination, resulting in a game with much long-term positional play.

The error in my last post was that one of the winning configurations was a superset of another. To see where the difficulty comes from, compare the three following positions (see my last entry for notation):

1. ((1, 3, 5)) ((1, 2, 3), (3, 4, 5), (5, 6, 1))

2. ((1, 3, 5), (1, 2, 3)) ((1, 3), (3, 4, 5), (5, 6, 1))

3. ((1, 2, 3, 5)) ((3, 4, 5), (5, 6, 1))

In each of these positions player A is strictly better than in the previous one. In each case where there are two completed positions which are individually ambiguous as to who should win and in which player A is strictly better in one, I wanted player A should win in the former, and lose in the latter. This criterion can't be satisfied due to position #2 above. I decided to make position #2 a win for player B, mostly because that makes the rules much more succinct.

A came up with a unified solution which applies both to Rubik's cube and Megaminx. It's a nice solution to either one even without that property.

Hexagon Game

The hexagon game I mentioned earlier is easier to win than necessary. When designing a game, one wants there to be no draws, but within that restriction you want it to be as difficult as possible to win, so as not to truncate interesting game play.

The new winning condition is that a player wins if they make a move such that after that if all the empty cells are filled in for the opponent then the opponent does not have any of the following:

• A single group which touches four edges

• Three separate groups each of which touch three edges

• Two separate groups each of which touch three edges and one of which touches three edges no two of which are adjacent

I'll now go over each of the specific winning configurations in detail and explain the reasoning behind them. My notation will be that the edges of the hexagon are numbered 1-6 going clockwise and that (a, b, c) describes a single group touching edges 1, 2, and 3. Multiple groups are grouped together to describe a player's position, so ((1, 3), (3, 5)) means that a single player has two groups, one connecting sides 1 and 3 and the other connecting sides three and five. To describe a whole board position I'll give two sets of groupings in a row, the first for player A and the second for player B.

Here are the winning configurations, not including rotations and reflections. Some entries will include two whose reasons for being winning are related. You may wish to get out two different colored pens and draw the actual diagrams.

((1, 2, 3, 4))

Consider the complete board ((1, 2, 3, 4)) ((1, 4, 5, 6)). This is rotationally symmetric, so it must be a winning configuration.

((1, 2, 3), (1, 4, 6))

Consider the complete board ((1, 2, 3), (1, 4, 6)) ((4, 5, 6), (1, 3, 4)). This is rotationally symmetric, so it must be a winning configuration.

((1, 2, 3), (1, 4, 5))

Consider the complete board ((1, 2, 3), (1, 4, 5)) ((1, 5, 6), (1, 3, 4)). This is symmetric about a line through the middle of sides 1 and 4, so it must be a winning configuration.

((1, 2, 3), (1, 3, 4), (4, 6))

Consider the complete board ((1, 2, 3), (1, 3, 4), (4, 6)) ((4, 5, 6), (1, 4, 6), (1, 3)). This is rotationally symmetric, so it must be a winning configuration.

((1, 2, 3), (1, 2, 4), (1, 5))

Consider the complete board ((1, 2, 3), (1, 2, 4), (1, 5)) ((1, 5, 6), (1, 4, 5), (1, 3)). This is symmetric about a line through the middle of sides 1 and 4, so it must be a winning configuration.

((1, 3, 4, 6)) and ((1, 2, 3), (1, 4), (4, 5, 6))

Compare the completed positions ((1, 3, 4, 6)) ((1, 2, 3), (4, 5, 6)) and ((1, 3, 4), (1, 4, 6)) ((1, 2, 3), (1, 4), (4, 5, 6)). Player A is strictly better in the first case, therefore A should win in the first case and B should win in the second case.

((1, 3, 4, 5)) and ((1, 2, 3), (1, 4), (1, 5, 6))

Compare the completed positions ((1, 3, 4, 5)) ((1, 2, 3), (1, 5, 6)) and ((1, 3, 4), (1, 4, 5)) ((1, 2, 3), (1, 4), (1, 5, 6)). Player A is strictly better in the first case, therefore A should win in the first case and B should win in the second case.

((1, 2, 3), (3, 4, 5), (1, 5, 6)) and ((1, 3, 5), (1, 5, 6))

Compare the completed positions ((1, 2, 3), (3, 4, 5), (1, 5, 6)) ((1, 3, 5)) and ((1, 2, 3), (3, 4, 5), (1, 5)) ((1, 3, 5), (1, 5, 6)). Player A is strictly better in the first case, therefore A should win in the first case and B should win in the second case.

I'm very happy with this game. There is a clear canonical winner in every position, and making any of the won positions happen is very subtle. It's missing the property that even if you kept playing after the game ended it would still be clear from the board position who the winner was, but that only happens with completely symmetric final positions, and having initiative play a strategic role may be a good thing.

The rules to Core Wars could use some improvement. Specifically, there's way too much of a paper-scissors-stone effect with strategies. No fundamentally new approaches have been invented in years.

I think the cause of this problem is that vampires are too powerful. They preclude techniques such as self-healing programs.

Here is my proposed solution.

Each location on the battlefield has an alignment. Initially the starting locations for both sides are set to their alignment and the empty space is all set to neutral.

When a MOV is executed, the target of that MOV is set to the same alignment as the MOV command. Note that this may be different from the alignment of the thread which executed the command.

When a SPL is executed by a command which has different alignment than its executing thread, it acts as a noop. This is what gets the strength of vampires under control.

When any read operation is done on a location with a different alignment from the executing command, it always reads as DAT 0 1. Whenever ADD or any other command which affects state is executed on a location with a different alignment than the one being executed, it has no effect. Note that these rules apply regardless of the alignment of the thread performing the instruction. These rules are designed to furthur reduce vampire-like techniques.

I think my rule variant does a good job of getting vampires under control. The vampire technique still applies and is extremely important, but a single capture no longer kills you.

Book Review: Moneyball

I highly recommend Moneyball, by Michael Lewis.

Moneyball is a book about financial shenanigans in baseball How does that happen? The Oakland Athletics win completely disproportionately many games for their salary budget by evaluating players better and buying undervalued ones. Moneyball is a story of the triumph of science and reason over the superstitions of an entrenched beurocracy which kept the truth out for decades by branding it as heresy.

One part of Moneyball possibly inadventantly explains why it's such a compelling story. At one point the author asks two people with ivy league educations if they feel bad using their advanced degrees on something so trivial as baseball. They burst out laughing and ask 'You mean, as opposed to having a deeply meaningful job on wall street?' Lewis's book Liar's Poker, while just as well written and about far larger sums of money, has a subject which simply cannot compete with competitive sport as the basis for a compelling narrative.

Twisty Puzzle Reviews

I just posted some twisty puzzle reviews.

Someone told me that Y suffers from the corners hardly ever getting used, making the effective board size very small. A similar game which fixes this problem is to play on a hexagonal board, and the first player to complete a group which either connects two opposite or three non-adjacent sides (meaning (1, 3, 5) or (2, 4, 6)) is the winner. This game also has no draws, and makes the whole board important while maintaining the subtleties of Y. I wonder if anyone has thought of this game before.

The sourceforge stats for PHP-Nuke for this week look extremely fishy.

My new favorite place to play games online is Little Golem.

I met up with John Tromp and we tried several different board games. The big winner among the ones we played was Y. Y feels conceptually simpler even than hex. The board is a triangle, rather than a rhombus, and there's no board orientation to keep track of. The strategy of Y also feels considerably more subtle, with no single central point of conflict.

I've been trying to design a board game which has a gradual build-up of positional strength until the very end when everything comes to a head. Unfortunately games where the goal is to create a pattern tend to force tactics to play out early, since one side or the other will benefit from the tactics finishing and hence force the play early. Misere games, in which the goal is to avoid making a pattern, avoid this problem, but tend to turn into two separate solitaire games which don't interact until the very end.

I've come up with a game which seems to fix that solitaire problem fairly well. Here are the rules:

Game played on a grid. White and black alternate placing stones. The first player to cause the four corners of an orthoganl square to all be filled with stones with two opposite stones being of one color and the other two of the other color loses.

The obvious drawing strategy of always moving on the point rotated 180 degrees from the last move can be prevented by playing on an odd sized board.

Whether this game is drawish, needs a swap rule, and is generally interesting to play needs to be determined by experimentation.

Pentagon Tilings

Pentagon tilings are cool.

The 'proportional representation' system I referred to in my previous entry was specifically the one where each voter votes for a political party, and the parties get to appoint candidates based on their percentage of the vote.

My objection to this very specific system is that it greatly increases the strength of political parties over individual politicians. It does have the advantage of making 'third parties' stronger, but that only looks good if you're using the horrendous two-party system as the basis for comparison. It can in fact have an ill effect of making the smallest of three major parties disproportionately powerful, by making them be the swing vote. Ideally political parties should be loose associations of politicians who share organising resources. Any system which results in an oligopoly of political parties running government is inherently flawed.

'Proportional representation' generally refers to systems in which multiple candidates are elected and a block of voters is capable of voting in a number of candidates proportional to their size. There are also proportional representation systems which use ranked ballots. In fact, I've spent a considerable amount of time working on proportional representation winner selection algorithms which are considerably less gameable than the standard instant runoff. At some point I'll do another round of experimentation and post my results.

Puzzles

While attempting to solve a very difficult solid metal parts puzzle, I came up with a very interesting question. The sort of puzzle I'm referring to is one in which there are several solid pieces which are entangled and the puzzle is to extricate them from each other without bending them. My question is: can you come up with a schema for solid parts puzzles which contains a fixed number of pieces and whose computational complexity of finding a solution is superlinear on the amount of data necessary to describe the pieces? All parts must come apart, not just one.

I've come up with an interesting solution. Here's a hint: use 3sum. (I'm assuming 3sum to be quadratic.)

Most Inefficient Sort

I got wind of an interesting informal competition to find the most computationally inefficient, but not completely contrived, sort algorithm. My solution is as follows: Assume all the values to be sorted are 32-bit integers. Have a candidate solution which starts off with all values set to zero. Repeatedly compare the candidate solution to see if it's a permutation of the input, and if not increase the last number by one, with overflow carried to earlier numbers. How do you check if two lists are permutations of each other? By trying all possible permutations and comparing them individually, of course.

apenwarr: Getting better election methods actually adopted is indeed the problem. The United States has had unranked ballots for so long that Duverger's Law has kicked in and we now have two completely entrenched political parties which have a vested interest in keeping things as they are.

Perhaps a clue can be gleaned from the defeat of proportional representation. Proportional representation as a method of electing congresspeople has been banned, which seems rather extreme given the usual bent towards states's rights. The reason this happened was actually a good one. Elected officials like having a considerable amount of personal power, and simple proportional representation would lead to them being completely subservient to the party they represent, easily replaced by party beurocrats.

One of the nice things about the way elections work in the US is that ballots always list individuals, not parties. In the above case, the interests of those individuals helped improve election methods used (or at least, keep it from getting worse). Perhaps incuments could be convinced to back ranked ballots.

Do ranked ballots favor incumbents? I'm honestly not sure. There are two forces at work; One is that ranked ballots make political parties have greatly reduced influence, so an incumbant doesn't need to worry so much about party backing going away. The other is that the will of the voters is more accurately reflected, possibly removing incumbents whose support relied on electoral distortions.

I suspect that incumbents could simply shift their positions to reflect the opinions of voters more than political parties, and wind up in a better position than they were before. However, real studies of the likelihood of and incumbent getting reelected when the voting system becomes ranked versus when it remains unranked are required.