Playing with Pac-Man

What the Puck?

For those unfamiliar, Pac-Man is an old arcade game, where you play as a cheese pizza trying to collect pellets while being chased round a maze by four whimsically named ghosts. Although really, if you are unfamiliar with Pac-Man, there's something wrong with you. Anyway, you can have a play online here.

The four ghost are Blinky, Pinky, Inky, and Clyde. For a good explanation of the ghosts' behaviours, here's a post from the tragically short-lived 'Game Internals' blog.

tl;dr Blinky chases, Pinky ambushes, Inky teams up with Blinky, and Clyde does pretty much whatever the fuck he wants. But really, you should read the article.

And as for the origin of the name, I'll let Scott Pilgrim explain. Or if you prefer to read, wikipedia.


Wakking Round in Circles

Graph Theory is a fantastic area of maths. Graph Theory can find you the shortest route, help you get out of a maze, tells you how to colour a map so no adjoining regions are of the same colour, to reconstruct DNA fragments, and help you find the best route for sight-seeing. Among many other things.

But sadly graph theory tends to be covered more in Computer Science courses than Maths courses. So for myself, i have to be content with books and the internet. Not that I let such thing hold me back.


So the question is this - Find the optimal route around the Pac-Man maze

What we want to do is find a route around the maze while collects every pellet. Or in graph theory terms, a route which travels along every edge at least once.

First of all, we need to turn the maze into a network graph. For this, we place a node at each junction, and join pairs of nodes according to whether or not there is a direct route between the pair.

So here's what the maze looks like, beside what the graph of that maze looks like.

The blue edges are the ones with pellets. The red edges are the ones without pellets, which you don't necessarily have to visit.

And we can assign to each edge a 'weight' - i.e. the distance (in grid squares) between the pairs of nodes

Now, first of all, we note that there are a lot of node where an odd number of edges meet (with odd degree). What this means is that the graph is not Eulerian - what that means is, there doesn't exist a route around the graph which visits each edge exactly once.

Which means that we will definitely have to travel along some paths more than once.


So the optimal path is going to be the one which minimises the total distance traveled. This is an example of the Chinese Postman Problem, and fortunately, there is an algorithm for finding the shortest route.

Without going into too much detail, what you do is pair up odd nodes, and find the shortest paths between them (using Dijkstra's Algorithm). This makes the graph Eulerian, i.e. so that a route that visits each edge at least once exists.

So if we take the bottom corner as an example, there are four node of odd degree (green).

By finding the shortest paths between pairs of odd nodes (red), we can make this mini-graph Eulerian - i.e. so all nodes have even degree. This means we can find the optimal tour around the graph (right). In this case we have to travel an additional 12 units.

Of course, it gets more complicated when you're working with the full Pac-Man graph.

When there are more than two nodes of odd degree, you also have to find the combination of pairings which minimises the total tour size. For an idea of scale, there are 20 odd nodes in the Pac-Man graph. That means there are 654,729,075 pair combinations to check and compare. And you have to run Dijkstra's algorithm 10 times for each of those permutations. It adds up.


So instead, I took the essence of the algorithm and constructed a route by hand. This is not necessarily the optimal route. For this route, you have to travel an extra 60 units - including 9 units along a path segment that doesn't contain any pellets.

There are other paths around the maze which cover (and recover) the same same ground as the above solution, and others that double back over different ground, but that add up to the same distance.

One constraint, in the case of Pac-Man, is that the path has to start at the point near the bottom of the maze, where Pac-Man starts in the game.

But also, it doesn't matter where the tour finishes (where as, the Chinese Postman starts and finishes at the same point). This means modifications to the 'optimal' solution may be possible/required.

In the bottom-corner example, we can eliminate some of the extra paths (up to 9 units worth) if we don't care where we end up.


If I ever get around to programming and running the proper algorithm, I'll let you know what the 'proper' solution is. And if you can find a better solution, let me know.


Of course what I haven't taken into account is the fact that, as you're making your way around the maze, you're also trying to avoid ghosts. I'll be honest, this path finding was more of an intellectual exercise than anything practical. You can find some strategic tips here.


This Maze Ain't Big Enough For the Both of Us.

If you follow me on Twitter, you may have already read about this - in a dream I formulated a multiplayer version of Pac-Man. But weird, subconscious machinations aside..

I looked it up on wikipedia, and there was already a multiplayer Pac-Man - Pac-Man Vs. But in that game you have one player playing as Pac-Man, and any additional players as ghosts. The aim is for the Pac-Man player to collect pellets and for ghost players to stop them. My idea is better.

First of all, you'd probably need to make the maze bigger. Each player plays as a Pac-Man, and like the normal game, their aim is to collect the most points, while trying to avoid ghosts. The game introduces a new special pellet which lets you cannibalise an opponent Pac-Man (much like the pellet that lets you eat ghosts).

Each player starts with two lives. If they lose both their lives they become a ghost. As a ghost, other ghosts can't hurt you, but you can't collect any pellets. If you catch an opponent Pac-Man, you steal one of their lives (becoming a 'living' Pac-Man again, with one life). If an opponent Pac-Man gets one of the special ghost pellets, they can eat a ghost opponent, killing them for good.

The game ends when all the pellets are collected or when all players are ghosts/dead. The winner is the player with the most points.

Or something like that.

If only I have the know how to make a real, playable version. But, hey, if there happens to be anyone out there reading this who could make it, please do..


Oatzy.

Picking and Scoring Words for Hangman

Hangman, for those unfamiliar, is a popular way for primary school teachers to teach spelling in the guise of a fun guessing game, and a way for secondary school teachers to pass the time at the end of term when they can't be bothered with teaching.


It Works Like This..

In a dystopian future where the powers that be like to play deadly games with their political prisoners, Hangman sees one such prisoner, 27 year old Adrian Silk, standing on a platform in front of a cheering crowd; his crime - logical thought.

Adrian is presented with an unknown word - 9 letters, title of a 21st century movie - and his task is to determine that word by guessing letters.

With each correct guess he gets closer to discovering the mystery word and winning a stay of execution. With each incorrect guess, another piece of the gallows is built. If he can't reveal the word before the gallows are fully constructed, he'll be dancing a dead man's jig for the crowd.

He starts by guessing the vowels - A, E, I, O, U - two incorrect guesses, two pieces of the gallows built: I__E__IO_

He guesses some common consonants - N, R, S, T - two more incorrect guesses, but still safe: IN_E_TION

Adrian stops to think - "are there any films called INFECTION? There are two, but they're pretty obscure.. Wait..!". And he hazards a guess - INCEPTION ..?

He's right! Adrian jumps for joy, and breathes a sigh of relief. And as the disappointed crowd jeers, Adrian is shot between the eyes by the Games Master - found guilty of the logical thought with which he'd been charged.

Still, if you think that's bad, you should see how they play KerPlunk!


Lets Play a Guessing Game

Okay, imagine you were guessing letters for an unknown word. But in this variation on the game, the hangman will only tell you when you've won, or else when you've run out of letters. That's all the information you get, nothing else.

The simplest approach to finding a word would be to just work your way through the alphabet - 26 letters, a maximum of 26 guesses to uncover any word.

But there will be a limit on how many incorrect guesses you can make - usually around 10. This means that, unless the word you're guessing contains 17+ unique letters this probably isn't the optimal approach.

So with no feedback and a guess limit, all you can do is guess letters 'at random'. But some letters appear more often in the English language than others. So you can make educated guesses, and go for the more common letters first: E, T, A, I, O, N, S, ...

If we assume that the probability, p(ci), of a person guessing a given letter is roughly equal to that letter's frequency in the English language, then the probability, big P, of that person guessing a correct letter in a word equals the sum of the probabilities of each unique letter in that word.

For example, in MISSISSIPPI, the unique letters would be {I,M,P,S}, so

P(MISSISSIPPI) = p(I)+p(M)+p(P)+p(S) = 4.025% + 2.406% + 1.929% + 6.327% = 14.687%


What this immediately suggests for choosing words is:

1) Words with 'uncommon' letters are better

