Chess world championship cycle

Interviews with Kramnik and Anand reveal six months preparation is "enough".

General structure: single elimination tournament, to prevent the Soviets from colluding.

Tunable knobs: how long the cycle is, time in betwen levels of the tournament, where the former champion gets seeded in.

2 year cycle

"former champ" == "last cycle's champion"

8 candidates announced January
  6 months pass
8-player match July
  6 months pass
4-player match January
  6 months pass
2 player match, yielding challenger July
  6 months pass, former champ enjoying laurels for total 2 years
final match December

---

15+1 announced, including former champion January
  6 months pass, former champ enjoying laurels
16 player match July
8 player match January
4 player match July
2 player match December

---

14 announced January
  6 months pass, former champ enjoying laurels
14 player match July
  6 months pass, former champ enjoying laurels for total 1 year
8 player match, 7+1 including former champ January
4 player match July
2 player match December

---

12 announced January
  6 months pass, former champ enjoying laurels
12 player match July
  6 months pass, former champ enjoying laurels
6 player match January
  6 months pass, former champ enjoying laurels for total 1.5 years
4 player match, 3+1 including former champ July
2 player match December

---
BEST PLAN:

24 announced January
  4 months pass, former champ enjoying laurels
24 player match May
  4 months pass, former champ enjoying laurels
12 player match September
  4 months pass, former champ enjoying laurels
6 player match January
  6 months pass, former champ enjoying laurels for total 1.33 years
4 player match July
  6 months pass
2 player match December

2 year cycle seems more than enough, though 3 years is OK stretching the time betwen matches to 9 or 6 months, which might be appropriate if the matches themselves are long and recovery time after matches.

Of the (say) 24 spots, reserve 1 for loser of the last championship, 1 for a large knockout world cup winner (allows a wild card-like entry), 1 for reigning women's world champion, 1 for blitz champion, remaining 20 (or more) go to highest rated.

Though really, I think this is all too complicated and have a better idea.

Grapefruit

A sticker on my grapefruit says:

Harbor Island
粘度センサー
使用
Florida
USA

For the use of the viscosity sensor?

Bug database part of open source

So many open source changelogs and commit messages refer to bug numbers in the project's bug database. Thus, in order to be able to understand the source code, one needs to be able to look at, and ideally dump, the project's bug database.

Unicode search bug

Blogger has a bug that searching for a string using UTF-8 does not find the same string which was originally written using the html character entity syntax (ampersand pound code point).

UCT

Now that completely naive UCT can select objectively good moves in go 囲碁 albeit slowly, we can calmly return to the task of finding heuristics to place prior probabilities on the UCT search tree. We no longer have the urgency that the heuristics be very good: the probabilistic nature of UCT can robustly handle a little bit of error in the heuristic.

We may derive heuristics automatically using machine learning.

How well does UCT do on the combinatorial game theory endgames?

I would like to see UCT applied to chess, with a limited depth search as the node prior generator. It should do well in "strategic" positions.

How well does UCT do on chess endgames, where computers these days play especially poorly?

Slashdot | FOSS Development As Economic Stimulus

Slashdot | FOSS Development As Economic Stimulus

I like this idea a lot. Open-source, ideally public domain, software is a public good, so promises a large bang for the stimulus buck.

A saying

A saying with no hits on Google:

"The road to hell is paved with silver lining."

from (I think) a Scientific American Martin Gardner column on Oulipo.

Mechanical hash

Build a mechanical implementation of any of the (good) SHA-3 competition entrants.

Ticking bomb TV show

The ticking bomb is a popular TV show concept, for example, "24". The hero generally succeeds in defusing the bomb. A variant of the theme is the bomb actually goes in half the episodes (the hero tries, but fails), leaving the audience truly in suspense as to what will happen. The cool part is if the disaster scenario actually happens, then it's an opportunity for cool special effects to depict the (yay fictional) disaster. It's a win-win.

Liquified Natural Gas tanker explosion

Scientology

