Ntuple Indemnity

I’ve long been reluctant to jump on the open source cheerleading bandwagon with quite as much zeal as most other people who work with computers, but I’ve become a convert overnight.

Oh, sure, I’ve been an end-user benefactor of the open source model’s more representative products for years, but that has only made me sympathetic to open-source software’s actual philosophical tenets to the same extent that feeling warm in a comfortable pelt on a winter’s day would make me exclaim, “Golly, it’s a joy that we still club baby seals.” By and large, it’s the product that matters, and as far as I was previously concerned, processes of production are pretty much interchangeable unless they hold things up or cause serious collateral damage. Like seal-clubbing, I liked open source when it worked, and it was not something I was ever clearly for or against.

No, what got me to believe in open source was a scenario where I really, really wanted something to work, and it just wouldn’t. Enter DarwiinRemote.

Continued »

I have remained silent about the Bear Scat debacle over the course of its development this summer, but I think it’s high time to decloak.

Any casual observer of student politics over the span of more than a few years can tell you that between the quick turnover time between successive executives or councils and the erratic fluctuation of institutional memory (if any is still around to fluctuate), nothing sticks, and apathy comes naturally. I’m long past the point where I can rely on the student government to commit to anything reliably, and you should be too.

That said, the U of A Students’ Union occasionally bumbles its way into something that actually impacts students, and that’s when it’s time to intervene—if it’s not too late. As such, I am going to provide a cursory analysis, and at the very end, propose a course of action.

Continued »

As some of you know, I’m spending a nontrivial chunk of the summer teaching kids (lower bound: 11, upper bound: 15) to make their own computer games. They are given five days and a copy of the Torque Game Engine that I modified and compiled for the specific purpose of their prescribed activities. There is, unavoidably, a bit of coding involved.

Something that has always piqued my curiosity is the pedagogical difficulties involved in the instruction of computer programming. I speculate that ill-designed or ill-instructed introductory courses at the freshman level are, in all likelihood, directly responsible for the loss of a significant number of potential students in fields related to computing. When it comes to the matter of instruction, the problem often lies in the gap that exists between instructors that have completely internalized an intuitive sense of what is correct, and students that have not even begun to develop that foundation.

If you look at student essays, even those that are written at the university level, there’s a similar gulf between those who effortlessly arrange words into sentences and sentences into arguments – the former is a grammatical activity; the latter, logical and rhetorical – and those who still struggle with comma splices and coordinate conjunctions, never mind the trouble they subsequently encounter in the minefield of logical fallacies. When something resides in the realm of intuition, one neglects to decompose it into its component subproblems. It’s especially true of fluency in a given language, natural, programming or otherwise.

To absolutely nobody’s surprise, I invariably favour an educational approach built on a strong foundation of fundamental principles. You can’t make a musician out of someone who emulates notes on a page without any thought to chords and scales and how they apply to the inferential shaping of a sensible phrase, and you can’t make a (procedural) programmer out of someone who doesn’t have a basic and language-independent understanding of control flow.

For example, it is my belief that if you have any aspirations to work with computer programming in any capacity, you should have some exposure to recursion as early as possible. True to the title of Donald Knuth’s monograph on the subject, programming is an art. There exist brownie points for elegance. If I had it my way, I’d wean everyone on Lisp.

However, when you only have a week, and the students are impatient to get underway with a tangible project that does something, you have to take some shortcuts; providing them with a game engine and a lot of code already filled in is only the first step.

Here are some points of confusion an even mildly experienced programmer familiar with the lingua franca of C/C++ (the syntactic elements of which are as generally applicable as periods, commas and the Roman alphabet are to most European languages) might completely overlook:

When do we use curly braces, as opposed to square brackets and parentheses? (This is a particular challenge of denotative ambiguity when it comes to youths, who by and large still refer to parentheses as “brackets.”)

When does case sensitivity matter?

Does such-and-such still work if we don’t type in the tabs and spaces?

Is that the letter O or the number 0?

A veteran programmer tends to consciously think about those issues about as much as a pianist scrutinizes his chromatic scale fingerings note by note. He doesn’t think about it at all; he just does whatever makes sense.

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!

I’m behind enough on my novel that the additional negative harm of dedicating a few words to the blog instead of my little green notebook is negligible. Ergo, let’s talk about board games.

But first, as I have been tending to do with increasing regularity, I am going to precede the main feature with some ancillary featurettes.

I don’t write that much about hockey (proportionate to my other interests) because other, more prolific minds know a lot more about the ins and outs of the subject than I do. But I do know music, and I’m a bit of a stickler when it comes to the singing of the national anthems. I remember, with astounding clarity, that the most execrable part of watching Tampa’s home games in the Tampa-Calgary series in 2004 (aside from seeing the Lightning hoist the Cup) was Brooke Hogan’s consistently lamentable butchering of “O Canada” – and I’m sad to report that since then, Hulk’s baby girl hasn’t faded into deserved obscurity, but has instead released an album and graduated to B-list pop-stardom.

