YouTube channel, College Humor, has a game show series called 'Um, Actually' - a game of nerdy corrections, and general nerd trivia.
One of the 'shiny questions' involves putting things is order, for example, putting space ships or fictional creatures in order by size.
The way the scoring works (as far as I can tell) is you get one point for each item you put in the right 'position'. So if you guess (1,3,2,4), then you would get 2 points for getting 1 and 4 in the correct position.
The problem was, in the creatures game, there was this one creature which looked like a single-celled organism, but was actually the size of a galaxy (or something), making it the largest.
So suppose you get everything else in the right order, but you fell for the trap and put this surprisingly massive organism as smallest e.g. (2,3,4,1)
In that case, everything is in the wrong position, so no points. But I would argue since all but one are in the right order you should only lose one point.
The FineBros channel does a similar game - e.g. put the top 10 most liked videos of 2019 in order. Under their scoring system, you get 2 points if an entry is in the right position, and 1 point if it's off by one. So (1,3,2,4) would be worth 6 points and (2,3,4,1) would be worth 3 points
This is slightly better, but you still have a case where you can lose significant points for getting just one or two entries out of place. For example, if you had (3,4,5,6,7,1,2), then you would get 0 points, even tho 5 of 7 are in the right order.
So, can we come up with a better scoring system?
Levenshtein Distance
The first things that comes to mind is Levenshtein or 'minimum edit' distance.
This measures the distance between two strings (words) based on the minimum number of edits to get from one to the other. In this context, an edit is a single character addition (cats -> chats), deletion (cats -> cat), or substitution (cats -> bats)
Now, this doesn't seem quite relevant to our problem; we're not adding, deleting, or substituting, we're swapping. For Levenshtein, a swap would be considered a deletion + an addition (or 2 substitutions) e.g. cats -> cas -> cast
We could calculate the Levenshtein distance and just divide it by 2 - effectively treat delete+add (2 edits) as equivalent to a swap (1 edit). Or else, we can just take the general principle of finding the minimum number of swaps required to get from the guess solution to the correct order.
As for the actual score, we can take the number of entries in the list (N) minus the minimum number of swaps.
So for our original examples, (1,3,2,4) is worth 3, and (2,3,4,1) is also worth 3.
In the latter case, 1 wasn't 'swapped' with an actual element, but you could think of it as a swap with an implied 'null' element - (..,null,1,2,3,4,null,..) -> (..,null,null,2,3,4,1,null,...)
Dynamic Programming
Dynamic programming is an approach to solving a certain class of problem which would take a ridiculous amount of time to solve by brute force. With dynamic programming, these problems can be solved in a more reasonable amount of time by breaking them down and solving recursively.
One of the classic problem in dynamic programming is - find the longest increasing sub-sequence in a list of numbers?
For example, in (2,3,1,7,4,9,5,8) the longest increasing sub-sequence would be (2,3,4,5,8). So in this case, we might say the score is 5/8
Going back to our other examples, (1,3,2,4) would have sub-sequence (1,2,4) or (1,3,4), worth 3 in either case. And (2,3,4,1) would be (2,3,4) which is also worth 3
Weighted Error
This is all well and good, but doesn't it feel like (2,3,4,1) is 'more wrong' than (1,3,2,4). Each has one element out of order, but in the former that one element if further from where it's 'supposed' to be.
One correction might be to calculate the error as sum[abs(x-x')] where x is the position of an element, and x' is where it's supposed to be. So (1,3,2,4) would be (abs(1-1) + abs(3-2) + abs(2-3) + abs(4-4)) = 2
However, this is flawed. For the (2,3,4,1) example, the error comes out at 6. Once again, we're being penalised for all the elements that are in the right order but off-by-one
So a slight modification would be to only calculate the error for those elements which are out of place - that is, find the longest sub-sequence, and then calculate the error for all elements which don't belong to that sub-sequence.
For (1,3,2,4) the error would be 1 and for (2,3,4,1) it would be 3
But how do we get from the error to the actual score?
We can start by calculating the maximum error, then subtracting the calculated error from it. So what's the maximum error?
The most wrong you can be would be to get everything in the wrong order - i.e. all elements reversed. So if we have N elements, the error would be
abs(1 - N) + abs(2 - N-1) + ... + abs(N -1) = (N - 1) + (N - 3) + ... + (N - 1) = 4 * (N - 2)
Actually, there's a subtle flaw in this reasoning - even if all the elements are reversed, there is technically a longest sub-sequence of 1, so one of the entries shouldn't count towards the maximum error. The element we chose as the 1 correct one will affect the maximum error. If we chose the first element in the sequence, the max error is reduced by N-1, whereas if we chose one from the middle the max error is reduced by 1 or 0 (depending if there is an odd or even number of elements)
For simplicity, we'll just assume the middle entry and say max error adjustment is 0
So going back once more to our original examples, (1,3,2,4) has a score of 8 - 1 = 7, and (2,3,4,1) has a score of 8 - 3 = 5, making the latter 'more wrong' as desired.
Conclusion
I'm not sure if there was a point to all this. I don't think this is useful outside of scoring this particular kind of game.
It might be interesting to run an neural net or genetic algorithm or similar using this as the score function. I'd be interested to see how a neural net performed at sorting, in terms of performance and correctness.
But anyway,
Chris.
Showing posts with label games. Show all posts
Showing posts with label games. Show all posts
Monday, December 30, 2019
Sunday, June 28, 2015
The Pirate Game
A few months ago, my friend was telling me about this mobile game he wanted to make. He, and some of our other friends, are teachers, and this is a game they play with their students. The students apparently love it. And if there were an app version, they'd be willing to pay 59p for it. Or so they say.
Now, as he was explaining the game to me, I thought maybe he was building towards asking for my help. I felt almost betrayed that he didn't. Several years ago, I'd built a website for this friend that he'd had nothing but praise and gratitude for.
A month or so later, I got a text message - "How are you at programming?" For whatever reason, the guy they had originally 'hired' wasn't doing it anymore.
"I'm capable", I replied. I'd done a course in Java at university. Admittedly, that was 'Java for Mathematicians'. And it was also almost 8 years ago. But how hard could it be to pick up again? Just like coding a bicycle. Or something like that...
The Game
As the title of the blog suggests, its called 'The Pirate Game'. In the classroom it's played on paper.
Basically, you have a 7x7 grid filled with items - mostly coins, but also some items that let you do other things. There are attacks that let you, for example, rob or kill other players. There's a shield and a mirror that let you defend against attacks. There's a bank item that let's you save whatever points you have from being stolen, etc. There's a bomb that blows you up (sets your points to zero). And so on.
At the start of the game, the players arrange the items in their grids to their liking. The teacher (game) then calls out random squares, and the players get whatever is in that square on their own grid. In the classroom, if a player gets an attack item, they have to raise their hand and tell the teacher who they want to use it on. The winner is whoever has the most points when all the squares have been called.
Making Games 1: The Right Tools
In a previous blog, I asserted that making mobile games was difficult. In fact, it turns out to not be so bad with the right framework. In this case I used the popular LibGdx. What's particularly nice about it is that there are a lot of how-to guides, and there's plenty of help for when things go wrong.
As they say, programming is 1% inspiration, 99% Googling.
For anyone interested in making their own Android game, I found these guides particularly helpful,
LibGdx Zombie Bird Tutorial
LibGdx Game Development Essentials
Set up Google Services with LibGdx
HAL9000
I got a first working version of the game done in the space of about a month - this was just the basic game mechanics, a bare-bones interface, and a single computer opponent that I could play against to check that the mechanics were doing what they were supposed to.
In those first few tests of the game, I found that the computer player kept beating me - at one point, 7 to 1. This seemed strange - neither I nor the computer could choose who we attacked, or which defences we used. So really, there wasn't anything either of us could do to influence the outcome of the game. The winner should have been totally random.
So loosing 7 times out of 8 seemed significant to me. As far as I could tell, the mechanics were working correctly. The only theory I could come up with was that maybe there was some advantage in the order in which we took our turns.
To try and figure out what was going on, I created a simulation. Basically, I re-wrote a very stripped down version of the player and game mechanics in Python. I then had two computer players play against each other in 10,000 matches. The results from this were - Player 1: 5005, Player 2: 4995.
In other words, the winner was just random chance. And turn order didn't matter.
If nothing else, this was a lesson in not drawing conclusions from such a small data set - it's not really statistically significant if there are only 8 data points (that's a standard error of ~3). After playing more games, the wins did end up averaging out.
Making Games 2: Coordinating Players
Development progressed. I got the full game mechanics working, and added more computer players (Clu and Ultron). I was now able to choose who I wanted to attack and what defences I wanted to use.
But the ultimate goal for the game is to let users play against their (human) friends. This meant I had to do a massive re-write to generalise the interaction mechanics.
Okay, lets look at an example of an interaction. Say I want to swap points with another player. First, my device needs to pop-up a player select dialog. Once I pick a target, the game needs to inform that player that I'm trying to swap points with them. If that player has a shield, their device needs to pop-up a dialog asking if they want to use it. The game then needs to inform me of my target's response - and if the target doesn't defend them self, we need to tell each other what our respective points are so that we can complete the swap.
That's a lot of back and forth to handle. Here are the rough diagrams I drew when I was trying to get the mechanics straight in my head.
So the way the interaction works in the code is, the attacker sends their target a data object telling them who the attacker is, what attack they're trying to use, and what points they have (though the points aren't visible to the target). Once the target has chosen their defence, they complete their side of the attack processing - so in the swap example, if the target doesn't defend, they set their points to those of the attacker.
The target then sends the attacker's original data, along with the defence they chose (if any) and their (pre-attack) points to all the other players. If the recipient is the original attacker, they complete their side of the attack. Then, all players are shown a notification telling them what happened.
All this coordination is done by a turn handler class. And what's nice is the computer players can also interact with each other, and with the local human player, via the turn handler.
All I need to do now is set up the stuff that actually sends the data between network players.
Game Theory
Through testing (looking for bugs and the like), I've played this game A LOT. And I've gotten a pretty good feel for how it works. It's actually quite fascinating when you really get into it. (Or maybe that's just Stockholm Syndrome talking).
Information is important to the game. Without it, players would be forced to make their moves at random. And when that happens, winning becomes mostly random chance. This is why players are shown notifications when other players interact - it allows them to strategise.
The most basic strategies are things like - rob people who have lots of points, don't try to rob people who have just been killed (they don't have any points to take), defend yourself when you have a lot of points (if you can). Really, this is just being sensible.
Then there are more subtle strategies. For example, sometimes it's better to lose a lot of points to the bomb or to being killed (removing those points from the game) rather than letting another player take them. Because, you don't need a lot of points to win, you just need more than everyone else.
Given the inherent randomness of the game, a lot of how you play will come down to how risk-averse you are. For example, a particularly risky strategy might be to let an opponent rob you (saving your defences), in the hopes that you can steal back your points, and more, later on.
When you play against humans (rather than AI), a whole bunch of social factors can come into play too. From what I hear, in the classroom, students tend to disproportionately target any members of staff that are playing. Though I can't imagine why.
One other interesting feature of the game is that it sometimes forces players to make disadvantageous moves. There's the bomb item that will take away your points when it inevitably comes up. And if you're in first place, the swap item forces you to give your points, and the lead, to another player.
So yeah, the game's not as simple as it might seem on the face of it.
Artificial Intelligence
In the first fully featured version of the game, the computer players made their decisions completely randomly. And that was fine - the game is perfectly playable with random opponents, it's not too easy, and the randoms can and will beat you on occasion. Sometimes by an embarrassing margin.
But random players also do things that don't make sense. So I wanted to create some computer players that used basic strategies to play more intelligently.
For interactions, these intelligent computer players (AI) use literal hit lists and avoid lists. As mentioned above, when two players interact, that information is sent to all other players. For humans, this information is displayed as a notification. For the AI, the information is processed to build/modify the hit and avoid lists.
For example, if Player 1 steals a lot of points from Player 2, then Player 1 is added to the hit list and Player 2 is added to the avoid list. If another player then kills Player 1, Player 1 is removed from the hit list and added to the avoid list. And so on.
If the AI then gets an attack square, they'll first check their hit list for a target. If the hit list is empty, they'll chose a random opponent who isn't on the avoid list. And so on.
There are also various basic heuristics for choosing which defences to use (and when), and for choosing a square when they get 'Choose Next'.
As they are, the AI are quite formidable, and at times frustratingly so. In general, I think it's better to have a mix of random and intelligent computer players. The AI offer a challenge, while the chaotic influence of the random players keeps things interesting.
Measuring Difficulty
In the game's current form, you can play against 2-7 computer players, and these players can be either random or 'intelligent' (as above). That means 33 unique opponent set-ups. Which raises the question - how can we rate the difficulty of any given set-up.
Obviously it's harder to win when there are more opponents. Specifically, the probability of a random player winning in a game of N random players is 1/N. Think of it like this - if all the players behave in the same way, they are indistinguishable. And if they're indistinguishable, they must all have the same probability of winning (turn order doesn't matter).
The same logic applies to intelligent computer players (AI) - since they all follow the same set of rules, they must also be indistinguishable from each other. Therefore, the odds of an AI winning in a game of N AI players must also be 1/N .
But what happens when there's a mix? How much harder are AI to beat than randoms?
To answer that, we can run some more simulations. This time, instead of re-writing code in Python, I created a modified version of the turn handler (see above) within the game project itself. Essentially I just removed all code that related to human players, and added a few bits to track statistics.
I set up the 33 different player configurations, ran 10,000 matches for each, and worked out the probability of winning for an AI player - for simplicity, we're assuming that a human player (playing strategically) is roughly equivalent to an AI.
From those simulations I made this lovely surface plot (using matplotlib).
And what we find is AI are roughly twice as hard to beat as randoms - notice the surface is higher on the right hand side (when there are fewer AI).
In other words, your odds of winning in a match against two AI is roughly equal to your odds of winning in a match against four randoms. For simplicity, we're going to assume that the relationship is exactly two to one.
We can now calculate an approximation of the odds of winning as
\[ p(R, I) = \frac{2}{R + 2(I+1)} \]
And if we compare these probabilities to those from the simulations, we find that they are within standard error (order 0.01 for 10,000 trials).
To get a difficulty rating, we can just turn the probability on it's head, and normalise by the probability for the easiest set-up (2 random opponents). That is,
\[ D = \frac{p_0}{p} = \frac{R + 2(I+1)}{4} \]
This gives us a difficulty rating between 1 and 4, which lets us easily divide the difficulty into three levels - easy, medium, and hard. Though, if your odds of winning in the easiest possible game is only 50:50, can it really be considered 'easy'?
Another nice property of this difficulty rating system is that the difficulty ratios match the probability ratios - that is, your odds of winning a 2 are half your odds of winning a 1, and so on. Specifically, your odds of winning are roughly \( \frac{1}{2D} \)
Incidentally, if we assume our human player instead makes their moves completely at random, then their odds of winning are lower overall - \( p = \frac{1}{R+1+2I} \) - but the difficulty stratification works out the same.
Conclusion
Ordinarily, I'd include my code for this sort of thing. But in this case, doing so might undermine my (and my friends') income. And they very kindly told me that I'd get the majority of the profits. Whatever those may ultimately be.
So far we've made a whopping 7p (!) just from having adMob set up in the test builds.
But before we can make any (real) money, we have to actually finish the game. The single player version is mostly done, and should be released in the near future. The last big thing to do is the UI (which is someone else'sproblem job).
Then the hard part is going to be setting up multi-player with Google Play Services. In particular, because there aren't any good guides (that I can find) for setting up Google multi-player with LibGdx.
When it is done, I'll post links and such here for anyone that might be interested.
[edit] - If you want to try the current beta, you can get it here.
Also, given that making an Android game has turned out to be much easier than I expected, I may in fact make the previously discussed relativity game myself (once the Pirate Game is finished). In that case, I might also provide my code.
Oatzy.
[I'd love to make an AI that uses machine learning to counter human players' personal strategies.]
Now, as he was explaining the game to me, I thought maybe he was building towards asking for my help. I felt almost betrayed that he didn't. Several years ago, I'd built a website for this friend that he'd had nothing but praise and gratitude for.
A month or so later, I got a text message - "How are you at programming?" For whatever reason, the guy they had originally 'hired' wasn't doing it anymore.
"I'm capable", I replied. I'd done a course in Java at university. Admittedly, that was 'Java for Mathematicians'. And it was also almost 8 years ago. But how hard could it be to pick up again? Just like coding a bicycle. Or something like that...
The Game
As the title of the blog suggests, its called 'The Pirate Game'. In the classroom it's played on paper.
Basically, you have a 7x7 grid filled with items - mostly coins, but also some items that let you do other things. There are attacks that let you, for example, rob or kill other players. There's a shield and a mirror that let you defend against attacks. There's a bank item that let's you save whatever points you have from being stolen, etc. There's a bomb that blows you up (sets your points to zero). And so on.
 |
| This is the prototyping design. The final product will look less utilitarian. |
At the start of the game, the players arrange the items in their grids to their liking. The teacher (game) then calls out random squares, and the players get whatever is in that square on their own grid. In the classroom, if a player gets an attack item, they have to raise their hand and tell the teacher who they want to use it on. The winner is whoever has the most points when all the squares have been called.
Making Games 1: The Right Tools
In a previous blog, I asserted that making mobile games was difficult. In fact, it turns out to not be so bad with the right framework. In this case I used the popular LibGdx. What's particularly nice about it is that there are a lot of how-to guides, and there's plenty of help for when things go wrong.
As they say, programming is 1% inspiration, 99% Googling.
For anyone interested in making their own Android game, I found these guides particularly helpful,
LibGdx Zombie Bird Tutorial
LibGdx Game Development Essentials
Set up Google Services with LibGdx
HAL9000
I got a first working version of the game done in the space of about a month - this was just the basic game mechanics, a bare-bones interface, and a single computer opponent that I could play against to check that the mechanics were doing what they were supposed to.
In those first few tests of the game, I found that the computer player kept beating me - at one point, 7 to 1. This seemed strange - neither I nor the computer could choose who we attacked, or which defences we used. So really, there wasn't anything either of us could do to influence the outcome of the game. The winner should have been totally random.
So loosing 7 times out of 8 seemed significant to me. As far as I could tell, the mechanics were working correctly. The only theory I could come up with was that maybe there was some advantage in the order in which we took our turns.
To try and figure out what was going on, I created a simulation. Basically, I re-wrote a very stripped down version of the player and game mechanics in Python. I then had two computer players play against each other in 10,000 matches. The results from this were - Player 1: 5005, Player 2: 4995.
In other words, the winner was just random chance. And turn order didn't matter.
If nothing else, this was a lesson in not drawing conclusions from such a small data set - it's not really statistically significant if there are only 8 data points (that's a standard error of ~3). After playing more games, the wins did end up averaging out.
Making Games 2: Coordinating Players
Development progressed. I got the full game mechanics working, and added more computer players (Clu and Ultron). I was now able to choose who I wanted to attack and what defences I wanted to use.
But the ultimate goal for the game is to let users play against their (human) friends. This meant I had to do a massive re-write to generalise the interaction mechanics.
Okay, lets look at an example of an interaction. Say I want to swap points with another player. First, my device needs to pop-up a player select dialog. Once I pick a target, the game needs to inform that player that I'm trying to swap points with them. If that player has a shield, their device needs to pop-up a dialog asking if they want to use it. The game then needs to inform me of my target's response - and if the target doesn't defend them self, we need to tell each other what our respective points are so that we can complete the swap.
That's a lot of back and forth to handle. Here are the rough diagrams I drew when I was trying to get the mechanics straight in my head.
 |
