Playing Jumble and Numble


Jumble

Consider the game of Jumble frequently found in newspaper puzzle sections. Typically, 5 or 6 letters are given, and the goal is to unscramble them into an English word. Writing computer programs to work on this puzzle and a related one called Numble (which we’ll describe later) is the subject of two essays in Fluid Concepts and Creative Analogies. The first essay, by Douglas Hofstadter, is on the Jumble problem.

There’s one obvious way of writing a computer program to solve Jumbles. To do this in the stupidest way possible, let the computer access a dictionary, and try out all permutations of the letters. Even if there are 6 distinct letters, there are only 720 combinations; this is a very speedy process.

Speedy indeed, but it’s completely antithetical to the way humans think about this problem. A human will invariably look for common letter patterns and try to make them into blocks.

Consider, as an example, the jumble "toonin." For those people who are sufficiently practiced at anagram puzzles, the solution may pop out immediately. For those of us who are not quite so good (like me), we have to think a bit. Here is one possible approach that works really well for this example. The letter sequence "tion" is very common at the ends of words; those letters are all present. When we subtract them, the remaining letters are "on." So, we anagram those. There are two natural possibilities: "ontion" and "notion." The second is a word; the first one isn’t.

But I didn’t have to look for the string "tion." I could have looked for other common strings instead. I could have considered "int" to be a common string, and then I would be left with "oon." Then I would have tried to play around with those letters to see if I could come up with a word.

So, there are a few pointers for how a program might approach the Jumble problem. What Hofstadter actually did when writing his program, Jumbo, is a bit more subtle, but it still follows the same basic ideas. He was inspired by two models: the bonding of atoms into molecules, and dating rituals.

In chemistry, certain atoms (or, more generally, ions) have affinities for bonding with other atoms or ions to form larger molecules. However, the process is very nondeterministic: if we imagine various parallel universes with the same starting configuration of atoms, we might see different molecules forming. But, some molecules are more likely to form than others. A very highly negatively charged ion is likely to bond with a very highly positively charged ion, but is less likely to bond with a moderately highly positively charged ion, and it will not bond with another negatively charged ion.

Similarly, in the dating world (about which, I hasten to add, I know nothing except as an outside observer), various people are likely to form dating groups, but it’s not guaranteed that the same n>=2 people will always form a dating block. (I absolutely refuse to require n=2.) Rather, there are just certain tendencies.

Let’s return to the situation of Jumble, and we’ll see how the formation of blocks, or gloms, can be visualized. Hofstadter thinks of them as floating around in a sea he calls the cytoplasm. From time to time, two gloms will meet, in a certain order. If there’s a high affinity between the two gloms, in that order, they are likely to join together to form a larger glom. On the other hand, if there is a low affinity between them, they are unlikely to join together to form a larger glom. For example, if the letters "s" and "h" meet, in that order, it’s quite likely that they will form a glom. However, if they meet in the other order, there is no affinity between them, so they won’t form a larger glom.

But wait! There are words which contain a substring "hs." Will we just not be able to find those words? Actually, we will. The point is that words containing a substring "hs" don’t contain that substring because those letters want to be adjacent; rather, they contain that substring by accident, because the "h" is the last letter of some syllable, and the "s" is the first letter of the next syllable, for example. So, the larger gloms (possibly syllables) have affinities for each other, even though the individual letters do not. Thus, the words get formed in a linguistically coherent manner, rather than simply as strings of letter.

Of course, as in the molecular world or the dating world, gloms can also be broken. This can happen either by internal stress, or by external pressures. One possible cause of internal stress might come from the inability to play well with other gloms. If a glom can’t fit together nicely with any others, it might break up. External pressure is caused by the appearance of a more attractive letter or glom to pair with. A glom might or might not survive a bit of internal or external pressure, with some probability based on how strong the pressure is.

I think that’s a pretty good picture of the Jumble universe that Hofstadter created. There are lots more details described in Hofstadter’s essay "The Architecture of Jumbo," which you can read if you’re interested in the specifics.

Numble

The other game I’ll discuss is a game popular in France, called "Le Compte est Bon." However, due to its similarity with Jumble, Daniel Defays prefers to refer to it as Numble. In this game, we are given a target number, and five other numbers. The goal is to reach the target number by adding, subtracting, and multiplying the five other numbers, but only using each one at most once. I’ll write the game as follows: Target number, followed by a colon, then the five other numbers. Here’s an example:

114: 11, 20, 7, 1, 6.

How do we solve this problem? One possibility is to try to get close by doing arithmetic that doesn’t involve (much) calculation. In this case, we might recognize that 20*6=120 is close to 114, so we’ll start there. Now, we need to subtract 6, and we have 11, 7, 1 left. We can get 6 as 7-1. Hence one solution is 114=20*6-7+1.

That seems to be the solution that people are most likely to give. However, there’s a shorter solution (meaning, one that uses fewer of the given numbers): 114=(20-1)*6. Why should this solution be harder to find than the other one? Because we’re more comfortable multiplying by 20 than we are multiplying by 19. Hence, we’ll look at that first and only backtrack if we can’t make it work.

