Too often, IA researchers describe the successes of their system, but they keep a lower profile when they get poor outcomes. I do not want to comply to this bad habit. I describe here CAIA’s behavior when success does not come, in the present case, the magic square problem. An order N Magic Square has N horizontal lines, and N vertical lines. Therefore, there are N2 squares, and each one contains a number between 1 and N2, so that each number appears only once. Moreover, the sum of the verticals, the horizontals, and the two diagonals, must have the same unknown value, SUM.
First, CAIA finds symmetries, which are permutations of the unknowns which lead to an identical set of constraints. Seven symmetries are evident for all magic squares: three rotations and four reflections with respect to horizontal, vertical, and both diagonals. CAIA knows nothing about geometry, but it can find all symmetries, both geometric and non-geometric. To do that, it uses the general component that solves constraint satisfaction problems. I had only to specify one particular problem: finding all the permutations of the unknowns leading to the initial set of constraints.
I hoped that it would find the seven geometrical symmetries. However, CAIA was far beyond any of my expectations: it found a huge number of symmetries that I never imagined existed. Even for N=4, it finds 31 symmetries! Some are completely unexpected, for instance, one of them transforms the first horizontal into the second vertical: both contain the same values, naturally not in the same order.
Finding this is not evident: almost 400 years ago, Bernard Frénicle de Bessy performed an outstanding study of the N=4 magic square. In particular, he defined a standard representation of the solutions, which is always used. However, he has found 880 basic solutions; multiplied by 8, this gives a total of 7040 solutions. CAIA found only 220 basic solutions; multiplied by 32, we find again 7040. When N grows, the number of symmetries increases at a startling rate: for N=10, CAIA finds 15,359 symmetries! On this point, CAIA’s behavior is flawless, although a lot of computer time is needed: 31,193 seconds for all the symmetries when N=10.
In the following step, CAIA tries to find other constraints. For the magic problem, it adds that the sum of the unknowns is equal to the sum of the first N2 integers, since there is a bijection. After that, it can find the value of SUM. For us, humans, this is easy because we are seeing the square: it is clear that the sum of the N horizontal lines is N*SUM. It is also evident that this sum contains all the squares, so its value is the sum of all the numbers between 1 et N2, that is N2*(N2+1)/2. Therefore, we have SUM=N*(N2+1)/2.
I did not give CAIA this formula, it has to find the value of SUM from the set of constraints. For this task, it is rather good: for N=16, it finds SUM=2056, after many substitutions in the 34 initial constraints, plus the bijection constraint. It would have been better to prove the general formula, but it is difficult for a blind system, which cannot see the square as we do. It does not find other constraints, and I do not believe that constraints with less than N unknowns exist for this problem. In total, for this task, CAIA has done well overall, although it could not set out the general formula.
The last part is to find the solutions, and this is the point where CAIA fails: it has been designed for finding all the solutions of a problem. For this reason, it is very interesting to find symmetries. However, it makes no sense to find all the solutions when there are billions of them. In its normal working, it considers the formulation of the problem, and particularly it finds new constraints, easier to use than the initial ones. In some cases, (as for N=3), it directly finds the solution. When there is no new constraint, it is often better to stop trying to be clever, but to write cleverly a combinatorial program that generates all the solutions.
For a magic square, this works well for the small values of N: for N=8, it generates the first 1,000 solutions in 4 seconds. Unfortunately, the search space dramatically increases with N: the number of unknowns grows as N2, and the number of possible values for each unknown also grows as N2. Very soon CAIA is completely overcome. The method still works for N=9: 10 seconds for the first 1,000 solutions. Unfortunately, there is a sharp discontinuity for N=10: after 14 hours, it has not yet found a solution.
The reason for this failure is that it is unthinkable that, given the huge number of solutions, one can ever find all of them when N is not small. It is sufficient to find one of them. We could think that all we have to do is to launch the search for solutions, and stop when one is found. In reality, it is often better to use other methods for scanning the search space, pinpointing the areas where the probability of finding a solution is high. For instance, one can find solutions for the set of equations when the unknowns may have continuous values. Then, one can look for the combinations of integer values close to the values of these solutions.
Another heuristic may be used, such as to make the initial problem more constrained, adding new constraints so that it would be easier to find solutions for this new problem. If it has solutions, they would also be solutions of the initial problem. When there are zillions of solutions, we can add constraints that remove some of them. In a future post, we will see how this could be very efficient for finding solutions for some magic square problems.
To sum up, although a problem may have many solutions, CAIA experiences serious difficulties when all its constrains has many unknowns, each unknown having many possible values; this is normal, the search space is huge. In this situation, it can, nonetheless, have excellent results when it can generate new constraints with few unknowns; this happened with the magic cube, where it found constraints with only three unknowns. If this is impossible, it must use completely different methods, good for finding a needle in a huge haystack. CAIA improves the combinatorial search with a meta-combinatorial search generating new constraints; this is sometimes not enough for solving this kind of problem, some modules must be added to CAIA.
Is N an input (given by you, J.Pitrat, with some concrete value like 4 or 8) to CAIA, or has CAIA tried to experiment several values of N by it own?
What is the actual syntax of input of the problem given by you? Did CAIA reason with a symbolic abstract value of N then found that the problem is not realistically possible for values above 8?
Has CAIA found by itself the similarities between magic squares and magic cubes?
In practice, the formalization of the problem is essential (as you said many times in other blog posts); it would be nice to have a concrete listing -or script of the interaction between you and CAIA- (and even nicer to be able to reproduce your experiment on our own computers).
Of course such listing might be too big for a simple blog entry, but you could publish it somewhere else on the Web and give an URL to it.
CAIA found by itself the similarities: finding them is a particular constraint satisfaction problem. It can find them using this general formulation, if they exist, for any problem given to CAIA.
For the present time, I explicitly gave the value of N for every magic problem it tried to solve. It would be possible to add the possibility of choosing interesting values of N by itself, and analyze the changes in the results for different values of N, but this has not yet been made.
You are right, the formalization of a problem is essential. However, for the magic square, only one formalization is natural. One has to find a bijection; there are one constraint generator for all the horizontal lines, one for all the vertical, and one for each diagonal. Therefore, for size N, it generates 2N+2 constraints, each one with N+1 unknowns. I do not give it the value of SUM, it finds it by itself.
Finding symmetries is indeed essential. However, it has two different purposes: improving the performance of the machine, and give solutions and execution traces easily understandable by humans.
If we focus on an AI system being used as a sophisticated and trusted problem solver software (we then view the AI system as a much improved spreadsheet or constraint solving program or SMT solver) we don’t care much about symmetries, we just want one (or several, or perhaps all) solution(s) to a particular problem (e.g. some magic cube or magic square)., but we prefer the software to answer as quickly as possible. With such a view, we don’t care about symmetries internally used by the software, or about the execution trace or explanation of the result. We just want the right result as quickly as possible.
Then, what is the threshold above which reasoning about symmetries is worthwhile? I am blindly guessing that for N=4 and perhaps even N=5 and perhaps even N=6 a naive combinatorial search is faster (on our current desktops) than a clever meta-reasoning. But for which values of N is that true?
Of course, you should be able to measure very short executions of CAIA, since for small problems I guess that a few milliseconds of CPU time is enough.
What are the heuristics CAIA uses to avoid spending time at the meta-level when it is not worth the effort (in terms of raw performance of CPU time)?
Software engineers have also such heuristics. For example, most carefully crafted sorting routines (in real world software libraries) are using different methods for sorting tiny arrays of a few dozen machine integers and big arrays of a hundred million numbers (but there is the theoretical proof that sorting an array of n numbers is an O(n log n) algorithm and no better algorithm exist). In several free software libraries I heard about or looked inside the source code, that sorting threshold is a few dozens. It might be machine specific.
Symmetries are useful for improving the speed of CAIA: when it finds a solution, it finds immediately all the symmetrical ones. This is important when one wants to find all the solutions. It is also helpful for finding new constraints: when one constraint is found, one has immediately all the symmetrical constraints. This is helpful even when one wants to find only one solution. For the Magic Square problem, the number of solutions grows very fast, so the first aspect is not very useful if N is greater than 4. On the other side, CAIA does not find new constraints with few unknowns (I do not believe that they exist), so the second aspect is also not useful here. Symmetries were essential for the magic cube, they are not very useful for the magic square, but one cannot know it before studying the problem.