BBC is reporting on a spectacular result from the upcoming issue of Science. Researchers at the University of Alberta have computed the entire game tree for the game of checkers. For non-cs geeks, the game tree is a data structure which describes every possible sequence of moves in a game. Knowledge of the complete game tree allows one to categorize a game such as checkers into one of three classes:

1. First mover can always win
2. Second mover can always win
3. It is always possible to force a tie

In the case of checkers, the answer turns out to be door number 3, which means that perfect players of checkers will always tie, regardless of who moves first. The paper’s authors have demonstrated this by writing a piece of software which “plays” checkers while in possession of the complete game tree. This program is of course not playing in the sense that other software plays. Rather, you can think of it as having a big checkers manual. When it considers moving, it turns to the page of the board it sees, and makes the move indicated on that page…which is the best possible move: guaranteed.

It is interesting to note that chess will never be solved in this fashion because the number of bits required to store the tree exceeds the information capacity of the universe we’re in. Same for the game of Go, which is not solvable even for a 9×9 teaching board, much less the full 19×19 board which is usually used.

computer science | No Comments »

jacob daum, photo, sophie daum | No Comments »

The latest column by our friend Diane Flacks came out yesterday.  As usual, it was terrific.  Had me laughing out loud from the beginning.  This installment’s subject was on the relationship between TV and parenting.  Diane’s take on the subject was funny and insightful.  The column also sparked a lively reader discussion in the comments, many of which made excellent points (especially the one I wrote).

Read the column here

parenting, purdy-flacks | 3 Comments »

jacob daum, photo, sophie daum | 2 Comments »

sophie daum | 1 Comment »

Sorry for the lack of blogging, but I just got back from a full week at a cottage north of Montreal.  Pics and blogs to follow…we thank you for your support.

admin | No Comments »

Worth reading is this magnificent post about Bush and Libby on Cosmic Variance. Lovely contrast between Bush’s behaviour here with his earlier refusal to help death row inmates.

bush, libby, politics, united states | 2 Comments »

So Bush went ahead and commuted Libby’s sentence, and made a clever speech pointing out that it isn’t a pardon.  Not so impressive given that

1. Libby is still pursuing his appeal, so could get off scott free
2. Bush says will still consider pardoning Libby

Frankly the whole thing makes me want to drive to the US and burn some cars.  One gets the feeling that the rule of law down there is on some pretty shaky ground at the moment.

The whole thing was made a bit worse by the fact that Bush did not consult the DOJ on the matter, and in fact acted in a manner contrary to longstanding DOJ policy.  It seems though, that this strategy is a bit on the dangerous side.  In his touching speech, Bush mentioned the two years of probation which would still need to be served by Libby.  Turns out that Libby was not sentenced to probation…but rather “supervised release”…something which can only occur after you’ve served some time.  This inconsistency was noticed by Reggie Walton, the sentencing judge in the case, who filed yesterday asking both sides to appear in court to present arguments on how exactly they feel the law should be interpreted in light of the seemingly contradictory commutation.

In light of the president’s unorthodox behaviour and the concerns of Judge Walton, the House Judiciary Committee has decided to hold hearings to look into the matter.  This was announced by Rep. Conyers, the committee’s chair along with the excellent words:

“In light of yesterday’s announcement by the President that he was commuting the prison sentence for Scooter Libby, it is imperative that Congress look into presidential authority to grant clemency, and how such power may be abused. Taken to its extreme, the use of such authority could completely circumvent the law enforcement process and prevent credible efforts to investigate wrongdoing in the executive branch.”

I love Conyers, but though he is eloquent I fear that words will be the start and the end of this thing.  Why are the Democrats unable to act?  It’s been half a year since they took over the congress, and the abuse goes on and on unchecked.  At what point will they realize that what’s at stake here transcends their pre-2008 posturing and actually take a stand?

bush, libby, politics, united states | No Comments »

So upset about the Libby I can’t talk about it. So I looked around to find something cheery and found this post on Cosmic Variance. Seems the FDA is considering a proposal to allow irradiated meat to be sold with no label.

The meat industry really wants this because they spend almost all of their efforts trying to keep shit from getting mixed in to the meat they ship. It would be much cheaper for them to just leave the shit in, except that would make lots of people sick (lots more than already do, that is). So they have this plan to “cold pasteurize” their product by shining it with an intense beam of high energy gamma radiation. This kills bad bugs by knocking apart their DNA so they can’t reproduce.

Unfortunately, it also knocks everything else apart too, filling the tasty beef with all sorts of radiolytic byproducts, smashed up molecule fragments, many of which do not occur in nature at all. Of course that’s only speculation, because the actual composition of these byproducts have not been closely studied. What has been studied is the radiation’s effect on the taste of the meat, which was described as “wet dog” or “singed hair”.

food, politics, united states | 3 Comments »