Older blog entries for Bram (starting at number 86)

Livejournal Valentine System

Stevey: You may wish to base a future version of the valentine system on the stable marriage problem. (Or, to simplify the interface a bit, the stable roommate problem).

Trust Metrics

Having everyone use a single central site for their messaging has tremendous benefits in terms of stopping spam. For one thing, there's no need to propogate data across the system. For another, it's reasonable to assume that the central site could make it sufficiently difficult to generate new ids that less than half the nodes in the system are spammers, which as we will see makes anti-spamming vastly easier.

My big problem with anti-certs up until now is that they enable censorship. I'm now convinced that censorship can be limited using the very simple mechanism of only allowing someone to anti-cert the sender of a message they actually received. It's probably a good idea to require that the anti-certing be done within a short period of time after the message is first read.

Now, for my improved algorithm for removing spammers. We would like for a spammer to be able to send out a fixed amount of spam for each node they compromise, and not get any benefit by making fake identities. Since we now have a concept of where the big island of nodes is, we can do exactly that. For a subset of nodes, we count the number of them who are certed by nodes in the big island. If that subset has 100 times as many spam marks as the externally certed nodes (or whatever the permitted amount of spam is) then none of the nodes in that subset are allowed to send out mail.

I'm not sure of a good algorithm for finding such subsets, but intuitively it doesn't seem like an intractable problem. Also, a reasonable case could be made for counting edges instead of nodes for the amount of spam allowed.

I'm quite happy with how workable this approach seems. It looks downright practical.

Voting Machines

chalst: Certainly electronic voting machines could in theory both have a paper audit trail and be much more reliable than any past vote counting mechanism. Rebecca Mercuri, whose ejection from a conference got us talking about this in the first place, has some very good thoughts on the topic. Unfortunately the current batch of voting machines are a big step back in terms of reliability, even ignoring their lack of paper trail and likely rigging of elections.

Minefield

chalst: In the case of two infinites which don't have a clear ordering neither player will successfully challenge the other and they'll have to play another round. The point of it being a game is that the players have the opportunity to try to challenge each other without it ever being necessary to prove that no such challenge exists, since proving the consistency of large infinites is by nature impossible to do without assuming the existence of yet ever larger infinites.

Trust Metrics

I've implemented my latest trust metric. This implementation requires Python 2.3, and includes some 'clever' algorithmic things which should make it reasonably fast in practice. I've tested this code, but not as thoroguhly as I'd like.

from bisect import insort
from __future__ import division
class TM:
    def __init__(self, seed, get_peers):
        self.seed = seed
        self.get_peers = get_peers
        self.point_to = {'phantom': [seed]}
        self.point_from = {seed: ['phantom'], 'phantom': []}
        self.targets = {seed: 1}
        # {peer: [(time, increase)]}
        # stays sorted by time
        self.dispensation_schedule = {'phantom': [(0, 1)]}
        # {peer: [{peer, proportion}]}
        self.dispense_to = {'phantom': [(seed, 1)]}
    def get_closest_peers(self, numaccept):
        result = []
        while True:
            if not result:
                times = [(1, self.seed)]
            else:
                times = []
                for i in self.targets.keys():
                    try:
                        times.append((self.time_to_finish(i), i))
                    except ZeroDivisionError:
                        pass
                times.sort()
            if not times:
                return result
            t, peer = min(times)
            completes = []
            result.append(peer)
            del self.targets[peer]
            if len(result) == numaccept:
                return result
            # change the dispensation schedules of everything which contributed to this new 
            # peer to reflect that their output is earmarked until the new peer is full
            for i in self.point_from[peer]:
                total = 0
                for j, (t2, inc) in enumerate(self.dispensation_schedule[i]):
                    if t2 > t:
                        self.dispensation_schedule[i] = [(t, total)] + self.distribution_schedule[j:]
                        break
                    total += inc
                else:
                    self.dispensation_schedule[i] = [(t, total)]
            # for all complete peers which newly have all their friends full, 
            # redistribute their outflow to their friends
            completes = []
            for i in self.point_from[peer]:
                for j in self.point_to[i]:
                    if j not in result:
                        break
                else:
                    completes.append(i)
            if completes:
                for c in completes:
                    self.redistribute(c, t)
    def time_to_finish(self, peer):
        incs = {}
        for i in self.point_from[peer]:
            for (t, inc) in self.dispensation_schedule.get(i, []):
                incs[t] = incs.get(t, 0) + inc
        inclist = incs.items()
        inclist.sort()
        current_rate = 0
        current_time = 0
        current_amount = 0
        for t, inc in inclist:
            new_amount = current_amount + (t - current_time) * current_rate
            if new_amount >= 1:
                break
            current_amount = new_amount
            current_time = t
            current_rate += inc
        return current_time + (1 - current_amount) / current_rate
    def redistribute(self, peer, t):
        # pull in friend information of peer's friends
        for p in self.point_to[peer]:
            if not self.point_to.has_key(p):
                self.point_to[p] = self.get_peers(p)
                for x in self.point_to[p]:
                    if self.point_from.has_key(x):
                        self.point_from[x].append(p)
                    else:
                        self.point_from[x] = [p]
                        self.targets[x] = 1
        # calculate the distribution of peer's outflow
        donefriends = []
        notdonefriends = []
        bounceback = 0
        for friend in self.point_to[peer]:
            if self.point_to[friend]:
                if self.dispense_to.has_key(friend):
                    donefriends.append(friend)
                    bounceback += self.dispense_to[friend].get(peer, 0)
                else:
                    notdonefriends.append(friend)
        try:
            mult = 1 / (len(donefriends) + len(notdonefriends) - bounceback)
        except ZeroDivisionError:
            mult = 0
        newdist = {}
        for friend in notdonefriends:
            newdist[friend] = mult
        for friend in donefriends:
            m = mult * (1 - self.dispense_to[friend].get(peer, 0))
            for p2, amount in self.dispense_to[friend].items():
                if p2 is not peer:
                    newdist[p2] = newdist.get(p2, 0) + amount * m
        # optimize peer out of other peers's distribution lists
        for i in self.point_from[peer]:
            if self.dispense_to.has_key(i):
                d = self.dispense_to[i]
                for friend, amount in newdist.items():
                    if friend is not i:
                        d[friend] = d.get(friend, 0) + amount * d[peer]
                del d[peer]
        self.dispense_to[peer] = newdist
        # add new scheduled distribution
        m = self.dispensation_schedule[peer][0][1]
        for friend, amount in newdist.items():
            insort(self.dispensation_schedule.setdefault(friend, []), (t, amount * m))
        del self.dispensation_schedule[peer]
