Darya, Darya, where do you go
with your rucksack and downcoat and laughter?
All who adore you are dying to know,
Darya, Darya, where do you go;
will Russia and Canada, covered in snow,
remember your footsteps hereafter?
Darya? Darya, that's where you go
with your rucksack and downcoat and laughter!
Tuesday, 10 August 2010
Monday, 1 February 2010
The Stable Marriage Problem
Previously I wrote about a mathematical model called the "Marriage Problem" which, whilst interesting, has a lot of shortcomings. Under very particular conditions (which are arguably quite unrealistic), it can optimise the chances of marrying the best possible partner I could expect. But even then it only optimises the probability of doing so, and that's small comfort if I marry someone today only to meet my true True Love tomorrow.
Go To Him
I still love you so, but if he loves you more, go with him.
Life is messy. What if you do fall even more in love with someone else than with your current spouse, and what if they fall in love with you? What if they also are married to another? Then should your respective vows forever keep your two hearts apart, or should you abandon that which once was beautiful but which beauty now hath ruined? What mockery is made of love in either case!
Oh, that this tragedy could have been averted! If only there were a way to ensure that everyone be happily married and never be tormented by temptation! If only Mathematics had something to tell us...
There is another mathematical problem, of similar name though quite distinct, called the "Stable Marriage Problem". Consider an equal number of men and women to be married to one another. Is it possible for everyone to marry, such that you could never find yourself in that lamentable hypothetical situation: preferring to be with someone else who would also prefer to be with you?
I'm Henry The Eighth
And every one was an 'enry...
Yes - it is possible.
Gale & Shapley devised a simple iterative algorithm for solving the problem: Each man should rank the women from best to worst according to his personal preferences, and each woman should rank the men according to hers. Then, each man should propose to the woman he prefers most. If a woman receives a proposal, she accepts it, and the couple are engaged. If a woman receives multiple proposals, she accepts the proposal from the man she prefers most. Then, each man who was rejected (because the woman he preferred most accepted another man's proposal) should propose to the next-most preferred woman on his list. As before, if a free woman receives a proposal, she accepts it, and if she receives multiple proposals, she accepts the one she prefers most. If an engaged woman receives a proposal from a man she prefers more than her current fiance, she dumps her current fiance and accepts the new proposal. Then, each man who was rejected or dumped proposes to the next-most preferred woman on his list... and so the process continues until every man (and therefore every woman) is engaged. At this point everyone marries their current fiance and the algorithm is complete.
This algorithm is guaranteed to finish (it won't keep iterating endlessly), and it is guaranteed to result in a "stable pairing" - an arrangement of marriages in which no two people prefer each other to their current spouses.
It is interesting to note how similar this model is, in principle, to the way our society has approached marriage in recent history.
Hungry Heart
Got a wife and kids in Baltimore, Jack, I went out for a ride and I never went back...
So if everyone followed these rules, would the world be a happier place? Not necessarily. Stability, in this sense, doesn't imply happiness: just because your marriage is "stable" doesn't mean that you wouldn't rather be with someone else - it just means that that person wouldn't rather be with you.
The mathematical "happiness" score of your marriage is determined by how high your spouse sits on your own personal preference ranking of all partners. The overall happiness of a given arrangement of marriages can be defined as the average happiness scores of all people. Note that husband and wife can have different happiness scores!
For any large enough group of men and women there will be multiple alternative arrangements of marriages that are all "stable", in the sense that no two people prefer each other to their current spouses. Some arrangements will be "happier" than others.
Gale & Shapley's model produces just one of many possible stable arrangements. In fact, there's a very interesting mathematical property of Gale & Shapley's model: It will always produce the arrangement that, whilst still being stable, is happiest for the men (who propose)... and unhappiest for the women.
Reflect for a moment, if you will, upon the parallels between this model and conservative real-life society: I wonder if it is coincidence that this model predicts unhappy marriages for women, and that our real-life notions about marriage are changing as women become more empowered?
All This Useless Beauty
What shall we do, what shall we do?
Remember that every man and woman ranks each potential partner from best to worst. These personal preferences are necessary for establishing that an arrangement is "stable" (we need some way of knowing whether any two people prefer each other to their current spouses), and is used to calculate the happiness of an arrangement of marriages. So far, and very politically correctly, we've assumed that the preferences are arbitrary, random - that beauty is in the eye of the beholder. But what if each person has an intrinsic "beauty" (or personality or intelligence; call it what you will, mathematically it's equivalent) that influences their standing in other people's preferences?
Caldarelli & Capocci showed that the more that "beauty" is allowed to influence the preferences, the more miserable everyone is in general. That's because the more homogenised our notion of beauty is, the more similar everyone's "personal" preferences become. The more similar everyone's preferences are, the less likely it is for you to marry high on your list, because the people high on your list are also high on the lists of rivals more attractive than you are. It's fine if you're beautiful, but rough for everyone else.
Surprisingly though, according to Caldarelli & Capocci's model, the more that beauty influences preferences, the happier that women are, on average, relative to men. The arrangements found by this model are still happiest for men and unhappiest for women, but the difference is less. And depending on how much weight is placed on beauty (not too little, not too much), a majority of women can end up much happier than if beauty plays no role.
I wonder, then, if emphasising beauty is a strategy for women as a group to maximise their happiness within a traditionally male-dominated society - making the best of an unfair situation?
So Far Away
You're so far away from me, so far I just can't see.
"Spatial homogamy" is the idea that people tend to marry people from their own area. "Propinquity" is the idea that the probability of forming a relationship is proportional to the square of the physical distance between people. Many studies have cemented these ideas in sociology: People tend to prefer partners who live close by. Someone commented on my previous article that the trick was to fall in love with someone within a certain distance. He was probably thinking about fuel prices and airfares, but how right he was - from a mathematical point of view!
If adding "beauty" to the model reduces overall happiness by homogenising people's preferences, then adding "distance" to the model does the opposite by mixing the preferences up again. Because everyone occupies a unique position in space, everyone's preferences are influenced in a unique way by the distances to other people.
In fact, I think it's probably even better than that. The distance relationship between two people is symmetrical, and therefore affects both of their preferences the same way - the person that you prefer because they live close by is more likely to prefer you as well, for the same reason. So the more emphasis placed on distance, the happier everyone should be. So - say hi to that cute guy or girl you see at the local market next time!
The Stable Marriage Problem is an incredibly rich area of research, bringing together combinatorial optimisation, game theory, economics, and even real sociological research. As far as I know it's not actually used to marry people off anywhere, but it is used for analogous problems like assigning students to schools and residents to hospitals.
There are a lot of other variants on the classical Gale-Shapley model that I haven't even touched - like models that take into account three-way matches (actually, even kinkier than it sounds if you were to apply it to dating...) and models that take into account "cheating" to get a better match for yourself.
There's even a variant, commonly called the Stable Roommate Problem, which matches pairs of people from within a single group, not across two groups like the Stable Marriage Problem. This might be a good model for gay marriage, but there's some bad news: there's no mathematical guarantee of stability in this single-group variant. But then, we've just seen that stability is no guarantee of happiness, so maybe that's not such a bad thing after all!
Go To Him
I still love you so, but if he loves you more, go with him.
Life is messy. What if you do fall even more in love with someone else than with your current spouse, and what if they fall in love with you? What if they also are married to another? Then should your respective vows forever keep your two hearts apart, or should you abandon that which once was beautiful but which beauty now hath ruined? What mockery is made of love in either case!
Oh, that this tragedy could have been averted! If only there were a way to ensure that everyone be happily married and never be tormented by temptation! If only Mathematics had something to tell us...
There is another mathematical problem, of similar name though quite distinct, called the "Stable Marriage Problem". Consider an equal number of men and women to be married to one another. Is it possible for everyone to marry, such that you could never find yourself in that lamentable hypothetical situation: preferring to be with someone else who would also prefer to be with you?
I'm Henry The Eighth
And every one was an 'enry...
Yes - it is possible.
Gale & Shapley devised a simple iterative algorithm for solving the problem: Each man should rank the women from best to worst according to his personal preferences, and each woman should rank the men according to hers. Then, each man should propose to the woman he prefers most. If a woman receives a proposal, she accepts it, and the couple are engaged. If a woman receives multiple proposals, she accepts the proposal from the man she prefers most. Then, each man who was rejected (because the woman he preferred most accepted another man's proposal) should propose to the next-most preferred woman on his list. As before, if a free woman receives a proposal, she accepts it, and if she receives multiple proposals, she accepts the one she prefers most. If an engaged woman receives a proposal from a man she prefers more than her current fiance, she dumps her current fiance and accepts the new proposal. Then, each man who was rejected or dumped proposes to the next-most preferred woman on his list... and so the process continues until every man (and therefore every woman) is engaged. At this point everyone marries their current fiance and the algorithm is complete.
This algorithm is guaranteed to finish (it won't keep iterating endlessly), and it is guaranteed to result in a "stable pairing" - an arrangement of marriages in which no two people prefer each other to their current spouses.
It is interesting to note how similar this model is, in principle, to the way our society has approached marriage in recent history.
Hungry Heart
Got a wife and kids in Baltimore, Jack, I went out for a ride and I never went back...
So if everyone followed these rules, would the world be a happier place? Not necessarily. Stability, in this sense, doesn't imply happiness: just because your marriage is "stable" doesn't mean that you wouldn't rather be with someone else - it just means that that person wouldn't rather be with you.
The mathematical "happiness" score of your marriage is determined by how high your spouse sits on your own personal preference ranking of all partners. The overall happiness of a given arrangement of marriages can be defined as the average happiness scores of all people. Note that husband and wife can have different happiness scores!
For any large enough group of men and women there will be multiple alternative arrangements of marriages that are all "stable", in the sense that no two people prefer each other to their current spouses. Some arrangements will be "happier" than others.
Gale & Shapley's model produces just one of many possible stable arrangements. In fact, there's a very interesting mathematical property of Gale & Shapley's model: It will always produce the arrangement that, whilst still being stable, is happiest for the men (who propose)... and unhappiest for the women.
Reflect for a moment, if you will, upon the parallels between this model and conservative real-life society: I wonder if it is coincidence that this model predicts unhappy marriages for women, and that our real-life notions about marriage are changing as women become more empowered?
All This Useless Beauty
What shall we do, what shall we do?
Remember that every man and woman ranks each potential partner from best to worst. These personal preferences are necessary for establishing that an arrangement is "stable" (we need some way of knowing whether any two people prefer each other to their current spouses), and is used to calculate the happiness of an arrangement of marriages. So far, and very politically correctly, we've assumed that the preferences are arbitrary, random - that beauty is in the eye of the beholder. But what if each person has an intrinsic "beauty" (or personality or intelligence; call it what you will, mathematically it's equivalent) that influences their standing in other people's preferences?
Caldarelli & Capocci showed that the more that "beauty" is allowed to influence the preferences, the more miserable everyone is in general. That's because the more homogenised our notion of beauty is, the more similar everyone's "personal" preferences become. The more similar everyone's preferences are, the less likely it is for you to marry high on your list, because the people high on your list are also high on the lists of rivals more attractive than you are. It's fine if you're beautiful, but rough for everyone else.
Surprisingly though, according to Caldarelli & Capocci's model, the more that beauty influences preferences, the happier that women are, on average, relative to men. The arrangements found by this model are still happiest for men and unhappiest for women, but the difference is less. And depending on how much weight is placed on beauty (not too little, not too much), a majority of women can end up much happier than if beauty plays no role.
I wonder, then, if emphasising beauty is a strategy for women as a group to maximise their happiness within a traditionally male-dominated society - making the best of an unfair situation?
So Far Away
You're so far away from me, so far I just can't see.
"Spatial homogamy" is the idea that people tend to marry people from their own area. "Propinquity" is the idea that the probability of forming a relationship is proportional to the square of the physical distance between people. Many studies have cemented these ideas in sociology: People tend to prefer partners who live close by. Someone commented on my previous article that the trick was to fall in love with someone within a certain distance. He was probably thinking about fuel prices and airfares, but how right he was - from a mathematical point of view!
If adding "beauty" to the model reduces overall happiness by homogenising people's preferences, then adding "distance" to the model does the opposite by mixing the preferences up again. Because everyone occupies a unique position in space, everyone's preferences are influenced in a unique way by the distances to other people.
In fact, I think it's probably even better than that. The distance relationship between two people is symmetrical, and therefore affects both of their preferences the same way - the person that you prefer because they live close by is more likely to prefer you as well, for the same reason. So the more emphasis placed on distance, the happier everyone should be. So - say hi to that cute guy or girl you see at the local market next time!
The Stable Marriage Problem is an incredibly rich area of research, bringing together combinatorial optimisation, game theory, economics, and even real sociological research. As far as I know it's not actually used to marry people off anywhere, but it is used for analogous problems like assigning students to schools and residents to hospitals.
There are a lot of other variants on the classical Gale-Shapley model that I haven't even touched - like models that take into account three-way matches (actually, even kinkier than it sounds if you were to apply it to dating...) and models that take into account "cheating" to get a better match for yourself.
There's even a variant, commonly called the Stable Roommate Problem, which matches pairs of people from within a single group, not across two groups like the Stable Marriage Problem. This might be a good model for gay marriage, but there's some bad news: there's no mathematical guarantee of stability in this single-group variant. But then, we've just seen that stability is no guarantee of happiness, so maybe that's not such a bad thing after all!
Saturday, 2 January 2010
The Marriage Problem
How do you know when it's time to get married? As a Maximiser (of which I shall write another time), this question troubles me. How do you know that the one you're with right now, of all the millions of people out there, is The One? How do you know that she isn't yet to come into your life? For that matter... how do you know that you haven't already said goodbye to her?
Don't Stop 'Til You Get Enough
Ooh!
Mathematically, if naively, the problem is simple to formulate. There are many mathematically equivalent versions - the most common is the "Secretary Problem". One version, called "Googol", presents it as a simple game. Imagine that in front of you is a stack of 100 unsorted pages, face down. On each page is written a number, any posible real number, within an unknown range. You can turn over a page from the top of the stack one at a time to see the number, and you can keep on turning as many pages as you like, but once you turn over a new page, you can't go back. Your goal is to stop when you think you've just turned over the highest number you think you'll ever get, and keep it - forfeiting all numbers yet to come and having already forfeited all numbers already seen.
What are your chances of selecting the highest number? Is it just pure luck, or is there a strategy? It turns out that there is a strategy to maximise the probability of selecting the highest number.
The basic idea is to "write off" some initial number of pages just to get an idea of the size of numbers that are in the stack, and use that knowledge to subsequently stop when you think you have the highest number.
Like in statistics, the trick is to obtain a large enough sample of the population to measure the natural variability, so that you can say with some degree of confidence that any given data point is, you might say, a significant other. The difficulty is that whereas in most statistics a larger sample set is better, in this problem a larger sample set increases the probability that the highest data point is in the sample set, and if it's in the sample set, you've already given it up.
So, what is the best strategy? It turns out to be in the form of a "stopping rule": turn over a certain number of pages, making a note of the highest number that you see, and then keep on turning over pages until you get a number higher than that previous best, and stick with this new best.
J. Gilbert and F. Mosteller of Harvard University proved that the optimal number of pages to turn over before stopping at the next new best is 37. This magic number is 100 (pages) divided by 2.72 (e, the base of the natural logarithm). This strategy works for any population size - just divide it by e and sample at least that many data points before stopping at the best so far.
When I'm Sixty-Four
Will you still need me, will you still feed me, when I'm sixty-four?
Now, let's apply this knowledge to the problem of getting married. What is the population size from which I can sample? Very roughly, let's say there are 6.4 billion people, 50% of which are women (3.2 billion), 50% of which are between 18 and 40 (1.6 billion), 25% of which are single and available, leaving 400 million. A demographer would be able to give you a more accurate figure, but what's a few hundred million amongst friends? Now, sadly, not every single one of those women is interested in dating me, but let's conservatively say that 1 in 40 will (because it makes a round number), resulting in a population size of 10 million. Going by Gilbert and Mosteller's 37% rule, then, I should date about 3.7 million women before thinking about getting married! If I 5-minute speed-date 24/7 for the next 35 years, then, and only then, I can think about settling down.
Love The One You're With
If you can't be with the one you love, love the one you're with.
Actually, it's a bit more complicated (no kidding!). In the classical version of this problem, the goal is to try to select the single highest number; the single best partner; The One. Anything less is failure. Aiming high is admirable, but risky: Gilbert and Mosteller's solution is optimal, but still results in only a 37% (1/e) chance of selecting the best partner. Not so great. But it gets worse: there's also a 37% chance of ending up with the last remaining option out of desperation (this would happen if my best partner was one of the first 37% of people that I passed over, meaning that I would never encounter anyone better and would search for the rest of my (dating) life in vain. So: a 37% chance of finding The One; a 37% chance of searching for my entire life only to end up with the last available option; and a 26% chance of something in between - not The One, but probably ok (guaranteed better than a random 37% sample of the population).
In light of those odds, maybe it's better not to optimise the probability of selecting the single best partner, and instead optimise the expected value of whoever is selected, even if they're not the best. In Googol the value would be the number on the page; in the marriage problem it might be the ranking of a partner's beauty, or intelligence, or some more sophisticated aggregate score (about which I shall also write later). The probability of selecting the single best partner will be lower, but the expected value of the partner who is selected will be higher.
J. N. Bearden of the University of Arizona showed that in this modified version of the Secretary Problem, called the Cardinal Payoff Variant, the optimal strategy is still a stopping rule, but the optimal sample size is the square root of the population size, not the population size divided by e. So now I only have to date 3162.27 people instead of 3.7 million - excellent! (sqrt(10,000,000) = 3162.27. I wonder how you date 0.27 of a person?)
This Year's Love
This year's love had better last...
So maybe applying the stopping rule to the literal population size is not feasible. Realistically, we're not constrained by the number of dates, we're constrained by time. Let's say that I want to get married before I'm 40 years old. I started dating when I was 19, so that gives me 20 years to date - 20 pages in my stack. The square root of 20 is 4.47. That means I should date for about four-and-a-half years before thinking about making a commitment. I'm 27 years old now... that's eight years into my dating window. I... I guess it's time to start looking for a wife!
Alright, let me concede that this is an extremely simplistic model of dating. It makes a bunch of assumptions that simply don't hold true in real life.
In real life, for example, I could go down on my knees - both for forgiveness and in proposal - and marry someone I've already dated.
In real life, direct sampling is not the only way of building up a predictive model of the (dating) world - we have anecdotes and movies and women's interest magazines; we share the models we've individually built up, with each other.
In real life... we fall in love and it just doesn't matter.
Don't Stop 'Til You Get Enough
Ooh!
Mathematically, if naively, the problem is simple to formulate. There are many mathematically equivalent versions - the most common is the "Secretary Problem". One version, called "Googol", presents it as a simple game. Imagine that in front of you is a stack of 100 unsorted pages, face down. On each page is written a number, any posible real number, within an unknown range. You can turn over a page from the top of the stack one at a time to see the number, and you can keep on turning as many pages as you like, but once you turn over a new page, you can't go back. Your goal is to stop when you think you've just turned over the highest number you think you'll ever get, and keep it - forfeiting all numbers yet to come and having already forfeited all numbers already seen.
What are your chances of selecting the highest number? Is it just pure luck, or is there a strategy? It turns out that there is a strategy to maximise the probability of selecting the highest number.
The basic idea is to "write off" some initial number of pages just to get an idea of the size of numbers that are in the stack, and use that knowledge to subsequently stop when you think you have the highest number.
Like in statistics, the trick is to obtain a large enough sample of the population to measure the natural variability, so that you can say with some degree of confidence that any given data point is, you might say, a significant other. The difficulty is that whereas in most statistics a larger sample set is better, in this problem a larger sample set increases the probability that the highest data point is in the sample set, and if it's in the sample set, you've already given it up.
So, what is the best strategy? It turns out to be in the form of a "stopping rule": turn over a certain number of pages, making a note of the highest number that you see, and then keep on turning over pages until you get a number higher than that previous best, and stick with this new best.
J. Gilbert and F. Mosteller of Harvard University proved that the optimal number of pages to turn over before stopping at the next new best is 37. This magic number is 100 (pages) divided by 2.72 (e, the base of the natural logarithm). This strategy works for any population size - just divide it by e and sample at least that many data points before stopping at the best so far.
When I'm Sixty-Four
Will you still need me, will you still feed me, when I'm sixty-four?
Now, let's apply this knowledge to the problem of getting married. What is the population size from which I can sample? Very roughly, let's say there are 6.4 billion people, 50% of which are women (3.2 billion), 50% of which are between 18 and 40 (1.6 billion), 25% of which are single and available, leaving 400 million. A demographer would be able to give you a more accurate figure, but what's a few hundred million amongst friends? Now, sadly, not every single one of those women is interested in dating me, but let's conservatively say that 1 in 40 will (because it makes a round number), resulting in a population size of 10 million. Going by Gilbert and Mosteller's 37% rule, then, I should date about 3.7 million women before thinking about getting married! If I 5-minute speed-date 24/7 for the next 35 years, then, and only then, I can think about settling down.
Love The One You're With
If you can't be with the one you love, love the one you're with.
Actually, it's a bit more complicated (no kidding!). In the classical version of this problem, the goal is to try to select the single highest number; the single best partner; The One. Anything less is failure. Aiming high is admirable, but risky: Gilbert and Mosteller's solution is optimal, but still results in only a 37% (1/e) chance of selecting the best partner. Not so great. But it gets worse: there's also a 37% chance of ending up with the last remaining option out of desperation (this would happen if my best partner was one of the first 37% of people that I passed over, meaning that I would never encounter anyone better and would search for the rest of my (dating) life in vain. So: a 37% chance of finding The One; a 37% chance of searching for my entire life only to end up with the last available option; and a 26% chance of something in between - not The One, but probably ok (guaranteed better than a random 37% sample of the population).
In light of those odds, maybe it's better not to optimise the probability of selecting the single best partner, and instead optimise the expected value of whoever is selected, even if they're not the best. In Googol the value would be the number on the page; in the marriage problem it might be the ranking of a partner's beauty, or intelligence, or some more sophisticated aggregate score (about which I shall also write later). The probability of selecting the single best partner will be lower, but the expected value of the partner who is selected will be higher.
J. N. Bearden of the University of Arizona showed that in this modified version of the Secretary Problem, called the Cardinal Payoff Variant, the optimal strategy is still a stopping rule, but the optimal sample size is the square root of the population size, not the population size divided by e. So now I only have to date 3162.27 people instead of 3.7 million - excellent! (sqrt(10,000,000) = 3162.27. I wonder how you date 0.27 of a person?)
This Year's Love
This year's love had better last...
So maybe applying the stopping rule to the literal population size is not feasible. Realistically, we're not constrained by the number of dates, we're constrained by time. Let's say that I want to get married before I'm 40 years old. I started dating when I was 19, so that gives me 20 years to date - 20 pages in my stack. The square root of 20 is 4.47. That means I should date for about four-and-a-half years before thinking about making a commitment. I'm 27 years old now... that's eight years into my dating window. I... I guess it's time to start looking for a wife!
Alright, let me concede that this is an extremely simplistic model of dating. It makes a bunch of assumptions that simply don't hold true in real life.
In real life, for example, I could go down on my knees - both for forgiveness and in proposal - and marry someone I've already dated.
In real life, direct sampling is not the only way of building up a predictive model of the (dating) world - we have anecdotes and movies and women's interest magazines; we share the models we've individually built up, with each other.
In real life... we fall in love and it just doesn't matter.
Friday, 1 January 2010
Unraveling Braid
I can't stop thinking about Braid; everything about it - gameplay design, art, sound - was executed nearly perfectly. And each of those aspects brought something new and interesting to the game. Nevertheless, being a game programmer, it's the code that I'm interested in here, and I can't help musing about how I would implement some of Braid's unique mechanics.
If you haven't played Braid yet but were kind of thinking about it, then stop reading this and go play it, right now! I don't want to deprive anyone of the smallest part of the wonder at exploring Braid's universe for the first time. If you haven't played Braid and don't intend to, then perhaps I can convince you to try it :)
Let me begin by making it clear that I don't know anything about the actual implementation of Braid; I haven't spoken to the developer and I haven't looked at the level editor. But how it's actually implemented is almost beside the point; this is a collection of more general thoughts inspired by Braid.
One of the first things to impress me about Braid was the consistency of its design. In essence, it's a platonic 2D platformer plus just 5 unusual mechanics:
1. The ability to rewind time for some objects in the world.
2. The idea of binding time to one of the dimensions of 2D space.
3. The idea of branching, but interacting, timelines.
4. The ability to distort time in one local region of 2D space.
5. The idea of making objects in some levels run backwards in time.
The ability to selectively rewind time (for some, but not all objects), and the ability to distort time (for some, but not all regions) provides ways for the player to affect the synchronisation of objects in the world to solve problems.
The idea of binding time to a spatial dimension in some levels, such that horizontal movement advances or rewinds time, ingeniously provides both an obstacle and a tool for overcoming other obstacles.
The idea of branching but interacting "shadow" timelines, such that the player can be in multiple places at once, provides a mind-bending tool for solving impossible puzzles.
The idea of running time backwards in some levels turns everything neatly on its head, makes the player gasp in delight when they realise some of the gameplay implications, and provides the most astoundingly clever ending to a game that I've ever had the pleasure to experience.
The player's immense satisfaction in each level comes from painstakingly learning how each new mechanic works, and then synthesising ideas to solve a problem. This game could only work by strictly adhering to the fundamental design mechanics. This is both impressive and requisite: it is impressive that the game never resorts to any special cases, but then, if it did, it would destroy the player's ability to derive satisfaction from their own cleverness.
And because the design never calls for any special cases, I imagine that the code must have been a joy to craft. That is what I am chiefly interested in here, for the observation that Braid adheres to a limited set of mechanics belies the subtle complexity of those mechanics, and therefore their implementation.
What follows is merely my guesswork.
1. Rewinding time.
At any point the player can rewind time by holding down a button, and release it at the point in time at which they wish to resume control and try again. That means what happened in the past needs to be buffered somehow.
Bad Idea Note: Simply buffering the player's inputs would not work, because although all games are deterministic, they are also convergent: given the complete state of the universe (including inputs), there will be exactly one proceeding state, but there may be multiple possible preceeding states (did the player get to their current position by running or falling?). This property of deterministic convergence is employed to mind-bending effect by mechanic #5.
A naive approach might be to simply record the position and state of each object at each frame. But besides being memory intensive, this would make interactions with other objects - which might be moving through time in a different direction or speed - awkward.
I think it would be better that the state of each object, including the player, be recorded at a slightly more abstract level - say, the start/endpoint and velocity of a jump. Each state would be coded to be able to play either forwards or backwards at a given speed, procedurally. This would allow objects to interact dynamically with others when slowed down or going backwards, and not be rigidly bound to what was recorded. This implementation would come in handy for mechanic #2, binding time to a spatial dimension, and #5, running some levels backwards in time.
The abstracted-procedural-state approach would allow every object in the game to have its own individual "timeline". For most objects their timelines would coincidentally match up - they would progress forwards and be rewound backwards synchronously - until their timeline is affected by another mechanic...
2. Binding time to a spatial dimension.
Using the above implementation, this would be fairly simple - control all affected objects' timelines based on the player's current velocity.
Bad Idea Note: It might be more intuitive to think of this mechanic as the player's horizontal position scrubbing backwards and forwards through time, like the progress bar on a media player. And it might therefore be natural to think of using the player's position, not velocity, to control object states. Unlike a prerecorded movie in a media player, however, the objects will not be in the same state on every occasion a given time is revisited. It's impossible to jump to a given time, you have to advance frame-by-frame, state-by-state, procedurally, so that all the interactions can play out dynamically.
That means using the abstracted-procedural-state approach with individual object timelines controlled by player velocity, even if all of the individual timelines happen to be controlled synchronously.
3. Branching but interacting timelines.
This idea, although the most mind-bending for the player to come to grips with, would actually be one of the easiest to implement. Assuming that we record what happened in the past using the abstracted-procedural-state approach, the implementation of this mechanic would be simple.
Each object has a "shadow" object, which is actually an entirely independent object. Shadow objects only interact with other shadow objects and purple objects, which bind together both their shadow and real selves. When time is rewound and control is resumed, most objects and their shadows resume what they were doing, following the same rules. Because it's a deterministic world, the objects and shadows stay in sync, unless something disrupts them by interacting with one but not the other.
However, the player is not deterministic, and can choose to take different actions when control is resumed. The player's shadow repeats whatever the player just rewound.
The player's shadow would be controlled by the recorded states: while rewinding time, instead of discarding the states that we rewind past, they would be kept to use as a control buffer for the shadow. When the recorded states run out, the shadow just slumps, uncontrolled.
4. Distorting time in localised regions of space.
This idea is nice and simple for both the player and the programmer. If each object has an individual timeline, then the speed of that timeline could be set to be proportional to the distance of the object from the distortion.
5. Run time backwards.
This idea is the most fascinating to play, and possibly the most difficult to implement, of them all - due to the deterministic-but-convergent property of games.
First, let's get the easy stuff out of the way. Using the abstracted-procedural-state approach, we would already have coded all the interactions for objects moving backwards through time - for example, a monster going from dead to alive when the player jumps on its head, rather than the other way around. So the basic interactions with objects are already taken care of.
Bad Idea Note: You might initially think that simply running time backwards at a fixed speed for all objects would be easy, given that we already have solutions for selective rewinding, variable timeline speeds, etc. The important difference is that in those cases, the past is known and it's just a matter of replaying it somehow - time can only be rewound backwards for as long as the player has been playing, to the start of the level. In this case, however, time runs backwards from the beginning of the level, and we haven't had a chance to record where each object was. Or will be. Or something. Arrgh!
From the player's perspective, this mechanic is amazing because, when time runs forwards, we can intuitively reconstruct where an object is likely to have come from by observing its current state in the environment. When time runs backwards, that reconstruction becomes a prediction. In a deterministic universe running forwards, given perfect knowledge, we can make perfect predictions - we know exactly where the monster will go. But in a convergent universe running backwards, even with perfect knowledge, we can't make perfect predictions - we can't know whether the monster will stay on the ground or "fall up" to a higher platform. It's amazing when, as the player, you realise that an object's "past" can be affected by actions in the "future", like blocking off a route which makes it impossible for a monster to have "come" from that route. It's like the weird world of quantum mechanics, in which a particle's past is determined by observations made in the future.
The difficulty is that deterministic-but-convergent property. All of the other mechanics could be implemented in a philosophically plausible manner, but I can't see any good way to do this mechanic except by "cheating".
In the other mechanics, the behaviour/AI of an object running backwards along its individual timeline is trivial - just reconstruct it from the recorded abstracted state information. In this mechanic though, we need some actual decision-making logic while running backwards. Take the example of a monster walking backwards along the ground, just about to go underneath a higher platform. Should it continue walking backwards along the ground, or should it "fall up" to the higher platform. What happened in its "past"?
Bad Idea Note: You might think of taking further inspiration from quantum mechanics and assigning a probability to each past, which is fine from a design point of view, but would be practically impossible from an algorithmic point of view. You would need to identify all the places at which the convergence tree can branch (perhaps this could be marked up in data). Then you would need an algorithm for traversing the convergence tree and pruning off the branches that come from impossible starting conditions. Then you would randomly select between the remaining branches. The problem would be identifying the impossible starting conditions - how far back do you branch before determining that the object is stuck in a loop with no start, and how do you account for the interactions with every possible branch of every other object? Combinatorial explosion!
The more sensible approach might be to have a deterministic "default" behaviour like "always walk", and to "cheat" by having the designer specify when the object should deviate from that default behaviour - for example, trigger a "fall up here" marker when the player blocks the ground route (meaning that the monster could not possibly have taken the ground route).
There are few levels that use this mechanic, and the places where there is ambiguity are even fewer, so this scripted approach would probably be manageable.
From a gameplay perspective this approach might also be desirable - having a deterministic default behaviour for each object results in predictability which is probably reassuring to the player, even though, philosophically, the player has no reason to expect the behaviour to be predictable.
So, that's all the main mechanics seemingly neatly implemented. I'm very impressed by how you would be able to get such varied gameplay from relatively simple, but far from obvious, rules.
Damn, I wish I'd made this game...
If you haven't played Braid yet but were kind of thinking about it, then stop reading this and go play it, right now! I don't want to deprive anyone of the smallest part of the wonder at exploring Braid's universe for the first time. If you haven't played Braid and don't intend to, then perhaps I can convince you to try it :)
Let me begin by making it clear that I don't know anything about the actual implementation of Braid; I haven't spoken to the developer and I haven't looked at the level editor. But how it's actually implemented is almost beside the point; this is a collection of more general thoughts inspired by Braid.
One of the first things to impress me about Braid was the consistency of its design. In essence, it's a platonic 2D platformer plus just 5 unusual mechanics:
1. The ability to rewind time for some objects in the world.
2. The idea of binding time to one of the dimensions of 2D space.
3. The idea of branching, but interacting, timelines.
4. The ability to distort time in one local region of 2D space.
5. The idea of making objects in some levels run backwards in time.
The ability to selectively rewind time (for some, but not all objects), and the ability to distort time (for some, but not all regions) provides ways for the player to affect the synchronisation of objects in the world to solve problems.
The idea of binding time to a spatial dimension in some levels, such that horizontal movement advances or rewinds time, ingeniously provides both an obstacle and a tool for overcoming other obstacles.
The idea of branching but interacting "shadow" timelines, such that the player can be in multiple places at once, provides a mind-bending tool for solving impossible puzzles.
The idea of running time backwards in some levels turns everything neatly on its head, makes the player gasp in delight when they realise some of the gameplay implications, and provides the most astoundingly clever ending to a game that I've ever had the pleasure to experience.
The player's immense satisfaction in each level comes from painstakingly learning how each new mechanic works, and then synthesising ideas to solve a problem. This game could only work by strictly adhering to the fundamental design mechanics. This is both impressive and requisite: it is impressive that the game never resorts to any special cases, but then, if it did, it would destroy the player's ability to derive satisfaction from their own cleverness.
And because the design never calls for any special cases, I imagine that the code must have been a joy to craft. That is what I am chiefly interested in here, for the observation that Braid adheres to a limited set of mechanics belies the subtle complexity of those mechanics, and therefore their implementation.
What follows is merely my guesswork.
1. Rewinding time.
At any point the player can rewind time by holding down a button, and release it at the point in time at which they wish to resume control and try again. That means what happened in the past needs to be buffered somehow.
Bad Idea Note: Simply buffering the player's inputs would not work, because although all games are deterministic, they are also convergent: given the complete state of the universe (including inputs), there will be exactly one proceeding state, but there may be multiple possible preceeding states (did the player get to their current position by running or falling?). This property of deterministic convergence is employed to mind-bending effect by mechanic #5.
A naive approach might be to simply record the position and state of each object at each frame. But besides being memory intensive, this would make interactions with other objects - which might be moving through time in a different direction or speed - awkward.
I think it would be better that the state of each object, including the player, be recorded at a slightly more abstract level - say, the start/endpoint and velocity of a jump. Each state would be coded to be able to play either forwards or backwards at a given speed, procedurally. This would allow objects to interact dynamically with others when slowed down or going backwards, and not be rigidly bound to what was recorded. This implementation would come in handy for mechanic #2, binding time to a spatial dimension, and #5, running some levels backwards in time.
The abstracted-procedural-state approach would allow every object in the game to have its own individual "timeline". For most objects their timelines would coincidentally match up - they would progress forwards and be rewound backwards synchronously - until their timeline is affected by another mechanic...
2. Binding time to a spatial dimension.
Using the above implementation, this would be fairly simple - control all affected objects' timelines based on the player's current velocity.
Bad Idea Note: It might be more intuitive to think of this mechanic as the player's horizontal position scrubbing backwards and forwards through time, like the progress bar on a media player. And it might therefore be natural to think of using the player's position, not velocity, to control object states. Unlike a prerecorded movie in a media player, however, the objects will not be in the same state on every occasion a given time is revisited. It's impossible to jump to a given time, you have to advance frame-by-frame, state-by-state, procedurally, so that all the interactions can play out dynamically.
That means using the abstracted-procedural-state approach with individual object timelines controlled by player velocity, even if all of the individual timelines happen to be controlled synchronously.
3. Branching but interacting timelines.
This idea, although the most mind-bending for the player to come to grips with, would actually be one of the easiest to implement. Assuming that we record what happened in the past using the abstracted-procedural-state approach, the implementation of this mechanic would be simple.
Each object has a "shadow" object, which is actually an entirely independent object. Shadow objects only interact with other shadow objects and purple objects, which bind together both their shadow and real selves. When time is rewound and control is resumed, most objects and their shadows resume what they were doing, following the same rules. Because it's a deterministic world, the objects and shadows stay in sync, unless something disrupts them by interacting with one but not the other.
However, the player is not deterministic, and can choose to take different actions when control is resumed. The player's shadow repeats whatever the player just rewound.
The player's shadow would be controlled by the recorded states: while rewinding time, instead of discarding the states that we rewind past, they would be kept to use as a control buffer for the shadow. When the recorded states run out, the shadow just slumps, uncontrolled.
4. Distorting time in localised regions of space.
This idea is nice and simple for both the player and the programmer. If each object has an individual timeline, then the speed of that timeline could be set to be proportional to the distance of the object from the distortion.
5. Run time backwards.
This idea is the most fascinating to play, and possibly the most difficult to implement, of them all - due to the deterministic-but-convergent property of games.
First, let's get the easy stuff out of the way. Using the abstracted-procedural-state approach, we would already have coded all the interactions for objects moving backwards through time - for example, a monster going from dead to alive when the player jumps on its head, rather than the other way around. So the basic interactions with objects are already taken care of.
Bad Idea Note: You might initially think that simply running time backwards at a fixed speed for all objects would be easy, given that we already have solutions for selective rewinding, variable timeline speeds, etc. The important difference is that in those cases, the past is known and it's just a matter of replaying it somehow - time can only be rewound backwards for as long as the player has been playing, to the start of the level. In this case, however, time runs backwards from the beginning of the level, and we haven't had a chance to record where each object was. Or will be. Or something. Arrgh!
From the player's perspective, this mechanic is amazing because, when time runs forwards, we can intuitively reconstruct where an object is likely to have come from by observing its current state in the environment. When time runs backwards, that reconstruction becomes a prediction. In a deterministic universe running forwards, given perfect knowledge, we can make perfect predictions - we know exactly where the monster will go. But in a convergent universe running backwards, even with perfect knowledge, we can't make perfect predictions - we can't know whether the monster will stay on the ground or "fall up" to a higher platform. It's amazing when, as the player, you realise that an object's "past" can be affected by actions in the "future", like blocking off a route which makes it impossible for a monster to have "come" from that route. It's like the weird world of quantum mechanics, in which a particle's past is determined by observations made in the future.
The difficulty is that deterministic-but-convergent property. All of the other mechanics could be implemented in a philosophically plausible manner, but I can't see any good way to do this mechanic except by "cheating".
In the other mechanics, the behaviour/AI of an object running backwards along its individual timeline is trivial - just reconstruct it from the recorded abstracted state information. In this mechanic though, we need some actual decision-making logic while running backwards. Take the example of a monster walking backwards along the ground, just about to go underneath a higher platform. Should it continue walking backwards along the ground, or should it "fall up" to the higher platform. What happened in its "past"?
Bad Idea Note: You might think of taking further inspiration from quantum mechanics and assigning a probability to each past, which is fine from a design point of view, but would be practically impossible from an algorithmic point of view. You would need to identify all the places at which the convergence tree can branch (perhaps this could be marked up in data). Then you would need an algorithm for traversing the convergence tree and pruning off the branches that come from impossible starting conditions. Then you would randomly select between the remaining branches. The problem would be identifying the impossible starting conditions - how far back do you branch before determining that the object is stuck in a loop with no start, and how do you account for the interactions with every possible branch of every other object? Combinatorial explosion!
The more sensible approach might be to have a deterministic "default" behaviour like "always walk", and to "cheat" by having the designer specify when the object should deviate from that default behaviour - for example, trigger a "fall up here" marker when the player blocks the ground route (meaning that the monster could not possibly have taken the ground route).
There are few levels that use this mechanic, and the places where there is ambiguity are even fewer, so this scripted approach would probably be manageable.
From a gameplay perspective this approach might also be desirable - having a deterministic default behaviour for each object results in predictability which is probably reassuring to the player, even though, philosophically, the player has no reason to expect the behaviour to be predictable.
So, that's all the main mechanics seemingly neatly implemented. I'm very impressed by how you would be able to get such varied gameplay from relatively simple, but far from obvious, rules.
Damn, I wish I'd made this game...
Subscribe to:
Posts (Atom)
Posts
