A review of AI puzzles

Puzzle problems are the framework in which the search for Artificial Intelligence takes place. The evolution from easier to more advanced understanding of AI is strongly connected to the evolution of AI puzzle problems. There are certain categories available:

1. easy: traveling salesman problem, chess problems, tictactoe game, Knight's tour, path planning
2. medium: 15 puzzle problem, piano movers problem, Tetris playing AI agent, pacman AI agent
3. advanced: dataset driven machine learning
4. hard: Visual question answering, instruction following, multimodal machine learning

Let us describe first the easy category. This sort of problems has the longest tradition in the AI literature and the problems including possible algorithms are described in high amount of papers. Nearly every introduction course in computer science, mention or explains the traveling salesman problem. It has become a standard challenge for investigating the performance of algorithms.

Most of the problem from the easy category can be solved with a backtracking algorithms. In case of chess problems, the algorithms needs improvement from an evaluation function but the main principle is to traverse the state space.

The problems from the medium section are less often explained and they are requiring sophisticated heuristics. The first puzzle in the section, the “15 puzzle problem” is used exclusively to explain the advantages of an evaluation function, namely the manhattan distance, while the other problems like “pacman AI agent” will need a finite state machine or an advanced behavior tree. Its not possible to solve the problem in the medium category with easy to implement backtracking algorithms because of the larger size of the state space.

The two remaining categories, advanced and hard, are only seldom described in the literature. The first papers about the subjects were published since the year 2000. For VQA related problems, the first written description is even available since 2010.

What all these problem categories have in common is, that they do not require software or hardware in terms of computer science. But the problems can be discussed independently of computer science. A typical problem description fits on a single piece of paper which reads like the description for a board game. So we can say, that the problems belong to the umbrella term of game theory. The complex reality gets simplified into game rules and the player can take decision inside the rule system.

Advantages of Linux in a single sentence

ffmpeg, mplayer, python3, gcc, git, vim, grep, awk, wget, ssh, docker, htop, nmap, pandoc, imagemagick, find, dd, ghostscript, latex, gnuplot, sqlite3.

The evolution in AI from 1990 to 2010

In the year 1990 no robotics was available. The only thing what was visible during this decade were classical computing machinery which includes home computers, supercomputers and even the Internet. Until 1990 it was unclear how to program Artificial Intelligence.

On the other hand, from 2010 AI was evolving quickly and many robots were developed and existing models were improved. So the natural question is: what exactly happened in the meantime which enabled AI and robotics?

The surprising situation is, that from a computer science perspective no measurable progress was made since 1990. Even if the amount of RAM in a typical workstation has improved, and even hard drives had become larger, there was no invention available like an AI chip or a revolutionary robot algorithms. Some attempts were made to create dedicated AI programming languages, and even parallel microprocessors were created for running neural networks – but all these innovations didn't resulted in artificial intelligence.

What was created instead is located outside of computer science and it was the discovery of AI related puzzles. Perhaps it makes sense to explain this idea in detail. A puzzle in the classical sense is a thinking game, for example the rubics cube is a 3d cube with random color surfaces, while, while a sliding puzzle like 15 puzzle contains of numbers on cells which can be moved in 2d space. There are word puzzles which are called crossword puzzles and jigsaw picture puzzles.

An AI related puzzle is a certain puzzle which was invented to investigate the subject of robotics and intelligent machines. These AI related puzzles were invented from 1990 to 2010 in a high amount of diversity. There are AI Related puzzles in a physical world which is about mechanical robots and also in a virtual environment which can be realized as video games. The creation of a certain AI related puzzle describes the reality from a different standpoint. This standpoint allows to define what AI is about.

Entry level AI puzzles are the mentioned 15 puzzle problem, chess based puzzles and the traveling salesman problem. None of these puzzles has to do with computer science in the classical sense which includes computer hardware, software or algorithms, but its invented outside of computer science. Computers are only used to solve these problems.