Uncommon letters have lower probability p(ci), so will make totals lower. E.g. C is less common than H, so (in the game described above) CAT is harder to guess than HAT

2) Words with fewer unique letters are better

If there are fewer (and smaller) targets, it's harder to hit one of them by just firing at random.


Parting Words

So what about in a real game, where you get lots of feedback - which letters are right or wrong, where each letter appears and how many times.. This makes deduction a lot easier.

Have you ever tried to cheat at a crossword? There are loads of 'helpers' online - put in the pattern and see what possible words match it. Well for hangman we take that a step further.
Say our pattern is E_UA_I__; there are 5 words it could be - EQUALITY, EQUALING, EQUALISE, EQUATION, EQUATING

First of all, EQUALISE is not a valid solution because it introduces an extra E. And if we'd guessed all the vowels to get that pattern, we can also rule out EQUATION since we've already determined that O doesn't appear in the solution word.

So to put it more concisely - we want to find words that match a given pattern, eliminating those which contain extra letters already guessed.

In the case above we're left with 3 words - EQUALITY, EQUALING, EQUATING - and which of the three the correct word is can be determined by guessing the letter T:

1) E_UA_IT_ which can only be EQUALITY
2) E_UATI__ which can only be EQUATING
3) T doesn't appear in the word, in which case it can only be EQUALING

The fact that T is the most common consonant probably means each of those 3 words are poor choices for hangman. This is an example of a low entropy pattern.

Imagine, instead, that you're presented with a 3 letter word, and you've gone through the vowel and found you're left with the pattern _A_

What could that be? Maybe you guess T next and get _AT - well that could be BAT, CAT, HAT, RAT, .. Or maybe T is wrong, then the word could be MAN, CAN, BAY, RAY, WAX, TAX, .. how many guesses have you got left?

In fact, there are 179 possible words which match this pattern. This would be a high entropy pattern.


So, more tips for picking good words:

1) Pick obscure words

Even if there is only one word a pattern could fit, if the opponent doesn't know that word, then they are forced to keep guessing letter-wise. Which makes things a little more tricky.

2) Pick shorter words

There are more 3 and 4 letter words in the English language than 8 and 9 letter words.

3) Avoid too many repeated letters

For example, MISSISSIPPI only has 4 unique letters, but once you've guessed I and S, you've uncovered 73% of the word, and there's really nothing else _ISSISSI__I could be.

4) Pick words with high entropy patterns


A Question of Uncertainty

In Information Theory, entropy relates to the uncertainty in a piece of information. It's measured in bits, and, for a set of equally likely outcomes, is calculated as the base two logarithm of uncertainty.

So a coin toss has an uncertainty of 2, because there are two possible, equally likely outcome. That gives an entropy of 1 bit. For a given character in a word, if we assume all letters are equally likely, then there is an uncertainty of 26 - so that gives an entropy of log2(26) = 4.7 bits.

But as pointed out above, all letters are not equally likely in the English language. So the entropy is more complicated to work out: H = -SUM[p(ci)*log2(p(ci))]. Anyway, it turns out the entropy of a given unknown letter is 4.18 bits.

In the case of word patterns, we work out entropy as log2 of number of valid words matching the pattern, since all matching words have the same probability of being correct.

For the low entropy example above, there are 3 possible words that match the pattern so that would give an entropy of log2(3) = 1.58 bits. The 3 letter, high entropy example, on the other hand - with it's 179 possible solutions - would have an entropy of 7.48 bits.


So Where Does This Leave Us?

The idea is this - to come up with a scheme for scoring the 'quality' of a word in terms of how hard it is to guess in a game of hangman.

First, we score our word by its letter, as described above, to get the probability of guessing a correct letter. We then take one minus this to find the probability that a letter guess is wrong - the lower the probability of guessing a correct letter, the higher that word's score.

Entropy has a well define method of measurement in Information Theory, as discussed above.

But if we measure the entropy of a word before any letters are guessed, we find that all words of the same length have the same entropy. So instead, it would be more useful to measure a word's entropy after, say, some common letters have been filled in. Since most people start by guessing the vowels, that is what I'm going to go with.

