Mathematical Go

I was taught to play go as a child, but it wasn't until a few years ago that I learned how complex the rules are, at least the ones used in tournaments. I had previously thought the rules were elegant and simple.

Actually, mathematicians have devised elegant and simple rules of go. [Broken? archived version] Unfortunately the mathematical rules are rarely used. Instead, there are several popular rule sets with different properties.

Luckily in most games the complicated cases never arise, but it is irritating to know that in general, the outcome of the game can depend on the legality of suicide, and in many cases it is unclear whether a group is live or dead if the mathematical rules are not followed. [Link broken; the FAQ can be found in the nextgo package.]

Evidently when the game was first invented, nobody thought about the messy corner cases. It seems as each one was discovered, an ad hoc solution was proposed, and over time these cumulative patches to the basic rules eroded the austere grace of the game.

As one might expect, starting afresh and approaching the game from a mathematician's point of view not only restores clarity and precision, but also yields unexpected results. For example, Berlekamp and Wolfe describe bizarre positions where highly nonintuitive moves are required to win. Even though such situations never occur in real play, studying them hints at the richness and depth of this ancient game. Unsurprisingly, it was a mathematician who first drew my attention to the flaws in traditional go rule sets!

I am not sure why the mathematical rules have not caught on. Are they too difficult to implement in a tournament? Is the grip of tradition is too strong? Or is it simply that most in the go world are unfamiliar with these recent developments?

Blog Basics: Permalinks

I wrote some scripts to add permalinks, which a typical blog should have. I can understand why many people use dedicated blogging software, but I'm content to reinvent this wheel, as I'm comfortable with, and even enjoy, writing shell scripts. I also have more control this way.

I have one directory for every date I've posted. Inside there is one file per blog entry, containing an HTML snippet with the title in a h2 tag, and the date within a h3 tag. One script converts this to a page to be permalinked, while another pastes the entry into the main blog HTML files.

Inspired by the official Google blog, the permalink's filename is the title converted to lowercase with spaces converted to dashes, and all other characters removed.

I should eventually look into how the popular blogging software organizes things, but this scheme appears to work well.

Geometry Algorithms

Happy Pi Day!

Once in a while I visit ACM Programming Contest Problem Set Archive. Reading and trying out a problem or two reminds me of a time when I was eligible to compete. But mainly it makes me realize how little I knew back then, and how much I still can learn. For example, as mentioned in a previous post, I only came across the Dancing Links algorithm recently which comes in handy for several contest problems.

Many problems require simple geometry algorithms. Back in the day I thought I could derive what I needed on the fly for these sorts of problems. I still believe inventing algorithms is a good thing to do, but at some point one should learn what has been done before, as it is easy to miss clever and elegant optimizations.

For example, consider the simple problem of determining which side of a line a given point lies, where the line is defined by two given points. In the past, I would have naively computed the equation for the line and substituted the point in to see which side it lies on, but now I know that it is much easier to calculate the signed area.