Thursday, October 06, 2016

Psychology Experiment: How Does the Human Brain Unscramble Words?

Oddly enough, many neuroscientists and psychologists don't appreciate that insights from the study of algorithms and the theory of computation are very relevant to understanding the brain and how it accomplishes what it does.

Here's an example. Consider the humble jumble, a game involving scrambled words that's been around for over 60 years. Players get words of length 5 or 6 and have to unscramble them. How, exactly, does the brain do that? And why are some words harder than others to unscramble?

Computer scientists will instantly think of two different algorithms. The obvious algorithm, given a word of length n, takes about n! log D time, where D is the size of the dictionary. To accomplish this, try all n! permutations and look each up using binary search in the dictionary, which we have presorted in alphabetical order.

A less obvious but much faster algorithm is the following: first, sort each word in the dictionary, putting the letters in each word in alphabetical order. Then sort these words relative to each other in alphabetical order, together with the original unscrambled version. Once this preprocessing is done, to unscramble a word, rewrite its letters in alphabetical order and look up this reordered word in our reordered dictionary, using binary search. This takes about (n log n) + log D time, which is enormously faster.

With other techniques, such as hashing, we could even be faster.

I doubt very much the brain could be using this second algorithm. That's because we probably don't have access to all the words that we know in any kind of sorted list. So probably some variant of the first algorithm is being used. Our brains probably speed things up a bit by focusing on word combinations, such as digrams and trigrams (two- and three-letter word combinations), that are common, instead of uncommon ones. Thus, I would expect that unscrambling length-n words with distinct letters would, on average, require time that grows something like (n/c)! for some constant c.

We could actually test this with a psychology experiment. I searched the psychological literature using a database, but found no experiments testing this idea. Are there any takers?


Jeffo said...

You should collaborate with psychology faculty on this experiment. The idea reminds me of Claude Shannon's famous experiment regarding entropy in English, in that it focuses on human ability to identify words with partial (in this case corrupted) information.

I agree that di/trigrams are important to solution time; the most challenging unscrambling problems (for humans) usually involve unusual letter juxtapositions.

It seems like machine learning is another area that could inform psychology experiments.

George said...

As a solver, I consider a letter as starting a word. If it is not a vowel, there are a lot of constraints on the second letter. It is likely that the second letter will be a vowel, so I search these combinations first. Not sure if this is the greatest strategy, I was never that good at Boggle.

George said...

Oops, I'm not familar with Jumble, I though you were referring to Boggle!

Dmswart said...

I made jumbles for a company news letter once upon a time. Two things I noticed from my experience which you might use as hypotheses / experiments:

1. I noticed words with the consonant/vowel patterns like 'piano' (i.e., cvvcv) seemed very tricky.

2 I also noticed rewriting the letters into a triangle (arranged like a human pyramid) helped with solving. (We called it the 'pyramid of clarity')