After finding symmetries, CAIA tries to find solutions to the magic cube problem, applying rules that enrich its formulation.

One of these rules states that, when there is a bijection between a set of unknowns and a set of values, the sum of the unknowns equals the sum of the values. Therefore, CAIA adds the constraint:

F(1)+F(2)+f(3)+…..+F(26)+F(27)=1+2+3+…..+26+27=378

When it substitutes the first three constraints in the preceding one, it sees that 3*VAL=378, so:

VAL=126

Using this value, and after many substitutions in the constraints, it finds several constraints with four unknowns, such as:

F(5)+F(23)=F(13)+F(15)

Later, it discovers a constraint with three unknowns:

 F(5)+F(14)+F(23) = 42

Using the symmetries, it immediately adds two other constraints with three unknowns:

F(11)+F(14)+F(17) = 42

F(13)+F(14)+F(15) = 42

All the other symmetries lead to one of the three preceding constraints.

Finally, it happens that it has no more rule to apply. CAIA can choose between two possibilities:

1. It chooses an unknown, and it examines what happens when it substitutes it by one of its possible value. It carries on this task, instantiating an unknown, then generating new constraints, until it finds a contradiction or a solution. In both cases, it backtracks, instantiating the last unknown by the following possible value. CAIA is not very fast: it finds a solution every three seconds, taking into account that a new solution immediately leads to 47 other solutions, using the symmetries.

2. It writes a combinatorial program, cleverly using the constraints that it has found. This C program has 280 lines. CAIA compiles it, and executes it. Then, it finds 130 solutions every second.

In both cases, it chooses to begin backtracking with F(14), the small cube in the center of the large one. There are many solutions for each of the 27 possible values for F(14).

Here is one of these solutions:

 Its success is mainly due to its analysis of the problem formulation: it finds symmetries, and collects useful new constraints, particularly the three constraints with three unknowns. I did not know them myself, I had only found constraints with four unknowns. Naturally, when one knows that they exist, it is easy to prove them.

A human researcher, who would specifically solve this problem, could realize a more efficient system. However, the intelligence would be in his head, not in his system.

 I wanted to compare CAIA with other problem solvers. Francis Sourd kindly gave this problem to two of the best general solvers for problems defined by constraints. ILOG Solver did not find a solution in a reasonable time, while ILOG CEPLEX found the first one after 14 hours. Incidentally, it shows that CEPLEX is excellent: the search space is enormous when it is impossible to manipulate the formulation of the problem. Therefore, it does not know the value of VAL, and all of its constraints have 10 unknowns.

CAIA solved this problem in a way that I did not know. As Pégoud with his plane, we must let our systems fend for themselves!

 I doubt that, at the moment, there exists a general system that could approach the performances of CAIA for this problem, when it is placed in the same conditions: knowing only to find a bijection satisfying the 15 constraints given in part I. If I am wrong, I would be very interested in knowing more on this system.

 For the cube problem described in the preceding post, CAIA begins with looking for symmetries in the problem formulation. What is a symmetry? For Richard Feynman: « A thing is symmetrical if there is something we can do to it so that after we have done it, it looks the same as it did before. »

There are many kinds of symmetries. CAIA only tries to find one of them: a permutation of the unknowns leads to the same set of constraints when each unknown is replaced by the corresponding one.

To do this, I defined a combinatorial problem: finding all the permutations of the unknowns that satisfy the preceding condition. This problem is given in the formalism used for all the combinatorial problems solved by CAIA. The interest of the bootstrap clearly appears here: knowing how to solve combinatorial problems allows us to solve problems necessary for solving combinatorial problems. For every new problem, CAIA solves a preliminary problem: finding which symmetries exist. Its data are the initial constraints of the main problem.

We are not restricted to the case where each constraint C is transformed in itself by the permutation, such as when one permutes A and B in the constraint A+B>0. Usually, most constraints are transformed into other ones.

For the cube problem, CAIA finds 47 solutions: for each solution that it finds, it can immediately add 47 new solutions.