More advanced AI related puzzles are OCR datasets used for neural network training, the visual question answering challenge, and robotics competitions like micromouse and robocup. What all these puzzles have in common is, that they fit on a single sheet of paper. The document constains the instruction what the puzzle is about. For example it consists of a map for a robot navigation task or explains what the rules of the robocup competition are. These instructions can be convertted into a computer science project which includes building of mechanical hardware and programming the robot software. So we can say, that AI puzzĺes are a meta technology which allows to create new AI related technology.

Let me give an example: A single puzzle description for the micromouse robot competition can be used as a starting point for a dozens of concrete projects. Some of the robots are realized with the Arduino microcontroller, while other are using Lego Mindstorms technology. Some of the projects might be programmed in Assembly language or with neural networks or with the C/C++ language. These detail decisions are taken place within classical computer science but they are not important for the AI problem directly. The only thing which counts is the AI puzzle itself.

The advancement in AI from 1990 to 2010 can be entirely explained with the invention of better AI puzzles. Early problems like tictacto or chess puzzles are resulting only in low quality AI projects, while later puzzles like “Mario AI”, deep learning datasets and instruction following problems in robotics are generating more advanced AI innovation. So we can say, that the main question in AI is “What sort of puzzle has to be solved?”

Success factors in U.S. universities

The university system in the United states are mostly described as the world leader. There is no single explanation available but quality is caused by multiple reasons. These factors are:

a) high amount of universities (4000 overall)

b) teaching language is English

c) focus on research and innovation

d) good infrastructure which includes lab equipment and libraries

An excellent university system is the result of all four factors combined. Other countries like India are good in some of the factors. For example, India has a high amount of universities and the teaching language is similar to the United States English, but India lacks in the other factors. In contrast, the university system in Germany has other strengths, for example Germany universities have a good infrastructure, but unfortunately, the teaching language isn't English and the amount of universities is very low (only 10% of the U.S.).

It seems, that especially the language English in combination with a focus on research and innovation is the cause why U.S. based universities are perceived as superior. The assumption is, that academic excellence is equal to research something new and write a paper in the language English as a result. If a country or an education system is devoted to this goal, it will ranked very high in the international university landscape.

Unterschiede im deutschen und amerikanischen Bildungssystem

Angesichts der rasenten Entwicklung innerhalb der Künstlichen Intelligenz und dem unbestreitbaren Vorsprung der USA in Bezug auf Forschung und Umsetzung von Large Langugage Modellen stellt sich ganz allgemein die Frage, worin die Unterschiede im Bildungssystem bestehen.

Häufig wird der Vergleich Deutschland vs. USA nach subjektiven Kriterien durchgeführt. Es gibt beispielsweise die Meinung dass die USA das bessere Hochschulsystem haben. Manchmal wird versucht diese Meinung anhand von Fakten zu belegen, das z.B. die USA mehr anwendungsorientiert forschen würden, wären in Deutschland eher die Theorie im Mittelpunkt steht. Es gibt jedoch noch einen weiteren rein messbaren Zugang um die sehr unterschiedlichen Bildungssysteme miteinander zu vergleichen.

Ausgangspunkt ist der simple Fakt dass es in den USA rund 4000 Hochschulen gibt, während in Deutschland die Zahl bei 422 liegt. (China hat 3000 Hochschulen, Europa hat 5000 Hochschulen). Ferner kann man anhand einer bibliometrischen Analyse ermitteln dass zu einem beliebigen Thema es auf Deutsch vielleicht 50 Paper gibt die sich damit beschäftigen, während es in der englischen Sprache rund 1500 Paper zum selben Thema gibt.

Das interessante ist, dass das einzelne auf Deutsch verfasste Paper oder die einzelne technische Hochschule in Deutschland eigentlich eine mittelmäßige bis gute Qualität haben. Das man eben keine inhaltlichen Schwächen findet. Der Wirkliche Unterschied scheint eher in der Anzahl zu liegen. Scheinbar hängt Forschung weniger davon ab, dass die einzelne Hochschule Spitzenleistung erbringt oder in dem konkreten Konferenz Paper irgendwas neues drinsteht sondern Forschung basiert, so die These, darauf dass in hoher Anzahl in Laboren geforscht, in Journalen Publiziert und in Vorlesungen gelehrt wird.