In some cases, there are so many possible pattern matches, that you'd do better to simply make educated guesses at letters until the solution is found. For this, we work out the letter-wise entropy. Again, before any letters are guessed, all words with the same number of unique letters have the same entropy.

So. Each unknown, unique letter in a word can be one of those not already guessed. So we can work out the entropy, H(alpha), of the alphabet, sans the letters already guessed. Then, multiply that by the number of unique letters left to find, n.

So for example, if we guess the vowels and get the pattern _A_, then the entropy is  2*H(consonants) = 5.62 bits


From a Practical Stand Point

To work out the word entropy we can download a dictionary, then write some code which will find and count the words which match our required pattern, excluding those containing already guessed letters.

We then find the 'smallest maximum' entropy - which of the character entropy and the word entropy is smallest. In most cases it'll be the word entropy.

And finally we multiply that by the probability, one minus big P, to assign to each word a score:

(1-P)*min{H(W), H(C)}

Or you can use this code.

In and of themselves, the scores this gives don't have any specific meaning - the exact score for each word will depend on your choice of dictionary and initial guess letters. But so long as you use them consistently, the scores should stand as an indicator of each word's relative 'quality'.

For example, by this system, CAT gets a score of 5.3, and EQUALITY gets a score of 1.4. So CAT is a much better hangman word than EQUALITY.


So What's the Best Word

JAZZ, apparently. In fact, while researching this blog, I came across a few other people's attempts to find the best words for hangman. Pleasingly, they went with different approaches to me.

In fact, JAZZ never occurred to me when I was thinking up random good words. The best I thought of was WAX. Also reassuring is the fact that JAZZ does score highly under my system - 6.07 - and scores only slightly better than WAX, with its score of 5.92

QUIZ is an interesting word. It contains the two least common consonants and the two least common vowels (P=9.89%). But there are only 12 words that match _UI_, so it has low entropy. Its final score is 4.13 - lower than that of CAT, with its more common letter set (P=20.0%).

Similarly GYM; it has P=6.34% and has no vowels, but there are only 29 words it could be, so has a score of 5.48. Or MY, with P=4.38% but only 5 possibilities, score 3.18. So it's a matter of balance between probability and entropy.

Ideally, I'd have run a whole dictionary through my system to look for a list of best words. But I didn't. You can if you really want. Otherwise, I'd recommend one of the blogs linked above for lists.


In Summary

So there you go. You can score some of your own words if you so wish. But for on the fly word assessment, just remember, pick:

1) Words with 'uncommon' letters
2) Words with fewer unique letters
3) Obscure words
4) Shorter words
5) Words with fewer repeated letters
6) Words with high entropy patterns

And if you're trying to guess a 4 letter word with an A in the second position, odds are someone is trying to outfox you with JAZZ.


Oatzy.


[Full disclosure: If I got the information theory stuff wrong, it's because I only know as much as the one chapter of this book, and odd bits on wikipedia.]

Su Doku Solver

Cold Hard Logic

Let's be frank, Su Doku solvers are dime a dozen. My favourite is the one in Google Goggles - you point your camera at a puzzle and it uses OCR to interpret it, then solves it for you. None of that faffing with inputting the puzzle by hand. Anyway.

At the most basic level, computers run on maths and logic. So logic puzzles should be easy for computers to solve - it's just following a collection of logical rules. No creative thinking required.

The problem are,

1) Inputting a problem in a form that the computer can parse (understand)
2) Translating the logical rules into a form the computer can apply
3) Applying said rules to a given input problem to find its solution.

Here's the main puzzle I'll be using as the example for this post [source]. Feel free to try and solve it yourself before continuing (it should be easy).

The Rules

So what are the rules? In the traditional version you're presented with a 9x9 grid, with some numbers already filled in. The idea is to enter into the grid the numbers 1-9, so that each number appears only once in each row, column, or box (3x3 square).

So that's fairly straight forward. But in that particular form, the rules are really only good for checking if your solution is right.


Brute Force

This can be use in a brute-force approach to solving, e.g.

1) Stick numbers in empty squares at random
2) If any of the numbers break the rules, try again
3) Repeat until the right solution is found.

But that's incredibly inefficient and inelegant, and certainly not the way it's solved by people in the real world.

As an example, say our placement technique is this - take the numbers missing from each row, and just shuffle them around within their given row.

[There are probably better brute-force methods.]

If we use this approach on the puzzle above, there are ~4.95E26 possible number placements (permutations), of which only one is correct. Say our computer can check 1 billion solutions per second, it would take 16 billion years to solve. Which is about 2 billion years longer than the current age of the universe.

As a ball park estimate, the general formula for the number of permutations for a grid of side n is given by -> ((n-a)!)^n  - Where a is the average number of numbers already placed in each row.

If, for example, we try to solve a 16-grid with a=8 (half the numbers already placed), then the number of possible permutations is a mind-meltingly inconceivable 4.88x10^73. At 1 billion checks per second, that would take 1.5x10^57 years to solve - 1 billionth the lifespan of a black hole with the mass of the sun (according to wikipedia).

This is an example of a non-polynomial time (NP) algorithm. More on that later.


Rewriting the Rules

The rules can be re-interpreted and applied in two fundamental ways

1) Which is the only square this number can appear in?

That is, a particular number has to go in one particular square, because if you try to put it in any other square in that row (or column, or box) it will break the rules.

This is the most common approach in real world solving - that is, "three can't go in that row, or those columns because they already have threes in them, so it must go there" sort of thing.

2) What is the only number that can go in this square?

That is, if every other number already appears in the same row, column, or box as a given square, then that square can only be one particular number.

This is most obvious in the case where every other number in a given row is already filled in, but can also be used by considering all the rows, columns and boxes a square belongs to.

This tends to be required more in the harder puzzles; you could probably solve the above puzzle by Rule One alone.


Setting Up The Problem

First of all, we create our grid. We can refer to each square in the grid by a sort of coordinate - (i,j) - with the square in the top left corner being (0,0) and the square in the bottom right being (8,8)