One of these solutions is the following permutation:

 All the classical geometrical symmetries are among these 47 solutions: to the center, to the mean planes, etc. However, it found them from the constraints: it does not know geometry; the method can be used for problems where there is no geometrical interpretation. For instance, if unknowns A and B appear only in the constraint A+B=1,000,000 exchanging A and B gives the same constraint. Naturally, CAIA can often add new constraints for avoiding to generate a solution and its symmetrical ones. In the preceding example, if the values of A and B are different, adding constraint A<B will remove all the symmetrical solutions.

For three main reasons, CAIA needs finding symmetries:

1. This decreases the size of the search space, because constraints are added to prevent finding symmetrical solutions.

2. This increases the speed of the resolution process: for every new solution, one can immediately generate all its symmetrical solutions. For the cube, the system is 48 times faster once it has found the symmetries.

3. It is easier to create constraints: for each new constraint, CAIA adds all the constraints that are obtained by symmetry. Let us notice that it does not generate 47 other constraints for each constraint: as few unknowns are in a constraint, many of the constraints generated in that way are identical.

If one believes to help the system by adding constraints to the initial formulation, this is a mistake: this may hide some symmetries. For instance, one may be proud to have proven the constraint F(17)+F(11)=F(5)+F(23). Unfortunately, adding this constraint in the initial formulation will remove most of the symmetries, including the one given above. Indeed, the constraint that would be created with this symmetry is F(11)+F(17)=F(15)+F(13); it is not among the initial constraints of this new formulation. As it often happens, when one has a clever system, it is not good to try to help it: one may complicate its task. Let us trust CAIA to do its job.

Finally, for me, the main interest of finding symmetries is to show concretely that bootstrapping is possible, and can be very useful: realizing a solver for problems defined by a set of constraints improves the solver itself.

In the next post, we will see how CAIA uses these symmetries for solving the magic cube problem.

 An AI researcher can always arrange his system so that it can find a solution that he already knows. To do that, he chooses a formulation well adapted to this solution, he includes all the methods necessary for this solution, and he indicates to avoid the roads that do not lead to the right direction. For this reason, it is always interesting to see a system finding a solution unknown by its author.

 We have already seen how ALICE, developed by Jean-Louis Laurière, had immediately solved a problem proposed by professor Schutzenberger. I will now describe how CAIA has solved a problem better than I would have done.

 Let us consider a kind of magic cube: the goal is to find a bijection F between the 27 small cubes that are in a 3x3x3 large cube, and the integers between 1 and 27. The sums of the planes containing nine cubes must have the same value VAL. There are 15 such planes: 3 horizontal, 6 vertical, and 6 diagonal. The small cubes are numbered in the following way, the first array is for the upper face, and the third one for the lower face, as shown below:

The three constraints for the horizontal planes are:

F(1)+F(2)+F(3)+F(4)+F(5)+F(6)+F(7)+F(8)+F(9) = VAL

F(10)+F(11)+F(12)+F(13)+F(14)+F(15)+F(16)+F(17)+F(18)=VAL

F(19)+F(20)+F(21)+F(22)+F(23)+F(24)+F(25)+F(26)+F(27)=VAL

The six constraints for the vertical planes:

F(1)+F(2)+F(3)+F(10)+F(11)+F(12)+F(19)+F(20)+F(21)=VAL

F(4)+F(5)+F(6)+F(13)+F(14)+F(15)+F(22)+F(23)+F(24)=VAL

F(7)+F(8)+F(9)+F(16)+F(17)+F(18)+F(25)+F(26)+F(27)=VAL

F(1)+F(4)+F(7)+F(10)+F(13)+F(16)+F(19)+F(22)+F(25)=VAL

F(2)+F(5)+F(8)+F(11)+F(14)+F(17)+F(20)+F(23)+F(26)=VAL

F(3)+F(6)+F(9)+F(12)+F(15)+F(18)+F(21)+F(24)+F(27) = VAL

The last six constraints are for the diagonal planes:

 F(1)+F(2)+F(3)+F(13)+F(14)+F(15)+F(25)+F(26)+F(27)=VAL

 F(7)+F(8)+F(9)+F(13)+F(14)+F(15)+F(19)+F(20)+F(21)=VAL

 F(1)+F(4)+F(7)+F(11)+F(14)+F(17)+F(21)+F(24)+F(27) = VAL

 F(3)+F(6)+F(9)+F(11)+F(14)+F(17)+F(19)+F(22)+F(25)=VAL

 F(1)+F(5)+F(9)+F(10)+F(14)+F(18)+F(19)+F(23)+F(27)=VAL

 F(3)+F(5)+F(7)+F(12)+F(14)+F(16)+F(21)+F(23)+F(25)=VAL