I played the 24 game quite a lot when I was in high school, so my first intuition upon seeing this game was to factor the target. Had I done that with this problem, I would instead have been led to the shorter solution.

However, this is in general not a great strategy. It works well in the 24 game because 24 has a lot of factors relative to its size, so it’s very likely that there will be a solution that looks like 8*3 or 6*4. These are more common than the solution of, for example,

24: 2, 5, 7, 9 (use all of them).

(My solution is 24=7*5-9-2.)

I should have known better though, even from my own past experience. When I was a student at SUMaC, I played the 73 game (which is the same as the 24 game, but with 5 cards, and a target of 73). Of course, the 73 game is much, much more difficult than the 24 game, for several reasons. Perhaps most importantly, 73 is prime, whereas 24 is, one might say, very composite. (I don’t know exactly what "very composite" means; just composite isn’t enough, since the 26 game will be substantially more difficult than the 24 game, but abundant also isn’t enough, since every multiple of 6 (other than 6 itself) is abundant.) But there are other difficulties in the 73 game. We’re less comfortable with arithmetic in the vicinity of 73 than we are with arithmetic in the vicinity of 24, so the patterns don’t pop out quite so readily. Finally, it’s harder to juggle five numbers than it is to juggle just four.

A better strategy, as outlined in the case of 114 above, is to use two numbers (if possible) to get close, and then use the rest of the numbers to fine-tune the solution. Here’s another example:

87: 8, 3, 9, 10, 7.

Two fairly obvious solutions are 87=8*10+7 and 87=9*10-3. These two are probably roughly equally easy to find.

Now, compare the following two problems:

25: 8, 5, 5, 11, 2.
102: 6, 17, 2, 4, 1.

Probably, nearly everyone will solve the first one as 25=5*5 (although, when I saw this problem, I immediately found 25=11*2+8-5 and looked no further). People see 5*5 and immediately know it’s equal to 25 without having to think at all. Now, what about the second one? People might suspect that 6*17 is going to get us close to 102, without realizing that 6*17 is actually exactly equal to 102. So, while these two puzzles can both be solved with just two numbers multiplied together, they feel different: in the first case, we knew, by virtue of past experiences, that 5*5 was the right solution, whereas in the second case, our number sense told us that 6*17 would put us on the right track, but only after we actually do the calculation (rather than refer to our ingrained knowledge that we have by virtue of the rote memorization we did when we were 5 years old, or somewhere around there) do we realize that we have solved the problem.

Let’s look at just one more example before discussing a general algorithm.

146: 12, 2, 5, 7, 18.

We know, from rote memorization, that 144=12*12, and 144 is close to 146. Furthermore, we have a 12 already handed to us. Can we make another one? Yes: 7+5=12. So, we start with 12*(7+5). Now, we need to get 2 from 2 and 18. Since one of those number is a 2, we know that a solution is 146=12*(7+5)+2.

What we did here was to form bricks that we were most comfortable with: one was the 12 already handed to us, and another was the extra 12 we built from 7+5. Then we searched around for a solution to a much smaller and, one hopes, easier problem.

The strategy that the program, Numbo, takes for solving these problems is very similar to the strategy that Jumbo takes for solving jumbles. Given the target, various subtargets are appealing to various degrees, and numbers are likely to form gloms if they are helping to get closer to the target. For example, in the 146 problem, the program will recognize, as a human would, that 144 is a nice subtarget. When various numbers collide in the cytoplasm, they are likely form gloms if they have some 144ishness. Naturally, 12 has a lot of 144ishness, as does a combination of 7 and 5.

The program, trying to emulate human thought processes, understands that multiplying certain numbers is more appealing than multiplying others. Hence, in the first example (with target 114), the program will be happier multiplying 20 by 6 than it will be multiplying 19 by 6. Defays gives a full transcript of the program’s thought process on that example, and he shows that it does indeed find the human solution of 20*6+7-1, rather than (20-1)*6. This, of course, is in contrast to a more brute-force search, which might first try to go through all possibilities with one number, then with two, then with three, and so forth.

Unfortunately, as I understand it, the program does not recognize analogies well. For example, to a human, it is almost as obvious that 22*3=66 as it is that 2*3=6, because we see the two as being analogous. Thus, in problems in which this is likely to be an important step, the computer may have more difficulty than the human. It is unclear to me what to do about this difficulty, but as the entire book is about analogies in human thought and artificial intelligence, I expect that the later essays will help to shed some light on this problem.

Advertisements

About Simon

Hi. I'm Simon Rubinstein-Salzedo. I'm a mathematics postdoc at Dartmouth College. I'm also a musician; I play piano and cello, and I also sometimes compose music and study musicology. I also like to play chess and write calligraphy. This blog is a catalogue of some of my thoughts. I write them down so that I understand them better. But sometimes other people find them interesting as well, so I happily share them with my small corner of the world.
This entry was posted in AI, book reviews. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s