We reference Row i as the set {(i,j) : j in [0,8]} and Column j as {(j,i) : j in [0,8]}

For boxes, we note that the index for the top-left square of each box are multiples of 3 - (0,0) (0,3) (0,6) (3,0) etc. So, Box (m,n) is given as {(3m+i,3n+j) : i,j in [0,2]} for m,n in [0,2]

So from this we can, for example, check the correctness of a puzzle (by rows) like this:

for i in range(0,9):
    for j in range(0,8):
        for k in range(j+1,9):
            if Grid[i][j] == Grid[i][k]:
                return "incorrect puzzle"

Checking columns and boxes works similarly.


If we have a fancy GUI, then inputting and parsing the grid is pretty straight forward. But we don't. So instead, we input the puzzle as one long string -> puzzle = "???36?9???2?.."

The first row is given by the characters (numbers) numbered [0,..,8], the second row is [9,..,17], and so on. In general, row i is the set of characters with index [9i,..,9i+j,...,9i+8]. 

Parsing our puzzle into the Grid works like this then:

for i in range(0, 9):

    for j in range(0, 9):

        Grid[i][j] = puzzle[9i+j]

And so on..


Applying the Rules

Now, if you've done Su Dokus, you might be familiar with the technique of filling each square with the numbers one to nine and eliminating numbers as appropriate. That's basically the bulk of how this solver works:

1) Assign to each empty square ("?") the set [1,...,9]

2) For each number in a given square's set:
    a) Check to see if that number is already fixed in another square in the same row, column, or box as the square in question. If so, eliminate the number from that square's set.

3) Repeat for all squares in the grid

From there, we can apply Rule Two:

4) For each square:
    a) if that square's set contains only one number, fix that square's value accordingly.

5) Go back to (2). Repeat until no more squares can be fixed.

You can actually created a shortcut for this - create a collection of sets for each row (etc.), which contain the values already fixed in that row. That way, instead of checking every square along each row for fixed values, you just check in that row's set. (Trust me, it's easier.)

Applying Rule One is easy as looking along each row (or column, or box) to see if a given number appears in only one of the squares.

Or more technically,

1) For a given row (etc), for each number 1-9:
    a) count how many times that number appears in square sets in that row
    b) if a number's count equals 1, fix the value of the square it appears in accordingly.

2) If you fix any new squares this way, go back to (2) to see if that will allow you to set any more squares.

You then just loop through rules One and Two until the puzzle is (hopefully) solved.


One More 'Rule'

In fact, this is just Rule Two, but with an added 'quirk'.

Here's what happens if you apply the method, so far, to a more difficult puzzle

This is where the program gets stuck. What do you do from here? If we focus on the bottom-right corner box

Notice there are no squares that can take only one value, and no values that only appear in one of the squares.

But look on that bottom row - the circled boxes can only take the values 3 or 5. What this means is that 3 and 5 can't go in any other of the squares in that box. So we eliminate 3s and 5s from the other squares in that box. Similarly for the 1/6 squares in the middle.

We now have the square in the top-right of the box that can only be 8, and the middle-right that can only be 9. So we fix those values. And from there, it's pretty straight forward to solve the rest - going back to looping through Rules Two and One.

Not only is it tricky to spot in real world solving, it's also tricky to translate it into computer logic. It mostly involves looking for pairs of squares in a box (etc.) which have matching sets of size two (or triplets, size 3, or etc.). Fortunately, this sort of thing doesn't come up often.


A Note on P versus NP

So as mentioned above, it's easy enough to apply the standard rules (as states) to check if a solution is correct - you just check to make sure no number appears more than once in any given row, column, or box.

It turns out, checking the correctness of a puzzle can be done in polynomial time (fast). For a grid of side n, the time required to check a solution* is given by -> 3(n^3 - n)/2

..Multiplied by the amount of time it takes a computer to work out if 2 numbers are equal or not (call this time t). So for a 9-grid, that time is 972t.

For a grid of side n=100, the time is ~1.5million t. Which on a modern computer is peanuts. For example, if our hypothetical computer can check 1 billion 9-grids in one second, then it can check 650,000 100-grids in a second.

By comparison, actually solving the puzzle - by the method outlined about, and by all other known methods - is done in non-polynomial time.

What this means, is that if you apply this algorithm to a larger grid - say, a 25x25, or a 36x36 grid - then the amount of time it will take to solve the puzzle increases rapidly (exponentially), to the point where a puzzle couldn't be solve in the lifetime of the universe.

But, since checking the puzzle for correctness is polynomial, even if the puzzle took longer than the life of the universe to solve, you could still check to see if the solution is correct (that no number appears more than once in each row, etc) in a reasonable amount of time.

As mentioned above, the brute-force method outlined is non-polynomial (NP). Notice that it takes catastrophically longer - 70 orders of magnitude - to solve a 16-grid by brute-force, than it takes to check the solution to a, much larger, 100-grid.

Admittedly, I don't know what the time function is for the method outlined above. But suffice it to say, it's more efficient than the brute-force, but still non-polynomial.

What P versus NP asks, then, is

if the solution to a problem can be checked in polynomial time (quickly), then does there exist an algorithm that can solve the problem in polynomial time?

At present, this is one of the great unsolved questions of mathematics and computer science, and a proof of whether or not P=NP will earn its discoverer $1million...


Where's The Code?

You'll probably have noticed, I've given a general, hand-wavy outline of how a program would work, and only given odd snippets of code.

I did write a solver in Python a few years back. I'd taken a Java programming course in my first year at university, and when the lecturer discussed a tic-tac-toe (naughts and crosses) playing program, it gave me the idea of how to represent a grid in a way a computer can parse. It also made me realise that there is actually a point to object-oriented programming.

Anyway, long story short, I wrote the solver 3 years ago. It's kind of sloppy and inelegant. And it can't handle the 'tricky' puzzles - although, oddly enough, according to my notebook, I had worked out a way of implementing it, but apparently never did.

Or to put it another way, it works, but compared to the myriad others out there, it's nothing special.