In this old version of CAIA, I have indicated that the value of VAL was between 1 and 300. This was a very small aid; in the future versions, telling that VAL is positive will be enough.

I have already drawn attention to the importance of the problem formulation. To sum up, CAIA knows that it must find a bijection of 27 unknowns on the set of integers from 1 to 27, and the value of the positive unknown VAL, less than 300, such that the 15 preceding constraints are satisfied.

One could think that this is an easy problem, since it is under-constrained: there are 28 unknowns and only 15 constraints, plus the fact that one has a bijection. It has millions of solutions. However, the search tree is very large since every F has 27 possible values, and 300 for VAL. Moreover, each constraint contains 10 unknowns, and one must instantiate 9 of them to get a value for the tenth: many instantiations have to be made before one sees a contradiction. From this point of view, the problem is extremely difficult to solve: there are many solutions, but they are hidden in billions of possible instantiations for the unknowns.

We will see in the following posts how CAIA solved this problem, beginning with the discovery of its symmetries.

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?

 A crypt-arithmetic problem is defined by one (or several) equations, where the digits are represented by letters. One has to find the value associated with each letter so that the operation is true; different letters must have different values. Moreover, the first letter of each number must be different from zero. The crypt-additions, where the only operation is the addition, are a special case of these problems. One of the more popular crypt-addition is:

DONALD+GERALD=ROBERT

 Frederic Bartlett was a pioneer of the study of human problem solving. In the 1950s, he asked his subjects to solve this problem; for facilitating their task, the value of letter ‘D’ was given. In spite of this, many of them failed. If the value of ‘D’ is not known, this problem is much more difficult. The unique solution is: 526485+197485=723970.

CAIA has received the description of a general crypt-addition. It is important to know what formulation has been chosen for describing a problem. In that situation, I have chosen to introduce the carries. One must find an injection between the letters and the numbers from 0 to 9 that satisfies the constraints given by each column. For DONALD, that generates the following six main constraints; C0 to C6 are the carries, which can only take the values 0 and 1 for this addition:

C1+D+G=R+10*C0

C2+O+E=O+10*C1

C3+N+R=B+10*C2

C4+2*A=E+10*C3

C5+2*L=R+10*C4

C6+2*D=T+10*C5

and also: C6=C0=0, and D#0, G#0, R#0 (first letters of each line).

 As computers are very fast, I can ask CAIA to write a combinatorial program. In one second, it writes this program, compiles and executes it: it contains 111 C instructions, but it can only solve the DONALD problem. It develops a tree with 262 leaves, and finds the unique solution. This is very satisfactory: the size of the search space is roughly 10 billions. When CAIA writes a combinatorial program, it does it cleverly. It is easy to check this solution, but it is more difficult to be sure that no solution is missing. We have seen that a meta-bug may create bugs in the generated program.

CAIA can also begin with a meta-combinatorial search, executing rules that modify the formulation of the problem. I call this approach ‘intelligent’ because its results look like those found by an intelligent human. In the present case, CAIA discovers that it has to find a bijection rather than an injection: there are 10 letters for 10 digits. This is very useful: for instance, if a digit D can be the value of only one letter L, then one is certain that the value of L is D. CAIA generates also new constraints, such as T is even, but the most useful is to state that E has only two possible values instead of 10: 0 and 9. Unfortunately, this meta-combinatorial search stops because all the rules have been applied.

In that situation, CAIA may decide to write a combinatorial program, leaving for good the meta-combinatorial search. It writes this program, including all the constraints that it has found, with particular attention to including the fact that it has now to find a bijection. It executes it, and it finds that there is only one solution after generating a tree, now with 192 leaves. The new program has almost the same size as the preceding one (118 C instructions), but both programs are completely different.

Another possibility for CAIA is to resume the combinatorial search after instantiating E with each of its two possible values. Then, it shows that E=0 leads to a contradiction, while E=9 leads to the solution. In both cases, it directly finds the result: now, the tree has only two leaves.