Anhand der oben genannten Zahlen zu den Anzahl der Papern und der Anzahl der Hochschulen kann man ungefähr sagen, dass die Hochschullandschaft in den USA mindestens 10x so groß ist wie die Deutschland. Wenn man sich englischsprachige Publikationen fokussiert, die auch an nicht-amerikanischen Hochschulen entstanden sind, ist das Verhältnbis sogar 1:20. Das interessante ist, dass die Mehrzahl der Paper die in den USA entstehen ähnlich wie die Veröffentlichungen aus Deutschland allenfalls mittelmaß sind. Eine Bachelorarbeit wird in der Regel nicht von Experten auf dem Gebiet erstellt sondern von Studenten mit relativ wenig Detailwissen die selbst noch lernen und womöglich zum ersten Mal überhaupt eine Arbeit schreiben. Es ist deshalb normal dass die Textgüte eher nur Mittrelmaß ist. Scheinbar ist das aber nicht wirklich ein Problem, weil es sehr viele von diesen Arbeiten gibt.

Mit dieser These kann man die Frage beantworten was genau Deutschland tun kann um mit den USA auf wissenschaftlichem Gebiet zu konkurrieren. Rein von den Zahlen müsste Deutschland ca. 20x mehr Forschungsprojekte durchführen als bisher. Damit wäre jedoch allenfalls Gleichstand erreicht. Natürlich ist das illusorisch, weil ersten die Bevölkerung in Deutschland kleiner ist und zweitens die deutsche Sprache keine Weltsprache ist. Wenn jedoch der Versuch scheitert quantitiv mit den USA gleichzuziehen ist das Ziel gescheitert.

Die These kann man auf eine simple Formel reduzieren. Dasjenige Land, wo es die meisten Hochschulen gibt, und diejenige Sprache in der die meisten wissenschaftlichen Aufsätze erscheinen steigt auf zur wissenschaftlichen Weltmacht. Während alle anderen Länder wo es anzahlmäßig weniger Hochschulen und Anzahlmäßig weniger Forschung gibt, leider zurückfällt und aus dieser Position heraus immer weiter den Anschluss verliert.

Anstatt auf die einzelne Hochschule in den USA zu fokussieren sollte man das System als Einheit betrachten. Je mehr Hochschulen es gibt, desto stärker die Notwendigkeit für die einzelne Institution sich zu spezilisieren. Dadurch entsteht dann automatisch ein sehr effizientes Hochschulsystem. Bei den publizierten Artikeln in Journalen ist es vergleichbar. Je mehr Artikel und Bücher schon existieren, desto stärker die Tendenz neue Artikel mit spezilisierten Fragestellungen zu erstellen um sich von den vorhandenen Veröffentlichungen abzuheben. Diese Spezilisierung ist auch für die Leser von wichtig weil sie so eher etwas interessantes entdecken. Umgekehrt ist es für deutschsprachige Fachzeitschriften unmöglich mit diesem quantiativ und qualitiv hochwertigem Corpus zu konkurrieren.

Zettelkasten can't replace experiments

 The main purpose of note taking is to memorize information from the past. Everything what is written in books can be converted into note cards. The ability to add new cards and retrieve existing content makes it easier to remember content read in the past. This provides to the researcher a perfect external memory of all the read information.

In spite all the advantages, note taking with the Zettelkasten principle has one major drawback: it can't replace the experiment. Experiments are used in science to gather new information not written down in the existing literature. There are physical experiments, e.g. measuring the voltage in a circuit, mathematical experiments e.g. a number crunching problem, and even musical experiments in which a new song gets composed. All these experiments are by definition not available yet so they can't be found in the existing notes. If a zettelkasten is a look back into time, an experiments looks forward into the future.

The main problem with the zettelkasten notetaking principle is that encourages the researcher to look only in the past. Creating lot of notes and read them multiple times is equal to stay within existing knowledge. This is equal to a very conservative philosophy and rejects novelty. The untold bias is that everything important was written in the past, either by the researcher itself or by other authors who have published books about the subject. And everything what is not written down in the past, doesn't exists.

