Monthly Archives: November 2014

DONALD revisited

When one claims that an AI system has solved a problem, it is important to specify how this problem has been defined: what is the problem really solved.

Let us again consider the DONALD problem. I chose to give CAIA a formulation using the carries that we are using when we are performing an addition. Nevertheless,  many other formulations are possible, and I tried another one: each number is represented by the sum of its digits multiplied by the correct tenth power. In that situation, apart the constraints indicating that the first letter of each row is not zero, only one constraint remains. For DONALD, it is:
100000*D+10000*O+1000*N+100*A+10*L+D+100000*G+10000*R+1000*A
+100*A+10*L+D=100000*R+10000*O+1000*B+100*E+10*R+T

CAIA also solved the problem given in that way, but it's not as good: in the most favorable situation, where it tries to develop a very small tree, the tree developed has 15 leaves instead of only 2 with the carries. When it starts with a combinatorial program, the tree has 5,544,820 leaves instead of 262!

Therefore, it is obvious that the choice of a formulation of a problem can drastically modify the performances of a solver.

AI researchers spend a lot of time finding the best formulation for their system. They can even add constraints that they have themselves found. Particularly, they could give useful constraints found by CAIA for instance, indicating that E has only two possible values, 0 and 9. In the experiments described in Thinking, Frederic Bartlett was more helpful, indicating that the value of D was 5. With this information, CAIA directly finds the solution: as D=5, T=0 therefore, E is not zero, which leaves only 9 as a value for E, and the end is easy.

I could increase the possibilities of CAIA for modifying the initial formulation. For instance, I would give it more rules using modular arithmetic so that it could find the formulation with carries from the one given above. I did not do it because it would be useful for just two families of problems: crypt-additions and crypt-multiplications, while CAIA has more than 200 families of problems. I try to avoid giving  too many ad-hoc rules, which are useful for few families.

Finding a good formulation is not always easy, it requires a large problem solving culture. Bartlett gave the problem in a visual form:
  DONALD
 +GERALD
  ROBERT
This formulation is very different from the preceding ones, but all the successful solvers in this Bartlett's experiment mentioned at least once the carries. Therefore, introducing carries is a natural step.

Evidently, the formulation using carries is better for solving the problem: with the other formulation, there is one constraint with nine unknowns. Eight instantiation are necessary for finding the value of the ninth unknown. With the carries, there are constraints with 3, 4, or 5 unknowns. Knowing the value of two unknowns in a three unknowns equality immediately gives the value of the third one. The combinatorial search is more efficient because one can see sooner the consequences of a choice. With the intelligent method, one creates new constraints with few unknowns.

For this reason, being clever does not reduce very much the size of the tree when one has received a good formulation of a problem: with the carries, 2 leaves instead of 232. On the other hand, the improvement when one uses the intelligent method is spectacular with the formulation without carries: 12 leaves instead of 5,544,820 leaves.

Finding a good formulation is fundamental for quickly solving a problem. AI researchers choose a formulation well suited for the method that they have defined; therefore, they are working for their system, doing the most difficult and important part of the job. The intelligence is in the researcher, and not in the AI system. I did it myself, choosing a good representation for crypt-additions, using the carries. However, as CAIA generates new constraints, it can move far away from the initial formulation.

Problems are often defined in a natural language, or with a drawing as Bennett did for DONALD. Unfortunately, as we will see in future posts, it is difficult to extract the useful information. Moreover, ambiguities are often present, especially when one uses a natural language. Removing them can lead to very different problems: which is the good one?