Archive

Archive for May, 2010

Hangman

Inspired by Peter Norvig’s essay about writing a spelling corrector, I was recently working on a puzzle and thought that it would make a good essay: I am attempting to write a program that can win Hangman.

The idea behind Hangman is simple: guess letters that are in the hidden word, and if you get all the letters then you win. Every time you get another letter wrong, draw another body part on the hanged man. Once he is fully drawn, you lose. (This man is represented in my program by a counter that goes up to some number. I call this the number of guesses you’re allowed to make, although strictly speaking it’s the number of incorrect guesses.)

Without trying to predict what word your opponent might choose, which would require some serious artificial intelligence programming, the optimal strategy is to select whichever letter is the most likely to be in a word like the one you’re looking at. The simplest way for a computer to do this is to have a list of letters by letter frequency, and then simply guess each letter in turn. The code looks like this:


frequency = "esiarntolcdugpmhbyfkvwxqjz" # This is letter frequency in dictionary words, and doesn't take into account that some words are more common than others.

while True:
letter = frequency[1:]
frequency = frequency[:1]
if hangman.guess(letter) == win:
break

The problem with this method, as you may have guessed, is that it is extremely unreliable. When you’re allowed six guesses, it only gets the word 11% of the time. When you’re allowed four guesses, that figure drops to 3%.

A better method is to consider that letter frequency is relative. Depending on what words you’ve eliminated already, the most probable letter is going to be different from just the next on the list of letter frequency. For example, if you have a word such as “___in_”, it is very probable that the last letter is a ‘g’ — even though the letter g is not very common in general. This simple change bumps up the 11% figure to a surprising 92%.

Next I tried something that is rather easy for humans. It is clear enough to us that all words have at least one vowel, so the program should recognize this too. I modified the program so that it would keep guessing vowels until it found at least one. Perhaps surprisingly, this only improved the program by 1% — barely a statistically significant margin, given how many trials I did. Perhaps the improvement would be more noticeable if the win ratio wasn’t already so high.

The ‘executioner’, as we may call the program that decides upon the word, was as yet not doing anything clever. It was time to change that. I wrote a simple method designed to evaluate how difficult a given word is: take the average of the rarity of each letter in the word. Then I had the executioner look through some number of words and pick whichever one is decided to be the hardest. When it looked through 50 words, the win ratio dropped to 72%; when it looked through 500 words, it went all the way down to 49%.

Given the current program, it seems like the optimal strategy for the executioner is simply to find the hardest-to-guess word and pick it every time. This might fool a computer, but it wouldn’t fool a person. The next step is to add some pattern recognition to the program.

This is the basic idea of how I was able to write a pretty powerful Hangman program for both sides. I was able to collect some data regarding the success of the program. It’s not a whole lot, but it gives you a rough idea of how successful the program is. Players were allowed six guesses: head, body, arm, arm, leg, leg.


human guesser: 2 wins against computer, 2 wins against human; 6 losses against computer, 10 losses against human
computer guesser: 7 wins against human; 2 losses against human

It is worth noting that humans seem to be much better at coming up with words than at guessing them, whereas the computer is about equally good either way when using the more sophisticated algorithms. But on both counts, the computer performed much better than the people did.

Unfortunately, one thing that humans are bad at and computers are not is pattern recognition. If many more trials had been done, the human players would have started guessing rarer letters. The computer assumes that rarer letters such as q and z are harder to guess, and so finds words that contain them (words like “buzz” and “minx”). The humans were already beginning to notice the abundance of rare letters.

Currently, the biggest flaw in the computer is that if you are the executioner and you give it the same word over and over, as long as the word is hard enough, the computer’s guesser will lose every single time. The necessary improvement there is clear enough, but actually implementing it could be tricky. I’ll leave that as an exercise to the reader . . . for now.

The Hangman Challenge

I recently wrote about a computer program that tries to win Hangman. With my current version, I wrote both the guesser and the executioner. But that’s not going to be very innovative. To try to make the Hangman program even better, I propose a competition. People design both a guesser and an executioner. Then, the guessers and executioners designed by different people go head-to-head, and we see who gets the most wins. Right now I can’t offer any sort of prize (and if I did it would create a conflict of interest), but I think it will be useful and fun.

Details:

The programs shall be written in Python. It is an easy language that a lot of people know, but more importantly, it’s the language that I wrote my original program in.

I have provided a skeleton program, which you can get here. Use the classes and methods in this skeleton to write your program. This is to make it easier to coordinate interactions between multiple programs. This package also contains my contact information.

There is no limit to the number of submissions per user. If you have more than one idea, by all means submit more than one program. The idea here is to find the best algorithms.

After there are enough submissions, or after a long enough period of time, I will publish the results.

If you submit a program, its contents may be released to the public. Do not submit anything that you do not want published.

I think that about covers it. So write some Hangman programs, and have fun!

The Interpreter, Chapter 3

The continuing story of one man’s quest to write an interpreter.

There is one very important thing that every language needs: variables. How was our hero going to implement variables?