In contrast, an experiment driven research project is working with the opposite principle of a Zettelkasten. The question is not what was written about a subject already, and the question is not what sort of notes are avaiable, but the question is how to investigate something from scratch without pre-knowledge. The idea is heat up water and measure at which degree the maximum is reached, the goal is to program a prototype in python and think about the difficulties. So we can say, that the limitation of the Zettelkasten has to do with the difference between past and future.

A chatbot which can grasp an apple

[2025-02-18 13:45:00] Human: Hello robot, can you help me with a task in the kitchen?

[2025-02-18 13:45:05] Robot: Hello! Of course, I'd be happy to assist you with a task in the kitchen. What would you like me to do?

[2025-02-18 13:45:15] Human: I need you to grasp an apple for me.

[2025-02-18 13:45:20] Robot: Certainly, I can help you grasp an apple. Let me process that request:
1. Locating the kitchen
2. Identifying an apple
3. Planning the grasping motion

Could you please confirm if there's a specific location in the kitchen where I should look for the apple?

[2025-02-18 13:45:35] Human: The apple should be in the fruit bowl on the counter.

[2025-02-18 13:45:40] Robot: Thank you for the additional information. I'll proceed with the task:
1. Navigating to the kitchen counter
2. Locating the fruit bowl
3. Identifying the apple among other fruits
4. Planning and executing the grasping motion

I'll narrate my actions as I perform them. Please let me know if you need me to do anything differently.

[2025-02-18 13:45:50] Human: That sounds good. Please proceed.

[2025-02-18 13:45:55] Robot: Understood. I'm starting the task now.

1. Navigating to the kitchen counter.
2. I've located the fruit bowl on the counter.
3. Scanning the contents of the bowl... I've identified several fruits, including an apple.
4. Planning the optimal grasping motion for the apple.
5. Extending my arm and adjusting my hand position.
6. Gently grasping the apple.
7. Lifting the apple from the bowl.

I've successfully grasped the apple. Would you like me to hand it to you or place it somewhere specific?

[2025-02-18 13:46:25] Human: Please hand it to me.

[2025-02-18 13:46:30] Robot: Certainly. I'm now:

1. Turning towards your location.
2. Extending my arm to offer you the apple.
3. Waiting for you to take it.

Please take the apple whenever you're ready. Once you've taken it, I'll release my grip.

[2025-02-18 13:46:45] Human: I've taken the apple. Thank you!

[2025-02-18 13:46:50] Robot: You're welcome! I'm glad I could assist you. I've released my grip on the apple now that you've taken it. Is there anything else you'd like me to help you with in the kitchen or elsewhere?

[2025-02-18 13:47:00] Human: No, that's all for now. Thank you for your help.

[2025-02-18 13:47:05] Robot: You're welcome! I'm happy I could help you with grasping the apple. If you need any assistance in the future, don't hesitate to ask. Have a great day!

Die wissenschaftliche Wende um 1900

 

Bis zum Jahr 1900 funktionierte die Wissenschaftswelt nach klassischen überschaubaren Prinzipien. Es gab die Naturwissenschaften welche sich untergliederten in Mathematik, Physik, Chemie, Biologie, Psychologie, Medizin und der Inhalt des jeweiligen Fachgebietes war in Nachschlagewerke erfasst.

Bis ungefähr dem Jahr wurde in jedem der Einzelwissenschaften eifrig geforscht und es wurden neue Erkenntnisse publiziert. So gab es irgendwann den Moment wo jemand das Ohmsche Gesetz entdeckte, oder zum ersten Mal Bakterien unter dem Mikroskop beobachtet hat. Diese goldene Zeit der Naturwissenschaft lief parallel zur industriellen Revolution ab und dauerte bis ca 1910.

Es gibt ein selten untersuchtes Phänomen was nach 1910 einsetze und als Stillstand der Naturwissenschaft bezeichnet werden muss. Damit ist gemeint, dass die gedruckten Nachschlagewerke aus den Bereichen Mathematik, Physik usw. sich seit diesem Jahr nicht oder nur noch sehr geringfügig veränderten. Der Grund dürfte sein, dass man wichtige Dinge wie die Zinsrechnung in der Mathematik oder die Mechanik-Gesetze der Physik nur einmal entdecken kann und danach wird man zu dieser Thematik nicht mehr viel neues entdecken.