If you're interested, as I mentioned at the beginning there are plenty of other solvers out there. They might not work according to the methods discussed in this post. But you should at least have an idea of how one might work, now.

And as a final note, these methods can also be used for hand-solving. It's generally not necessary to be so rigidly systematic, though. It's easier for humans to pick out number placements at a glace, without having to go through the whole set-and-elimination approach.


In Case You Were Interested

Here's the solution to the Su Doku at the top of the page

You're on your own with finishing the other ('difficult') one..


Oatzy.

Quick Look: Don't Blink..

"..Don't even blink. Blink, and you're dead!" threatened the frustrated photographer, following a fifth failed photo..

No, this isn't a Doctor Who thing (sorry). No, this is based on another lost article I read a while back:

How many photos do you have to take in order to get at least one where no one's blinking?


First things first, what's the probability of one person blinking when you take a photo of them?

Well for one thing, that's going to vary depending on environment, lighting, etc. And also on the shutter speed of the camera being used to take the picture.. But for simplicity, I'm ignoring all that.

The average person blinks around 10 times per minute, with an average blink lasting 300-400 milliseconds (call it 350ms). So in any given minute, the average person's eyes will be closed for a total of 3.5 seconds.

We'll say the shutter is open for less than the duration of a blink. So the probability of a persons eyes being closed while the shutter is open -> p = 0.058.

[I'll be honest, I'm not not entirely convinced that's right. But I'll go with it anyway.]

So the probability they don't blink -> (1-p) = 0.942


If you're taking a picture of one person, that's only a 5.8% chance of the subject ruining a photo by blinking. So your odds of a good shot are pretty good.

But if we have a much larger group of people - n = 30 - the probability that none of those people blink while a photo is being taken:

p1 = (1-p)^n = 0.165

That's an 83.5% chance that at least one person will blink. Those odds aren't so good.


So if we take S number of photos, what is the probability that at least one of those is 'perfect'?

This goes back to the methods use in the Law Of Truly Large Numbers post - the probability of at least one perfect photo, big P, is one minus the probability that none of the S photos are perfect:

P = 1 - (1-p1)^S

So if we were to take, say, S = 5 photos -> P = 0.594

Bearing in mind that you have to make these 30 people stand around while you take your however many photos, an almost 60% chance of the perfect shot from 5 tries it pretty reasonable.

But let's say you're the panicky sort, and you want to be 90% certain that you have at least one perfect shot..?

Without going into the nitty-gritty, we can find S for P = 0.9, using some logarithms and algebra thus:

S = ln(1-P)/ln(1-p1) = 12.8 shots

And if you can get a group of 30 people to stand still for 13 photos, knowing that there's still a 10% chance you won't get that perfect shot, then more power to you.


When people know they're having their picture taken, they generally try harder not to blink. Especially if you use a count down. So the probability of blinking, and by extension, the number of photos you'd have to take, drops dramatically. The numbers worked out above are probably more applicable for candid shots.

On the other hand, maybe the flashing going off (if you use one) will cause some people to automatically blink. And, admittedly, I've taken pictures of myself that have still managed to get capture me mid-blink. Though that might be down to a delay between click and shutter.


Of course, in this day and age, of digital cameras with instant preview, you can just keep shooting until you get the photo you want. Not like the dark old days of film cameras and photo roulette...


Oatzy.


[The word 'blink' and its variants appear ~17 times in this post]

[As a random aside, working out the number of pokéball you need to throw to catch a given Pokémon is done in much the same.]

The Toilet Seat Conundrum

Gentlemen, do you leave to toilet seat up, or courteously put it down after use?

I read a (somewhat tongue-in-cheek) article a while back, I can't remember where, that explained the toilet seat conundrum in terms of game theory.  As best I can remember, it was quite clever. I was recently reminded of it when reading a Cracked article, and thought I'd try to recreate it, and - as is my wont - take it a step further.

Game theory, for those unfamiliar, is an area of maths/economics that studies 'competitive' interactions, "in which an individual's success in making choices depends on the choices of others".


Preamble

The (average) probability of the gentleman needing to 'sit down' when visiting the bathroom, we call p*. The probability of not is (1-p).

If the toilet seat is in the 'wrong position' for a given visit, we call the cost of this c1, and we assume that this cost is the same for both genders. This may not be strictly true.

The simplest cost would be in having to move the seat, typically in the form of mild inconvenience, and the potentially unpleasant experience of having to touch the underside of the seat. I'm also told that there are certain perils in visiting the toilet at the night, if the seat is in the upright position and is required to be otherwise. I can't say this is a cost I've ever experienced.

One might argue that the 'costs' are inconsequential; but for the sake of arguing, they aren't.

For the sheer hell of it, we'll call the woman Alice and the man Bob. Alice and Bob have been in a relationship/living together just long enough to quarrel over such matters. I suspect, for most people, this is a non-issue; but that's not the point of the post.

There is a third possible game, not discussed below, in which Bob can just leave the seat down at all times. In this case, we have c3, the cost of clean up if Bob's aim isn't quite up to scratch.

Oh, and there is a fourth game, where the default position of the the seat is upright. This is the worst possible game for Alice, and is only the best possible game for Bob if p<0.28. I can only imagine this game working in an all male household, and even then (a re-adjusted) Game One works out better.


Game One - Leave It As Is

Probability of the seat being down is the probability of Alice being the last to visit the lav plus the probability Bob was the last and left the seat down. Probability the seat is up is 1 minus the above.

Here's the cost matrix for this game

Where cost is c1 multiplied by the probability that the seat is in the wrong position

To get the total costs to Alice and Bob for this game, we work out

(Probability the seat is down x the cost if seat is down) + 

(probability seat is up x cost if seat is up)

And we can work out the ratio of costs

B:A  =>  2p+1 : 1

In the extreme case, where p=0 (Bob never poops), their costs are equal. But in all other cases, Bob's cost is greater than Alice's.


Game Two - Return to Default

Default meaning the seat is always returned to the downright position after use. The probability of the seat being up is always 0.