| I doubt this helps clarifies things for anyone else. |
So the way the interaction works in the code is, the attacker sends their target a data object telling them who the attacker is, what attack they're trying to use, and what points they have (though the points aren't visible to the target). Once the target has chosen their defence, they complete their side of the attack processing - so in the swap example, if the target doesn't defend, they set their points to those of the attacker.
The target then sends the attacker's original data, along with the defence they chose (if any) and their (pre-attack) points to all the other players. If the recipient is the original attacker, they complete their side of the attack. Then, all players are shown a notification telling them what happened.
 |
| I figured I should give the computer players more piratical names. |
All this coordination is done by a turn handler class. And what's nice is the computer players can also interact with each other, and with the local human player, via the turn handler.
All I need to do now is set up the stuff that actually sends the data between network players.
Game Theory
Through testing (looking for bugs and the like), I've played this game A LOT. And I've gotten a pretty good feel for how it works. It's actually quite fascinating when you really get into it. (Or maybe that's just Stockholm Syndrome talking).
Information is important to the game. Without it, players would be forced to make their moves at random. And when that happens, winning becomes mostly random chance. This is why players are shown notifications when other players interact - it allows them to strategise.
The most basic strategies are things like - rob people who have lots of points, don't try to rob people who have just been killed (they don't have any points to take), defend yourself when you have a lot of points (if you can). Really, this is just being sensible.
Then there are more subtle strategies. For example, sometimes it's better to lose a lot of points to the bomb or to being killed (removing those points from the game) rather than letting another player take them. Because, you don't need a lot of points to win, you just need more than everyone else.
Given the inherent randomness of the game, a lot of how you play will come down to how risk-averse you are. For example, a particularly risky strategy might be to let an opponent rob you (saving your defences), in the hopes that you can steal back your points, and more, later on.
When you play against humans (rather than AI), a whole bunch of social factors can come into play too. From what I hear, in the classroom, students tend to disproportionately target any members of staff that are playing. Though I can't imagine why.
One other interesting feature of the game is that it sometimes forces players to make disadvantageous moves. There's the bomb item that will take away your points when it inevitably comes up. And if you're in first place, the swap item forces you to give your points, and the lead, to another player.
So yeah, the game's not as simple as it might seem on the face of it.
Artificial Intelligence
In the first fully featured version of the game, the computer players made their decisions completely randomly. And that was fine - the game is perfectly playable with random opponents, it's not too easy, and the randoms can and will beat you on occasion. Sometimes by an embarrassing margin.
But random players also do things that don't make sense. So I wanted to create some computer players that used basic strategies to play more intelligently.
For interactions, these intelligent computer players (AI) use literal hit lists and avoid lists. As mentioned above, when two players interact, that information is sent to all other players. For humans, this information is displayed as a notification. For the AI, the information is processed to build/modify the hit and avoid lists.
For example, if Player 1 steals a lot of points from Player 2, then Player 1 is added to the hit list and Player 2 is added to the avoid list. If another player then kills Player 1, Player 1 is removed from the hit list and added to the avoid list. And so on.
If the AI then gets an attack square, they'll first check their hit list for a target. If the hit list is empty, they'll chose a random opponent who isn't on the avoid list. And so on.
There are also various basic heuristics for choosing which defences to use (and when), and for choosing a square when they get 'Choose Next'.
As they are, the AI are quite formidable, and at times frustratingly so. In general, I think it's better to have a mix of random and intelligent computer players. The AI offer a challenge, while the chaotic influence of the random players keeps things interesting.
Measuring Difficulty
In the game's current form, you can play against 2-7 computer players, and these players can be either random or 'intelligent' (as above). That means 33 unique opponent set-ups. Which raises the question - how can we rate the difficulty of any given set-up.
Obviously it's harder to win when there are more opponents. Specifically, the probability of a random player winning in a game of N random players is 1/N. Think of it like this - if all the players behave in the same way, they are indistinguishable. And if they're indistinguishable, they must all have the same probability of winning (turn order doesn't matter).
The same logic applies to intelligent computer players (AI) - since they all follow the same set of rules, they must also be indistinguishable from each other. Therefore, the odds of an AI winning in a game of N AI players must also be 1/N .
But what happens when there's a mix? How much harder are AI to beat than randoms?
To answer that, we can run some more simulations. This time, instead of re-writing code in Python, I created a modified version of the turn handler (see above) within the game project itself. Essentially I just removed all code that related to human players, and added a few bits to track statistics.
I set up the 33 different player configurations, ran 10,000 matches for each, and worked out the probability of winning for an AI player - for simplicity, we're assuming that a human player (playing strategically) is roughly equivalent to an AI.
From those simulations I made this lovely surface plot (using matplotlib).
 |
| Configurations with more than 7 opponents have been set to zero. |
And what we find is AI are roughly twice as hard to beat as randoms - notice the surface is higher on the right hand side (when there are fewer AI).
In other words, your odds of winning in a match against two AI is roughly equal to your odds of winning in a match against four randoms. For simplicity, we're going to assume that the relationship is exactly two to one.
We can now calculate an approximation of the odds of winning as
\[ p(R, I) = \frac{2}{R + 2(I+1)} \]
And if we compare these probabilities to those from the simulations, we find that they are within standard error (order 0.01 for 10,000 trials).
To get a difficulty rating, we can just turn the probability on it's head, and normalise by the probability for the easiest set-up (2 random opponents). That is,
\[ D = \frac{p_0}{p} = \frac{R + 2(I+1)}{4} \]
This gives us a difficulty rating between 1 and 4, which lets us easily divide the difficulty into three levels - easy, medium, and hard. Though, if your odds of winning in the easiest possible game is only 50:50, can it really be considered 'easy'?
Another nice property of this difficulty rating system is that the difficulty ratios match the probability ratios - that is, your odds of winning a 2 are half your odds of winning a 1, and so on. Specifically, your odds of winning are roughly \( \frac{1}{2D} \)
Incidentally, if we assume our human player instead makes their moves completely at random, then their odds of winning are lower overall - \( p = \frac{1}{R+1+2I} \) - but the difficulty stratification works out the same.
Conclusion
Ordinarily, I'd include my code for this sort of thing. But in this case, doing so might undermine my (and my friends') income. And they very kindly told me that I'd get the majority of the profits. Whatever those may ultimately be.
So far we've made a whopping 7p (!) just from having adMob set up in the test builds.
But before we can make any (real) money, we have to actually finish the game. The single player version is mostly done, and should be released in the near future. The last big thing to do is the UI (which is someone else's
Then the hard part is going to be setting up multi-player with Google Play Services. In particular, because there aren't any good guides (that I can find) for setting up Google multi-player with LibGdx.
When it is done, I'll post links and such here for anyone that might be interested.
[edit] - If you want to try the current beta, you can get it here.
Also, given that making an Android game has turned out to be much easier than I expected, I may in fact make the previously discussed relativity game myself (once the Pirate Game is finished). In that case, I might also provide my code.
Oatzy.
[I'd love to make an AI that uses machine learning to counter human players' personal strategies.]
Monday, February 23, 2015
Designing a General Relativity Based Casual Game
Let's suppose, for the sake of arguing, that I'm unemployed. It'd pretty great if there were a way I could make a quick buck (or a quick quid, in my case). Obviously, the solution is to make a super addictive mobile game. Then I can just sit back and watch the cash come pouring in.
Okay, so that's a pretty terrible plan - making a mobile app of any kind is no trivial thing, and there's no guarantee of making any significant amount of money (or any money at all). Still, I thought about it, and wondered - if I were to make a game, what would I do. This is one of the ideas I came up with.
Game Concept
A common type of casual game is the physics-based game - that is, a game where objects obey a form of classical Newtonian mechanics: your Angry Birds, your Flappy Birds, your games that don't involve birds. So, for example, when you catapult an angry bird, it follows a parabolic path like a real bird would (drag not-withstanding).
And that's all fine, but I wondered if you could make a game based on non-classical physics - quantum mechanics, relativity, that sort of thing.
Now, I don't want to call this 'Interstellar: The Game' (not least because of copyright). That is, however, a good short hand for the idea behind the game.
The idea is this: you've been off exploring space, and now it's time to go home. So the main objective is to get back to Earth as quickly as possible, whilst dodging obstacles like planets, stars, black holes. But these massive objects have a gravitational pull, which can make maneuvering a little trickier, especially if you get too close to a black hole.
On the other hand, you can use massive objects to get a speed boost, by doing for example a powered flyby. But being close to massive objects for too long (black holes in particular) will cause time dilation, which might make you late home.
Game Construction
The way I imagine the game is as a 'side-scroller', where you move right to left (assuming the phone/tablet is held in landscape). I figure it would be a top-down view, moving in the x-direction with the spaceship - i.e. the sprite would be fixed in the x-direction, with freedom of movement up and down. All the obstacles would then move towards the sprite in the negative x-direction.
Here's what a (non-relativistic) binary orbit looks like from a frame of reference moving in the x-direction with the particle (blue).
In the code, this is done by calculating the particle velocity as normal, but instead of adding the velocity in the x-direction to the particle, you subtract it from all the obstacles.
For the sprite's up-down movement, you could either constrain the player to within the screen, or else if they drift off the edge of the screen, it would be a 'lost in space' game over.
Level construction can either be done by hand, or levels can be generated randomly / procedurally by adding massive objects of varying type/size/mass etc. at various points along the game map. I'd say go for random/procedural, since that makes creating levels easier, and would mean there are effectively unlimited levels. Though it might be worth storing generated levels for replayability.
For the representation of black holes, you could show an accretion disc (like they did in Interstellar), have a background star field that's gravitationally lensed, or show a dotted line for where the event horizon is. Alternatively, you could do nightmare mode - give no visual indication of a black hole, and let the player infer its presence from its gravitational pull.
I tend to think that controls should be kept simple, and should be appropriate to the medium - in other words, no on-screen d-pads on touchscreens (if you can help it). Instead, I'd say use four directional swipes for a speed boost in whichever direction. In terms of code, this would be done by adding some constant to the velocity in the direction of the swipe.
One thing to remember is that in space there is no drag - nothing to slow you down (gravity notwithstanding). Steering like this can be surprisingly tricky. If you accelerate left, you will keep moving leftwards until you accelerate right to counter balance.
On the other hand, no drag means the player could keep accelerating forward until they're going arbitrarily fast. To stop this, you could put a limit on how many times the player can accelerate - for example, say that there's a limited amount of fuel. This also means the player would have to use their fuel wisely - baring in mind that breaking counts as accelerating. This makes tricks like gravitational assists even more important.
Anyway, having an idea is all well and good, but really an idea isn't worth much if you can't prove that it's viable. So...
Game Mechanics
Preamble
I studied theoretical physics at university, and that included a module on General Relativity. But that module only covered the basics. As the lecturer pointed out, General relativity is a graduate level topic.
I read a bunch of articles for this blog, and have tried to get as scientifically accurate as possible - or at least I've tried to avoid making massive errors. But even so, there are numerous assumptions, approximations, and inaccuracies in this formulation. So just bear that in mind - I don't necessarily know what I'm talking about. Do feel free to offer corrections.
Prototyping - For coding the prototype/simulations I used Python with PyGame.
In PyGame, coordinates are defined with the origin (0,0) in the top right corner. This isn't a problem mathematically, it just means the graphical layout is 'upside-down'.
To make the videos in this post, I added the line
Terminology - I'm going to refer to moving objects as 'particles', 'planets', or as a 'spaceship' in the context of the game. I'll refer to static, gravitating objects as 'obstacles', '(massive) bodies', or 'stars'. In images and videos, planets are blue, and stars are yellow.
Units - I chose to use 'pixels' as the unit of length, and 'frames' as the unit of time. In this case, velocity is measured in 'pixels per frame' (px/fr).
This is useful, because it means the velocity of our particle is updated as \(v(t) = v(t-1)+a(t)\) and the position is updated as \(x(t) = x(t-1)+v(t)\). For my simulation, I used a frame rate of 50fps.
Physical Constants - We could use geometrised units, where the Gravitational Constant (G) and the Speed of Light (c) are both set equal to one. In that case we wouldn't need to include them in the maths/code. However, my inner-mathematician likes generality, so I'm going to keep them around.
The constant 'G' only ever appears alongside obstacle masses (as GM), so we can set it to one and say that it's value is absorbed into the (otherwise arbitrary) mass values. It's worth keeping G around though, so we can easily tweak the strength of gravity, if need be.
The speed of light controls the strength of relativistic effects - larger c, weaker relativity. In my code I set the speed of light to c = 12 px/fr. This seems to make things behave in a way that looks 'right'.
Object Properties - We could try to go for a certain level of realism - try, for example, to work out a conversion between real world distances and pixels, try to get everything to scale. But that's too much faffing. Besides, if everything were to scale, a 1px Earth would orbit at a distance of 23000px around a 100px sun.
For obstacle masses, I set M = 500 (arbitrary units). The particle mass isn't really important since it can be cancelled out in all the equations. From a theoretical perspective, all that matters is that it's much smaller than the obstacle masses. I set both the obstacles and particle radii to 12.5 pixels (25x25px sprites). Object radii aren't important outside of collision handling.
Newtonian Gravity
For particle acceleration, we start with Classical Newtonian gravity.
\[ a = \frac{G M}{r^{2}} \]
where G is the gravitational constant, M is the mass of the gravitating body (the obstacle) and r is the distance between the centres of our particle and the obstacle. We're assuming that the particle is moving in a 2D plane, so we have \(r = \sqrt{dx^{2} + dy^{2}}\), where \(dx = x_p - x_{ob}\) and \(dy = y_p - y_{ob}\) are the x and y distances between the particle and obstacle.
This gives us the magnitude of the acceleration, pointing from the centre of the particle to the centre of the obstacle. For our purposes, we need to resolve this acceleration into x and y components.
The components are given by
\[ \ddot{x} = -\frac{G M}{r^{2}} \cos(\theta) \equiv -\frac{G M}{r^{3}} dx\\ \\
\ddot{y} = -\frac{G M}{r^2} \sin(\theta) \equiv -\frac{G M}{r^{3}} dy\]
Where \(\theta = \arctan\left(\frac{dy}{dx}\right) \) is the angle between the x-axis and the position/acceleration vector. The double dots mean 'second derivative with respect to time', i.e. acceleration.
If there are multiple gravitating objects, we have to calculate the contributions from each, and add them all together to get the total acceleration.
\[ \ddot{x} = -\sum_i \frac{G M_{i}}{r_{i}^{3}} dx_{i} \\ \\
\ddot{y} = -\sum_i \frac{G M_{i}}{r_{i}^{3}} dy_{i} \]
As mentioned above, once we have the acceleration we add that to the velocity, then add the velocity to the position to work out where the particle moves to. Below is an example of a Newtonian orbit using the above.
General Relativity
Since we want the game to include General Relativistic effects like time dilation, we also have to take into account the other effects of relativity - in particular, how it modifies particle motion/acceleration.
For simplicity, we're going to assume our obstacles (planets, stars, black holes) are uncharged, and non-rotating. In that case, we use the Schwarzchild metric, which describes the gravitational field in the vicinity of an (uncharged, non-rotating) massive object.
\[ c^2 d\tau^2 = \left(1 - \frac{r_s}{r}\right) c^2 dt^2 - \frac{dr^2}{\left(1- \frac{r_s}{r}\right)} - r^2 d\theta^2 \]
We're assuming the particle is moving in the 2D plane around the equator of the massive object. \(r_s\) is the object's Schwarzchild radius (also known as the 'event horizon' in the context of black holes), defined as
\[ r_s = \frac{2GM}{c^2} \]
Without going into too much detail, we can derive from the Schwarzchild metric the particle's acceleration in Cartesian-like coordinates as
\[ \ddot{x} = - \frac{G M}{r^3} dx - \frac{3 G M L^2}{c^2 r^5} dx \\ \\
\ddot{y} = - \frac{G M}{r^3} dy - \frac{3 G M L^2}{c^2 r^5} dy \]
Where the first term is the classical Newtonian gravitation, as seen above.
The second term is purely relativistic, and will usually only have a significant effect when a particle is sufficiently close to a massive body's Schwarzchild radius.
The main effect of this term is to increase gravitational acceleration in the vicinity of the massive object, and to cause close orbits to precess, as can be seen below
Notice that the point at which the particle is closest to the 'star' (the perihelion) moves over time. This doesn't happen in the classical limit of Newtonian gravity. In fact, explaining the anomalous precession of Mercury was one of the first pieces of evidence supporting the theory of General relativity.
In the acceleration equation, L is the angular momentum (per unit mass) of our particle, and c is the speed of light. Angular momentum (per unit mass) is calculated as
\[ L = \left|r\right| \left|v\right| \sin(\phi) \equiv (dx\ v_y - dy\ v_x) \]
where \(\phi\) is the angle between the radial vector (r) and the velocity vector (v)
The angle can be calculated as
\[ \phi = \alpha - \theta = \arctan\left(\frac{v_y}{v_x}\right) - \arctan\left(\frac{dy}{dx}\right) \]
where \(\alpha\) is the angle between the velocity vector and the x-axis, and \(\theta\) is the angle between the position vector and the x-axis.
In the two body case, angular momentum is a constant of motion, so only needs to be calculated once - say, once the particle's initial position and velocity has been set.
Caveat - Strictly speaking, the radial length 'r' in the Schwarzchild metric is not the same as the Euclidian distance \(\sqrt{dx^2 + dy^2}\). At least, not when relativistic effects are significant. Rather, r is defined as the circumference of a sphere surrounding the massive body, divided by \(2\pi\). Defining r this way means the length of an interval dr isn't affected by the curving of spacetime near the massive body.
By comparison, an observer falling towards a black hole would see lengths stretching longer and longer the closer they got to the black hole event horizon - an observer at a distance r would measure the interval dr to have a length of \( \left( 1 - \frac{r_s}{r} \right)^{-\frac{1}{2}} dr \).
All this to say, the particle distances displayed in the game (and the simulation videos) are distances in Schwarzchild coordinates, projected onto a Euclidean plane, not distances as viewed by an observer such as our particle/spaceship.
Relativity for Multiple Bodies
This is where things get dicey. In the General relativistic limit, combining the fields of multiple massive objects is not so straightforward.
The lazy way of doing this is to just vector sum the relativistic accelerations, like we did for the Newtonian case. This is problematic, though, because it assumes the particle's angular momentum around each massive body is constant. This is not true.
Instead, we can make a simplification - we can sum the Newtonian terms as before, but we'll only consider the relativistic term when we're sufficiently close to any given body. This cut-off is going to be fairly arbitrary. Ideally, we want the 'radius of influence' to be as big as possible, but small enough that the particle can never be within the relativistic limits of more than one body at a time. The main problem here is that the way the game is set up means all the massive bodies are unrealistically close together, so it's hard to make the radius of influence big enough to be ideal. In my code, I chose the cut-off to be \(10 r_s \simeq 70px\).
Now, the angular momentum around this close body is still not constant (although, arguably, it may be sufficient to assume it is). The forces from other local bodies can cause torque, which will change the particle's angular momentum.
Torque is calculated as
\[ \Gamma = \left|r\right| \left|F\right| \sin(\gamma)\ \equiv r_x\ F_y - r_y\ F_x\]
where \(\gamma = \theta_1 - \theta_0 = \arctan(\frac{dy_1}{dx_1}) - \arctan(\frac{dy_0}{dx_0}) \) is the angle between the position vector (r) and the force vector (F), and \(\theta_0\) and \(\theta_1\) are the angles between r and the x-axis, and F and the x-axis, respectively.
For the force from a gravitating body, the torque can be written out as
\[\Gamma = \frac{G M_1 }{r_1^3} \left(dy_0\ dx_1 - dx_0\ dy_1\right) \]
We only need to take into account Newtonain gravitation in calculating torque, since we're already assuming the particle is outside the relativistic limit of these other bodies.
So once the particle enters a massive body's radius of influence, we calculate it's initial angular momentum, as above. Then, in each time step (for as long as the particle is in the radius of influence), we calculate the total torque from all local bodies, and add that torque to the particle's angular momentum (before calculating the new acceleration).
This is a big simplification. But it's good enough, and correct in the limiting case of a single/well isolated body. Especially if the radius of influence can be made sufficiently big.
While we're on torque - if our spaceship accelerates (fires its thrusters) while it is close to a massive body, we will need to take into account any torque from that as well
\[ \Gamma = dx_0\ a_y - dy_0\ a_x \]
Where \(a_x\) and \(a_y\) are the x and y accelerations caused by the thrusters. This is ignoring the details of how a spaceship actually maneuvers. If you're interested, you'll have to look into that for yourself.
So putting it all together we have
\[ \ddot{x} = -\sum_i \frac{G M_i}{r_i^3} dx_i \ - \frac{3 G M_0 L_0^{2}}{c^2 r_0^{5}} dx_0\\ \\
\ddot{y} = -\sum_i \frac{G M_i}{r_i^3} dy_i \ - \frac{3 G M_0 L_0^{2}}{c^2 r_0^{5}} dy_0 \]
where \(M_0\) is the body whose radius of influence the particle is within (if any), and
\[L_0 = L_{0}(t-1) +\sum_{i\ne 0} \frac{G M_i}{r_i^3}(dx_i\ dy_0 - dx_0\ dy_i) + (dx_0\ a_y - dy_0\ a_x)\]
Time Dilation
For a single massive object, the time dilation can be derived from the Schwarzchild metric (see above). Dividing through by \(c^2 d\tau \) and rearranging we get
\[ \left(1- \frac{r_s}{r}\right)^2 \left(\frac{dt}{d\tau}\right)^2 = \left(1- \frac{r_s}{r}\right)\left(1 + \frac{r^2 \dot{\theta}^2}{c^2}\right) + \frac{\dot{r}^2}{c^2} \]
where the dots mean 'derivative with respect to \(\tau\)'. And since \( \dot{r}^2 + r^2 \dot{\theta}^2 \equiv v_x^2 + v_y^2 = v^2 \), we can re-write and rearrange further to get
\[ dt = \frac{d\tau}{\left(1- \frac{r_s}{r}\right)}\sqrt{1- \frac{r_s}{r}\left(1 + \frac{r^2 \dot{\theta}^2}{c^2}\right) + \frac{v^2}{c^2}} \]
where dt is the 'coordinate time' - time as measured by an observer at rest, far away from any gravitational fields. For the sake of the game we can say that this represents time as measured on Earth. In reality, the Earths gravitational field does cause it's own time dilation effect. \(d\tau\) is the 'proper time' - time as measured by a clock on our spaceship.
Notice, in the limit of a stationary particle, that is \(\dot{r}=r\dot{\theta}=0\), we get the purely gravitational time dilation
\[ dt = \frac{d\tau}{\sqrt{1 - \frac{r_s}{r}}} \]
Similarly, in the limit of \( r \gt\gt r_s\) (i.e. when our particle is far from any gravitating bodies), the time dilation equation reduces to the Special Relativistic case
\[ dt = d\tau \sqrt{1 + \frac{v^2}{c^2}} \]
Note - in this, the velocity v is the 'proper velocity' - velocity with respect to proper time. This is different from coordinate velocity - velocity with respect to coordinate time.
While a particle can't have a coordinate velocity greater than the speed of light 'c', because of time dilation it can have a proper velocity greater than 'c'. This doesn't, however, mean that a particle can travel faster than light, since light has a proper velocity of infinity. Coordinate velocity and proper velocity are related by
\[ v_c = v \left(\frac{d\tau}{dt}\right) \equiv \frac{v}{ \sqrt{1+\frac{v^2}{c^2}}}\]
where the equivalence is true in the Special relativistic limit. Notice that when proper velocity equals the speed of light (c), the coordinate velocity equals \(\frac{c}{\sqrt{2}}\) - less than the speed of light.
Time Dilation for Multiple Bodies
Here, we once again have the problem of combining the effects of multiple gravitating masses. Some would argue, at this point, that trying to be scientifically accurate is more trouble than it's worth. Still, I'm going to at least try.
To start, we can replace the Schwarzchild radius terms with the local (Newtonian) gravitational potentials as
\[ \frac{r_s}{r} = \frac{2GM}{c^2 r} \rightarrow \sum_i \frac{2 G M_i}{c^2 r_i} = \sum_i \frac{2U_i}{c^2} = \frac{2U}{c^2}\]
Where \(U_i\) are the individual gravitational potentials of the various local gravitating bodies.
For the term in \(r^2 \dot{\theta}^2\), we note that \(r^2 \dot{\theta}^2\ = \frac{L^2}{r^2} \), where L is angular momentum (per unit mass). So we can use the same trick we did for combining accelerations - that is, only take this term into account when the particle is within a body's radius of influence.
So putting it all together, we have
\[ dt = \frac{d\tau}{\left(1 - \frac{2U}{c^2}\right)}\sqrt{1 - \frac{2U}{c^2} - \frac{2U_0}{c^2}\frac{L_0^2}{r_0^2 c^2} + \frac{v^2}{c^2}} \]
With \(L_0\) defined as above. Alternatively, we could just omit the angular momentum term since it's of order \(c^{-4}\). In my simulation, it amounted to a ~0.17% decrease in the dilation ratio.
The typical dilation ratio in my simulation was \(\frac{dt}{d\tau} \approx 1.07\), which admittedly isn't significant.
In the movie Interstellar, a lot of the time dilation came from the fact that their black hole (Gargantua) was spinning very fast. If you want to do that, you'll have to work it out for yourself - for that you would use the Kerr metric. With rotating black holes, you'd also need to take into account other effects like frame dragging.
Of course, we've chosen arbitrary masses, an arbitrary speed of light, distances not to any sort of realistic scale. We can always tweak the specific time dilation to our liking. In particular, if the realistic dilation isn't dramatic enough, we could artificially inflate it. So long as we keep key behaviours, like dilation going to infinity when the particle reaches a black hole event horizon, etc.
Collision Handling
Collision handling is important for figuring out when the game is over - for figuring out if the player crashed into a planet, or fell into a black hole. Now, PyGame has in-build collision handling. But where's the fun in that.
The easiest way to check if two circular objects have collided is to check if the distance between their centres is less than the sum of their radii
In other words, we have the condition - a collision occurred if \( dx^2 + dy^2 \le (r_p + r_{ob})^2 \).
Easy. There is a special case though - because the particle moves in discrete steps from frame to frame, if the particle is moving fast enough, it could move from one side of an obstacle to the other without ever overlapping.
The basic collision handling would miss this. So this is a little trickier to catch. In the above diagram, I've traced the path going from the particle's position in the previous step to its current position.
We can say that the particle collided with the obstacle if there's a point on that path that's closer to the centre of the obstacle than \( R = r_p + r_{ob} \). In other words, if the particle had moved continuously along the path from \(x_0\) to \(x_1\), would there have been any point(s) where the particle and the obstacle overlapped.
To figure this out, first we find the equation for the line passing through the particles' two positions as
\[ y = m x + c = \left(\frac{v_y}{v_x}\right) x + \left(y_0 - \frac{v_y}{v_x} x_0 \right) \]
(in this case, m and c are gradient and constant, respectively, not mass and speed of light).
Second, we're going to define a function for the distance between a point on the particle's path and the obstacle's centre
\[ f(x) = (x_{ob} - x)^2 + (y_{ob} - y)^2 = (x_{ob} - x)^2 + (y_{ob} - m x - c)^2 \]
Now we're going to look for the point along the path of closest approach to the obstacle. To do that we look for x such that the separation f(x) is minimised. In other words \( \frac{d}{dx} f(x) = 0\)
If you work through the maths, you get
\[ x_{min} = \frac{x_{ob} + m y_{ob} - m c}{1 + m^2} \]
Which gives us the condition - a collision occurred if \(f(x_{min}) \le R^2\) and \(x_0 \le x_{min} \le x_1\) (assuming \(x_0 \le x_1\)).
Both these collision handlers can also be used to check if the particle crosses a black hole's event horizon - just replace \(r_{ob}\) with \(r_s\), the Schwarzchild radius.
Of course, in the game, the spaceship sprite wouldn't be circular. But, you know. You could create an 'imaginary' circle around the sprite, or give the sprite a radius of zero (so it collides when its centre overlaps the obstacle). Or you could just use a third party library. Either way.
Bonus: Elastic Recoil
For my own amusement, I had the particle elastically recoil off of the obstacles, as well as the sides of the screen, so that I could just watch it drifting and bouncing about endlessly. It's weirdly hypnotic.
For screen boundaries, you have, for example
In this case, we flip the particle velocity in the x-direction as \( v_{x}' = -v_{x} \), and move the particle's x position to \( x_{p}' = W - (x_{p} - W) = 2 W - x_p \), where W is the pixel width of the game window. You do the same sort of thing for the other 3 boundaries.
For recoil off obstacles, things are not so straight forward. The procedure works like this: First, check for a collision. Then, find the point along the particle's path where it first makes contact with the obstacle - that is where \(f(x) = R^2\).
Finding this point is just a matter of solving a quadratic equation to get
\[ \begin{align*}
x' &= \frac{x_{ob} + m y_{ob}-mc}{1 + m^2} \pm \frac{\sqrt{(x_{ob} + m y_{ob}-mc)^2 - (1+m^2)(x^2_{ob} + y^2_{ob}+c^2 - 2 c y_{ob} - R^2)}}{1 + m^2} \\ \\ &\equiv a \pm b
\end{align*} \]
If \(v_x \gt 0\) then x' = a - b, if \(v_x \lt 0\) then x' = a + b
So move the particle back to the point of first contact. Then we want to flip the particle velocity so that the angle of incidence \(\phi\) between the velocity vector (v) and the position vector (r) equals the angle of reflection
The new velocity is given by
\[v'_x = -\left|v\right| \cos(\beta) \\ \\ v'_y = -\left|v\right| \sin(\beta)\]
with \(|v| = \sqrt{v_{x}^{2} + v_{y}^{2}} \), and
\[ \beta = \alpha - 2 \phi = 2\arctan\left(\frac{-dy}{-dx}\right) - \arctan\left(\frac{v_y}{v_x}\right) \]
where \( \alpha \) is the angle between the x-axis and the old velocity vector (v), and \(\beta\) if the angle between the x-axis and the new velocity vector (v').
Note - in the code I used 'arctan2(y,x)' from the Numpy library, for which the signs of 'x' and 'y' are important. dy and dx are negative in the above because I have the position vector pointing from the particle to the obstacle (opposite to how it's defined).
Finally, we want to move the particle to where it should be from recoiling.
In other words, we want to move the particle to the point along it's new velocity vector, such that it's the same distance from the contact point as it would be if the particle hadn't collided. To do this, we can just resolve the distance \( r' = \sqrt{(x_1 - x')^2 + (y_1 - y')^2} \) in the direction of the new velocity vector, as
\[ x_1 ' = x' - r' \cos(\beta) \\ \\ y_1 ' = y' - r' \sin(\beta) \]
Admittedly, this doesn't work perfectly - sometimes it behaves a little screwy. Especially when the particle spirals in on an obstacle. Of course, none of this recoil stuff is necessary for the game, since you want collisions to end the game. Like I said, this was more for my own amusement.
Conclusion
If you were feeling really ambitious, you could do the game from the first-person perspective of someone on the spaceship - see for example 'Falling into a Black Hole', or the Interstellar papers.
There are almost certainly things wrong with this 'formulation' of General Relativity. But then, this is meant to be for a game, so it doesn't need to be 100% scientifically accurate. I did feel like I should make an effort, though. And I'm willing to call this good enough. If you're someone who knows what they're talking about, feel free to offer your thoughts/corrections.
Anyway, I've done my job as a theoretician - now it's up to someone else to actually make the game. If you do, please send me link to the completed game. And maybe give me a name-check? A little kickback would be nice too... ;)
You can have a look at my prototype/simulation code here.
Oatzy.
[Gravity, don't mean too much to me.]
Okay, so that's a pretty terrible plan - making a mobile app of any kind is no trivial thing, and there's no guarantee of making any significant amount of money (or any money at all). Still, I thought about it, and wondered - if I were to make a game, what would I do. This is one of the ideas I came up with.
Game Concept
A common type of casual game is the physics-based game - that is, a game where objects obey a form of classical Newtonian mechanics: your Angry Birds, your Flappy Birds, your games that don't involve birds. So, for example, when you catapult an angry bird, it follows a parabolic path like a real bird would (drag not-withstanding).
And that's all fine, but I wondered if you could make a game based on non-classical physics - quantum mechanics, relativity, that sort of thing.
Now, I don't want to call this 'Interstellar: The Game' (not least because of copyright). That is, however, a good short hand for the idea behind the game.
The idea is this: you've been off exploring space, and now it's time to go home. So the main objective is to get back to Earth as quickly as possible, whilst dodging obstacles like planets, stars, black holes. But these massive objects have a gravitational pull, which can make maneuvering a little trickier, especially if you get too close to a black hole.
On the other hand, you can use massive objects to get a speed boost, by doing for example a powered flyby. But being close to massive objects for too long (black holes in particular) will cause time dilation, which might make you late home.
Game Construction
The way I imagine the game is as a 'side-scroller', where you move right to left (assuming the phone/tablet is held in landscape). I figure it would be a top-down view, moving in the x-direction with the spaceship - i.e. the sprite would be fixed in the x-direction, with freedom of movement up and down. All the obstacles would then move towards the sprite in the negative x-direction.
Here's what a (non-relativistic) binary orbit looks like from a frame of reference moving in the x-direction with the particle (blue).
In the code, this is done by calculating the particle velocity as normal, but instead of adding the velocity in the x-direction to the particle, you subtract it from all the obstacles.
For the sprite's up-down movement, you could either constrain the player to within the screen, or else if they drift off the edge of the screen, it would be a 'lost in space' game over.
Level construction can either be done by hand, or levels can be generated randomly / procedurally by adding massive objects of varying type/size/mass etc. at various points along the game map. I'd say go for random/procedural, since that makes creating levels easier, and would mean there are effectively unlimited levels. Though it might be worth storing generated levels for replayability.
For the representation of black holes, you could show an accretion disc (like they did in Interstellar), have a background star field that's gravitationally lensed, or show a dotted line for where the event horizon is. Alternatively, you could do nightmare mode - give no visual indication of a black hole, and let the player infer its presence from its gravitational pull.
I tend to think that controls should be kept simple, and should be appropriate to the medium - in other words, no on-screen d-pads on touchscreens (if you can help it). Instead, I'd say use four directional swipes for a speed boost in whichever direction. In terms of code, this would be done by adding some constant to the velocity in the direction of the swipe.
One thing to remember is that in space there is no drag - nothing to slow you down (gravity notwithstanding). Steering like this can be surprisingly tricky. If you accelerate left, you will keep moving leftwards until you accelerate right to counter balance.
On the other hand, no drag means the player could keep accelerating forward until they're going arbitrarily fast. To stop this, you could put a limit on how many times the player can accelerate - for example, say that there's a limited amount of fuel. This also means the player would have to use their fuel wisely - baring in mind that breaking counts as accelerating. This makes tricks like gravitational assists even more important.
Anyway, having an idea is all well and good, but really an idea isn't worth much if you can't prove that it's viable. So...
Game Mechanics
Preamble
I studied theoretical physics at university, and that included a module on General Relativity. But that module only covered the basics. As the lecturer pointed out, General relativity is a graduate level topic.
I read a bunch of articles for this blog, and have tried to get as scientifically accurate as possible - or at least I've tried to avoid making massive errors. But even so, there are numerous assumptions, approximations, and inaccuracies in this formulation. So just bear that in mind - I don't necessarily know what I'm talking about. Do feel free to offer corrections.
Prototyping - For coding the prototype/simulations I used Python with PyGame.
In PyGame, coordinates are defined with the origin (0,0) in the top right corner. This isn't a problem mathematically, it just means the graphical layout is 'upside-down'.
To make the videos in this post, I added the line
pygame.image.save(screen, 'output/frame%05d.png' % framenum)to the code's main loop to save individual frames as a series of images (you'll need to iterate 'framenum'). I then used 'ImageJ' to convert those images to (avi) video.
Terminology - I'm going to refer to moving objects as 'particles', 'planets', or as a 'spaceship' in the context of the game. I'll refer to static, gravitating objects as 'obstacles', '(massive) bodies', or 'stars'. In images and videos, planets are blue, and stars are yellow.
Units - I chose to use 'pixels' as the unit of length, and 'frames' as the unit of time. In this case, velocity is measured in 'pixels per frame' (px/fr).
This is useful, because it means the velocity of our particle is updated as \(v(t) = v(t-1)+a(t)\) and the position is updated as \(x(t) = x(t-1)+v(t)\). For my simulation, I used a frame rate of 50fps.
Physical Constants - We could use geometrised units, where the Gravitational Constant (G) and the Speed of Light (c) are both set equal to one. In that case we wouldn't need to include them in the maths/code. However, my inner-mathematician likes generality, so I'm going to keep them around.
The constant 'G' only ever appears alongside obstacle masses (as GM), so we can set it to one and say that it's value is absorbed into the (otherwise arbitrary) mass values. It's worth keeping G around though, so we can easily tweak the strength of gravity, if need be.
The speed of light controls the strength of relativistic effects - larger c, weaker relativity. In my code I set the speed of light to c = 12 px/fr. This seems to make things behave in a way that looks 'right'.
Object Properties - We could try to go for a certain level of realism - try, for example, to work out a conversion between real world distances and pixels, try to get everything to scale. But that's too much faffing. Besides, if everything were to scale, a 1px Earth would orbit at a distance of 23000px around a 100px sun.
For obstacle masses, I set M = 500 (arbitrary units). The particle mass isn't really important since it can be cancelled out in all the equations. From a theoretical perspective, all that matters is that it's much smaller than the obstacle masses. I set both the obstacles and particle radii to 12.5 pixels (25x25px sprites). Object radii aren't important outside of collision handling.
Newtonian Gravity
For particle acceleration, we start with Classical Newtonian gravity.
\[ a = \frac{G M}{r^{2}} \]
where G is the gravitational constant, M is the mass of the gravitating body (the obstacle) and r is the distance between the centres of our particle and the obstacle. We're assuming that the particle is moving in a 2D plane, so we have \(r = \sqrt{dx^{2} + dy^{2}}\), where \(dx = x_p - x_{ob}\) and \(dy = y_p - y_{ob}\) are the x and y distances between the particle and obstacle.
The components are given by
\[ \ddot{x} = -\frac{G M}{r^{2}} \cos(\theta) \equiv -\frac{G M}{r^{3}} dx\\ \\
\ddot{y} = -\frac{G M}{r^2} \sin(\theta) \equiv -\frac{G M}{r^{3}} dy\]
Where \(\theta = \arctan\left(\frac{dy}{dx}\right) \) is the angle between the x-axis and the position/acceleration vector. The double dots mean 'second derivative with respect to time', i.e. acceleration.
If there are multiple gravitating objects, we have to calculate the contributions from each, and add them all together to get the total acceleration.
\[ \ddot{x} = -\sum_i \frac{G M_{i}}{r_{i}^{3}} dx_{i} \\ \\
\ddot{y} = -\sum_i \frac{G M_{i}}{r_{i}^{3}} dy_{i} \]
As mentioned above, once we have the acceleration we add that to the velocity, then add the velocity to the position to work out where the particle moves to. Below is an example of a Newtonian orbit using the above.
General Relativity
Since we want the game to include General Relativistic effects like time dilation, we also have to take into account the other effects of relativity - in particular, how it modifies particle motion/acceleration.
For simplicity, we're going to assume our obstacles (planets, stars, black holes) are uncharged, and non-rotating. In that case, we use the Schwarzchild metric, which describes the gravitational field in the vicinity of an (uncharged, non-rotating) massive object.
\[ c^2 d\tau^2 = \left(1 - \frac{r_s}{r}\right) c^2 dt^2 - \frac{dr^2}{\left(1- \frac{r_s}{r}\right)} - r^2 d\theta^2 \]
We're assuming the particle is moving in the 2D plane around the equator of the massive object. \(r_s\) is the object's Schwarzchild radius (also known as the 'event horizon' in the context of black holes), defined as
\[ r_s = \frac{2GM}{c^2} \]
Without going into too much detail, we can derive from the Schwarzchild metric the particle's acceleration in Cartesian-like coordinates as
\[ \ddot{x} = - \frac{G M}{r^3} dx - \frac{3 G M L^2}{c^2 r^5} dx \\ \\
\ddot{y} = - \frac{G M}{r^3} dy - \frac{3 G M L^2}{c^2 r^5} dy \]
Where the first term is the classical Newtonian gravitation, as seen above.
The second term is purely relativistic, and will usually only have a significant effect when a particle is sufficiently close to a massive body's Schwarzchild radius.
The main effect of this term is to increase gravitational acceleration in the vicinity of the massive object, and to cause close orbits to precess, as can be seen below
Notice that the point at which the particle is closest to the 'star' (the perihelion) moves over time. This doesn't happen in the classical limit of Newtonian gravity. In fact, explaining the anomalous precession of Mercury was one of the first pieces of evidence supporting the theory of General relativity.
In the acceleration equation, L is the angular momentum (per unit mass) of our particle, and c is the speed of light. Angular momentum (per unit mass) is calculated as
\[ L = \left|r\right| \left|v\right| \sin(\phi) \equiv (dx\ v_y - dy\ v_x) \]
where \(\phi\) is the angle between the radial vector (r) and the velocity vector (v)
The angle can be calculated as
\[ \phi = \alpha - \theta = \arctan\left(\frac{v_y}{v_x}\right) - \arctan\left(\frac{dy}{dx}\right) \]
where \(\alpha\) is the angle between the velocity vector and the x-axis, and \(\theta\) is the angle between the position vector and the x-axis.
In the two body case, angular momentum is a constant of motion, so only needs to be calculated once - say, once the particle's initial position and velocity has been set.
Caveat - Strictly speaking, the radial length 'r' in the Schwarzchild metric is not the same as the Euclidian distance \(\sqrt{dx^2 + dy^2}\). At least, not when relativistic effects are significant. Rather, r is defined as the circumference of a sphere surrounding the massive body, divided by \(2\pi\). Defining r this way means the length of an interval dr isn't affected by the curving of spacetime near the massive body.
By comparison, an observer falling towards a black hole would see lengths stretching longer and longer the closer they got to the black hole event horizon - an observer at a distance r would measure the interval dr to have a length of \( \left( 1 - \frac{r_s}{r} \right)^{-\frac{1}{2}} dr \).
All this to say, the particle distances displayed in the game (and the simulation videos) are distances in Schwarzchild coordinates, projected onto a Euclidean plane, not distances as viewed by an observer such as our particle/spaceship.
Relativity for Multiple Bodies
This is where things get dicey. In the General relativistic limit, combining the fields of multiple massive objects is not so straightforward.
The lazy way of doing this is to just vector sum the relativistic accelerations, like we did for the Newtonian case. This is problematic, though, because it assumes the particle's angular momentum around each massive body is constant. This is not true.
Instead, we can make a simplification - we can sum the Newtonian terms as before, but we'll only consider the relativistic term when we're sufficiently close to any given body. This cut-off is going to be fairly arbitrary. Ideally, we want the 'radius of influence' to be as big as possible, but small enough that the particle can never be within the relativistic limits of more than one body at a time. The main problem here is that the way the game is set up means all the massive bodies are unrealistically close together, so it's hard to make the radius of influence big enough to be ideal. In my code, I chose the cut-off to be \(10 r_s \simeq 70px\).
Now, the angular momentum around this close body is still not constant (although, arguably, it may be sufficient to assume it is). The forces from other local bodies can cause torque, which will change the particle's angular momentum.
\[ \Gamma = \left|r\right| \left|F\right| \sin(\gamma)\ \equiv r_x\ F_y - r_y\ F_x\]
where \(\gamma = \theta_1 - \theta_0 = \arctan(\frac{dy_1}{dx_1}) - \arctan(\frac{dy_0}{dx_0}) \) is the angle between the position vector (r) and the force vector (F), and \(\theta_0\) and \(\theta_1\) are the angles between r and the x-axis, and F and the x-axis, respectively.
For the force from a gravitating body, the torque can be written out as
\[\Gamma = \frac{G M_1 }{r_1^3} \left(dy_0\ dx_1 - dx_0\ dy_1\right) \]
We only need to take into account Newtonain gravitation in calculating torque, since we're already assuming the particle is outside the relativistic limit of these other bodies.
So once the particle enters a massive body's radius of influence, we calculate it's initial angular momentum, as above. Then, in each time step (for as long as the particle is in the radius of influence), we calculate the total torque from all local bodies, and add that torque to the particle's angular momentum (before calculating the new acceleration).
This is a big simplification. But it's good enough, and correct in the limiting case of a single/well isolated body. Especially if the radius of influence can be made sufficiently big.
While we're on torque - if our spaceship accelerates (fires its thrusters) while it is close to a massive body, we will need to take into account any torque from that as well
\[ \Gamma = dx_0\ a_y - dy_0\ a_x \]
Where \(a_x\) and \(a_y\) are the x and y accelerations caused by the thrusters. This is ignoring the details of how a spaceship actually maneuvers. If you're interested, you'll have to look into that for yourself.
So putting it all together we have
\[ \ddot{x} = -\sum_i \frac{G M_i}{r_i^3} dx_i \ - \frac{3 G M_0 L_0^{2}}{c^2 r_0^{5}} dx_0\\ \\
\ddot{y} = -\sum_i \frac{G M_i}{r_i^3} dy_i \ - \frac{3 G M_0 L_0^{2}}{c^2 r_0^{5}} dy_0 \]
where \(M_0\) is the body whose radius of influence the particle is within (if any), and
\[L_0 = L_{0}(t-1) +\sum_{i\ne 0} \frac{G M_i}{r_i^3}(dx_i\ dy_0 - dx_0\ dy_i) + (dx_0\ a_y - dy_0\ a_x)\]
Time Dilation
For a single massive object, the time dilation can be derived from the Schwarzchild metric (see above). Dividing through by \(c^2 d\tau \) and rearranging we get
\[ \left(1- \frac{r_s}{r}\right)^2 \left(\frac{dt}{d\tau}\right)^2 = \left(1- \frac{r_s}{r}\right)\left(1 + \frac{r^2 \dot{\theta}^2}{c^2}\right) + \frac{\dot{r}^2}{c^2} \]
where the dots mean 'derivative with respect to \(\tau\)'. And since \( \dot{r}^2 + r^2 \dot{\theta}^2 \equiv v_x^2 + v_y^2 = v^2 \), we can re-write and rearrange further to get
\[ dt = \frac{d\tau}{\left(1- \frac{r_s}{r}\right)}\sqrt{1- \frac{r_s}{r}\left(1 + \frac{r^2 \dot{\theta}^2}{c^2}\right) + \frac{v^2}{c^2}} \]
where dt is the 'coordinate time' - time as measured by an observer at rest, far away from any gravitational fields. For the sake of the game we can say that this represents time as measured on Earth. In reality, the Earths gravitational field does cause it's own time dilation effect. \(d\tau\) is the 'proper time' - time as measured by a clock on our spaceship.
Notice, in the limit of a stationary particle, that is \(\dot{r}=r\dot{\theta}=0\), we get the purely gravitational time dilation
\[ dt = \frac{d\tau}{\sqrt{1 - \frac{r_s}{r}}} \]
Similarly, in the limit of \( r \gt\gt r_s\) (i.e. when our particle is far from any gravitating bodies), the time dilation equation reduces to the Special Relativistic case
\[ dt = d\tau \sqrt{1 + \frac{v^2}{c^2}} \]
Note - in this, the velocity v is the 'proper velocity' - velocity with respect to proper time. This is different from coordinate velocity - velocity with respect to coordinate time.
While a particle can't have a coordinate velocity greater than the speed of light 'c', because of time dilation it can have a proper velocity greater than 'c'. This doesn't, however, mean that a particle can travel faster than light, since light has a proper velocity of infinity. Coordinate velocity and proper velocity are related by
\[ v_c = v \left(\frac{d\tau}{dt}\right) \equiv \frac{v}{ \sqrt{1+\frac{v^2}{c^2}}}\]
where the equivalence is true in the Special relativistic limit. Notice that when proper velocity equals the speed of light (c), the coordinate velocity equals \(\frac{c}{\sqrt{2}}\) - less than the speed of light.
Time Dilation for Multiple Bodies
Here, we once again have the problem of combining the effects of multiple gravitating masses. Some would argue, at this point, that trying to be scientifically accurate is more trouble than it's worth. Still, I'm going to at least try.
To start, we can replace the Schwarzchild radius terms with the local (Newtonian) gravitational potentials as
\[ \frac{r_s}{r} = \frac{2GM}{c^2 r} \rightarrow \sum_i \frac{2 G M_i}{c^2 r_i} = \sum_i \frac{2U_i}{c^2} = \frac{2U}{c^2}\]
Where \(U_i\) are the individual gravitational potentials of the various local gravitating bodies.
For the term in \(r^2 \dot{\theta}^2\), we note that \(r^2 \dot{\theta}^2\ = \frac{L^2}{r^2} \), where L is angular momentum (per unit mass). So we can use the same trick we did for combining accelerations - that is, only take this term into account when the particle is within a body's radius of influence.
So putting it all together, we have
\[ dt = \frac{d\tau}{\left(1 - \frac{2U}{c^2}\right)}\sqrt{1 - \frac{2U}{c^2} - \frac{2U_0}{c^2}\frac{L_0^2}{r_0^2 c^2} + \frac{v^2}{c^2}} \]
With \(L_0\) defined as above. Alternatively, we could just omit the angular momentum term since it's of order \(c^{-4}\). In my simulation, it amounted to a ~0.17% decrease in the dilation ratio.
The typical dilation ratio in my simulation was \(\frac{dt}{d\tau} \approx 1.07\), which admittedly isn't significant.
In the movie Interstellar, a lot of the time dilation came from the fact that their black hole (Gargantua) was spinning very fast. If you want to do that, you'll have to work it out for yourself - for that you would use the Kerr metric. With rotating black holes, you'd also need to take into account other effects like frame dragging.
Of course, we've chosen arbitrary masses, an arbitrary speed of light, distances not to any sort of realistic scale. We can always tweak the specific time dilation to our liking. In particular, if the realistic dilation isn't dramatic enough, we could artificially inflate it. So long as we keep key behaviours, like dilation going to infinity when the particle reaches a black hole event horizon, etc.
Collision Handling
Collision handling is important for figuring out when the game is over - for figuring out if the player crashed into a planet, or fell into a black hole. Now, PyGame has in-build collision handling. But where's the fun in that.
The easiest way to check if two circular objects have collided is to check if the distance between their centres is less than the sum of their radii
In other words, we have the condition - a collision occurred if \( dx^2 + dy^2 \le (r_p + r_{ob})^2 \).
Easy. There is a special case though - because the particle moves in discrete steps from frame to frame, if the particle is moving fast enough, it could move from one side of an obstacle to the other without ever overlapping.
The basic collision handling would miss this. So this is a little trickier to catch. In the above diagram, I've traced the path going from the particle's position in the previous step to its current position.
We can say that the particle collided with the obstacle if there's a point on that path that's closer to the centre of the obstacle than \( R = r_p + r_{ob} \). In other words, if the particle had moved continuously along the path from \(x_0\) to \(x_1\), would there have been any point(s) where the particle and the obstacle overlapped.
To figure this out, first we find the equation for the line passing through the particles' two positions as
\[ y = m x + c = \left(\frac{v_y}{v_x}\right) x + \left(y_0 - \frac{v_y}{v_x} x_0 \right) \]
(in this case, m and c are gradient and constant, respectively, not mass and speed of light).
Second, we're going to define a function for the distance between a point on the particle's path and the obstacle's centre
\[ f(x) = (x_{ob} - x)^2 + (y_{ob} - y)^2 = (x_{ob} - x)^2 + (y_{ob} - m x - c)^2 \]
Now we're going to look for the point along the path of closest approach to the obstacle. To do that we look for x such that the separation f(x) is minimised. In other words \( \frac{d}{dx} f(x) = 0\)
If you work through the maths, you get
\[ x_{min} = \frac{x_{ob} + m y_{ob} - m c}{1 + m^2} \]
Which gives us the condition - a collision occurred if \(f(x_{min}) \le R^2\) and \(x_0 \le x_{min} \le x_1\) (assuming \(x_0 \le x_1\)).
Of course, in the game, the spaceship sprite wouldn't be circular. But, you know. You could create an 'imaginary' circle around the sprite, or give the sprite a radius of zero (so it collides when its centre overlaps the obstacle). Or you could just use a third party library. Either way.
Bonus: Elastic Recoil
For my own amusement, I had the particle elastically recoil off of the obstacles, as well as the sides of the screen, so that I could just watch it drifting and bouncing about endlessly. It's weirdly hypnotic.
For screen boundaries, you have, for example
For recoil off obstacles, things are not so straight forward. The procedure works like this: First, check for a collision. Then, find the point along the particle's path where it first makes contact with the obstacle - that is where \(f(x) = R^2\).
\[ \begin{align*}
x' &= \frac{x_{ob} + m y_{ob}-mc}{1 + m^2} \pm \frac{\sqrt{(x_{ob} + m y_{ob}-mc)^2 - (1+m^2)(x^2_{ob} + y^2_{ob}+c^2 - 2 c y_{ob} - R^2)}}{1 + m^2} \\ \\ &\equiv a \pm b
\end{align*} \]
If \(v_x \gt 0\) then x' = a - b, if \(v_x \lt 0\) then x' = a + b
So move the particle back to the point of first contact. Then we want to flip the particle velocity so that the angle of incidence \(\phi\) between the velocity vector (v) and the position vector (r) equals the angle of reflection
\[v'_x = -\left|v\right| \cos(\beta) \\ \\ v'_y = -\left|v\right| \sin(\beta)\]
with \(|v| = \sqrt{v_{x}^{2} + v_{y}^{2}} \), and
\[ \beta = \alpha - 2 \phi = 2\arctan\left(\frac{-dy}{-dx}\right) - \arctan\left(\frac{v_y}{v_x}\right) \]
where \( \alpha \) is the angle between the x-axis and the old velocity vector (v), and \(\beta\) if the angle between the x-axis and the new velocity vector (v').
Note - in the code I used 'arctan2(y,x)' from the Numpy library, for which the signs of 'x' and 'y' are important. dy and dx are negative in the above because I have the position vector pointing from the particle to the obstacle (opposite to how it's defined).
Finally, we want to move the particle to where it should be from recoiling.
In other words, we want to move the particle to the point along it's new velocity vector, such that it's the same distance from the contact point as it would be if the particle hadn't collided. To do this, we can just resolve the distance \( r' = \sqrt{(x_1 - x')^2 + (y_1 - y')^2} \) in the direction of the new velocity vector, as
\[ x_1 ' = x' - r' \cos(\beta) \\ \\ y_1 ' = y' - r' \sin(\beta) \]
Admittedly, this doesn't work perfectly - sometimes it behaves a little screwy. Especially when the particle spirals in on an obstacle. Of course, none of this recoil stuff is necessary for the game, since you want collisions to end the game. Like I said, this was more for my own amusement.
Conclusion
If you were feeling really ambitious, you could do the game from the first-person perspective of someone on the spaceship - see for example 'Falling into a Black Hole', or the Interstellar papers.
There are almost certainly things wrong with this 'formulation' of General Relativity. But then, this is meant to be for a game, so it doesn't need to be 100% scientifically accurate. I did feel like I should make an effort, though. And I'm willing to call this good enough. If you're someone who knows what they're talking about, feel free to offer your thoughts/corrections.
Anyway, I've done my job as a theoretician - now it's up to someone else to actually make the game. If you do, please send me link to the completed game. And maybe give me a name-check? A little kickback would be nice too... ;)
You can have a look at my prototype/simulation code here.
Oatzy.
[Gravity, don't mean too much to me.]
Thursday, January 01, 2015
Lights Out (Game)
I was watching this year's RI Christmas Lectures, and it reminded me of this game I had when I was much younger. It was, I think, a Christmas present from my grandparents, back in '96. It was called Lights Out, and it looked something like this.
Basically, the console had a 5x5 grid of these rubbery, transluscent buttons with little red lights underneath them. When you press a button, that button and the four adjacent buttons switch state - light on to light off, or off to on. So, in the example below (where blue square are lights), if you press the centre square, the centre square turns off and the four adjacent squares turn on.
In the game, you're given a pattern of lights, such as the one above, and the task is to press buttons until all the lights are out.
Interestingly, in the pattern above (on the left), you can clear the board by just pressing the squares that are on at the start (in any order).
Anyway, I was reminded of that. Meanwhile, I'd been learning some Pygame for this other thing (that I'll talk about in a later blog). Now, Pygame is a Python library for making games (amongst other things). So you can probably see where this is going...
Coding a 'Lights Out' clone was straightforward enough - the code is short and not too complicated. The above images are actually screenshots. You can look at my code/download it here. You'll need Python and Pygame to run it.
This is a very threadbare version of the game. You can load a level as a text file of five lines of ones and zeros, like here. Or else you can just play from a blank board - make patterns then try to get rid of them again (not necessarily as easy as it sounds).
If you want something more fancy, or if you don't want to install Python and all that, there are probably loads of playable clones online.
Now, at this point you're probably thinking "Yeah, that's great. But what about the maths of Lights Out?". And you'd be damn right to ask. If you're interested, there's a good summary, as well as links to articles/papers, on the wikipedia page. I don't want to just repeat what's written there. Basically, it all comes down to linear algebra.
Anyway, have fun with that.
Oatzy.
[Call this a late Christmas present.]
Basically, the console had a 5x5 grid of these rubbery, transluscent buttons with little red lights underneath them. When you press a button, that button and the four adjacent buttons switch state - light on to light off, or off to on. So, in the example below (where blue square are lights), if you press the centre square, the centre square turns off and the four adjacent squares turn on.
In the game, you're given a pattern of lights, such as the one above, and the task is to press buttons until all the lights are out.
Interestingly, in the pattern above (on the left), you can clear the board by just pressing the squares that are on at the start (in any order).
Anyway, I was reminded of that. Meanwhile, I'd been learning some Pygame for this other thing (that I'll talk about in a later blog). Now, Pygame is a Python library for making games (amongst other things). So you can probably see where this is going...
Coding a 'Lights Out' clone was straightforward enough - the code is short and not too complicated. The above images are actually screenshots. You can look at my code/download it here. You'll need Python and Pygame to run it.
This is a very threadbare version of the game. You can load a level as a text file of five lines of ones and zeros, like here. Or else you can just play from a blank board - make patterns then try to get rid of them again (not necessarily as easy as it sounds).
If you want something more fancy, or if you don't want to install Python and all that, there are probably loads of playable clones online.
Now, at this point you're probably thinking "Yeah, that's great. But what about the maths of Lights Out?". And you'd be damn right to ask. If you're interested, there's a good summary, as well as links to articles/papers, on the wikipedia page. I don't want to just repeat what's written there. Basically, it all comes down to linear algebra.
Anyway, have fun with that.
Oatzy.
[Call this a late Christmas present.]
Sunday, June 24, 2012
Too Many Lotteries
So recently I'd gotten really into this TV show - it's called 'Life', and it's a 'murder of the week' crime drama starring Damian Lewis. Lewis plays Detective Crews, who was previously in prison for a muder he didn't commit, and he's into zen and such. It's a bit silly. But in an endearing sort of way.
Unfortunately, the only way I could watch it (short of buying the DVDs) is to stay up til 4am. Which isn't really a problem; I don't have anything to get up for. Though it is tricky getting to sleep as the sun's coming up.
Anyway, the point is, by 4am, there are only, like, four adverts on rotation (on FX, at least). These are: upcoming shows on FX, whatever product JML is flogging, that tacky accident helpline ad with Esther Rantzen, and this 'Win Trillions' thing.
Win Trillions is a lottery sindicate thing - from what I understand, it works like this: a bunch of people from around the world get together, each buying tickets for their respective countries' lotteries. If one of the sindicate members wins, they split the winnings with their fellow sindicate members (and presumedly, Win Trillions takes a cut).
Really, though, the details aren't that important. What is important is their slogan - "play more lotteries, get more chances".
Which isn't a false claim. It's just kind of misleading; playinng more lotteries does mean more chances of winning, but only in a similar way as buying more tickets for a single lottery means more chances of winning - your odds of winning are so small to begin with (~1 in 13,983,816) that you'd have to play thousands of lotteries (or buy thousands of tickets) to significantly improve your chances. And there are only so many lotteries in the world.
Strategies
You'll notice I used the word 'similar' back there; the fact is, buying more tickets, and playing more lotteries don't 'improve' odds in the same way.
So the question is, which is the better strategy - buying many tickets for a single lottery, or buying one ticket for each of several lotteries?
First, imagine I have a dice; I'm going to roll the dice, and you have to bet on the outcome. Your choice is this - would you rather place three bets on one dice roll, or one bet on each of three dice rolls?
For the first case, say you place your bets on it being 1, or 2, or 3. Your odds of guessing the correct number (and winning) is 3 in 6 (=0.5).
For the second case, say you bet that each of the rolls will be 6. Then your odds of winning 'something' is odds of winning just one of the dice rolls, plus the odds of winning just two of the dice rolls, plus the odds of winning all three.
Which is trickier to work out. For example, the odds of winning the first roll only, is odds of getting the first roll right (1 in 6), and not getting the second roll right (5 in 6) and not getting the third roll right (5 in 6) - which makes the probability of getting just the first roll right = 1/6 * 5/6 * 5/6 = 25 in 216
And you have to work out the probabilities for all possible winning outcomes (in this case, there are seven winning outcomes, one losing.).
Alternatively, we can use the trick that the odds of winning something is one minus the odds of winning nothing. The odds of winning nothing is the odds of getting all the bets wrong: 5/6 * 5/6 * 5/6 = 125 in 216 (0.58)
So the odds of winning something is 91 in 216 (=0.42)
So for this dice game, it's better to place your three bets on a single dice roll.
But what about in general?
We say each game has a probability p of winning, and that we're going to place n bets (with n>1).
For the single game bet, the probability of winning is n*p
For the multi-game bet, the probability of winning is
Which is bigger?
Well for n = 1, the games are idential. For n = 2, the single game is 2p, the multi-game is 2p - p^2; the single game has higher odds. For n >= 1/p, the single game gives a probability greater than or equal to 1 - i.e. guaranteed win - where the multi-game always gives a values less than one; again, the single game gives better odds.
So it's looking like the single game is always better. But how do we prove it?
For this, we look at the binomial expansion of (1-p)^n
A Binomial Expansion works like this
where k! is the factorial of k. For example: 2! = 2*1; 3! = 3*2*1; 4! = 4*3*2*1; etc.
In this case, x = 1 and y = -p, so the expansion becomes
Which makes the probability of winning the multi-game
So whether or not the mutli-game has higher odds than the single game depends on the sum of the terms after np.
First, we compare the k-th and (k+1)-th (adjacent) terms in the expansion
Which simplifies to
The righthand side has it's maximum value when n is maximum. We previously defined the maximum value of n as 1/p, so
since p and k are always greater than 0.
Which means
In other words, each term in the expansion is smaller than the ones before it.
This means that, if we pair up terms,
i.e. the sum of each pair will be negative. Therefore, the sum of all the pairs (all the terms in the expansion after np) is negative. So necessarily
Which means the odds of winning the single game is ALWAYS better than the odds of winning the multi-game.
Pay-Outs
You might have noticed that the single game has a single possible payout, where playing the multi-game means you could win double, triple, or even more of the prize. So the odds of winning the multi-game are lower, but you stand to win more.
Does that mean it's worth the extra risk?
For this, we look at the expected winnings for each game. The expected winnings is calculated as the probability of winning multiplied by the prize amount.
So if you were guessing the outcome of a dice roll, and the prize was £1, then the expected winnings from playing that game would be ~17p.
Or think of it like this - if you had to guess the outcome of a dice roll six times, you would expect to be right once out of six. So your expected prize for 6 rolls is £1, or 17p per roll.
For this single game, the payout is easy: w*n*p (where w is the prize for winning one game)
For the multi-game it's more complicate. We can't use the same trick as last time; instead, we have to work out odds of winning one game times prize from one game + odds of winning two games times prize from two game + etc.
The general form is the series sum
Which can be manipulated and simplified to give
Now, if we expand it out again
Then there's a factor of np in each term, so we can take that outside the bracket
And since n is some arbitrary interger, we can substitute m = n - 1 and put it back in summation form
Now, you might notice the summation part is actually a binomial expansion; in this case we have x = (1 - p) and y = p, so
For all values of p and m = n - 1.
Therefore, the expected payout of the multi-game is always w*n*p
You'll notice that this is the exact same expected payout as for the single game. As in, regardless of which strategy you use, your expected payout is the same.
So the question is, would you rather a low risk low prize game, or a high risk (potentially) high prize game?
Complexities
You'll notice for this I assumed all lotteries have the same odds of winning and the same prize amount. This is not necessarily true.
Even so, from this, the best strategy would be to find the lottery with the best single game single bet expected payout (prize * probability of winning), and buy several tickets for that game, rather than spread your money around.
The other thing in lotteries is you can usually win smaller prizes for matching fewer numbers. But I don't imagine that changes which strategy is best.
So now you know. For what it's worth. The odds of winning playing, say, 70 tickets on one lottery is only about two 10,000ths of a percent better than playing one ticket on 70 lotteries.
Incidentally, those derivations up there count as mathematical proofs. So these conclusions I've drawn are irrefutable*. And the results apply to any game where you're placing bets on a single probability random outcome - not just lotteries.
Oatzy.
[*- Assuming I haven't cocked it up...]
Unfortunately, the only way I could watch it (short of buying the DVDs) is to stay up til 4am. Which isn't really a problem; I don't have anything to get up for. Though it is tricky getting to sleep as the sun's coming up.
Anyway, the point is, by 4am, there are only, like, four adverts on rotation (on FX, at least). These are: upcoming shows on FX, whatever product JML is flogging, that tacky accident helpline ad with Esther Rantzen, and this 'Win Trillions' thing.
Win Trillions is a lottery sindicate thing - from what I understand, it works like this: a bunch of people from around the world get together, each buying tickets for their respective countries' lotteries. If one of the sindicate members wins, they split the winnings with their fellow sindicate members (and presumedly, Win Trillions takes a cut).
Really, though, the details aren't that important. What is important is their slogan - "play more lotteries, get more chances".
Which isn't a false claim. It's just kind of misleading; playinng more lotteries does mean more chances of winning, but only in a similar way as buying more tickets for a single lottery means more chances of winning - your odds of winning are so small to begin with (~1 in 13,983,816) that you'd have to play thousands of lotteries (or buy thousands of tickets) to significantly improve your chances. And there are only so many lotteries in the world.
Strategies
You'll notice I used the word 'similar' back there; the fact is, buying more tickets, and playing more lotteries don't 'improve' odds in the same way.
So the question is, which is the better strategy - buying many tickets for a single lottery, or buying one ticket for each of several lotteries?
First, imagine I have a dice; I'm going to roll the dice, and you have to bet on the outcome. Your choice is this - would you rather place three bets on one dice roll, or one bet on each of three dice rolls?
For the first case, say you place your bets on it being 1, or 2, or 3. Your odds of guessing the correct number (and winning) is 3 in 6 (=0.5).
For the second case, say you bet that each of the rolls will be 6. Then your odds of winning 'something' is odds of winning just one of the dice rolls, plus the odds of winning just two of the dice rolls, plus the odds of winning all three.
Which is trickier to work out. For example, the odds of winning the first roll only, is odds of getting the first roll right (1 in 6), and not getting the second roll right (5 in 6) and not getting the third roll right (5 in 6) - which makes the probability of getting just the first roll right = 1/6 * 5/6 * 5/6 = 25 in 216
And you have to work out the probabilities for all possible winning outcomes (in this case, there are seven winning outcomes, one losing.).
Alternatively, we can use the trick that the odds of winning something is one minus the odds of winning nothing. The odds of winning nothing is the odds of getting all the bets wrong: 5/6 * 5/6 * 5/6 = 125 in 216 (0.58)
So the odds of winning something is 91 in 216 (=0.42)
So for this dice game, it's better to place your three bets on a single dice roll.
But what about in general?
We say each game has a probability p of winning, and that we're going to place n bets (with n>1).
For the single game bet, the probability of winning is n*p
For the multi-game bet, the probability of winning is
Which is bigger?
Well for n = 1, the games are idential. For n = 2, the single game is 2p, the multi-game is 2p - p^2; the single game has higher odds. For n >= 1/p, the single game gives a probability greater than or equal to 1 - i.e. guaranteed win - where the multi-game always gives a values less than one; again, the single game gives better odds.
So it's looking like the single game is always better. But how do we prove it?
For this, we look at the binomial expansion of (1-p)^n
A Binomial Expansion works like this
In this case, x = 1 and y = -p, so the expansion becomes
First, we compare the k-th and (k+1)-th (adjacent) terms in the expansion
Which means
This means that, if we pair up terms,
Pay-Outs
You might have noticed that the single game has a single possible payout, where playing the multi-game means you could win double, triple, or even more of the prize. So the odds of winning the multi-game are lower, but you stand to win more.
Does that mean it's worth the extra risk?
For this, we look at the expected winnings for each game. The expected winnings is calculated as the probability of winning multiplied by the prize amount.
So if you were guessing the outcome of a dice roll, and the prize was £1, then the expected winnings from playing that game would be ~17p.
Or think of it like this - if you had to guess the outcome of a dice roll six times, you would expect to be right once out of six. So your expected prize for 6 rolls is £1, or 17p per roll.
For this single game, the payout is easy: w*n*p (where w is the prize for winning one game)
For the multi-game it's more complicate. We can't use the same trick as last time; instead, we have to work out odds of winning one game times prize from one game + odds of winning two games times prize from two game + etc.
The general form is the series sum
Therefore, the expected payout of the multi-game is always w*n*p
You'll notice that this is the exact same expected payout as for the single game. As in, regardless of which strategy you use, your expected payout is the same.
So the question is, would you rather a low risk low prize game, or a high risk (potentially) high prize game?
Complexities
You'll notice for this I assumed all lotteries have the same odds of winning and the same prize amount. This is not necessarily true.
Even so, from this, the best strategy would be to find the lottery with the best single game single bet expected payout (prize * probability of winning), and buy several tickets for that game, rather than spread your money around.
The other thing in lotteries is you can usually win smaller prizes for matching fewer numbers. But I don't imagine that changes which strategy is best.
So now you know. For what it's worth. The odds of winning playing, say, 70 tickets on one lottery is only about two 10,000ths of a percent better than playing one ticket on 70 lotteries.
Incidentally, those derivations up there count as mathematical proofs. So these conclusions I've drawn are irrefutable*. And the results apply to any game where you're placing bets on a single probability random outcome - not just lotteries.
Oatzy.
[*- Assuming I haven't cocked it up...]
Friday, February 24, 2012
A Problem With Puzzles
Here's a puzzle, tweeted by Aetherling
Have a go at it yourself. Solution below.
You see these sorts of puzzle every now and again. And there are usually common 'tricks' to them.
My first instinct was to add the digits. Nothing. Modulus? Nope. Sum and modulus, multiply digits, square, divide? Nope.
So, what?
For some reason, I decided I was going to try some algebra - ignore the fact that the left-hand sides of the equations are numbers, and treat them as variables with some unknown values. And then, add up whatever those values are to get the numbers on the right of the equations.
i.e. 9313 -> '9' + 2x'3' + '1' = 1; 1111 -> 4x'1' = 0; etc.
So from 1111=2222=3333=5555=7777=0 we get that 1,2,3,5,7 = 0
From 0000=6666=9999=4 we get that 0,6,9 = 1
And from 6855=3, 1+'8'=3 => 8=2
4 is undefined. And that makes the answer to the puzzle 2581=2.
It took me about half an hour to come up with that answer..
"If all you have is a hammer, everything looks like a nail"
That is the right answer. But the puzzle suggests that a preschooler would get the correct answer with ease. And I doubt a preschooler would do so with algebra.
So, what would a preschooler do? And why does it take 'higher educated' people so much longer?
What's the 'correct' answer? Take a look at the below
Basically, it's the number of loops in the digits on the left-hand side. This had to be pointed out to me by Aerliss.
But here's the interesting thing - take a look at the values I assigned to the number.
I got to the same answer, and effectively 'derived' the number of loops in the digits, without realising that that's what I was doing.
Source on the subheading quote - Maslow's Hammer.
It's not a perfect analogy, but the idea is this - the more mathematical training you have, the more techniques you'll be trying to use to solve the problem; possibly causing you to miss the 'obvious' answer. As, indeed, I did.
In this analogy, maths is the hammer.
And, strictly speaking, this puzzle isn't a maths problem - even though it's presented as if it were. And even though it can be solved using maths.
Another Problem
Here's another puzzle, recently posted on Reddit
The problem here is that the correct answer isn't known.
The 'obvious' answer (in as much as the one that most commenters came up with) was to add the four cross numbers, divide by 10, and round to the nearest whole number. In that case, the missing number is (23+20+12+3)/10 = 5.8 ~ 6 (B).
But that doesn't explain the set up - why the crosses? Are the positions of the numbers in the cross significant? And rounding is a little messy.
The most compelling proposed solution, once again, doesn't actually involve any maths:
Finite Rule Paradox
At any rate, what the comment thread shows is, in the absence of a 'true' answer, any answer is potentially correct with some valid justification. Case in point, I've just presented two different possible answers with two valid justifications.
This is an example of Wittgenstein's Finite Rule Paradox.
Stated explicitly - "This was our paradox: no course of action could be determined by a rule, because any course of action can be made out to accord with the rule"
Basically, what I described above..
There's a clearer explanation here. The topic is also a plot point in the novel (and subsequent film adaptation) The Oxford Murders; recommended if you're into maths-fueled murder mysteries.
The paradox is more apparent in 'find the next term in the sequence' puzzles.
For example, if you're given 2, 4, 8, 16 and asked what the next number is, then the obvious answer is 32 - twice the previous number/powers of two.
However, 31 is an equally valid continuation, as Marcus du Sautoy explains:
In fact, you can define a function, f(n), which satisfies the first 4 terms of the above sequence, and will give any number you like for the fifth.
The Easy Path
How is that possible? Lagrange Interpolation.
[Discussed in Professor Stewart's Hoard of Mathematical Treasures]
Lagrange interpolation applies to any (numerical) sequence of any (finite) length; so, there are infinitely many ways to continue any given sequence - and, necessarily, one cannot say with absolute certainty that a given sequence will continue in one particular way, only.
Unless the person who set the puzzle says otherwise. Because if it's their puzzle, they know what answer they're looking for. And if you try to score easy marks on an exam by citing Wittgenstein, you're probably going to fail.
Of course, Lagrange polynomials - although interesting that they exist - are likely to be the least interesting way to continue a sequence. Certainly, the equivalent Lagrange polynomial isn't as meaningful or interesting as the circle division sequence; even though they both give the same first 5 terms.
And a Lagrange polynomial will probably never be the most obvious/aesthetically pleasing solution.
There Must Be Another Way
The important thing is, the existence of Lagrange polynomials 'proves' the Finite Rule Paradox for numerical sequences.
By the same logic, there must exist some functions, f(a,b,c,d), which satisfy the first 20 equations in the first puzzle, but give some values other than 2 for the last. Or, multiple functions which do give 2, but by different methods to the correct one.
Of course, such functions aren't likely to be easy to find. Especially when there are 20 'initial rules' to satisfy. But the fact that there are finitely many rules means it's possible.
Not that counting loops, or manipulating letters count as mathematical functions. But the point still stands.
At any rate, the important thing to remember is not to get too obsessed with the consequences of the Finite Rule Paradox. Or you may end up trying to lobotomise yourself to prove a theory.
Oatzy.
[What comes next - 3, 3, 5, 4, 4, 3, 5, 5, 4, ?]
You see these sorts of puzzle every now and again. And there are usually common 'tricks' to them.
My first instinct was to add the digits. Nothing. Modulus? Nope. Sum and modulus, multiply digits, square, divide? Nope.
So, what?
For some reason, I decided I was going to try some algebra - ignore the fact that the left-hand sides of the equations are numbers, and treat them as variables with some unknown values. And then, add up whatever those values are to get the numbers on the right of the equations.
i.e. 9313 -> '9' + 2x'3' + '1' = 1; 1111 -> 4x'1' = 0; etc.
So from 1111=2222=3333=5555=7777=0 we get that 1,2,3,5,7 = 0
From 0000=6666=9999=4 we get that 0,6,9 = 1
And from 6855=3, 1+'8'=3 => 8=2
4 is undefined. And that makes the answer to the puzzle 2581=2.
It took me about half an hour to come up with that answer..
"If all you have is a hammer, everything looks like a nail"
That is the right answer. But the puzzle suggests that a preschooler would get the correct answer with ease. And I doubt a preschooler would do so with algebra.
So, what would a preschooler do? And why does it take 'higher educated' people so much longer?
What's the 'correct' answer? Take a look at the below
Basically, it's the number of loops in the digits on the left-hand side. This had to be pointed out to me by Aerliss.
But here's the interesting thing - take a look at the values I assigned to the number.
I got to the same answer, and effectively 'derived' the number of loops in the digits, without realising that that's what I was doing.
Source on the subheading quote - Maslow's Hammer.
It's not a perfect analogy, but the idea is this - the more mathematical training you have, the more techniques you'll be trying to use to solve the problem; possibly causing you to miss the 'obvious' answer. As, indeed, I did.
In this analogy, maths is the hammer.
And, strictly speaking, this puzzle isn't a maths problem - even though it's presented as if it were. And even though it can be solved using maths.
Another Problem
Here's another puzzle, recently posted on Reddit
The 'obvious' answer (in as much as the one that most commenters came up with) was to add the four cross numbers, divide by 10, and round to the nearest whole number. In that case, the missing number is (23+20+12+3)/10 = 5.8 ~ 6 (B).
But that doesn't explain the set up - why the crosses? Are the positions of the numbers in the cross significant? And rounding is a little messy.
The most compelling proposed solution, once again, doesn't actually involve any maths:
"As far as I can tell, the answer is C: 7 [...] The formula for the number in the center is the number of unique letters shared by the top and bottom numbers as written in English plus the number of unique letters shared by the right and left numbers.."
Finite Rule Paradox
At any rate, what the comment thread shows is, in the absence of a 'true' answer, any answer is potentially correct with some valid justification. Case in point, I've just presented two different possible answers with two valid justifications.
This is an example of Wittgenstein's Finite Rule Paradox.
Stated explicitly - "This was our paradox: no course of action could be determined by a rule, because any course of action can be made out to accord with the rule"
Basically, what I described above..
There's a clearer explanation here. The topic is also a plot point in the novel (and subsequent film adaptation) The Oxford Murders; recommended if you're into maths-fueled murder mysteries.
The paradox is more apparent in 'find the next term in the sequence' puzzles.
For example, if you're given 2, 4, 8, 16 and asked what the next number is, then the obvious answer is 32 - twice the previous number/powers of two.
However, 31 is an equally valid continuation, as Marcus du Sautoy explains:
"[L]et me explain why 31 can be a perfectly legitimate way to continue the sequence 2, 4, 8, 16 ... Draw three dots on a circle and join the dots with lines. The circle gets divided into four pieces. If you now take four dots on the circle and draw all the lines between the dots then you cut the circle into eight pieces. Five dots leads to 16 pieces. But if you draw all the lines between six dots you will only get 31 pieces rather than the 32 you'd expect."
In fact, you can define a function, f(n), which satisfies the first 4 terms of the above sequence, and will give any number you like for the fifth.
The Easy Path
How is that possible? Lagrange Interpolation.
[Discussed in Professor Stewart's Hoard of Mathematical Treasures]
Lagrange interpolation applies to any (numerical) sequence of any (finite) length; so, there are infinitely many ways to continue any given sequence - and, necessarily, one cannot say with absolute certainty that a given sequence will continue in one particular way, only.
Unless the person who set the puzzle says otherwise. Because if it's their puzzle, they know what answer they're looking for. And if you try to score easy marks on an exam by citing Wittgenstein, you're probably going to fail.
Of course, Lagrange polynomials - although interesting that they exist - are likely to be the least interesting way to continue a sequence. Certainly, the equivalent Lagrange polynomial isn't as meaningful or interesting as the circle division sequence; even though they both give the same first 5 terms.
And a Lagrange polynomial will probably never be the most obvious/aesthetically pleasing solution.
"[H]e conjectured that, though in principle all answers were equally probable, there might be something engraved on the human psyche [...] which guided most people to the same place, to the answer that seemed the simplest, clearest or most satisfying. He was definitely thinking that some kind of aesthetic principle was operating a priori which only let through a few possible answers for the final choice." - The Oxford Murders, Chptr 9Though, as seen in the Reddit puzzle, the simplest answer isn't necessarily the most correct one.
There Must Be Another Way
The important thing is, the existence of Lagrange polynomials 'proves' the Finite Rule Paradox for numerical sequences.
By the same logic, there must exist some functions, f(a,b,c,d), which satisfy the first 20 equations in the first puzzle, but give some values other than 2 for the last. Or, multiple functions which do give 2, but by different methods to the correct one.
Of course, such functions aren't likely to be easy to find. Especially when there are 20 'initial rules' to satisfy. But the fact that there are finitely many rules means it's possible.
Not that counting loops, or manipulating letters count as mathematical functions. But the point still stands.
At any rate, the important thing to remember is not to get too obsessed with the consequences of the Finite Rule Paradox. Or you may end up trying to lobotomise yourself to prove a theory.
Oatzy.
[What comes next - 3, 3, 5, 4, 4, 3, 5, 5, 4, ?]
Subscribe to:
Posts (Atom)