One may wonder whether it is worth using the intelligent approach: the computer times are almost the same, the time necessary to generate and execute the combinatorial program is approximately the same as the time for enriching the formulation of the problem. However, the results of the meta-combinatorial search may be checked and explained. Moreover, for other problems, the time required for the combinatorial approach is unacceptable.

The solution found by CAIA was a pleasant surprise. ALICE, probably the first AI system using a meta-combinatorial search, found a solution with 6 leaves. Jean-Louis Laurière improved it to only 4 leaves. He subsequently asked hundreds of students to study this solution, and no one ever suggested that it was possible to generate a smaller tree. For its part, CAIA made unexpected decisions: a crucial step in the solution was the use by CAIA of the new constraint:

10*E+C3+N+D+G=99*C1+B

which was essential for the discovery of the contradiction in the case E=0.

It is often useful to mix both approaches: one begins with the meta-combinatorial search, and one finishes with the combinatorial search. In some situations, the best way is to examine many situations as fast as possible. Therefore, CAIA must become meta-intelligent: It will acknowledge that, sometimes, it is better not to be too intelligent, but rather to stop the meta-combinatorial search. This happens when one can foresee that the time spent in a meta-combinatorial search will not lead to a significant improvement of the formulation. Then, the best move is to write a combinatorial program, but one must generate this program in a very intelligent way.

 The solution of a problem often depends upon a set of variables, whose all possible values are known; the combinatorial search considers which combinations of these values satisfy all the constraints of the problem. This can also be used when there is a finite number of legal actions, and one considers the situations after all the legal sequences of these actions. This search is widely used in AI, for instance for chess programs. It frequently gives useful results: with their speed, the computers can develop trees much larger than those that we could ever generate.

However, even when this method succeeds, we are not satisfied: the only way to understand a solution found in that way is to know that everything has been considered, and one has found nothing else. We cannot check such solutions. Moreover, it cannot be used when the search space is very large, and always when there is an infinite number of values; this often happens in solving arithmetic problems.

Instead of considering all the possible values for each variable, one can also consider a combination of the rules that can create new constraints, enriching the formulation of the problem. In many cases, the new problem may become very easy to solve.

In order to clarify this idea, let us consider how CAIA solves a particular arithmetic problem: to find all the integers m and n satisfying the equation 4m+3n²=34 .

One cannot use the combinatorial search, there are an infinity of possible values for m and n. Here is CAIA’s solution:

3n² is the difference of two even numbers, so it is even.

As 3n² is even, and 3 is odd, n² is even.

Therefore n est even.

Then n² is a multiple of 4,

and 3n² is a multiple of 4.

So, 4m+3n² is a multiple of 4.

As it must be equal to 34, which is not a multiple of 4, there is a contradiction: no solution.

Naturally, at each step, CAIA must find and apply an element of its set of rules, for instance: in an equation, if a member is a multiple of integer I, then the other member is also a multiple of I. Another useful rule is: the sum of two expressions that are multiple of integer I is also a multiple of I.

A huge advantage of the meta-combinatorial search over the combinatorial one is that one has not to consider all the possible applications of the rules: one has only to find a sequence that leads to the solution. Many other rules were perhaps considered; if they are not necessary for the proof, it is useless to indicate that one attempted to use them. For instance, it happened that CAIA found that, as the square n² is a positive or null integer, this is also true for 3n². Therefore, 4m=34-3n²<=34, and m<9. I do not included this result in the preceding proof, the contradiction has been proved without using it.

The combinatorial search could be used in a variant of this problem where the absolute values of both m and n are less than one billion. Then, one can consider all the possible values of n, and check that 34-3n² is a multiple of 4. A lot of time would be wasted to find that there is no solution. Proving first that n is even and m<9 would reduce the size of the search space. Indeed, it is often interesting to use both kinds of search: the meta-combinatorial search trims down the problem, then the combinatorial search solves when the size of the search space is reasonable. We will show in future posts how CAIA manages to use both methods.

The mathematician frequently uses a meta-combinatorial search. He may spend years finding the proof of a theorem, writing notebook after notebook, when the final solution takes only a few pages.

