Output Shakespeare with the highest probability
We all know that a monkey hammering out random bytes will output the works of Shakespeare with some probability. This probability is extremely low.
But what if the monkey would type out a computer program instead, and then we run the computer program and see if that outputs the works of Shakespeare? The program might output random text but with biases that make the works of Shakespeare much more likely to appear. That way, the overall probability of outputting Shakespeare might be much higher. But how much higher? Let's find out.
The essence of this challenge is to maximise the following probability:
p(the monkey outputs your program) * p(your program outputs the works of Shakespeare)
But to make that work as a practical challenge we have to introduce some rules and a little bit more maths, so read on.
This challenge is similar in spirit to my previous Write Moby Dick, approximately, but the scoring system is very different and this should lead to a significantly different challenge.
more details
The following file contains the complete works of Shakespeare in ASCII format. [to do: create the file and upload it somewhere]
In principle your program is meant to output random text, but we need to do that in such a way that we can calculate the probability of a given output. For most programming languages that isn't possible, so instead of having your program behave randomly we will have it output a probability distribution.
It works like this: your program (or function etc.) will be called multiple times (about 3,500,000 times). On each invocation it will be given the first n characters of bill.txt
and it will output a probability distribution over ASCII characters, which is its probability of guessing a given next character. This output can be in any reasonable format - for example, it could be a Python array of 128 floats. But it must be a probability distribution, i.e. in this example the floats must sum to 1.
The following pseudocode shows how your score is calculated:
log_p_monkey_outputs_program = -(size of your submission in bytes)*8
log_p_program_outputs_shakespeare = 0
bill = contents of bill.txt
for n = 1 to length(bill)-1
probabilities = your_program(first n characters of bill)
correct_prob = probabilities[(n+1)th character of bill]
log_p_program_outputs_shakespeare += log2(correct_prob)
score = log_p_monkey_outputs_program + log_p_program_outputs_shakespeare
The score that this program calculates is the logarithm of the probability that the monkey outputs your program and the program outputs Shakespeare, assuming that we always feed the program's output back in as input. We calculate the logarithm to avoid floating point errors, as the final probability will be extremely small. Note that the logarithm is to base 2.
If the scoring program is implemented correctly, the score will always be negative. A higher score (closer to 0) is better.
Note that your program outputs a probability distribution but it should not itself behave randomly. Your program may not use a random number generator - it must always return the same probability distribution for a given input.
If you want to store state in between invocations this is allowed. You can do this by writing to an external file, by using static
or global variables, by submitting a class rather than a function, using a state monad, or whatever else works for your language.
Submission format
Your submission should include the following, which do count towards the size of your submission. If they are excessively large you can link to github etc.
- your program
- any data it needs in order to run
Your submission should also include the following, which don't count towards its size:
- the code used to calculate its score, implementing the pseudocode above
- any code that was used to generate your submission (e.g. to create any data files that you included)
- an explanation of how your submission works.
Rules
As mentioned, your program must run deterministically, so that it always outputs the same probability distribution given the same input (and hence always gets the same score).
If at any time the value of correct_prob
in the scoring pseudocode is 0, then your score is -∞, which is the worst possible score.
You may not use any libraries or functions that your language might have that include data or statistics about natural language. This includes pre-trained neural networks, word lists, etc. It also includes any built-in function that outputs any of Shakespeare's works. It's fine to use neural networks and word lists etc., but the data or weights must be included in your submission and count towards its byte count.
You may not use any libraries or functions designed for text compression. It's fine to use algorithms like bzip etc., but you have to implement them yourself (and hence include the implementation in your byte count).
Your submission should include the code used to calculate its score. (This doesn't count towards the byte count.)
If you want to store state between invocations you can do this however you like, as long as your program never has access to 'future' bytes from the bill.txt
file. (So, for example, you can't just pass it a string containing all of the input and get back a big list of probability distributions as output.)
You must actually run your test program and calculate/verify your score before submitting your entry. If your submission runs too slowly for you to verify its score then it is not qualified to compete, even if you know what its score would be in principle.
You may import existing libraries other than the exceptions above, but you may not load any other external files unless they're included in your byte count. Your code may not access the bill.txt
file in any way other than described above.
sandbox notes:
I'm unsure about the rule banning built-in compression algorithms. It seems more elegant to leave it out, but in Paint Starry Night, objectively, in 1kB of code they spoiled the fun a bit, and I'm worried that with this scoring system the same could happen here. I'm happy to hear any thoughts about that.
I'm also worried about this being closed as a duplicate of Write Moby Dick, approximately. That challenge was popular (it's the 12th highest scoring question on the site), but I wasn't really satisfied with it because the answers ended up being dominated by one method. I've been thinking for years about how to improve the scoring system so that that won't happen. A huge amount of thought has gone into what makes a good scoring system and why this one in particular should encourage more creative answers than the previous one - but that work isn't visible in the question text itself, so I'm worried that people will see two questions about predicting the next character in a text file and vote to close it. I welcome any thoughts about how to avoid this possibility.
I'd also really like feedback on the score calculation pseudocode - is it sufficiently clear how the score is calculated, and can I make it clearer?
Finally, a very specific query: the ban on word tables seems like it would rule out some golfing languages. I'm unsure whether I should make an exception for those, or if that would be seen as giving those languages an unfair advantage.