I continue to post blog entries to bramcohen.livejournal.com

The deadline for CodeCon 2005 submissions is on December 15, less than two weeks away. Time to get those submissions in.

I've been posting blog entries exclusively to the livejournal version lately, because it's more featureful. Check there for the latest entries.

The last variant on boom-boom I gave had fairly slow, plodding play. I've since come up with the following game, which is by far the best board game I've ever invented:

Play is done on an othello board, with both players having one color and moving alternately. On a turn, a player may either place a new piece in an empty square, or 'explode' a piece they already have. Placed pieces may not touch an opponent's piece on either a side or corner.

To explode a piece, the player places one of their pieces in each of the eight spaces touching the piece they exploded. If a piece is already there, it's left alone. A piece may not be exploded if it's already completely surrounded. After a piece is exploded, all opponent pieces which border on the exploded piece (either edges or corners) are flipped over, then all opponent piece which border on those are flipped over, and so on, until there aren't any places where two pieces of opposing sides border each other.

The first player to be unable to move on their turn loses.

I've play-tested this game and it went over very well. There are plenty of simple tactics for someone just starting out, and lots deeper and more interesting tactics as you master those. Kids love flipping over so many pieces, and find the rules easy to follow. An 8x8 board is a little small for this game, perhaps it would be good to use that as a beginner board and a larger board for tournament play.

Anyone who wants to follow up to this post should do so via livejournal comments rather than posting to advogato, because I find advogato blog conversations clunky and probably won't follow up to responses there.

comments

There are two concepts in car pollution which people generally get mixed up. Some exhaust gases are simply stinky and noxious, most notably particulate carbon and carbon monoxide. Those do direct damage to the humans near them and crops which grow nearby and are clearly bad. Pollutants are clearly bad and there isn't much direct economic disincentive for any one person to make their car produce less of them.

The other troublesome kind of exhaust is greenhouse gases, mostly carbon dioxide. The amount of damage caused by these is much less clear, and there's a straightforward economic disincentive to produce them, because they correspond pretty much directly to the amount of gas your car consumes. Carbon dioxide also happens to be produced in mass quantities by respiration.

If you really want to know how clean a car is, look it up on the EPA web site. There are some surprises, for example the honda civic hybrid with a manual transmission has mediocre pollution ratings.

Erasure Codes

People keep asking me about using erasure/rateless/error correcting codes in BitTorrent. It isn't done because, quite simply, it wouldn't help.

One possible benefit erasure codes is that when sending data to a peer there are so many potential pieces that you can send any random one you have and it won't be a duplicate. The problem is that the peer may already have gotten that same piece from another peer, so that benefit is destroyed, and on top of that the overhead of communicating and remembering which peer has what is increased tremendously.

Possible benefit number two is that erasure codes increase the chances that your peers won't already have the pieces which you've downloaded. But simply downloading pieces which fewer of your peers have first handles that problem quite nicely, so a vastly more complicated solution is unwarranted.

Possible benefit number three is that if there's no seed left erasure codes increase the chances that the entire file will be recoverable. In practice, when a file becomes unrecoverable it's because there was only one seed and several downloaders started from scratch, then the seed disappeared after uploading less than the total length of the file. Erasure codes obviously would not help out in that case.

There are other possible benefits and corresponding rebuttals, but they get more complicated. The short of it all is that the possible benefits of erasure codes can be had with much more straightforward and already implemented techniques, and the implementation difficulties of such codes are quite onerous.

While I'm pissing on everyone's parade, I should probably mention another scenario in which everyone wants to use erasure codes and it's a bad idea: off-site backup. If you store everything straightforwardly on each backup site, and each site has two nines (99%) uptime (if it doesn't you shouldn't be using it for backup) then the overall reliability will be six nines (99.9999%). Engineering for more than six nines is nothing but intellectual masturbation, because unforseeable problems completely dominate failure at that point. Therefore one-of-three gets great reliability with unreliable backup sites in exchange for having to store three times the amount of data you're backing up.

