Artificial Intelligence

- die Loisch Ergänzungen

An algorithm has to be seen to be believed.

Donald Knuth

Ich habe einge der in der Vorlesung "Künstliche Intelligenz", die im Sommersemester 2003 an der Albert-Ludwigs-Universität gehalten wurde, vorgestellten Algorithmen in Python oder Ocaml implementiert. Sogar ein kleines Schachprogramm ist dabei entstanden. Hier findet ihr sie.

Implementierungen von wichtigen, interessanten oder historisch relevanten KI Problemen

Chess Author(en) David Leuschner [2003-06-22]
Sprache Ocaml

A short and simple implementation of the well known board game in less than 1000 lines of code. I've used a very simple evaluation function and the alpha-beta-variant of the minimax algorithm. I did not implement a transposition table (in fact I tried but since my board representation is not efficient it made my program even slower). The board representation is intuitive and shows how nice datastructures can be represented in Ocaml but is far from efficient. A real implementation should use bitboards instead.

CSP Solver Author(en) David Leuschner [2003-06-22]
Sprache Python

This is an implementation of a constraint satisfaction problem solver demonstrating several well-known heuristics like forward checking, maintaining arc consistency (using ac-3), most constrained variable (a.k.a minimum remaining values) and least constraining value selection. My program demonstrates how to solve crypt-arithmetic problems (like SEND+MORE=MONEY or TWO+TWO=FOUR) and map-coloring problems. It is able to break down non-binary constraints (like for example a+4*b = c + d) into binary constraints.

If you have any problems or questions please contact me and I'll try to help. And just a note: don't try to solve real-world problems as this implementation is incredibly inefficient.

General Problem Solver (GPS) Author(en) Oliver Olesen, David Leuschner [2003-05-08]
Sprache Python

Der General Problem Solver implementiert die manchen vielleicht aus der kognitiven Psychologie bekannte Mittel-Ziel-Analyse. Die Mittel-Ziel-Analyse ist ein Vorgehen beim Problemlösen bei dem Mittel zur Lösung des Problems zwischenzeitlich selbst Ziele werden können. Ein in der Literatur häufig genanntes Beispiel ist das einer Mutter, die ihr Kind zur Schule bringen möchte. Ein Mittel mit dem das Kind zur Schule gebracht werden kann ist das Auto. Falls das Auto aber kaputt ist wird die Anwendung des Operators (die Nutzung des Autos) zwischenzeitlich zum neuen Ziel. Zunächst wird also das Ziel einen bestimmten Operator anwenden zu können gelöst um dann darauffolgend wieder das eigentliche Ziel (hier das Kind zur Schule zu bringen) zu verfolgen und den jetzt verfügbaren Operator zur Erreichung des Hauptzieles einzusetzen.

In unserer konkreten Implementierung wird der Zustand der Welt durch eine Liste von Strings beschrieben, z.B.

['being-at-home', 'car-at-home', 'car-broken']
. Die Ziele werden ebenfalls durch eine solche Liste beschrieben, wobei ein Ziel als erreicht gilt, wenn derselbe String in der Liste, die den Weltzustand beschreibt, vorkommt. SInd zum Beispiel die Ziele
['being-at-home', 'car-working']
gegeben, wäre das erste Ziel
'being-at-home'
bereits erreicht. Um das Ziel
'car-working'
zu erreichen muss der Weltzustand mit Hilfe eines Operators transformiert werden. Operatoren werden als Python dictionaries (andere übliche Bezeichnungen sind z.B. Hashtable, Map, etc.) dargestellt, wobei jeder Operator im dictioary die Schlüssel name, preconditions, add-list, del-list enthält. Hierbei ist preconditions eine Liste von Strings die im Weltzustand enthalten sein müssen, damit der Operator angewendet werden kann. Die beiden Listen add-list und del-list beschreiben die Auswirkung des Operators bei Anwendung auf den Weltzustand. Die in add-list enthaltenen Strings werden zum Weltzustand hinzugefügt, die in del-list enthaltenen Strings werden (sofern vorhanden) aus dem Weltzustand entfernt. Ein Operator könnte also folgendermaßen angegeben werden:

    op = {
      'name': 'repair-car',
      'preconditions': ['being-at-home', 'car-broken'],
      'add-list': ['car-working'],
      'del-list': ['car-broken']
    }
            

Der Operator könnte in dem oben als Beispiel gegebenen Weltzustand angewendet werden, da der Weltzustand beide preconditions

'being-at-home'
und
'car-broken'
enthält. Nach Anwendung würde
'car-broken'
aus dem Weltzustand entfernt und
'car-working'
hinzugefügt werden.

Wie der GPS arbeitet ist im Quellcode dokumentiert. Ausserdem enthält er ein großes Beispiel rund ums Kind-zur-Schule-bringen. Viel Spaß!

Simulationsumgebung für autonome Agenten Author(en) David Leuschner, Peter Norvig [2003-05-08]
Sprache Python

Ein kleiner Simulator in dem autonome Agenten verschiedene Staubsaugermodelle, die mit unterschiedlichen Sensoren und Aktionsmöglichkeiten ausgestattet sind, steuern können.