Funny Story

So there's four of us at the pub, and we're playing the one word game. And we decide that, since this is the future, we should play a marathon game, via Twitter (complete with hashtag, #OneWordGame).

The One Word Game is where a group of people attempt to collectively tell a story, one word at a time. (Also known as Word at a Time Story).

At this point, we've been playing for about two weeks.


So what's our story? Before that, lets play a game.

Below are two 'stories' - one of them is our word-at-a-time story, the other has been randomly generated (using Markov text generation).

Which is which?

When the wizard was masturbating upon a picture of your face which is ugly he said that a giant octopus with swashbuckling offspring however walrus munched on his wardrobe handles while reciting to Steve the only one who played the harmonica case under his umpalumpa cheese tasted spectacular when dipped in French wine and peanut butter making apples with a slightly tangy bumhole that had smelly teeth and pickled onions with slices of cherry on toast. Suddenly a massive caterpillar spawned from a seed which smells of turnip. When select acorns they exploded penises all turned into a

There was no further sound other than the soft tinkle of water. But in the middle of the surface area were encrusted with hard-caked earth but the girl who was confined them to perpetual darkness. This time there would be a very narrow neck extending about an inch above the rest. Could be worth a try I think he changes his name from time to time. Since it was meant to support an entire career However I

The correct answer is, ours is the first one - probably evident from the vulgar language.

As for the second one; I've discussed Markov generators before. In the simplest case, they work by randomly picking words based on how likely they are to follow the preceding word. This particular example was generated from the first four chapters of Dirk Gently's Holistic Detective Agency (Douglas Adams) using this site.

How does this relate to our game?

Well, the game was spread out over such a period of time that, usually, I'd forgotten the story much beyond the previous few words. So, I was picking my words based on what seemed like a coherent continuation to those few. Not unlike a Markov generator.

And, you have to admit, the two make about as much sense as each other.


At any rate, the game is still on-going..


Oatzy.


[What? I never claim our story was funny..]

Fibonacci's Rainstorm

A couple years back I got it in my head that I was going to try and write a musical about time travel.

Yeah, I don't know either.

But perhaps the maddest thing about that idea is that I have next to no musical training. Not that I'm the sort to let that stop me. So instead, the plan was to try and create music using maths. Which is a little weird.

But not actually as mad as it sounds. After all, Pythagoras (yes, that Pythagoras) was the first - or so the legend goes - to study the maths of harmonics, and why certain sounds are more pleasing to the ear than others.

It's all to do with fractions. But I won't go into all that because it's not relevant to my thing - there's a good, brief explanation in this video, How to Solve a Song with Math.


Musical Integers

The basic idea was as simple as this - you assign an musical note to each integer - say, starting with 1 = Middle C, 2 = C#, etc. though there are other methods of assignment - then generate integer sequences and seeing what they sound like.

For a good example of this sort of thing, here's mathemusician Vi Hart on the music of pi.

After playing around with various functions, what I settled on where that Hailstone numbers; which I misremembered as being called rainstorm numbers.


Collatz Conjecture

The Collatz Conjecture (also known as the hailstone numbers) works something like this

Well, all except the last sentence fragment. The actual idea is that, regardless of what starting number you pick, the sequence will always end on the number 1 (full details on the wiki page).

The Collatz Conjecture is currently unproven, though recently someone published a proposed proof - currently under scrutiny. But that's a whole other story.

So you pick some number, generate the sequence and see what it sounds like. Here's the sequence for 12

That is - 12, 6, 3, 10, 5, 16, 8, 4, 2, 1

The problem with using hailstone numbers is that it has the potential for massive jumps - for example 7, 22, 11, 34, 17, 52, etc - and such a sequence would not sound pleasing (this goes back to Pythagoras).


Lateralis

So my second idea was to combine it with the Fibonacci Sequence - that is 1, 1, 2, 3, 5, 8, 13, etc - where each number in the sequence is the sum of the two preceding numbers.

This was actually inspired, slightly, by the Tool song Lateralis, where the syllables of the lyrics form a rising and falling Fibonacci Sequence:

Black / then / white are / all I see / in my infancy / red and yellow then came to be / reaching out to me / lets me see.

So the idea was to perform the Collatz algorithm on the numbers of the Fibonacci sequence - which sounds something like this

 

1 / 1 / 2, 1 / 3, 10, 5, 16, 8, 4, 2, 1 / 5, 16, 8, 4, 2, 1 / 8, 4, 2, 1

Finishing Touches

Now the next part's a bit fuzzy. While I still have the notebook in which I worked out the tune, my notes aren't exactly clear.

But, basically, what happened was that the resulting tune (see above) was far too erratic in places. So I made a lot of modifications to it, but still based vaguely on patterns in the generated tune.

And the final touch I added to make the tune sound richer was chords. Again, I didn't know anything about chords. But a quick look on wikipedia told me how to make major and minor chords, so I decided to add the minor chords of the first notes of each bar.

Here's what the final tune sounds like

 
Yes, it's a bit short and basic. But all things considered, I'd say I did pretty well.


More Math Music

I've already mentioned above the music based on the digits of pi.

There was also a guy who worked out a way to convert games of chess into music.

And, as mention briefly in a previous post, you can go (almost) completely random and generate music using Markov chains - for example.


Oatzy.


[Oh, and I never did write that musical. Not that that should surprise you.]

Markov's Next Tweet

Have cookie. All is a little intrusive So close to be Everyone is we haven't blogged in mall bathroom -!

If you've ever taken the time to read spam - and you really should - you might have come across something like this; text that almost seems human, but on closer inspection just doesn't quite make sense.


Markov Chains

I've mentioned Markov Chains before, for example, in the Snakes and Ladders post. Here's the formal definition from Wikipedia,

A Markov chain, named for Andrey Markov, is a mathematical system that undergoes transitions from one state to another (from a finite or countable number of possible states) in a chain-like manner. It is a random process endowed with the Markov property: the next state depends only on the current state and not on the past.

In the context of snakes and ladders, this basically says that the square you'll land on in the next turn depends on the square you're currently on, and the roll of a dice.


What the Dickens?

So what does this have to do with text generating?

Here's a visual example of how it works. These are the first few lines from A Tale of Two Cities as a flowchart,

In the above, you have the lines broken up word-wise, and linked by which words follow each other. To generate a sentence, pick a starting point and follow the arrows. When you get to a junction pick which way you go at random.

So for text generation, your 'current state' will be some word - say, 'of' in the above. The Markov text generator then picks a word to follow it. In the above, there are 5 words that could follow 'of', each with an equal chance of being chosen; except for 'times' which is twice as likely as the others, since it appears twice in the source.

It should be noted that it isn't just shuffling the words completely at random - words are chosen based on what they appear together with in the source.


Tweets Go In, Gibberish Comes Out

By feeding different source texts in to a generator, you can get all variety of different results; to some extent matching the style of the source writer. This is what can make the output seem so human, while being so beautifully nonsensical.

In fact, the quote at the very top of the post was generated by "That Can Be My Next Tweet".

The only explanation the site gives as to how it works is,

This page generates your future tweets based on the DNA of your existing messages.

But it seems safe to assume, from that and what it outputs, that it's using Markov text generation with your - or in this case my - previous tweets as the source text.


What if I don't really is

He opened the door and got into the car engine shuddered into life and the vehicle lurched down the driveway..

That bit of text is actually an extract from "How to write badly well: Forget what you're doing halfway through a sentence", and is human written. But it demonstrates the point well.

In the above text, you have two sentence fragments either side of 'the car'; each makes sense individually, but not when they're put together.

And unfortunately, these sudden changes of direction are a major trip up point for Markov text; especially since this sort of thing can happen multiple times in a single sentence.


Letters and Words

You don't have to chop up the source text word-wise.

You could, for example, run a Markov chain letter-wise (or even by groups of letters).

This is particularly good at creating bizarre, new, portmanteau-ish words. For example, if your source is the US states, you get such gems as - Floridaho, Oklabama, and Flork.

The drawback to this approach is that it's no good at sentences, since what you'll get is likely to be a nonsensical collection of made-up words.

Alternatively, you could work with pairs of words, or indeed n-grams of any size. This has the benefit of creating more readable-text, but at the cost of variation.

Similarly, a smaller source text can produce lots of sentence fragments that never vary, while a large source can will give greater randomness.

It all ultimately comes down to getting a desirable balance between variability and comprehensibility.


Stuff to Play With

I threw together this quick and dirty implementation in python - mostly just to show that I could. I ran it on the first few paragraphs of this post (pre-editing), and got this as an example output,

almost seems human but while no-one is going on some spam was text that has anyone really should you might have postulated that has anyone really

That Can Be My Next Tweet, mentioned above.

On TweetCloud, you can enter a word and get a word cloud of words that commonly follow that word in tweets. Word.

Word-O-Matic, also mention above, creates words based on any source text you give it. See also: associated Reddit thread with lots of example results.

Markov Text Synthesizer, a general online generator you can play with.

There are various Twitter-bot attempts here.

Markov Shakespearean Sonnet (uses a slightly more complex generation method)

Someone who explains it better than me.

Oh, and you can also use Markov Chains to generate music.


Enjoy.


Oatzy.


[Spam is weirdly hard to come by these days.]

Snakes and Ladders

Or Chutes and Ladder, if you're American. Yes, I am talking about the board game.
The idea came from having read about people analysing Monopoly with simulations, Markov chains and the likes. You can read about it in Math Hysteria by Ian Stewart or find a similar discussion here.

In the book, Professor Stewart also suggests that the reader might like to try the same for Snakes and Ladders. So I did*.


If you're not familiar with Snakes and Ladders and how it works, you had a very deprived childhood. There's an example game board below

[wikipedia]

I don't know if or by how much game boards vary. But for simplicity, I'm assuming this is a representative layout. Variations aren't likely to dramatically affect the overall behaviour.


Simulating the Game

You start with a 'board' with a value for each square. All squares start with a value of 0. You can simulate the dice roll by randomly picking a number between one and six and move accordingly. Whatever square you land on, you add one to that square's value. If you land on a snake or a ladder, you move along it. Repeat until you get to square 100.

At the end, you have a record of how many times each square was visited.

Here's a network graph of all possible moves.

Over-arcs are forward movements (dice rolls and ladders), under-arcs are backwards movements (snakes).

One run of the simulation is equivalent to one possible game. So what you do, is run the simulation, say, 10,000 times, and measure things like, how many times you land on each square, average or minimum number of turns it takes to get to the end, etc.

There is a way of solving this exactly, and mathematically, as discussed for Monopoly in Ian Stewart's book, and indeed as was done in this paper [pdf]. But this way is much easier.

You can get the code here.


Results

Here's a graph of number of times each square is landed on (out of 10,000 simulations). Snakes are green, ladders are red, arcs show which squares are connected.

And you've got this slightly weird, overall, wave shape. And obviously, the snake and ladder landing squares are outliers - most visited ladders, 36-44 and 28-84; most visited snakes, 47-26 and 49-11.

NB/ technically I shouldn't include the 'entrances' of snakes and ladders in the graph, since when they're landed on, you move straight to the 'exits'. But for interests sake, they are included. They aren't included in the moves count as separate moves.

You can also graph the number of moves it takes to get to the end

The minimum moves is 7, and interestingly, you can also derive that answer from the network graph - that is the absolute minimum.

In this simulation, the mode is 21 and the average is 36.2. The maximum, in this case, is effectively around 215. But theoretically, if you were really unlucky you could keep landing on the same snake over and over; in which case, the maximum number of moves tends to infinity.

And, the last thing to look at is how much more likely you are to land on a snake than a ladder. First of all, there are (typically) 10 snakes and 9 ladders, so the simple answer would be 1.11 times more likely.

But when you go down a snake, as mentioned above, there's a chance you can go down the same snake again (or down other snakes or up other ladders). So it turns out, you're actually 1.23 times more likely to land on a snake than a ladder. Which isn't a dramatic difference; but the important thing is, you need no longer wonder.

On average, you'll land on about 4 snakes and 3.2 ladders per game.


End Games

Say you land on square 97 and roll a four; there are three possible ways to end the game:

Past the End - assume that moving past 100 means you've reached the end (this is what I did above).
This is the easiest way to end the game.

Roll Again - stay in the same square and roll again until you roll a 3 (or less).
This is effectively the same as the above, except (on average) it takes more rolls of the dice (but not necessarily more moves) to reach the end.

Loop Back - move three spaces forward (to 100) then one space back. Repeat until you land exactly one square 100.

This last one takes longer to get to the end, and has a greater risk of you landing on the snakes on squares 95 or 98, sending you back to 75 and 78 respectively.

And that's demonstrated in the graph below - both lines are effectively the same until about the last 25 squares, where the 'loop back' diverges towards more visits (as expected).

You also have the moves distribution,

which in this case is broader and pushed to right slightly; the average now 43.3. Note also that 7 is still the minimum number of moves.

Also, in the 'loop back', the odds of landing on a snake goes up again - now 1.41 times more likely than a ladder. So on average, you'll land on about 5.2 snakes and 3.7 ladders per game.


Triple Sixes

Another rule you could chose to include is - if you roll three 6s in a row, you go back to square 'zero'.

According to the simulation, you'll roll a triple six in about 13.4% of games, on average.

But the triple six seems to have no significant effect on what squares you land on, the number of snake and ladders you'll land on, or oddly enough, the distribution of how many moves it takes to get to the end. This is probably because throwing triple sixes is so rare.


So there you go. Bet you didn't think snakes and ladders could be so complicated.


Oatzy.


* truth be told, this is something other people have already done. But I like to try these things for myself.