With erasure codes, you could make it so that each backup site only had to store half as much stuff, but that two of them would still need to be up to recover data. If you then have four backup sites, there's a savings of 1/3 of the storage versus the much more straightforward approach. This is a pretty small reduction given that the price of mass storage is very small and plummeting rapidly. It also comes at great expense: you have to deal with four backup sites instead of three, and the software is much more complicated. In systems like this, the recovery software not working is a significant part of the chances of the system as a whole failing. Also, any economic benefit of savings on disk space must be weighed against the costs of the software system which runs it. Given the ludicrous prices of backup systems these days, a much simpler albeit slightly less efficient one would probably be a great value.

ECC of course has some great uses, for example data transmission of noisy mediums and storing data on media which can get physically corrupted, and recent developments in it are very exciting, but it's very important to only use sophisticated tools when clearly warranted.

Comments?

Here is an interesting question - Given the electoral college system, does it favor the large or the small states? The very short answer is that it ridiculously disproportionately favors the small states, because they're flat-out given disproportionately large representation. And if that weren't the case then switching to a simple electoral majority would be uncontroversial, following the trend of a simple majority deciding within each state.

But if we pretend that this is an issue of real interest, what are the effects? Well, that depends. If we had a country of two states, one larger than the other, than the chances of one's vote mattering in the smaller state would be just about nil. In a country of three states two of which were just slightly larger than half the size of the largest state the small states would be far disproportionately represented.

In practice there are enough states that statistical effects overwhelm the weirdnesses of specific enumerable outcomes. We can adopt a much more simplistic model of there being many small states, and we compare two, one of which is roughly double the size of the other. If we assume that the race is a dead heat across the entire country, (a completely unrealistic assumption, as I'll get to in a minute), the chances of a voter swinging the half size state is approximately 1.4 times that of the double size state (because a standard deviation is proportional to the square root of the number of voters) and the chances of it swinging the overall election are about half, so the chances of a single vote from the smaller state swinging the election are about a third less.

But we don't have a homogeneous voting population, and very few races are dead heats across the entire country. In practice state lines jerrymander quite heavily against New York and California, whose votes in recent elections have been such a foregone conclusion that nobody bothers campaigning in them. With the two coasts being very populous and the economic centers of the country, and getting more so, this effect is likely to become even more pronounced in the future.

And then there's the question of, in a close race, which states do you give out more candy to? The ones which are close races, obviously, and the ones which you can more likely affect the outcomes of. Small states are much easier to win by buying off votes, because a much smaller number of votes can change their outcome. The likelihood of their swinging the overall election is negated here because we don't go into elections blind - campaigns poll to find out what states are up in the air, and ignore the ones which aren't.

Which states are close races varies from election to election, so there's a random crapshoot which decides who gets the most resources each time. The result is inevitable arbitrary disparities, which the only consistent thing being their arbitrariness, and strong incentivization for local officials to make their states be close, or at least appear to be close.

If this all sounds stupid and unpleasant, it's because it is. The only clear effect of a truly voter weighted electoral college would be that New York and California would be (still) jerrymandered against. All the other effects are random and generally bad for everybody.

Unfortunately the chances of the electoral college getting fixed via an orderly political process are just about nil. Fixing it would require a constitutional amendment, which would have to be approved by 2/3 of the states, and most of them are, unsurprisingly, small. The smallest states get several times their proportional say in the electoral college, and many times their propotional say in the senate, with a flat two senators from every state, so any constitutional amendment cleaning up the mess would be dead in the water.

The rules favoring small states, by the way, were set up at the time of the formation of the United States to get the south to join. Back then, the rules were even worse because slaves counted towards representation, even though they couldn't vote. It took the civil war, which was caused by the political imbalances favoring the less economically productive parts of the country and the separation being on neat geographic lines, for the mess to get cleaned up. Kind of like the situation today, except that it hasn't gotten to the point of internal warfare, at least not yet.

On that note, I feel obligated, this being election day, to encourage everyone to vote. Unless of course you'll be voting with a diebold machine, or your registration got mysteriously lost, as mine did. [Update - I showed up to vote and they did manage to find my registration in some obscure place, but my wife, whose registration was sent in at the same time and on the same day, had to cast a provisional ballot.]

comments