Here's what the matrix looks like

In this case, Alice incurs no cost. Bob, on the other hand, incurs double cost - when he needs to urinate, he has to move the toilet seat twice: up before use, and down afterwards.

It's obvious that Alice, once again, fairs better than Bob.

Game Three, mentioned in the preamble, works the same as this, but with 2c1 replaced with c3. Alice still comes out better though. Unless she doesn't like the thought of sitting on a toilet seat that's (potentially) been peed on - even if it is cleaned - in which case, there's some abstract cost to her.

If she doesn't mind, then which of games Two and Three Bob would prefer depends on which is smaller: 2c1 or c3.


Lowest Costs

First of all, we note that in both games Alice comes out better than Bob - incurring a lower cost in both cases. That said, Alice does better in the latter game, incurring no cost at all in that one. So Game Two is preferable to Alice.

But what about Bob?

If we take the cost ratio of game one to game two for Bob, this is what we get

B1:B2  =>  2p+1 : 4

In the extreme case of p=1 (Bob never urinates), Game Two incurs a greater cost for Bob (3:4) - and by extension, Game Two always incurs a greater cost to Bob.

THIS is where and why the conflict arises.

Alice prefers Game Two, Bob prefers Game One.


Tipping the Scales

So Alice would prefer to play Game Two, but she has to encourage Bob towards it. So Alice introduces a new penalty - c2 - for Bob leaving the toilet seat up.

The cost will typically be something along the lines of a bollocking, silent treatment, arguments, or whatever.

So what we do is this - the odds of Bob leaving the toilet seat up, and Alice being the next to use the bathroom -> (1-p)/2

Multiplied by the cost, c2, and added to the pre-existing total cost for game one

Now, we - or rather, Alice - wants the cost to be such that Game Two is preferable, i.e. B'1 > B2

Rearranging and simplifying, we get

c2 > 4c1(2p+1)

However, if Alice were feeling kind, she could introduce a 'reward' for putting the toilet seat down, instead. It works effectively the same - barring psychological, carrot/stick considerations.

For this, Alice would have to offer a reward, R, with

Arguably, Bob could introduce a new cost - or enticement - himself, to 'persuade' Alice towards Game One. But TV leads me to believe that this is seldom thought of, or executed.

This might be because Alice has more to gain/lose - in as much as, Alice can avoid any cost by 'playing' Game Two. Bob, on the other hand, incurs some cost in both games.

You can draw your own conclusions on that one.

In terms of a co-operative solution, if we add together Alice and Bob' costs in each game and compare, we find that Game One has a lower total cost than Game Two.

So one could argue that Game One is better overall. The challenge, though, is convincing Alice that that is the best solution for both of them, given that, from Alice' point of view, she does worse in Game One.


Casino Bathrooms

So this is all well and good, but it's kind of a specialised case - the situation of a house with one male, one female, and one toilet. In our house, for example, we have two males, two females and three toilets. What then?

There are a few other problems with the probability-based approach, as well. For one thing, it uses an average poop-probability for the gentleman. It also assumes both Alice and Bob use the bathroom about the same number of time during a given time period - whereas some people have more robust insides than others.

So for this, we create a Monte Carlo simulation.

[This is what we call excessive commitment to an idea.]

In the simulation, we create a 'person' object, and assign to them a gender, an average number of bathroom visits, and, for males, an average bladder to bowel movement ratio. To capture the day to day variability in number of visits to the bathroom, we use Poisson distributions.

We also create a 'toilets' set, representing however many toilets there are, and their current states -> 1 = toilet seat up, 0 = toilet seat down. Each toilet has an equal chance of being chosen for use by any given person at any given time.

Each person has a counter, which is incremented when the person in question has to move the seat. At the end, these counters are grouped by gender for comparison.


In the Middle of Our Street

So I created a 'house' of two males, two females, and three toilets (variables chosen arbitrarily). Then ran the simulation for 10,000 hypothetical days.

The Game One simulation gives a result of ~ 3.28 seat moves per male per day, and 2.27 seat moves per female per day. That's a male:female seat move ratio of 1.44.

The Game Two simulation gives a result of 9.11 seat moves per male per day - bearing in mind, men have to move the seat twice per standing visit, in this version - and women never have to move the seat.

Code here.

Fun fact: Without additional costs and rewards, Game One is always preferable to men, Game Two to women. Regardless of the balance of men and women in a house.

So now you know!


Of course, in some cultures the conflict never really arises, since it is 'the norm' for men to sit for all visits to the lavatory.


Oatzy.


*[inb4 shouldn't p be the probability of needing to urinate lol]

Social Posting - Part Two: We Post Together

Where were we..

So the main limit to the stripped down model in the previous post is that it only puts people into one of two states - posting, or not posting.

A more realistic model would take into account how much people are posting. The nice thing is, the change to the model is only minor - T no longer has the condition that makes its value has to be either one or zero.

The values T_i now represents the post rate of each user - that is, the number of posts posted during some arbitrary time period, n.

Here is the full, modified equation for the model

Two More Things

As you've probably noticed, we've introduced two new variables. They are:

2) Beta

Beta is a column matrix, with values represent each user's baseline post rate - that is, the rate at which a user would post if there was no-one else online - no audience, no-one to talk to.


1) Alpha

Alpha is a little more complicated. But loosely speaking, its values relate to the upper limit of each user's post rate (ignoring external effects).

It works like this: first, imagine everyone has some maximum post rate. Tbar (T with a line over the top) is the column matrix of these values. Now, suppose everyone is posting at their maximum rate. Alpha values are calculated by rearranging the model equation, thus

Any negative values in W are set to 0, since (in theory) a user has their highest post rate when any of their antagonist are not online.

What this means, is that post rates are capped by their appropriate upper limits; when all members of the population reach their maximum post rates, we find that T(n) = T(n-1) for all n - i.e. the post rates all remain constant, unless externally affected.

For technical reasons alpha is a diagonal matrix.

Alpha and Beta look like this

They won't all ways be size 4, of course. Their size will depend on the size of each particular network. The values of alpha and beta could vary over time, but for all intents and purposes, it will suffice to hold them constant.