Die o.g. Naturwissenschaften müssen statisch verstanden werden. Sie sind auf dem Stand von ca. 1900 eingefroren und haben sich seitdem fast nicht mehr weiterentwickelt. Zwar kann man auch heute noch Experimente wiederholen, wie z.B. den Temperaturverlauf von Wasser messen was man bis 100 Grad erhitzt, das Resultat ist jedoch identisch mit dem Jahr 1850. Man wird dazu nicht mehr viel neues entdecken oder eine andere Erklärung finden als jene die in den Büchern um 1900 auch schon notiert wurde.

Gehen wir mal einen Schritt zurück um die Brisanz dieses Themas besser bewerten zu können. Bis ca. 1900 waren die Naturwissenschaften der Motor der technischen Entwicklung. Es wurden aufregende neue Dinge entdeckt und dann von der Physik, Psychologie oder Medizin in Theorien überführt. Dadurch wurde es möglich, praktsiche Anwendungen zu entwickeln wie z.B. die Eisenbahn, die Röntgenstrahlung oder die Haltbarmachung von Lebensmitteln. Bis ca. 1900 gab es einen ungeheuren Erkenntnisgewinn und es gab dauernd neues zu entdecken.

Ab ca. 1900 änderte sich die Lage schlagartig. Es gab weniger eine Krise in der Mathematik oder in der Physik selber sondern die Krise bestand darin, dass kein neues Wissen mehr dazugefügt wurde. Im Grunden haben die Naturwissenschatler bis 1900 bereits alles entdeckt was wichtig ist und damit entstand ein Wissensplateau. Das heißt der Gipfel in den Wissenschaften war erklommen, und alles was man über die reale Welt erforschen konnte war bereits bekannt.

Die Herausforderung und die Notwendigkeit zur ständigen Innovation verlagerte sich auf ein anderes Gebiet. Es begann eher unscheinbar unter dem Begriff Nachrichtentechnik und mechanische Rechenmaschinen und weitete sich aus in den Bereich der Computer sciences. Computer science hat ihre Ursprünge zwar in der Mathematik und Physik, funktioniert aber nach anderen Prinzipien. Der Unterschied besteht darin dass in den Computerwissenschaften nicht die Natur untersucht wird, sondern dass selbst erschaffene Gebilde in Form von Programmen und Daten diskutiert werden. Dieser virtuelle Realität ist auch als Cyberspace bekannt. Anders als die Realität ist die virtuelle Realität sehr viel komplexer. Anhand der Historie der Computerwissnschaft ab 1910 kann man zeigen, dass es permanent neue Entwicklungen gab. Eigentlich jedes Jahr gibt es neue Computermodelle und neue Computersoftware. Es ist nicht möglich zur Computerwissenschaft ein Referenzbuch zu verfassen, weil es nach spätestens 10 Jahren hoffnungslos veraltet wäre.

Sosehr die Mathematik seit 1910 von einem Stillstand geprägt ist, sosehr ist die Computerwissenschaft von einer Aufbruchstimmung geprägt. Anders als in den etablierten Naturwissenschaften gibt es in der Informatik noch sehr vieles zu entdecken. Und je mehr erforscht wurde, desto größer sind die Bereiche die noch gänzlich unerforscht sind.

Die wachsende Bedeutung der Computerwissenschaften lässt sich anhand der anzahl wissenschaftlicher Publikationen erkennen. Um 1910 war die Anzahl die sich mit Rechenmaschinen beschäftigte sehr klein. Das stieg jedoch konstant an. Heute hat die Mehrzahl der Publikationen in den Wissenschaften entweder direkt oder indirekt einen Bezug zur Informatik. Selbst Literaturwissenschaftler nutzen den Computer zur Textanalyse, während Mathematik ihn verwenden um Diagramme zu plotten, und Mediziner den Computer nutzen um Datenbanken anzulegen. Moderne Wissenschaft ist automatisch eine Computerwissenschaft. Es bedarf zwingend des Einsatzes leistungsfähiger Webserver, professioneller Software und neuartiger Algorithmen.