Crowdsourced brute-forcing: how Fez was a coop game for a couple of hours
This was perfect for the problem at hand since the sequences could be entered in any order, only the last 7 button presses were checked to see if the sequence was right.
In the image above, entering the first row in order then entering the last input of each subsequent rows will input all 4 sequences in 8 inputs instead of 20. For 10 sequences of 7 characters, that's 16 inputs instead of 70.
No more than a couple hours were needed to build a rudimentary version of the app. I unit tested the basic algorithms to make sure they behaved correctly and launched the app on heroku only a few hours after I had started working on it. I then shared the link (
fez-monolith.heroku.com fez.mbillard.com) on a Gamefaqs thread where some players had gathered to work on the puzzle.
Trolls, false positives and false negatives
As soon as the app went live I was already working on the next version where people could confirm or deny sequences marked as being right. This turned out to be very important because trolls were already trying to negate the work of others by entering false information like marking untested sequences as invalid or marking invalid sequences as being the solution.
The fix for false positives was quite easy, people could just confirm or deny them, they would then disappear from the list of potential solutions. However, false negatives were harder to detect, the only way was to have more than one person try each sequence. Unfortunately for the community, the correct sequence was marked as invalid relatively early in the life of the app.
Causes of false negatives and why mysql != postgresql
Each false negative was the result of one of these 3 problems:
- trolls purposefully marking any sequence as being invalid
- users not inputting the sequences correctly
- my lack of experience with postgresql
To understand, take a look at the following code used to retrieve 10 supposedly consecutive sequences (which had been created in order in the database):
# Get a random set of X consecutive sequences
@sequences = Sequence.where("id >= ?", random_sequence_id).limit(nb_sequences)
What's wrong? There's no ordering in the retrieval of the sequences. On my development machine this wasn't a problem because I was using MySQL which was returning the sequences in the expected order. Postgresql on the other hand, which was required on Heroku, did not always return the sequences in order. This probably caused some users to input the sequences using the suggested method (the first sequence fully then only the last input of each following sequence). Someone reported the issue, but unfortunately I could only fix it much later in the day after my normal workday. This was entirely my fault for not knowing that a SQL query is non-deterministic without an
order by clause.
Some stats and conclusion
Time between when the app went live to when the solution was found: ~18h
Number of contributors: more than 1300
Number of trolls: 123 people found a correct sequence, 20 of them found a lot more than one
Number of tested sequences: 66,227/78,125 (84.771%)
Number of false positives: 515
The solution had been marked as negative about 5 hours after the app went live either by someone trying to ruin the efforts of the others, because of an error from the player inputting the sequence or due to the ordering error in my code mentioned earlier.
Overall I am very satisfied with the project, it was shared by many on Twitter and on various forums as well as on Kotaku. I managed to set-up a very useful application in a matter of hours using Rails, Heroku and Bootstrap. The current website will remain live as I see no reason to take it down, I have put it in a frozen state to preserve its state at the time the sequence was found.