Before it could use variables, the interpreter had to be able to handle hash tables. Jackson looked online for a hash table library, and found a pretty good one. Unfortunately, it could only map strings to strings. The interpreter was using a dynamically typed system, and it needed to be able to have anything as a key and anything as a value. Despite having no idea how to worked, Jackson was faced with the task of implementing a hash table. And, lo and behold, after twenty minutes of Wikipedia-reading and three hours of struggling with implementations and bugs, a working hash table was born.

But just how good was this implementation? Jackson ran some benchmarks against the string hash table he had found online — his was a mere tenth as fast. He knew he could do better. So he spent the next three days trying to improve the system. As it turned out, his hash function was far too slow. Converting every value to a string and then using a hash function on a string was taking a long time. So he wrote a hash function that could handle different data types. There were more collisions (that is, two different values hashing to the same number), but it was worth it to make the hash function three times faster. At that point, Jackson accepted that it was simply impossible to make a hash table for any value as fast as a hash table for only strings; the program was fast enough.

Next, it was time to implement variables. The interpreter contained a hash table with variable names pointing to actual values. In fact, variables proved surprisingly easy to implement. It only took a couple of hours before they had full functionality.

The program had progressed surprisingly far, but many basic functions — exponentiation and logarithms, among others — still did not work. Floating-point numbers in GMP were insufficient. A supplementary library, MPFR, was added to provide additional support. It had the power to do exponents and logarithms for not just positive integers but for decimals and negative numbers as well. The initial stages were complete.

Chapter 4

Categories: The Interpreter

Hostage Situations

May 12, 2010 1 comment

A hostage situation is a pretty common scenario (at least in movies). I often find myself questioning the actions of those involved. So I was wondering, what is the right decision in a hostage situation?

The captor is holding a single hostage, and demands something in exchange for release of the hostage. For the sake of simplicity, let’s say it is a million dollars. The negotiator has the money, and is negotiating with the captor.

The simplest set of possibilities is this. It’s very similar to the prisoner’s dilemma. Both players (captor and negotiator) can either cooperate or defect.

1. Both cooperate: Captor gets the money, hands over the hostage and escapes. Everybody wins.
2. Both defect: Negotiator doesn’t pay the captor, and the captor doesn’t hand over the hostage. The situation is the same as before.
3. Cooperate/defect: Captor hands over the hostage, but isn’t paid. Captor loses.
4. Defect/cooperate: Captor is paid, but doesn’t hand over the hostages. Negotiator loses.

In a single play, the only smart strategy is to defect. But in an iterated game, other strategies prevail.

This alone is not very interesting in itself, because it is identical to the prisoner’s dilemma. But things start to get more interesting once complications are added.

Complication 1: Killing

The captor may at any point kill the hostage. This is very bad for the negotiator, but ensures that the captor will not receive payment. Also, there is the possibility that the captor will be arrested.

At this layer, the captor should not threaten to kill the hostage. Rather, he should threaten to keep the hostage captive until the money is paid. If the hostage is killed, the captor loses all bargaining power and both parties lose.

Complication 2: Unequal Values

There is also the fact that the hostage’s life and the million dollars are not equally valued. It is possible that if the captor kills the hostage, even if he loses his million dollars, then the loss of the negotiator is a good deal greater. Since the negotiator is trying to maximize her own needs regardless of what the captor gets (at least theoretically), she will not risk the captor being killed. If the pays the million dollars but the captor still refuses to give up the hostage, this is still better for the negotiator than if the hostage were killed. But even if the captor loses the million dollars by killing the hostage, this is no better or worse than if the negotiator refused to pay the million dollars — the money is lost either way. So the negotiator has a much stronger incentive to keep the hostage alive.

Complication 3: Arrest

If the captor still has the hostage, then he is safe from arrest because he can use the hostage as leverage. But if he kills the hostage, then he can be arrested — he has lost his leverage. He cares more about his own life than the negotiators care about that of the hostage, so he has the strongest incentive yet to keep the hostage alive. The negotiator knows that a fail to pay could in result in the killing of the hostage followed by the arrest of the captor, which is even worse for the captor. It would seem that the captor no longer has an incentive to kill the hostage, which means that the negotiator no longer has an incentive to pay.

But this is not so. Remember that neither side cares if the other loses, only if they themselves win. If the captor assumes that he will be arrested if he kills the hostage, then he has no reason to kill the hostage — even if the negotiator tries to arrest him while he still has the hostage. He goes to prison either way. He no longer has an incentive not to kill the hostage, which means that the negotiator can’t expect him not to.

Despite these complications, the best way to try to maximize one’s own gain is still to defect. The captor has no incentive to release the hostage after being paid, because if he does he may be arrested. Therefore, the negotiator has no incentive to pay the money. Therefore, the captor has no incentive not to kill the hostage. Therefore, the negotiator has no incentive not to arrest the captor. Everybody loses.

This all changes, of course, in iterated hostage situations and in multiple hostage situations.

