Monthly Archives: May 2014

A pleasant surprise from Alice

Usually, we have unpleasant surprises when we are developing an AI system that must satisfactorily solve a family of problems. We start this system hopefully, and its results are very poor for unforeseen reasons. We have to analyze this setback in order to improve its performances.

However, I will present a rare situation where a pleasant surprise happened. Jean-Louis Laurière had started his thesis in 1971. His goal was to realize a general solver for combinatorial problems, called Alice. Jean-Louis defined a formalism for describing problems. When Alice received a problem defined in this formalism, it had to find its solutions.

Professor Marcel-Paul Schützenberger was a mathematician, specialized in combinatorics. He was also a very strong opponent of AI: for him, such researches were a waste of time because it was unrealistic to build programs as intelligent as ourselves. In 1975, he was studying a particular family of combinatorial problems (this family is described p.440 in Laurière’s book, and p.407 in its French version). Therefore, he had to ask an excellent programmer to write a combinatorial program for solving only these problems. Naturally, writing a program requires some time, and the professor was losing patience.

Hearing that Jean-Louis was developing a general problem solver, and meeting him in a corridor at Jussieu, he challenged him to solve with Alice his problem, which he rapidly described. One hour later, he had his results! This was not a surprise for us: the undisputed interest of general systems is to give the solution of a problem as soon as it is described. On the other hand, professor Schützenberger was impressed, so much that he accepted to be a member of Jean-Louis’ examining committee, in spite of his strong prejudices against our science.

For us, the surprise came later, when the programmer had completed his work. As everybody at this time, we thought that general systems were convenient, since one has not to wait the completion of a program for getting the solution of a particular problem. Nevertheless, we believed that these general systems were inefficient, a lot of computer time is wasted for finding a solution. It just happened that Alice was more efficient than the program specifically written for this family of problems. In some cases, Alice found the solutions  of a particular problem in a few minutes, while the specific program was stopped after running two hours without finding anything.

Even after a pleasant surprise, work is not completed: we have to understand why it happened. The first reason is that, for each problem, some methods are obviously useful. Therefore, they are included in the specific program, and they are also added to the set of methods of the general system. As Alice has to solve a large variety of problems, Jean-Louis gave it many methods; it has an expertise for choosing among them the most appropriate one, depending on the present situation. It often happens that, for a particular problem, it surprises us by successfully using a method found useful for other problems. As it was not easy to see that it was useful for this problem, the author of the specific program did not include this powerful method in his program, while Alice correctly chose to use it.

Another reason for this surprise is that the programmer often defines an algorithm which does not take into account the numerical data. With different data, it may be better to consider first the first variable, or the last one, or the fifth one, etc. When the order for considering the variables is wrong, a program can waste a lot of time if the latest considered variable could immediately show a contradiction. Sometimes, Alice can also add new constraints that dramatically reduce the size of the search space. It automatically fits every situation that it meets while solving a problem. If the efficiency of a method strongly depends on the data, and if one meets a large variety of situations while solving the problem, the improvement may be considerable.

Of course, it is always possible to write a specific program as efficient as a general system, but sometimes they will be identical!