Given Scientologists tendencies to work with one another in Hollywood, can one unmask the closet Scientologists (starting with a known members) simply from a list of cast and crew of a bunch of movies?

Apollonian gasket

What is an algorithm to rapidly generate a random pattern of circles each tangent to three others? We'd like to avoid a few big circles dominating the area.

Generalize to create a pattern of non-overlapping uniformly scaled copies of an arbitrary shape. Non-rotated is easy case, rotation makes things harder.

Pasta sauce

I wish I could get single-serving size containers of pasta sauce.

Surprising string in Firefox binary data

hg changeset 7165ce2d87c7

$ tail -c +11039 src/browser/branding/unofficial/firefox.icns | head -5c

XYZZY

You bring shame to yourself and your political party

Penalties for convictions for political corruption should be political, as opposed to say jail time.

Here are some ideas:

Fines levied against re-election campaign finances. With the permission of donors, fines may be paid out out of donations.

Prohibition of campaign spending, including advertisement and payment of campaign workers, until the fines are paid.

To circumvent the loophole, "third" parties are prohibited (with the penalty of imprisonment) from campaigning for a convicted candidate until the fines are paid. Third parties may contribute toward paying the fines.

You bring shame not only to yourself but also to your party. This is the second component: penalties that other candidates of the party face because of corruption of one member. This places a burden on the party to nominate honest candidates and maintain oversight so they remain honest. This is a good thing.

Penalties to the party are especially relevant if the convicted politician is not running for re-election due to term limits, for example.

We establish a hierarchical notion of "taint". A convicted corrupt politician taints all candidates of his or her party below himself or herself in the hierarchy in his or her political district. The hierarchy is ordered by power, or number of constituents governed: President, governor, U.S. senator, U.S. representative, state senator, state representative, city councilor.

To simplify the exposition, we also say a tainted politician taints himself or herself.

A tainted candidate is also prohibited from campaign spending until fines are paid.

Another way to punish corruption is to change the ballot.

Tainted incumbent candidates lose their incumbency designation on the ballot.

In order to vote for a tainted candidate, a voter must jump through an extra hoop. For example, underneath a tainted candidate's ballot bubble "This candidate belongs to the same political party whose lack of ethics gave us convicted politician Ted Stevens. To confirm that you really intend to vote for this candidate despite his (her) party's lack of ethics, please fill in only bubbles 1, 4, 5, and 8 below."

What is art?

In the process of its creation, the artist must have been trying to optimize some non-objective characteristic about his or her work.