When our AI systems will have many methods for enriching the formulation of problems, they will efficiently use the meta-combinatorial search. Some day, the mathematicians will be as surprised as the chess players were some years ago: during many years, they were laughing at the poor performances of the programs, and at their ridiculous moves. For the present time, they are reduced to demand that their artificial opponent will be shackled by the interdiction to use all its capacities; this does not prevent them to lose.

 The realization of a bootstrap has a serious drawback: the improvements are not obvious for all those that do not realize it. For them, it seems that we are at a standstill: the interest of a bootstrap only appears when it is completed, ant that may require many years.

Naturally, I will consider CAIA; its goal is to become an Artificial Researcher in Artificial Intelligence. I began with a pure AI system, that could solve combinatorial and arithmetic problems. I defined the methods included in this system, and I improved them according to the results. My present goal is to transform it into a system that will build a new system capable of performances at least identical to those of my first system. I have to replace my initial modules by modules capable to create new modules doing the same tasks as the initial ones. Later, it will be necessary to define a third class of modules that could create the second kind of modules. One could think that this ascent would carry on for ever, but this is not true: one will arrive at a level where modules can create similar modules. At that time, the bootstrap is completed.

To clarify the ideas, let us consider the following rule given to the system:

If -1 is raised to power n, and if n is even, then its value is equal to 1.

I decided that the system must look, for every newly created expression, whether -1 appears raised to an integer power. If so, and if the exponent is even, it will replace this sub-expression by 1. In that way, it easily simplifies expressions. However, I can decide another way to use this rule: if the exponent is an expression, it can try to prove that this expression is always even: for instance, the expression is x²+x, or y+3 when it already knows that y is odd. In both cases, it will be possible to replace the expression by 1. Now, CAIA will have to find decisions similar to those I took when it receives a rule. Instead of defining myself, for each rule, how use it, I have to discover an expertise that defines, for each rule, how to use it.

Therefore, in the bootstrap, that I am currently developing for CAIA, the system receives mathematical rules without any direction for use: it has to discover when it will use it. If it associates good methods to each rule, the performances will be the same than when it used my directions, but this is a progress: it is much easier to add new rules since it finds by itself how to use them. However, it is necessary to give the system other rules, which are meta-rules since they are applied to rules, enabling it to find when and how to use the basic rules.

Moreover, this will be an important step in the bootstrap: these meta-rules can find how to use a rule. As a meta-rule is a special kind of rule, the meta-rules will be also able to find how to use themselves! Naturally, this is not that simple: at the beginning, as they still do not exist, I will be obliged to find and give them. However, in the following steps, I will be able to create them by meta-rules found with the help of my new meta-rules. Finally, they will take the part of my own meta-rules.

Unfortunately, it will be necessary to manage another bootstrap: it is not sufficient to know how to use a bit of knowledge, it is also important to find it. In the present case, the mathematicians have found, a long time ago, mathematical rules such has the simplification of -1 raised to a power. However, in a new domain, it is important to be able to discover rules for this domain. The system has to discover knowledge for finding new knowledge in a new domain. This is also a kind of meta-knowledge, and the bootstrap will be possible because this meta-knowledge will also be able to find new meta-knowledge. Naturally, this will be a very long-term process.

During all these steps, we will be at a standstill for the performances; the improvement is in the autonomy of the system, which can solve more of my initial task, which will become more and more easy.

However, there is sometimes a good surprise: an unexpected progression of the performances, when I replaced a module that I had written by a module created by the system. I had several times noticed that the module created by CAIA was more efficient than my own module. Two reasons can be put forth to explain this fact:

Even when I know a rule, I do not always apply it correctly.

There are often many special cases with a low probability. Sometimes, I do not deal with them, because that requires too much work for improvements that occur rarely. On the contrary, an AI system spares no effort: it systematically considers many possible situations. The results are improved because an action was sometimes more useful than I thought, or because several small ameliorations can lead to a large progress.

To conclude, a big challenge with this approach is to show that the system is making good progress: the reader has to pry into the details of a very complex system. It is almost impossible to write an easily understandable description of the system progression. As the present structure of the research promotes the number of publications, this certainly does not encourage scientific research in this field.