Rainbow Graphs

Going back to the graph from last time, we might get a system equation like this

In this full model, it's not just a matter of online or offline. So instead of a series of network graphs, we represent the progression of a network as a set of line graphs.

What we find then is that the system described by this equation seems to tend towards some constant, stable point - regardless of initial conditions.

For example, with the equation described above, and starting at T(0) = [1,0,0,0] we get

And even if we start from T(0) = [100, 100, 100, 100], we get

In each case, the system converges to [15, 10, 5, 10] - Tbar - the maximum rates set when defining the variables for this system.


Interestingly, here's what happens when you set beta = 0 for all users - alpha values recalculated as [1.5, 1.11, 0.5, 1.11]

You get this weird bouncing about. It does seem like they're converging towards some fixed points. And it's converging to points roughly in proportion to Tbar, though much lower.

In fact, in online/offline form, the system looks like this

It's this early jumping on and off -line that causes the system to oscillate at first, before starting to settle down as time goes on.

We also see that, because the system starts much lower than its defined stationary point (Tbar), and because it doesn't have the boost of the base-rates, the actual stationary point the system is converging to is much lower.

If, however, T(0) were set to Tbar, then the system would have stayed constant at Tbar. Similarly, if T(0) were set to [0,0,0,0], then the system would stay there, since it wouldn't have the base-rates to get any of them off the ground.


Antagonistic Altercations

If we set up an antagonist system like that in the last post - with beta and Tbar as above, and conjugate alpha - we get a line graph that looks like this

In this case, the base-rates act to temper A's dislike of B, so that B stays online; though the result is that the stable point is lower than the maximum for everyone. The stable point for A is lowered the most.

But if we remove the base-rates (and recalculate alpha accordingly), the system progresses much like it did last time

That is, as soon as B shows up, A leaves - eventually followed by everyone else.


Upping The Tension

Now, what if we change the setup so that A and B both want to avoid each other.

One might question why two people who dislike each other would be 'friends' (in the social networking sense). I dunno. This is a hypothetical situation meant to demonstrate a point, god damn it!

Here's the system equation

Matrix of maximums, Tbar, stays the same as above at [15,10,5,10].

So if we set T(0) = [0, 10, 5, 10], here's what happens

A comes online because of their base-rate, and once they do, B disappears. Here's this system's initial and stable points

In antagonistic systems such as this and the one before, Tbar isn't a stable point.

In this case, for example, the peak rate for A occurs when B is offline and C is at their peak rate. But C is at their peak rate when both A and B are online. So if B is offline, C can't be at their peak rate, and as a result neither can A. And vice versa. So Tbar can't be achieved, since the tension between A and B pushes down the rates of everyone, themselves included.

The system does still stabilise however. It just to stabilises with B offline, and everyone else at a slightly lower rate in this case.


Now, if we do as we did in the previous blog, and take A offline (indefinitely), here's how the system evolves

In this case, the stable rates of C and D are lower than they were when B was 'forced' offline by A. And even though A isn't online, B isn't posting at their maximum rate.


Exogenous Effects

So as before, we also have to consider external effects.

People can suddenly, and unexpectedly disappear - maybe fall ill, get a job, or just not post for a while. Conversely they could find themselves in a situation where they're posting more - maybe because of a major news event, or because they're at work (procrastinating).

We can quite easily create these effects artificially, then observe how the model responds to that change. For example, we could gauge a person's importance (to a network) by removing them and seeing how dramatic an effect that has.

So in the antagonist examples above, we could say that A is more important to that network than B, since removing B had a greater (negative) effect on the C and D.


For this, we define some arbitrary function, E(n). We then multiply our model equation by this function

So for the example last time, where we removed two users C and D, then later reintroduced C, the function(s), E(n), might look like this

Or, if some major news story broke between n=2 and 5, then the function might look like this

So, if we were to, say, remove A (indefinitely) from the top system above, then the result would look like this

The important thing to note here is that even though B is the only person directly linked to A in the network, removing A from the graph lowers the rates of everyone.

Alternatively, we could double A

In this case, multiplying A by two brings everyone else's stable points up. It's also worth noting that A' stable point isn't just doubled, but multiplied by 2.7. This is a good example of the feedback effect mentioned at the start of the previous blog - increasing A' rate increases everyone else's rates, increases A' rate.

Or if we half A

In this case, everyone else' rates drop too, and A's rate stabilises at less than half it's maximum.


Agitated Antagonist

So what if we go back to our antagonist system, and start poking it...

First of all, if we half A

Then B is able to stay online, but with a stable point much lower than their maximum.

But, here's where things get interesting - if instead we double B, here's what happens

This time, they each scare each other off. But, once the other goes offline, they each come back in the next turn, only to scare each other off again. And so on. And all this jumping between extremes makes C and D jump about as well, but half a cycle out of sync.

At least, that's what happens for initial conditions [0, 10, 5, 10]. If we start with all at 0, the behaviour is nearer to that with no external effects.


In General

So it seems to be the case that externally changing one user affects (almost) everyone in the graph.

That being said, I would expect that when the model is generalised to much larger networks, we would find that the greater the distance between two users, the less affect they will have on each other.

It probably stands to reason then that, for a given user, it's only worth considering a graph as wide as friends of friends. Maybe friends of friends of friends for (a collection of) dramatic changes at that distance.

