There is a new internet community game taking off called Twitch Plays Pokemon. The concept is simple: set up a server that takes the next properly formatted input (“up”, “down”, “a button”) from a chat window, and apply it—in order, with no filtering—to a copy of Pokemon Red.
This is going about as well as can be expected, with 90,000 players, about a third of whom are actively attempting to impede progress.
So, a TDT style challenge: Beat the game in the shortest number of steps
If there are no trolls, but you cannot communicate with other players
If some percentage p of players are trolling and the timeless plan must be adjusted to be robust.
What do you mean by “communicate”? If I send a command, and you observe the result of that command on the game, we’ve communicated.
If that’s allowed, the non-troll case is easy: Wait a random amount of time, then send a command. If yours was the first command to be sent, play the game. If someone else sends a command before you do, do nothing ever again.
I have been checking in on this for the last few days. I do not think they will be able to make it through victory road. This would require them to get through a passage, where they have to go down once, then left 11 times, then up once without pressing down at any point along the way. If they make it through, they will have to solve a large number of boulder puzzles in a cave with lvl 40 wild pokemon, and if they die at any time, they have to go across the passage again.
I did an estimate of how long I think it would take them to accomplish just walking across the passage once, based on how they did on similar passages in the past, and it came out to 50 years.
This estimate was before they changed the system to some weird democracy system, which will likely help them.
I did an estimate of how long I think it would take them to accomplish just walking across the passage once, based on how they did on similar passages in the past, and it came out to 50 years.
Hm, that feels a bit long. How did you estimate that?
According to this it took 12 hours to execute a move that requires 8 rightward movements. If the “victory road” requires that they execute 13 moves correctly, and the time it takes grows exponentially with the number of steps (as a power of two), then it might be a reasonable ballpark to suggest it would take 12*2^(13-8) hours, which would be 16 days. Of course, this is an overestimate because assuming more than 50% of people are making the right move, it should grow as a power less than 2. Much less than 50 years I would expect, but then again I’ve never played Pokemon so could be missing some element here that changes the complexity.
On second thought, I think it was a bad estimate. It is very dependent on how many of the people are trying to make them fail, and I really have no idea what that is. It is also very dependent on the lag.
The problem is that there is lag, and a single down vote after they are on the passage makes them have to start over. Trolls and honest people who do not understand the strategy will be pressing down for a large part of the travel, so the likelihood of making it across will not be high. I think it would be generous to say that every time they mess up, it will take them 1 minute to get back to try again. 10 minutes seems more accurate to me.
Most attempts will fail at the beginning, because they need the correct number of people to press down, and no more to get lined up with the ledge. Then the question becomes, can they get 11 lefts and an up before they get a down.
You can see why 40% trolls and 20% trolls will change this estimate a lot.
I do not think this matters that much though, because they changed the system, and the democracy system will make it a lot easier for this part.
Ah. The approach I was thinking of was to model it as a binomial or Poisson, infer the probability of success at each step by noting that it took 12 hours (or let’s say, 720 tries) to have 8 successes in a row, and then calculate how many tries would be required to get 13 successes in a row. Unfortunately I wasn’t sure how to go from ’720 tries for 8 successes in a row’ to ‘probability of 1 success’ and gave up there.
the probability of one success is 720^(1/8), so it should take 720^(13/8) tries, which is about a month. However, the fact that they could line themselves up for the last one just by pressing up and down, and not risking having to start over will make a huge difference.
They did a similar ledge, in about 8 hours, but that ledge was much easier, because you did not risk having to start over just by aligning yourself to get ready to cross it. It was also only length like 6 or 8.
I think if they got to that point, they would be very cautious about the very first down movement so as not to overshoot and it shouldn’t be too bad from there.
Use the stream-of-commands as seen from the chat and the stream to estimate the delay between inputs now and results later. Generate a probable future state, given the current distribution of commands. Evaluate what distribution of commands maximizes positive results, and spam that distribution.
The biggest time sink other than the program logic is creating pathing/scoring rules. I’d start with “how to successfully deposit the first pokemon in your party”—Markov chains is where you want to go.
I pointed out right away that the non-trolls will want to overlevel their team (if that’s a thing, I dunno), to be safe against interference.
Of course, trolls will be very effective at preventing you from getting far in menus (menu cancel spam) so you may be stuck with your starting pokemon or whatever for a long time. And heaven help you if the game requires you to go deep into a menu hierarchy to activate level up bonuses.
I think, at least before they changed it to democracy, trolls are much less of a problem than coordination problems between individuals who are legitimately trying.
Mildly interesting challenge:
There is a new internet community game taking off called Twitch Plays Pokemon. The concept is simple: set up a server that takes the next properly formatted input (“up”, “down”, “a button”) from a chat window, and apply it—in order, with no filtering—to a copy of Pokemon Red.
This is going about as well as can be expected, with 90,000 players, about a third of whom are actively attempting to impede progress.
So, a TDT style challenge: Beat the game in the shortest number of steps
If there are no trolls, but you cannot communicate with other players
If some percentage p of players are trolling and the timeless plan must be adjusted to be robust.
What do you mean by “communicate”? If I send a command, and you observe the result of that command on the game, we’ve communicated.
If that’s allowed, the non-troll case is easy: Wait a random amount of time, then send a command. If yours was the first command to be sent, play the game. If someone else sends a command before you do, do nothing ever again.
Hm.
Yeah, I don’t think I can remove that communication channel without breaking the game entirely. So that makes the first exercise rather trivial.
I have been checking in on this for the last few days. I do not think they will be able to make it through victory road. This would require them to get through a passage, where they have to go down once, then left 11 times, then up once without pressing down at any point along the way. If they make it through, they will have to solve a large number of boulder puzzles in a cave with lvl 40 wild pokemon, and if they die at any time, they have to go across the passage again.
I did an estimate of how long I think it would take them to accomplish just walking across the passage once, based on how they did on similar passages in the past, and it came out to 50 years.
This estimate was before they changed the system to some weird democracy system, which will likely help them.
Hm, that feels a bit long. How did you estimate that?
According to this it took 12 hours to execute a move that requires 8 rightward movements. If the “victory road” requires that they execute 13 moves correctly, and the time it takes grows exponentially with the number of steps (as a power of two), then it might be a reasonable ballpark to suggest it would take 12*2^(13-8) hours, which would be 16 days. Of course, this is an overestimate because assuming more than 50% of people are making the right move, it should grow as a power less than 2. Much less than 50 years I would expect, but then again I’ve never played Pokemon so could be missing some element here that changes the complexity.
On second thought, I think it was a bad estimate. It is very dependent on how many of the people are trying to make them fail, and I really have no idea what that is. It is also very dependent on the lag.
Here is the route in question.
The problem is that there is lag, and a single down vote after they are on the passage makes them have to start over. Trolls and honest people who do not understand the strategy will be pressing down for a large part of the travel, so the likelihood of making it across will not be high. I think it would be generous to say that every time they mess up, it will take them 1 minute to get back to try again. 10 minutes seems more accurate to me.
Most attempts will fail at the beginning, because they need the correct number of people to press down, and no more to get lined up with the ledge. Then the question becomes, can they get 11 lefts and an up before they get a down.
You can see why 40% trolls and 20% trolls will change this estimate a lot.
I do not think this matters that much though, because they changed the system, and the democracy system will make it a lot easier for this part.
Ah. The approach I was thinking of was to model it as a binomial or Poisson, infer the probability of success at each step by noting that it took 12 hours (or let’s say, 720 tries) to have 8 successes in a row, and then calculate how many tries would be required to get 13 successes in a row. Unfortunately I wasn’t sure how to go from ’720 tries for 8 successes in a row’ to ‘probability of 1 success’ and gave up there.
the probability of one success is 720^(1/8), so it should take 720^(13/8) tries, which is about a month. However, the fact that they could line themselves up for the last one just by pressing up and down, and not risking having to start over will make a huge difference.
They did a similar ledge, in about 8 hours, but that ledge was much easier, because you did not risk having to start over just by aligning yourself to get ready to cross it. It was also only length like 6 or 8.
I think if they got to that point, they would be very cautious about the very first down movement so as not to overshoot and it shouldn’t be too bad from there.
Use the stream-of-commands as seen from the chat and the stream to estimate the delay between inputs now and results later. Generate a probable future state, given the current distribution of commands. Evaluate what distribution of commands maximizes positive results, and spam that distribution.
The biggest time sink other than the program logic is creating pathing/scoring rules. I’d start with “how to successfully deposit the first pokemon in your party”—Markov chains is where you want to go.
Weird. Someone showed this to me just on Monday.
I pointed out right away that the non-trolls will want to overlevel their team (if that’s a thing, I dunno), to be safe against interference.
Of course, trolls will be very effective at preventing you from getting far in menus (menu cancel spam) so you may be stuck with your starting pokemon or whatever for a long time. And heaven help you if the game requires you to go deep into a menu hierarchy to activate level up bonuses.
The problem is most definitely not being strong enough to fight the trainers they need to fight, it’s getting to them in the first place.
There are a lot ledges that you can only go one way on, and many of them lead from the end of a path right back to the beginning.
Maybe they could try something a little less finnicky? Final Fantasy 1, say, with a team of black belts?
I think, at least before they changed it to democracy, trolls are much less of a problem than coordination problems between individuals who are legitimately trying.
The lag really hurts too. I’m not sure I could play any game on a reasonable timeframe with 30s delay