Notice that this is all just speculation; there are plenty of other options one could include in the scenario. Although I find it fascinating, I don’t know much about game theory, so I may be wrong about this reasoning.

How do other factors change the situation? Is there any way to ensure that everyone gets what they want? Discuss.

Categories: Math

Background for My Critique of “Imagining the Tenth Dimension”

In my critique of Imagining the Tenth Dimension, I referenced a couple of concepts that you may not understand very well: The Mandelbrot Set and Aleph One. This is an attempt at explaining what you need to know about those concepts in order to understand what I was talking about.

First is the Mandelbrot set. It was proposed by Beniot Mandelbrot, who effectively invented fractal geometry and is one of the most brilliant mathematicians alive today. The Mandelbrot set is a type of fractal. What is a fractal? Well, a fractal is a type of object that has self-similarity. If you zoom in on the object, it looks similar to the object as a whole. This is very useful for modeling real-life systems. Look at rocks, for example. Have you ever noticed that a small rock looks a lot like a boulder? That, if you look up close at one part of a boulder, it looks like it itself could be a boulder? Trees exhibit the same behavior: a twig with leaves on it looks like a smaller version of a tree. This is true for many types of objects.

As explained by a song:

Take a point called z on the complex plane. Let z1 be z squared plus c. Let z2 be z1 squared plus c. Let z3 be z2 squared plus c. And so on. If the series of z’s will always stay close to z and never trend away, that point is in the Mandelbrot set.

So when you do this, you end up with a graph that looks rather complicated, but exhibits self-similar properties: if you zoom in on some spots, it looks the same as the whole picture.

How does this relate to dimensions? Well, traditionally the Mandelbrot set appears on a two-dimensional graph. There is one axis for the real numbers and one for the imaginary numbers. But the set is actually three-dimensional; the third dimension is simply not represented using a spatial dimension. Instead, it is represented using color.

What is this third dimension? Well, some areas of the graph are black. A black point is part of the Mandelbrot set. But if the point is not part of the Mandelbrot set, then it is given a color, where this color represents how long it takes for the point to diverge. This is a pretty useful example of representing a dimension using something other than space.

Aleph One

This concept takes much more explanation, so try to bear with me.

Infinity was not a particularly well-understood concept until the invention of Set Theory by Georg Cantor, around the end of the 19th century. Cantor was considered to be insane by many of his contemporaries, but that’s not really the point. The point is that he effectively defined how to look at different infinities.

Cantor defined infinity in terms of infinite sets. For any finite set with N elements, the infinite set has more elements than that. The simplest example here is the set of all natural numbers. This set contains the number 1, the number 2, the numbers 3, 4, 5, 6, and so on. Any natural number you can possibly think of is contained within this set.

There are also other infinite sets of the same size. (When two sets have the same number of elements, we say that they have the same cardinality.) To prove that two sets have the same cardinality, see if you can match all their elements in a one-to-one correspondence. If you can match every element in set A to an element in set B, then the sets have the same cardinality. This can be used to prove that two infinite sets are the same size.

From this we can infer that any set of numbers that can be listed out (even if it takes forever to finish) has a one-to-one correspondence with the natural numbers; that is, the sets have the same cardinality.

Look at the set of all integers (both positive and negative whole numbers). You could try listing 1, 2, 3, etc, and when you’re done you can list 0, -1, -2, -3, etc. But the problem is, you’re never done so you’ll never get to list the negative numbers.

But there is a solution. You can list out every integer by alternating: 0, 1, -1, 2, -2, 3, -3, etc. If you continue this process, it’s impossible to name an integer that won’t be contained within this set.

It’s also possible to list every fraction and mixed number; the actual process is rather difficult to explain in a blog format, so see this page for a fun explanation. (Edit: It looks like that site is down. See this one instead.)

What about the real numbers? Surely there must be some way to list them out. To make it simple, let’s just list every number from 0 to 1. Here is such a list, in no particular order.


0.018374020....
0.487384738....
0.297998172....
0.693729348....
0.382749207....
....

Since we are talking about all the real numbers (both rational and irrational), most of these numbers will have an infinite decimal expansion.

Now we can prove that there are more real numbers than naturals by showing that it is impossible to list every real number, even given an infinite amount of time. Move down the list in a diagonal path and change every digit to something else. For example, in the first number change that 0 to a 1, in the second number change the 8 to a 9, then change 7 to 8, 7 to 8, and 4 to 5. Use these changed digits to create a new number: 0.19885…. Once you go through the entire list, you’ll have a new number. Since this number is different from every other number by at least one digit, you now have a number that you did not include on your list. But your list was infinitely long; how is this possible?

What this means is that it is actually impossible to list out every real number. Therefore, there are actually more real numbers than there are natural numbers.

Sets of infinity are named using Aleph numbers. The first infinity, that of the natural numbers, is called aleph naught. The second infinity, the infinity of the reals, is called aleph one.

This should give you a good enough understanding of the concepts to understand their relevance to my original post. If I didn’t explain it well enough, or if you want to know more, you can find plenty of information on the World Wide Web.

Categories: Math