From the archives: Mathematics

Or, if you'd prefer, return to the most recent posts.


Connecting Four: Optimism and Optimality

Thursday, 10 May 2007 — 6:42pm | Board games, Computing, Hockey, Mathematics, Music, Science, Scrabble

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.

Annotations (1)


Mandelbrot and Julia

Monday, 19 December 2005 — 3:58pm | Insights, Mathematics

Scenario: A mathematician defines a recurrence relation that, when applied, generates a fractal image. He leaves it up to a user on the front-end – any user, through a web interface, for instance – to define or adjust some minor but nontrivial parameters: colourization, magnification, the number of iterations, et alii.

Problem: Is it art? If so, who is the artist?

(We assert that in all cases, as a direct result of the elegance of the algorithm, the rendered image is measurably beautiful. Although we are not dealing with human subjects, the millihelen scale is one applicable metric.)

Annotations (0)


Here’s looking at Euclid

Sunday, 26 June 2005 — 7:53pm | Casablanca, Film, Insights, Mathematics

Let P = the set of all problems; Tn = the set of properties belonging to n little people; W = this crazy world.

Blaine’s Theorem: ∀x: xPT3, ∃ a hill of beans hW such that Σx < h.

Annotations (2)


« Back to the Future (newer posts)