More in general, when you apply the model to a system of more than four people (as we've looked at here), you would expect things to get more complicated.

But the overall results should be similar - that is, in most cases the system will tend towards some stable state. It may just take longer to reach that point, depending on the size of the graph.


In Conclusion


So the long and short of it is this - in most cases, a group's post rates will typically converge towards some stable point.

If there aren't any antagonists, and if the base-rates aren't zero for everyone in the network, then the stable state will typically be the common maximum, Tbar. Otherwise, the system may oscillate, or else become stable at a much lower set of rates.

If we set all base-rates to 0, we find that the systems behave much like they did in the simplified online/offline model discussed in the previous blog; with some quirks of their own.

In the absence of base-rates, or in the presence of antagonists, initial conditions become important, affecting if and where the system stabilises.

When we consider external effects, the same will tend to be true - but with the stable points altered, according to what that effect is.

Modifying one user affects everyone else in the graph (to some degree). Modifying different users will have different effects on the rest of the graph, depending on the 'importance' of that user.

Of course, in the real world, external effects are unpredictable, and will tend to keep the system off-balance (unstable). But we do what we can.


Oh, and if you were wondering how I got the numbers for the graphs, here's the code I used. But be forewarned, it's very sloppy.


Oatzy.


[..and the fundamental interconnectedness of all users.]

Social Posting - Part One: Who's Online?

Coherence of Absence

So imagine it's Sunday, there's nothing to do, nothing's open, nowhere to go, nothing on TV. So why aren't people spending all this free time online - tweeting, Facebooking, whatever?

Sunday is an online dead-zone.

A random hypothesis I thought up to explain this, posits that this may be the result of large numbers of people thinking "why post, if there's going to be no-one around to see it?". After all, no-one's around on Sunday. If they were, they'd be posting stuff.

I called it Coherence of Absence, because a fancy name can make a daft idea sound respectable. The alternative was The Sunday Effect.

Of course, it could be that people mostly social network when they're at work (procrastinating). Or maybe they're asleep/hungover on Sunday. Or have nothing to talk about, since Sundays are so boring. I dunno. I'm unemployed, so Sundays aren't much different to any other day of the week.


In Other Words

So this can be boiled down to two principles:

1. People are likely to post more when there are more people online

2. The number of people perceived to be online at any given time is based on who is posting

It's fairly intuitive that when there are more people online (posting), you'll post more - not just because there are more people to talk to - tweets to reply to, posts to comment on - but also because there's a bigger audience; more people to see what you have to say, regardless of how interesting or mundane that might be.

In essence, these two together create a feedback effect where your posting habits are based on your friends' posting habits, are based on (to some extent) your posting habits. And so on.

For point two, we can't generally say for sure whether or not someone is online, except for when they post something. Though there are exceptions. Of course, the irony of this model is that it assumes that everyone is online all the time - just waiting for someone else to indicate their presence with a post.

Don't get me wrong, I'm not saying this is definitely how the world works. This is more of a, let's suppose this is how it works - what then?

NB/ the people a user follows are referred to as 'friends', since 'the people a user follows' is such a mouth full. These imaginary people may not, strictly speaking, consider each other friends.


Technically

Right, let's dive in: for some network of users, define a matrix M with entries

For example

NB/ connections between users needn't necessarily be two-way (except in the case of Facebook).

Next, we define a column matrix, T(n), with entries

Now, we say that if at least one of a user's friends is posting, then the user will 'come online' and post in the next turn. Vice versa, if none of their friends are posting, then the user will 'go offline' and not post in the next turn.

To do this mathematically, we just multiply the matrix M by the matrix T. For example, if we start with only B online (blue),

Then, as expected, all the people who follow B come online. B goes offline since none of the people they follow were online in the previous turn.

You'd then multiply M by T(1) to get T(2), M by T(2) to get T(3), and so on. Here's another example, starting with only A online,

Easy.


That's Not Normal

The problem with the model so far is that there only needs to be one other person online for a user to join them. But one person online will be more significant to a person following 5 people, than to a person following 100.

So we might instead say, if at least half of a user' friends are online, then the user will join them in the next turn. First of all, we define a matrix, W, with entries,

So for the example above, we get

That is, the matrix M normalised so that the sum along each row equals 1. Our definition of T then becomes

Which is just a fancy way of saying, if at least half of a user' friends are posting, then the user will post in the next term.

So, for example, if we start with A and D online,

As before, everyone ends up online. But in this case, if we had started with only A online, then that means only a third of B' friends are online, so B wouldn't come online in the next turn. Nor would anyone else, for that matter - everyone ends up offline.

Of course, you could change it so that a user will come online if a third, or a fifth, or whatever of their friends are online. If you really wanted to.


Weightlessness

Of course, this supposes that a user cares about all their friends equally. In reality, we might care more about one person being around than another. There may even be people we don't care about at all (in terms of what we post), or people that we want to avoid.

The trick is this - instead of assigning everyone a 1 in the matrix M, let user i assign to each of their friends, j, some numerical weighting, based on how much i cares about j. If i prefers to avoid j, then this value may be negative.

Call this matrix W'. This matrix is, again, normalised to generate W, as before; making the sum along each row equal 1. The only difference is that with antagonists, some rows may add up to 0. So to avoid division by zero we have this

At this point, I'll introduce the equation for the model so far

Avoid the Antagonist

So let's say this is our network now, with accompanying normalised-weighting matrix

B has no qualms with A, but for whatever reason A harbors some secret dislike of B, and will typically want to avoid them. Why does A still follow B? Keeping up appearances, stalking? I dunno. Let's just pretend there's a good reason.

So, for example, if we start with A, C, and D online, here's what happens

B comes online because both their 'friends are online. But B coming online effectively scares everyone else off, one by one. Admittedly, that's partly because I specifically chose weightings that would cause this to happen. But you get the idea.

Of course, once B goes offline, A might decide to come back online again, with D and then C following shortly after. At which point, we end up back at the start (1), where the cycle repeats.


Can't Talk

For this we go back to the first graph above, weightings all the same. Say one or more of the users go offline - maybe they're out on the town, or asleep, or something of that sort. What then?

If we take just one person offline, then nothing will happen to any of the other users - except if you remove B, in which case only A goes offline. So in the below example we take C and D offline (red)

By (4) everyone is offline, so that when D comes back online at (5) there's no-one else online to keep them around. And D alone isn't sufficient to bring anyone else back online.


Wait For It

So this is a very simplified model. For one thing, it only considers people as either online or offline - or if you prefer, posting or not posting. It also assumes that, in the absence of an 'audience', a person won't post. And that leads to the implication that a social network can be destroyed by strategically removing users. It can't. I don't think.

Anyway, til next time..


Oatzy.