Trust Metrics

I think I've figured out how to fix the gameability problems I've talked about in the last few entries.

Water pours in at a fixed rate from the seed. At any given time, each node is either trying to collect water, done collecting water and now dispensing it, or done dispensing water and simply passing it through. When a node is dispensing water it will do so at a rate depending on the amount of water flowing into it.

We will construct a schedule of what water goes where when. For each node which is trying to collect water, we ask 'if all dispensing nodes were to allocate their full amount to this node, when would it be full?' The node which does so the fastest gets added first, and all the dispensation of the nodes which certify it gets allocated up until the time. When deciding on later nodes to add, it is assumed that dispensers don't start contributing until after their previously allocated contributions are done.

Note that when a node is first added its rate of dispensation is zero. When all of the nodes which a dispenser certifies have been added, then that node's rate of dispensation is distributed evenly across all the nodes it certifies. Dead ends are skipped over, to avoid water wastage. More sophisticated forms of backlogging indirect dead ends could be made, but the simplest one should work fine in practice.

I'm very enamored of this technique. It does accurate proportional representation and is very hard to game outside of the gameability inherent in having proportional representation at all. My one current gripe is that while the technique for selecting which node gets added next is linear on the number of nodes, the technique for redistributing the dispensation of full peers is quadratic. Harumph.

To see the gameability inherent in proportional representation, consider this case: There are three voters, who will elect three candidates. Two voters prefer A, B, and C, while the third one prefers A, B, and D. Clearly the winners should be A, B, and C, but the third voter can list simply D and get exactly the candidates he wants elected.

Election Methods

On a related subject, I've for a long time been thinking about improvements to single transferable vote. There is a form of gameability of STV which I think can be completely overcome. Specifically, a voter can make their vote much stronger by taking a candidate who has no hope of winning and ranking them first. This causes very bad distortions, including the occasional candidate with no hope who actually wins!

My modification is surprisingly simple. The first winner is selected by the condorcet method. Later candidates are elected one at a time using essentially the condorcet method but with the pairwise results modified based on previous winners. Specifically, if we're comparing candidates A and B, then if X was already elected we take all candidates who ranked X above both A and B and evenly distribute a reduction in their vote strength by a total of the droop quota.

