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.
Saturday, 2 January 2010
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