So, for all the press about how epic the Buffalo-Ottawa series will be when it comes to the action on the ice, I think it falls to somebody to mention two of the lesser-recognized reasons why it will be (and already is) so fun to watch: Doug Allen and Lyndon Slewidge. I haven’t seen every regular anthem singer currently making the rounds in the NHL, of course, but of the ones I have, these two are the very best. (And being from Calgary, where we get the excellent Heather Liscano, I do have standards.) What does the trick is their clarity, charisma, genuine quality of musicianship, and unflinching respect for what they are singing. Oh, and they stay in time. I’ve lost count of the wannabe divas who trill left and right and demonstrate nothing but a lack of education in the basics of metrical tempo (to say nothing of tone control). We’ll have none of that.

Next: Its run at the Varscona Theatre closes on Sunday, but Shadow Theatre’s production of David Belke’s Dreamland Saturday Nights is an absolute delight. I’m not as well-versed in appreciating the subtleties of the stage as I am with cinema or music, but this was my best experience with live theatre in some time. I do wonder, however, if it plays nearly as well to people who aren’t major cinephiles, as so much of its magic is referential.

And now, as promised, a bit about board games.

Last week, I went out into the wilderness with my new colleagues (pamperedness level: heated cabins), and one of them had the presence of mind to bring along the familiar diversion that we all know as Connect Four. On the last evening of our trip, when I was busy nursing a pot of cheap strawberry tea and making absolutely no progress on my cute little novel-in-progress about space colonies and married women, he challenged me to a friendly match. One friendly match quickly ignited into thirteen. We stopped when I hit ten wins. For those of you in the audience who can’t add, that’s a 10-3 record.

On paper, it looks like I demolished the poor guy; he certainly thought so, and it wasn’t until the next morning (when he beat up on someone else) that he regained some elementary semblance of confidence. To be fair, I started with six straight wins, and finished with a considerably weaker 4-3 thanks to careless errors in observation, unnecessary experimentation, and (in my opinion) noticeable improvement on the part of my opponent.

Now, I hadn’t played Connect Four in an absurdly long time: I only vaguely remember playing round after round on my Macintosh SE back in the black-and-white halcyon days of System 6, and I may have faced the occasional human opponent, though I’ve never owned a physical set myself. But the rules are simple enough that it’s not like you’re liable to forget how to play. The name of the game and the design of the board (i.e. it’s vertical, and pieces dropped in the slots tend to fall) make the mechanics about as self-evident as is possibly conceivable. That said, it would be foolish to understate its strategic complexity.

I can’t say I’ve ever considered myself any more than a casual player, and by purely casual standards, I don’t think my opponent was exceptionally bad. How, then, did I manage to be so dominant? What has really changed since the age of nine? Board game skills aren’t like fine wines: they don’t improve with age alone.

Two things come to mind: 1) serious exposure to other games of strategy, and 2) an education in the little-understood field of computing science.

The first is probably obvious. In the case of Connect Four – elegant, turn-based (but otherwise symmetrical) and fundamentally geometric – it’s easy to see how some half-decent Scrabble skills might help: looking for hotspots, settling into a rhythm of risk and reward, differentiating high-risk offensive positions from conservative and defensive ones. More pertinent would be a deterministic game like chess, where you learn to recognize certain patterns as opportunities for setting up zugzwangs and forced mates. I kind of wonder how well someone with a background in grid-based video games like Tetris Attack would fare.

There’s also the psychological element of the discipline it takes to focus on a game, exercise the patience to find the best move, intuit what your opponent is trying to do, and avoid stupid mistakes, but I don’t have that.

Less obvious to the layman is the value of a computing science education, which a lot of people out there think of as the study of computers, when in many cases it would actually be more accurate to say it is the study of problem-solving. (That’s a crude generalization as well, but still more accurate.) It’s not too hard to see how excellence at games of strategy is so often conceived as the pinnacle of whatever it is computing scientists do.

I am not saying that in a given turn in Connect Four, I’m culling a game tree in my head or performing a systematic limited depth-first search. But just as a basic level of comfort with calculus provides you with a substantially better intuitive grasp of infinities and convergences even if you don’t remember the ins and outs of solving triple integrals by substitution, I wager that an understanding of rational, computational processes provides one with an intuitive basis for pattern recognition and logical reasoning.

On top of that, it provides you with the tools to easily pursue further study. The reason I am writing this post is in part because tonight, I thought about how I might design a Connect Four AI, and I started looking at what had already been done. As a mechanically straightforward (and fully deterministic) game, it did not come as a surprise that Connect Four had already been solved. (The relevant thesis, which you can download as a 91-page PDF, is Victor Allis’s “A Knowledge-Based Approach of Connect-Four,” published in 1987. I’m not through much of it, but so far, it’s a terrific read.)

It turns out that with perfect play, the first player to move (“White” in the standard literature, as I don’t think many people with the standard Milton Bradley set care if red or yellow go first) always wins if the first move is down the centre column, just as how X can’t lose in tic-tac-toe if the first move is in the centre square. It seems intuitive, but there’s no comfort like the warm cushion of a mathematical proof.