This includes a great many things that might not be traditionally considered art. It also excludes a few (I'm not positive if any) works which just kind of happened -- a product of randomness -- without the artist exhibiting any control or optimization.

This means "But is it art?" cannot be answered without "inside" information about the artist and how the work was created.

The inspiration for this was a meditation about scientific hypotheses and how they must be rejectable. Thus a stronger condition than the above is that not only must the artist be trying to maximize some measure of "quality" but he or she must also have a threshold of "acceptable" quality below which he or she will "reject" the work, which means something like not publishing or exhibiting it. Art must be rejectable.

Various technologies which ought to be used more

Speex Ogg Vorbis flac

DJVU png Jpeg2000

lzma

AES-256 SHA-512 ECC

Ubuntu intrepid installation problem

Using the "alternate" CD installer, and choosing guided partitioning with encrypted LVM, I encountered "grub error 18". I suspect the fact that it put the boot partition on sda5 instead of the normal sda1 has something to do with it.

Typing with a stylus

Create an arrangement of letters and punctuation to minimize the distance traveled while using it as an on-screen keyboard.

I'm guessing Spacebar will be in the center, and Shift will be next to I. Throw in a Fitts Law constraint in there -- a time penalty for small area keys.

An additional degree of freedom: some letters may be duplicated.

Different layouts for different aspect ratios or shapes the whole keyboard fits into.

Tit for tat

Tit for tat is a Nash equilibrium strategy to Prisoners' Dilemma, and to many conflicts.

The key feature of any Nash equilibrium strategy is you have nothing to lose by announcing your strategy and nothing to gain by keeping it secret. It is by definition optimized against the best response your opponent may come up with against it.

Announcing your strategy, credibly, may induce the opponent to act differently than if the opponent does not know your strategy. In the case of Tit for Tat, your opponent will cooperate.

Thwarting telemarketers

Forcing a valid caller ID, because after the callee answers, the call is reversed to that number for the conversation. This forces the telemarketer to reveal contact information you can sue.

Another evil idea: you can make your number act like a 900 number. You can forgive charges at the time of the call or in advance for your friends.

The pride and sorrow

Not once, not twice, but three times an American chess player as seemingly come out of nowhere, shown himself to be (arguably) the best in the world, and then abruptly retired.

The first two are the well-known Paul Morphy and Bobby Fischer. The third I argue is the computer Deep Blue, which after defeating Kasparov, was disassembled by IBM without any chances for additional challenges by other humans or other computers.

Speech interface games

When you are too lazy to even mash buttons on the controller.

Apple Chess tries but doesn't quite have the best vocabulary. And it's not multi-player networked.

Slightly Advanced Chess

We wish to avoid lots of opening theory memorization and blunders. To that end we allow each player access to a vast opening database (of their own) and a very weak (not powerful ) computer -- not really capable of selecting the best move, but capable of detecting a blunder.

A handheld device may satisfy both of these functions.

On-screen keyboard feedback

For example, the on-screen keyboard on a Palm needs better feedback that the letter has been successfully pressed. Perhaps highlight the key for longer.

Not double pass

How often in professional go (囲碁) does one player pass, and the next player does not pass, but plays a move probably attacking a group the first player thought was safe?

This appears to be the crux of the difference between Japanese and Chinese scoring. Under Chinese scoring, a player may "shore up" his own possibly weak groups at the end of the game with impunity. Japanese scoring encourages players to leave their groups just barely living to maximize the amount of enclosed territory.

No-fly list

How can someone be considered so dangerous that they must not be permitted to fly, even after a more intrusive secondary search, but not so dangerous that they cannot be arrested?

The point of freedom of speech is that a free dissemination of ideas is good for society. If a person, having undergone a more intrusive secondary search, is found not to carry anything dangerous, then the thing he or she is carrying is his or her brain, and the ideas within it. The no-fly list implies those ideas must not be permitted to travel.

Measuring the speed of the subway

I have often wondered how fast the subway is going. Without knowledge of the distance between lights in the tunnel, it seemed impossible to determine without an accelerometer. But here is a way:

Two people with synchronized watches at opposite ends of a subway car note the time when passing certain landmarks, for example lights in the tunnel. Measure within the car the distance between the observers, and divide that by the time difference. This gives the instantaneous velocity.

Two video cameras with synchronized timestamps also work.

Jury nullification initiative

A ballot initiative stating that, before deliberation, judges must inform the jury that they may vote their conscience, even if it contradicts the letter of the law, that is, the right of jury nullification. I believe not enough citizens are aware of this right.

The win-win situation here is, even if the initiative fails, its debate by the people before the election (assuming a media campaign to encourage passage) will inform the populace of this right even if judges are not required to inform them.

Opponents of jury nullification like to point out the example of white juries refusing to convict lynchers. I believe this is an extremely unusual anomaly from an exceptionally tense time in American history. Instead, these days I routinely see so many bad laws passed purely due to well-funded special interest groups. Jury nullification puts ordinary citizens back into the loop of the how the laws of this country are made and enforced.

California, with its liberal initiative process and large contingent of free-thinkers is a prime target for this initiative. It is important that there be money behind the initiative in order to assure the win-win scenario described above.

Soap box, ballot box, jury box, (cartridge box? ).

IPv6 government subsidy

Would a government subsidy to ISPs who offer IPv6 to their customers (or a rebate directly to customers who use an ISP who offers IPv6) accelerate its adoption? Or are there other technical or political hurdles which will cause the subsidy to be ineffective?

Widespread adoption of IPv6 has a network effect (pun!) of being good for society as a whole, so it is well within the government's perogative to encourage it.

It need not be a national government subsidy; state and local governments could do it, too.

Illegal to build

I'm glad to see Selectable Output Control rejected by the FCC (for now). But what is the complete list of other consumer devices and products that are currently illegal to build or sell under the justification of "industry protection"? Or are crippled or taxed in some way (defective by design)?

This is not about manufacturers voluntarily building defective-by-design products to "protect" themselves (e.g. game consoles), but one industry special interest creating government laws and regulation to impose its will on another manufacturer prohibiting it from building a product that consumers would want to buy.

Our own government is being subverted by special interests to make life difficult for the consumer.

If this list were to exist, it may serve as a focal point to mobilize consumers ("Gee, I wish I could buy such a product") into overturning the regulations that were making it illegal to build.

Humorous anti-terrorism

Announcements, signs, etc. at airports, train stations, etc., e.g. "unattended packages will be destroyed" ought have some humor. Terrorism is extremely rare, and if you let the threat of terrorism negatively affect your life, the terrorists have won.

Do natural processes create entangled particles?

Are there any interesting natural phenomena demonstrating or resulting from "spooky action at a distance"?

Don't budget cut education

In a down economy, education is important, for it is ultimately educated people developing technology which powers the long-term growth of the economy (or recovery). The worse the economy, the younger one should target the education stimulus, for they are the ones who will be working once the economy re-rights or re-corrects itself.

Bruce Willis's character's education stopped at a very young age in 12 Monkeys.

Data structures for manifold environments

Consider a first-person shooter set not in Euclidean 3-space, but on a curved manifold such as a 3-sphere. By definition of a manifold, space locally around you will look almost like Euclidean space, so it will not be too disorienting to play.

For implementing such a game, what data structure should one use to keep track of where things are? Assume we want something generalizable to many different 3-manifolds, not just the 3-sphere. From a level designer's perspective, we want to be able to create an object and translate it around in space without it weirdly changing shape and size, so straight usage of the 3-sphere equivalent of latitude and longitude will not work. The level designer, and player, should be unaware of any "poles" in the underlying coordinate representation of the manifold.

Daemon packages

Software packages which attempt to start a daemon or do something significantly different than just installing files ought to have a warning that they are about to do so. They don't just work inside a chroot. Hello exim4.

Coin flip election

Despite its problems as being demonstrated in Minnesota, I think the way it's done now is still the right way to do it.

That said, here is an interesting alternative. The vote totals are merely used to determine probability weights for a "coin flip" that determines the election. The advantage of this idea is that the coin flip may be done in one place under the scrutiny of many election observers. Using cryptographic random number generators for the "coin", the process might even be made secure. In contrast to the current system where voter fraud of a hundred votes anywhere in the state (a tremendous area for election monitors to monitor) can decide a close election, such fraud only buys a little bit of advantage in the coin flip.

The scheme I propose is that the vote totals determine the weights of a coin. For example, if 49 votes are cast for candidate A, and 51 for B, then we use a coin biased 49%-51%. We flip this coin a number of times equal to the number of total actual votes cast, in this case, flip it 100 times. Then, count who gets more coin flips in their favor.

Chudnovsky competitive

Chudnovsky's formula adds a constant number of digits per iteration, or linear increase in precision. Gauss-Legendre doubles the number of digits per iteration, or quadratic convergence. Borwein's quadruples the number of digits per iteration, or quartic convergence.

Thus it's interesting that Chudnovsky is competitive, if not better, than Gauss-Legendre or Borwein in terms of CPU time in actual implementations.

I think binary splitting has something to do with it.

Car industry

A politically viable way to help the auto industry while still letting market forces do their work: extend additional unemployment benefits and retraining programs to the workers inconvenienced by the turmoil. Help the bottom of the pyramid, not the top. But this is probably more expensive.

Blood diamonds

What happens to conflict diamonds? Ideally, market pressures would prevent them from being mined in the first place, but I doubt it. I'm guessing there is an elaborate laundering process by which they get smuggled into a "clean" diamond stream. One of the steps might be the ironic smuggling of diamonds into a diamond mine. And diamond mine administrators would quietly look the other way, for it means more profits for them.

Awkwardness of planar graphs

Some planar graphs are more awkward to draw on a plane using only straight edges than other planar graphs.

We might speak of the awkwardness of a particular two-dimensional embedding of a graph, or the awkwardness of the graph itself, implicitly minimized among all possible embeddings.

What is a good measure of awkwardness? Most acute angle? Ratio of longest to shortest edge? But I don't feel a wheel graph is that awkward.

Generalize to sphere.

Automatic calling home

The following applications on Ubuntu Linux (although the problem is likely more general) automatically access the network without the user getting a reasonable (IMHO) chance to stop it or the user may not realize the potential danger of it like the privacy implications or if the user is on a pay-by-the-byte network connection.

Firefox update

Firefox extension update

Ubuntu update gnome applet

Gnome gweather applet

Firefox home page

Firefox BBC RSS feed

Archimedes' Death Ray done right

The general idea is lots of mirrors each on a two-axis steerable mount, so it can be pointed in any direction, within limits.

Using cameras and sensors, all mirrors automatically track the sun and the target.

The exciting part is trying to make the design as simple, elegant, and inexpensive as possible (as inexpensive as a design with thousands of individually controlled mirrors can be).

One idea is a single central sun and target tracker which wirelessly (to avoid having to string a cable to every mirror) tells each mirror how to point itself. The orientation computation is done centrally. (Another possibility is distributed computation, but I don't think it is worth it.)

The second challenge is calibrating every mirror so that the central computer knows its position and orientation. This can be done automatically beforehand with some fixed targets. A mirror is directed to do a boustrophedonic raster scan (or an irrational Lissajous scan) until it hits a target, detected by the central camera. Repeat for several targets and sun positions, and the central camera and computer gathers enough information to solve for the position and orientation of the moving mirror. Repeat for each mirror: the calibration process may take a long time, but it's fully automated.

Each mirror can be solar powered, for its steering motor and radio. Then we don't have to string thousands of power cables.

Application isolation by packages

Applications only see a virtual filesystem consisting only of themselves and the packages they depend on, as if the user had decided to install a system that had only the minimal functionality to get that application working.

And a nearly empty home directory populated with only the files the user chose to make readable to the application.

A way to facilitate a collision attack

This is a way to do a contest for Code Show. Don't do this in real life.

Submit your first program to one server which verifies that your program is a Perl script consisting entirely of printing constant strings. Calculate the checksum of the program and put the checksum in a database.

Submit your second program to a second server which also contains the key on a local file. The server calculates the checksum of the second program to see if it is on the "safe" database, and if it is, runs the program and reports its output to the user.

Obviously, the way to penetrate the second server is to create two different programs the have the same hash. The first program is "safe" and the second does something like print `cat key`.

Perl's syntactic flexibility gives lots of freedom for the programs to achieve colliding hash digests.

Word obfuscation and solving

Similar to the premise/mechanism of the TV game show "Wheel of Fortune". Start with a word or phrase. The first player gets to see the phrase and selects the order in which the letters will be revealed. The second player tries to solve the phrase as quickly as possible. The goal of the first player is to choose an ordering which he thinks will make it most difficult to solve.

Variations: reveal single letters of the phrase at a time, or all occurrences of a given letter. Many Orderers. Many Solvers. Whoever does the best among the many orderers or solvers. Choose a revelation order that makes it the most easiest to solve.

Happy new year and birthday

For the purposes of government age limitation and identification, everyone's birthday can be January 1 of the year they were born. For examples, voting, drinking. No one will get younger in the transition. There will be a few people born in December who get to be up to 364 days older than their biological age. I believe society is well equipped for some extra debauchery that this might induce on New Year's day.

Your actual birthday may be a piece of private information that you only share with friends and the government benefits none from knowing it to a precision better than a year.

It works kind of like this in China.