image provider

A Tractable Artificial Intelligence Problem


Disclaimer

This essay does not describe an existing computer program, just one that should exist. This essay is about a suggested student project in Java programming. This essay gives a rough overview of how it might work. I have no source, object, specifications, file layouts or anything else useful to implementing this project. Everything I have prepared to help you is right here.

This project outline is not like the artificial, tidy little problems you are spoon-fed in school, when all the facts you need are included, nothing extraneous is mentioned, the answer is fully specified, along with hints to nudge you toward a single expected canonical solution. This project is much more like the real world of messy problems where it is up to you to fully the define the end point, or a series of ever more difficult versions of this project and research the information yourself to solve them.

Everything I have to say to help you with this project is written below. I am not prepared to help you implement it; or give you any additional materials. I have too many other projects of my own.

Though I am a programmer by profession, I don’t do people’s homework for them. That just robs them of an education.

You have my full permission to implement this project in any way you please and to keep all the profits from your endeavour.

Please do not email me about this project without reading the disclaimer above.

This is a fairly simple artificial intelligence problem that mimicks, in miniature, the problem computer programmers have extracting specifications from users and turning those specifications into code.

Have a look at The Learn To Count Applet, particularly the source code. It contains code to count out in words in various languages.

I wrote the class for each language by getting a set of example numbers and words from a native speaker or a phrasebook or by sampling Internet posts, e.g. 21 == vingt et un in French and deducing the rules for converting numbers to words and writing the code. I would then print out a set of sample numbers using the rules (selecting the samples to ensure I cover all the rule variants) and check them with a native speaker. He would then give me some more examples to explain the exceptions to the rules he had forgotten about previously. I would then convert those exceptions into rules, code them and go round again until the native speaker was happy. Sometimes the native speaker would tell me the rules directly. Usually, these were less useful and less ambiguous than two or three examples.

I discovered there were various patterns in the rules. Different languages had various combinations of the standard patterns.

The process was fairly easy, quite mechanical and allowed for a fair bit of trial and error rather than demanding brute reasoning.

Could you automate the task of writing code for additional languages?

Could you write a program that, just shown some counting examples from a foreign language, could compose a program to generate all the longs out in words? The answer is yes, you could write such a program, no problem, though it would be cheating . It would just require a bit of patience to manually write the code for each human written language, then recognize it and cough up the previously optimised code when handed a set of examples in that language.

What we want is something a little cleverer, that could work on a language it had never seen before, but that was a human language. Again you could cheat, in a lesser way this time, my simply cataloging all features of counting in all written human languages, writing custom code to recognize each feature and cranking out code by turning on or off pieces of preformed boilerplate.

One way to attack the problem is to ask yourself, "How could I rapidly generate, generalise and optimise the cheating solution?" Another is, how could I solve the simpler problem of just handling the 20 or so languages the Learn To Count Applet already knows, or some subset of them.

So think of it as a contest. You will be handed a Java class, that will accept a long positive or negative and will return you a String for the corresponding number in words in the target language. Your program will then, by probing the class for examples and making inferences, construct a program that reproduces the one inside the black box to convert numbers to words for the unknown language inside the class.

You get points for:

  1. Elegance (mathematically simple and ingenious)
  2. Generality (ability to handle various curves thrown at it.)
  3. Compactness, speed and beauty of both the code itself and the code generated.
  4. How accurate generated code is.
  5. How few calls to the black box class to generate examples you required. Only unique samplings count. There is no penalty for asking for the same number more than once.
  6. If you want a slightly simpler problem, for fewer points, assume you are given a bit map of interesting examples to start, that cover at least one example of each of the quirks of the language. You may still need to probe other numbers to test your assumptions about the patterns behind those examples.
  7. You get bonus points if you can also generate code to go the other way, take a word accurately spelled out in numbers in the foreign language and convert it to a long.
  8. You also get bonus points for being the first to submit a long->words class with Java source for any actual human language to the Learn To Count class library. There is no point in great duplication of effort there.

This page is posted
on the web at:

http://mindprod.com/project/ai.html

Optional Replicator mirror
of mindprod.com
on local hard disk J:

J:\mindprod\project\ai.html
Canadian Mind Products
Please the feedback from other visitors, or your own feedback about the site.
Contact Roedy. Please feel free to link to this page without explicit permission.

IP:[65.110.21.43]
Your face IP:[44.200.122.214]
You are visitor number