Ntuple Indemnity

From Andrew Curry and Wired comes this comprehensive article on Settlers of Catan, a superb piece of board game journalism if I’ve ever seen one, and a must-read for players of all levels. It’s got a bit of everything: a look at why Settlers fit the market like a glove, a little about designer Klaus Teuber, an overview of the “German style” of board game design of which Settlers is the most prominent ambassador, and a peek into the complexity underlying the game’s infamously balanced mechanics.

This caught my attention:

In 2006, Brian Reynolds, a founder of Maryland software company Big Huge Games and the programmer who developed the AI behind the addictive computer classic Sid Meier’s Civilization II, set out to make an Xbox 360 version of Settlers. To help programmers develop the game’s AI, Teuber spent months exploring the mathematics of his most famous creation, charting the probability of every event in the game. The odds of a six or eight being rolled are almost 1 in 3 for example, while the chance of a four being rolled is 1 in 12. There is a 2-in-25 chance of drawing a Year of Plenty development card. Teuber created elaborate logic chains and probability matrices in a complex Excel spreadsheet so the videogame developers could see how every possible move and roll of the dice—from the impact of the Robber to the odds of getting wheat in a given scenario—compared. The end result was a sort of blueprint for the game that gave Big Huge Games a head start and showed just how complex the underlying math was. “It was the biggest, gnarliest spreadsheet I had ever seen,” Reynolds says.

I want to see this.

One of the best things that happened to the Civilization series was how in Civilization IV, lead designer Soren Johnson laid the mathematics and AI bare for everyone to see, expanding on a series tradition in the Sid Meier games to make all the data easily accessible (and therefore modifiable).

Settlers is elegant enough that I’m sure people have already figured out the math through a spot of reverse engineering; it’s really not that hard. But I’d love to see Teuber’s spreadsheet for its immense historical value as a design document alone. Surely there was a calculated rationale to everything from the fifteen-road limit to the assignment of three ore/brick hexes instead of four—and I often wonder if the perpetual endgame glut of sheep is here as an intentional crimp.

This week’s selection: Hexaflexagons, Probability Paradoxes, and the Tower of Hanoi (2008) by Martin Gardner.

In brief: This revised anthology of Martin Gardner’s “Mathematical Games” columns in Scientific American, the first of fifteen volumes, is an ample exhibition of the author’s repute as the canonical journalist of recreational mathematics. Though the brevity of the articles leaves the details of proofs bottled up in the extensive bibliography, the non-technical approach goes a long way towards illustrating the everyday relevance of esoterica in topology and combinatorial theory.

(The Wednesday Book Club is an ongoing initiative of mine to write a book review every week. I invite you to peruse the index. For more on Hexaflexagons, Probability Paradoxes, and the Tower of Hanoi, keep reading below.)

Continued »

I’m not someone who is intimately familiar with poetry, but I’ve always had a weakness for heroic verse—a trait that has become all too apparent to me again as I pore over the sweeping couplets of Lord Byron’s The Corsair. It’s a pity that the ongoing reinvention of poetic forms in the last century and a half, much as I appreciate some of its products, has progressed at the expense and exclusion of antecedent formal constraints: my impression is that most journals of poetry don’t even take rhyming couplets anymore as an editorial decision—partly under the expectation that nobody can do it well, that they are bound to tumble off the shoulders of the giants of the Western Canon and spiral towards a fiery and generally messy doom. It’s easy to imitate rhyming and metrical patterns and let a work fall into parody, but I almost wish for epic poetry of genuine earnest and good faith.

I’m sure it’s out there, and I just don’t know about it. That’s one of the first rules of art consumption in any medium: never assume that something hasn’t been done. I got a taste of the possibilities when I attended Derek Walcott’s reading at the University of Alberta last month, and I’m really going to have to look into Omeros, Walcott’s reinvention of Homer’s Odyssey.

This is all a fancy setup, by the way, for one of my ill-conceived what’s-the-big-ideas: why not deploy the heroic epic in the genre of science fiction?

Continued »

As it is, I’m already very indecisive when it comes to shopping for books. But if you really want to trap me at a display case for nigh on an hour, toss in an NP-hard combinatorial problem (my non-mathematical readers: refer to this simple illustration) and I’m done for.

The scenario: I won a $250 book prize for an essay I wrote last year (something to do with moral culpability in Adam Bede, if I remember correctly), redeemable for anything published by the University of Alberta Press. Because I insist on getting my money’s worth, we can formulate this as Objective 1: Spend $250 on books.

Oh, but it doesn’t stop there. You see, when I went to go pay the UAP a visit and make my book selection, I travelled by bicycle, which inadvertently introduced a second dimension, making this a doubly-constrained knapsack problem. Objective 2: Select books of appropriate size and weight that will fit in my backpack without getting wrecked, so I can actually carry them home on a bike.

Of course, I wasn’t just going to pick any set of books I see just so I could use up the entirety of the book prize without having to pay extra for going over. Objective 3: Maximize the sum of the value-functions assigned to the contents of the books selected. (In plain English: “Pick interesting books that I will actually read.”)

My solution?

Continued »

Here’s something I would have posted last Thursday if I hadn’t cut myself off from the Internet in what was, in hindsight, an excellently timed and perfectly necessary pre-Potter lockdown. It’s been all over the news at a national and international level, as it damn well should be, but I feel it is my duty as an enthusiast of games of strategy and an alumnus of the University of Alberta’s esteemed Computing Science department to once again highlight the tremendous accomplishment that Dr. Jonathan Schaeffer and the GAMES group made last week. I heard rumblings of a major breakthrough about two months ago, but the details were kept under embargo. With the publication of the accomplishment in Science, it’s official: checkers has been solved.

For those of you who aren’t familiar with computing science, game theory or their related fields, what it means in layman’s terms is this: consider how with a simple game like Tic-Tac-Toe, pretty much everyone over the age of five has stumbled upon a strategy that will always play to a win or a draw. Well, it’s been a long time coming, but they’ve just done that with checkers.

There’s a considerable wealth of information on the Chinook website, where you can step your way through a demonstration of the proof or find your way to the article in Science.

More than anything else, I hope this kind of high-profile accomplishment encourages others to pursue studies in what is, I think, a grossly misunderstood and often ill-introduced branch of the sciences. I know that I, for one, had little idea just what I was missing until I transferred into their programme in my third year, a decision about which I have almost no regrets. Computers aren’t just tools that are meant to sit around generating heat in office cubicles, waiting to be thrown out a nearby window; their study is not limited to job training for information-age janitors, network witch-doctors and software monkeys. There’s a genuinely interesting field of scientific enquiry there to which few receive anything remotely resembling a proper introduction. I sincerely hope this is a step towards the elusive remedy.

Next stop, poker!