Apart from questions of the “how did I win” variety, I think there’s another issue in play: why did I have fun? (This might not occur to those of you on another planet who play games solely for amusement and diversion and not necessarily to win, but I do, on occasion, actually have fun.)

Let’s proceed by example and analogy, shall we?

Anybody who has known me for any period of time probably has at least a cursory knowledge of where I stand when it comes to board games. There are three games in the top tier. I play Scrabble (far and away my favourite game of any sort) seriously enough to compete but not obsessively enough to truly excel; I’m fascinated by Diplomacy, but inexperienced; I adore Settlers of Catan, but I’m not nearly as good as the statement “I finished second at the University of Alberta’s POGOB! tournament in October and I’m playing in the Western Canadian championship next week” might suggest. (With games like Diplomacy and Settlers, a good reputation is a huge liability. People start ganging up on you.)

I have the deepest respect for chess, checkers and Go, but there’s such a gulf between my level of skill and what I would consider an acceptable competitive standard that I view them much like I view movies that are obviously imbued with the finest craftsmanship, but do not stir any passions on a personal level, and cannot be said to be among my favourites.

Among the other popular entertainments: I used to enjoy Risk, but I abandoned it after I found Diplomacy, and I haven’t played it since. Back when I was an only child, my family played Monopoly, but we would fight over the game and inevitably leave it unfinished; later, I discovered that we weren’t following the rules correctly anyway. I’ll play Battleship, but it’s just not the same without the “Sploosh!” and “Kaboom!” sound effects from the version in The Legend of Zelda: The Wind Waker. Then there’s the whole class of games like Cranium and Trivial Pursuit that I’m not even sure I should count: they suit social settings well, but you can’t “study” the game without feeling like you’re cheating.

I hate the Game of Life. (Not Conway’s cellular automaton, but that thinly-veiled wheel-spinning instrument of social engineering where you drive around in a little car and add pins to it when you get married, have kids, and coast towards your inconsequential demise in the thorny brambles of the American Dream.) Life sucks. No strategic depth whatsoever.

Now, let’s play Spot the Correlates. Is there anything I consistently like or dislike about board games?

If you look at the top tier – Scrabble, Diplomacy, Settlers – all three of them have an element of nondeterminism (stochastic in Scrabble, qualitative in Diplomacy, both in Settlers), but success or failure is primarily and repeatably dependent on conscious strategic decisions on the part of the player. In addition, a significant number (but not all) of these decisions are independent of who the opponent is, because they involve tactical knowledge of the game mechanics. It is possible to get progressively better as a player, but impossible to win all the time.

Connect Four initially falls into the same qualitative category as chess – although Go would be a better comparison, as it is based on placing pieces, not moving them, and there is only one type of piece. Connect Four doesn’t belong to nearly the same order of complexity, of course, but it feels like a faster-paced incarnation of the same deterministic experience. There is at least the persistent illusion of a fair fight, whereas in chess, I will almost always lose to someone who has a library of openings down pat, and almost always beat someone who can’t find his way around basic pins and skewers.

In a casual or novice-level game, you will almost never see a stalemate in chess except by accident, because the players aren’t skilled enough to set one up to avoid a loss, but they are skilled enough to finish off a familiar pattern like having a king and a rook to the opponent’s king. In expert play, draws are virtually the norm, and the result is a phenomenon called draw death: the prevalence of stalemates between players of sufficient skill exposes a serious air of futility that hangs over the game as a whole. A more familiar example of draw death is in tic-tac-toe. It doesn’t take very long for even a small child to figure out how to play every game of tic-tac-toe to a draw, at which point there is no real incentive to play anymore.

To be fair, this also happens in expert-level Diplomacy, where it is possible and not at all uncommon for the last two remaining players to entrench themselves in a stalemate line that cuts across the map, preventing each other from reaching the 18 supply centres required for victory. And a game like chess is sufficiently complex that unlike tic-tac-toe, it’s still possible to hold a championship. Draw death isn’t a reason to not play chess unless you are outstanding, in which case your name is Bobby Fischer and you remedied the problem by inventing a chess variant (Fischerandom/Chess960) where the initial placement of pieces is randomized within certain constraints.

I’m sure that against sufficiently skilled players, draw death presents a huge problem for Connect Four. But the real barrier to enjoying games of strategy is when improvement relies on the memorization of positions instead of principles; I also see it occur in Scrabble, where you need to dedicate a tremendous effort to memorizing words just to have a chance to apply strategic ideas. I like words enough that I don’t mind so much, but that obviously isn’t the case for everybody.

The elegance of Connect Four is how much complexity it manages to preserve in order to remain interesting, while its simplicity entails that it is never an exhausting game to play; it goes by so quickly that one can play round after round with little trouble. It owes at least some of its speed to a certain lack of choice, with only seven or fewer possible moves per turn. It also does not seem as susceptible to massive disparities in skill as many other games of its ilk. On the other hand, it’s entirely possible that I just don’t know the game very well yet, and that once I do, the number of players with whom I feel evenly matched (in either direction) will plummet.

And that’s why I’m behind on my novel.