I did some testing of this and found (assuming I didn't botch up my implementation) that when using minimax there are circumstances in which the weight of a vote becomes negative. I suspect this stops happening if you use ranked pairs instead.

This technique completely obliterates the rank-a-weak-candidate-higher form of gaming which plagues STV. It also has the nice feature of not requiring all votes to be kept around. All you need to do is collate the vote counts of each two- and three-way race and the winners can be calculated from that.

Voting Machines

chalst: unfortunately the electronic voting systems are far less accurate than the paper-based ones they're replacing. Not only do they not have a paper trail, making any sort of double-checking impossible, but they run on un-audited proprietary software. The software has been known to crash in deployment. The solution? Reboot it.

There is one thing which could be done to increase the accuracy of vote counting and the difficulty of vote fraud. Instead of creating a single paper ballot, create two, which go into two different bins, and are sent to two different vote counting agencies, which are run by two different political organisations.

Sadly, the current trend is in the exact opposite direction, with paper trails getting eliminated entirely. They're replaced by unpublished electronic protocols which we're simply supposed to trust. There is a very real possibility that in the near future every major election in the united states will be rigged.

Trust Metrics

I've been thinking about how to apply ciphergoth's new trust metric ideas, discussed in my last few entries, with negative certs for spam resistance. The two match up very well. When a bucket is full, in addition to dribbling out more positive water, it also dribbles out some anti-water to all of its negative certs. Anti-water can filter backwards until it's negated an entire bucket then flow backwards from there. This approach needs more polish, but I like its game-resistance properties.

I figured out an in some ways better way to do simple peer ordering. For each new inclusion, figure which peer has the greatest total sum weight pointing at it, then include that peer and move weight of all the peers which certify it onto that one, setting the weight to 1/numcerts * peerweight for each certifier. Unfortunately this removes the disincentive for certifying peers by replacing it with a strong incentive for certifying peers, since the more peers you certify the less your strength gets diluted.

More thought is required. I've figured out one nice straightforward criterion though. If the seed certifies two peers, and the first one certs x peers and the second one x+y peers, then they should get to alternately appoint includes until they've both selected x, then the y extras should get added at the end.

Math Puzzles

It's impossible to position three solid tori in 3-space in such a way that they're borromean linked without deforming them. Is it possible to position a larger number of solid torii such that the entire set of them is linked but no pair is?

How can you find the midpoint of two points using a compass only, no straightedge?

6 Aug 2003 (updated 8 Aug 2003 at 23:00 UTC) »
Ciphergoth's trust metric

Ciphergoth made a nifty web toy based on his new trust metric. It's gotten so popular in just two days that it can't handle the load. From this and Friendster, it seems that it's extremely easy to get lots of users if you let them study their friends neigborhood, but it's hard to handle all the load.

Thinking about the first few people added to the metric, it's clear that ciphergoth's approach has some definite advantages over the one I gave in my last entry. Specifically, once you're done with the immediate friends list, the person who is a friend of a friend in the most ways should be selected next. My approach most definitely does not do that.

When selecting the first friend of a friend, what we have is essentially a voting problem. Ciphergoth's approach tries to find the best next person by assuming honesty, while my approach tries to reduce the amount of dishonesty by selecting the next person in as non-gameable a way as possible. Of these two tradeoffs, ciphergoth's seems to be the more appealing. This analysis indicates that maybe a condorcet style approach to picking the next person will achieve the best of both approachs. I'll have to think about that.

Minefield

Minefield is a game involving infinite numbers for two players.

Both players write down an infinite number (assuming the axiomatic basis ZF). They then both reveal what number they wrote down.

Both players now have a set amount of time to come up with a challenge to the other person's number. This can be done either by showing that the statement of the existence of the other person's infinite causes a contradiction, or by showing that your infinite is at least as large as the other person's.

If exactly one player shows that the other person's number causes an inconsistency, then that person wins. Otherwise, if exactly one person shows that their infinite is at least as big as the other person's, then that person wins. Otherwise the game is a do-over. In the case where someone should win by being larger, the opponent has an opportunity once they see the proof to challenge the consistency of the other player's number. This is to prevent the cheap trick of saying 'my number is inconsistent, therefore all statements are true, so it's at least as large as yours.

This game can be played, although it's a bit odd. Mostly I've thought of it as a way of getting a visceral sense of how very large infinites work.

Triumvirate

The 'degenerate' case of my game second best is actually the most interesting. Three players each write down either a 0 or 1, then all reveal what they wrote down. If they all wrote down the same number, then they all get one point. Otherwise, the player who wrote down the number which is in the minority gets three points. I'm calling this game triumvirate.

In triumvirate, two players can gang up on the third one by putting down different numbers, but then the third player can pick which one of them will win, and thus easily bully around either of them. I believe that triumvirate gets to the heart of what's difficult about multi-player, zero-sum games in much the same way that prisoner's dilemma gets to the heart of what's difficult about two-player, non-zero-sum games.

2 Aug 2003 (updated 12 Aug 2004 at 05:10 UTC) »
Backwards Compatibility

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.

BitTorrent home

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.

BitTorrent home

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.

21 Jun 2003 (updated 21 Jun 2003 at 02:55 UTC) »
Lost Mail

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.

Rubik and Megaminx pun

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.

77 older entries...

New Advogato Features

New HTML Parser: The long-awaited libxml2 based HTML parser code is live. It needs further work but already handles most markup better than the original parser.

Keep up with the latest Advogato features by reading the Advogato status blog.

If you're a C programmer with some spare time, take a look at the mod_virgule project page and help us with one of the tasks on the ToDo list!