Direkt zum Inhalt

Computer spielen Fußball

Eine Berliner Mannschaft hat die Weltmeisterschaft im simulierten Fußball gewonnen. Ihre Programme traten den imaginären Ball geschickter als die Konkurrenz.

An Körperkraft ist der Mensch der Maschine ohnehin hoffnungslos unterlegen, und auch sein geistiges Primat ist in Frage gestellt, seit ein Computerprogramm den Schachweltmeister geschlagen hat. Was bleibt dem verletzten Stolz des Homo sapiens? Gibt es eine genuin menschliche Tätigkeit von so hohem Niveau, daß eine Maschine sie auf absehbare Zeit nicht beherrschen wird? Die Antwort ist ja: Fußballspielen.

Forscher auf dem Gebiet der maschinellen Intelligenz begreifen dies als neue Herausforderung. Interessanterweise stehen damit nicht nur rein geistige, sondern auch motorische und sinnliche Fähigkeiten wie Orientierung in schnell wechselnden Umgebungen, Erfassen von Situationen, schnelles, präzises Reagieren und kooperatives Verhalten zum Vergleich.

Ein Fußball spielender Roboter, der sich mit menschlichen Ballartisten messen kann, liegt noch in weiter Ferne: Man rechnet mit einer Entwicklungsdauer von etwa 50 Jahren. Aber die ersten maschinellen Kicker haben sich schon mehr oder weniger unbeholfen um das runde Leder gebalgt: Vom 25. bis zum 28. August letzten Jahres fand in Nagoya (Japan) im Rahmen der Internationalen Konferenz für Künstliche Intelligenz (IJCAI-97) die erste Weltmeisterschaft der Fußball-Roboter, der "RoboCup", statt – mit nur fünf "Mann" starken Teams auf reduzierten Spielfeldern (Bild).

Die Kickerautomaten der ersten Generation kämpfen oft noch mehr mit den eigenen Unzulänglichkeiten als mit dem Gegner. Zum Beispiel ist Rot für sie das Erkennungsmerkmal des Balles – und so kann sie ein rotes Hemd im Zuschauerraum zu einer wilden Attacke auf die Spielfeldbegrenzung veranlassen. Mancher Roboter verlor angesichts unzähliger störender Signale den Kontakt zum steuernden Computer und irrte ziellos auf dem Feld umher. Aber trotz manchem Fehlschuß wurden die kleinen Fahrzeuge mit ihren originellen Konstruktionen angefeuert wie echte Spieler auf dem grünen Rasen. Zuschauer und Konstrukteure hatten einen Riesenspaß.

Nun finanzieren die Sponsoren – vor allem Computer- und Elektronikhersteller aus Japan – die Entwicklung künstlicher Dribbelkünstler keineswegs zum bloßen Vergnügen: Wer die entsprechenden Technologien beherrscht, wird sie auf vielen – ökonomischen – Feldern nutz- und gewinnbringend einsetzen können. Den Wissenschaftlern bietet das Spiel eine einzigartige Herausforderung, die mit der Integration unterschiedlicher Techniken von der Roboter-Hardware bis hin zur künstlichen Intelligenz zu bewältigen ist. Die Öffentlichkeit aber kann den Entwicklungsstand mit eigenen Augen erfassen und beurteilen.

In der 15-Zentimeter-Klasse (die Größenangabe bezieht sich auf den maximalen Durchmesser der Roboter) setzte sich das Team von Manuela Veloso und Peter Stone von der Carnegie-Mellon-Universität in Pittsburgh (Pennsylvania) mit klaren Siegen gegen die drei anderen Mannschaften souverän an die Spitze. In der 50-Zentimeter-Klasse wurde dagegen im Finale torlos bis zur Erschöpfung der Batterien gekämpft: Den ersten Preis teilten sich die Universität Osaka (Japan) und die Universität von Süd-Kalifornien in Los Angeles.

Damit die Erprobung intelligenter Techniken nicht warten muß, bis die Roboter die erforderliche "Körper"beherrschung erlangt haben, nähert man sich dem Fernziel derweil auch von der anderen Seite und programmiert den virtuellen Fußball in einer simulierten Welt. Muskeln und Gehirn trainieren sozusagen separat und müssen dann nur noch zusammengestöpselt werden. Außer den beiden Roboter-Ligen gab es in Nagoya deshalb auch eine Simulations-Liga, in der immerhin 29 Mannschaften aus den verschiedensten Ländern antraten.

Das simulierte Fußballfeld

Grundlage für das virtuelle Fußballspiel ist ein Programm namens Soccerserver, das die reale Welt zwischen den beiden Toren simuliert. Es empfängt von den 22 Spielerprogrammen Informationen über deren beabsichtigte Aktionen und berechnet danach die Bewegungen der Akteure und des Balls – und zwar durchaus realitätsnah: Der Ball rollt allmählich aus, und ein Zusammenprall bewirkt einen Rückstoß; anstelle kleiner Unebenheiten im echten Rasen ist es der Einfluß eines Zufallszahlengenerators, der gelegentlich die geradlinige Bewegung des runden Leders ablenkt. Auch die Kraftreserven der Spieler sind begrenzt: Wenn ein Kämpe viel gelaufen ist, verlangsamen sich seine Bewegungen, bis er sich nach einer gewissen Ruhezeit wieder erholt hat. Der Soccerserver übernimmt ferner die Standardentscheidungen des Schiedsrichters: Anstoß, Abstoß, Einwurf, Eckstoß und Anerkennung von Toren. Nur die komplizierte Abseitsregel ist bisher nicht implementiert. Auch Foulspiel wird durch menschliche Überwachung geahndet.


Gegenwärtig finden die Spiele noch in einer zweidimensionalen virtuellen Welt statt, die über ein weiteres Programm namens Soccermonitor visualisiert wird. Ein dreidimensionaler Simulator ist in Entwicklung. Itsuki Noda vom Elektrotechnischen Laboratorium (ETL) in Tokio hat Soccerserver und Soccermonitor entwickelt und zur freien Verfügung ins World Wide Web (WWW) gestellt (siehe Kasten auf dieser Seite).

Die virtuellen Fußballmannschaften bestehen aus jeweils elf autonomen Programmen. Jedes von ihnen fungiert als Gehirn eines Spielers, dessen Körper im Soccerserver steckt. Es muß völlig auf sich gestellt arbeiten und der Spielsituation angemessene Entscheidungen fällen; menschliches Eingreifen während des Matches ist nicht erlaubt.

Das Programm erhält alle 0,3 Sekunden vom Soccerserver Informationen über die momentane Spielsituation, die der aktuellen Wahrnehmung des Spielers entsprechen: In einem Blickwinkel von 90 Grad sind Objekte sichtbar, wobei die Schärfe mit der Entfernung abnimmt (Kasten auf Seite 21). Alle Angaben beziehen sich auf den jeweiligen Standpunkt und die Blickrichtung des Spielers. Wie im wahren Leben sind die Daten nicht immer ganz zuverlässig: Der Soccerserver baut hin und wieder – zufallsabhängig – kleine Abweichungen ein.

Der Spieler kann maximal zehn elementare Aktionen pro Sekunde auf dem Spielfeld ausführen: Drehen ("turn"), Treten ("kick") und Laufen ("dash"). Dazu sendet das ihn repräsentierende Programm entsprechende Nachrichten an den Soccerserver, der diese in die Simulation des Spielgeschehens einbringt. Für die Übermittlung wurde bewußt das unsichere UDP/IP-Protokoll gewählt: Bisweilen gehen Meldungen verloren, so wie auch im Alltag nicht immer alle Nachrichten korrekt ankommen.

Die Kunst beim Entwurf einer virtuellen Mannschaft besteht darin, effiziente Mechanismen zu finden, durch die der Rechner die massenhaft anfallenden, möglicherweise verfälschten Daten zu einem möglichst präzisen Bild der Situation verarbeiten und auf dieser Grundlage schnell zu zweckmäßigen Entscheidungen gelangen kann. Nur die Formate für den Nachrichtenaustausch mit dem Soccerserver sind vorgegeben, alles andere ist frei programmierbar. Es gehört zu den Regeln sportlichen Anstandes, daß die Spieler eines Teams nicht heimlich Nachrichten untereinander austauschen.

Unsere virtuelle Mannschaft namens "AT_Humboldt" schlug im Viertelfinale mit 14:7 ein Programm, das am Tokyo Institute of Technology trainiert worden war, im Halbfinale die Mannschaft der Carnegie-Mellon-Universität mit 6:0 und im Finale ein weiteres Team vom Tokyo Institute of Technology mit 11:2. Damit errang sie den begehrten Pokal. Man kann sich die Protokolle aller Spiele über das WWW beschaffen und die Begegnungen dann zu Hause am Computer nachvollziehen.

Was geht im "Kopf" eines virtuellen Fußballspielers vor?

Unser Erfolg beruht auf der Integra-tion unterschiedlicher Verfahren aus

Mathematik, Softwaretechnik und künstlicher Intelligenz. Grundlage war die Technik des agentenorientierten Programmierens. Mittels objektorientierter Programmierung (bei uns realisiert in der Programmiersprache C++) konzipierten wir jeden Spieler als einen Agenten, das heißt ein Programm, das zwar Aufträge von übergeordneter Stelle ausführt, aber eigenständig darüber entscheidet, wie es das tut. Anhand einer Vorstellung oder "Überzeugung" (belief) von seiner Umwelt entscheidet es sich für eines von mehreren möglichen Zielen (desires) und verfolgt daraufhin eine Absicht (intention), das heißt wählt eine unter mehreren möglichen Handlungsfolgen zum Erreichen des angestrebten Ziels. Dieses Programmschema, die sogenannte BDI-Architektur, geht auf den Philosophen Michael E. Bratman von der Stanford-Universität in Kalifornien zurück ("Inten-tions, Plans, and Practical Reason", Harvard University Press, 1987).


Der Spieler gewinnt seine Vorstellung von der aktuellen Spielsituation, indem er die vom Soccerserver übermittelten (relativen) Daten in absolute Koordinaten und Geschwindigkeiten umrechnet. Durch Extrapolation kann er zukünftige Situationen berechnen und somit auch mögliche Ergebnisse seiner weiteren Handlungen bewerten.

In unserer Umsetzung dieses BDI-Schemas analysiert und klassifiziert der Spieler seine Umwelt und wählt das – nach seiner Vorstellung – beste Ziel aus einem fest vorgegebenen Sortiment wie "Ball abfangen", "Abspielen", "Torschuß" und "Position einnehmen". In den Entscheidungsprozeß gehen auch die Möglichkeiten der anderen Spieler ein, soweit diese im Blickfeld sind: "Ball abfangen" wird zum Beispiel nicht ausgewählt, wenn ein Spieler der eigenen Mannschaft sichtlich günstiger steht.

Als nächstes muß das grobe allgemeine Ziel zu einer konkreten Absicht verfeinert – sprich: parametrisiert – werden. Wenn es zum Beispiel darum geht, den Ball abzufangen, ist zunächst die günstigste Position für die Ballannahme zu ermitteln. Diese Parametrisierung erfolgt bei unserem Programm in zwei Schritten: Zunächst wird die günstigste Realisierung des verfolgten Ziels ermittelt und daraufhin eine geeignete Folge elementarer Aktionen geplant. Eine solche Aktionsfolge kann zum Beispiel den präzisen Schuß mit maximaler Kraft in eine sinnvolle Richtung nach vorherigem Zurechtlegen des Balles beinhalten. Diese besondere Fähigkeit war eine der meistgefürchteten Stärken unserer Spieler.

Am einmal festgelegten Handlungsablauf wird so lange festgehalten, bis neue Informationen eingehen. Dann beginnt der Entscheidungszyklus von vorn, und der Spieler faßt wieder ein Ziel ins Auge. Oft handelt es sich – weil sich die Situation kaum geändert hat – um dasselbe wie zuvor. Wegen der aktuelleren Information läßt sich der Weg, auf dem es zu erreichen ist, jedoch im allgemeinen präziser ermitteln – und die Absicht entsprechend revidieren. Dabei wäre es allerdings ein Fehler, einmal eingeleitete Handlungsabläufe allzu bereitwillig abzuändern oder gar zu stoppen, weil der Spieler sonst zu häufig Zeit und Energie an Aktionen verschwendet, die er hinterher abbricht. Vielmehr fordert das Rationalitätsprinzip von der Stabilität einmal gefaßter Absichten, unter Umständen einen Plan auch dann weiterzuverfolgen, wenn er nicht mehr optimal ist. So kostet etwa eine Kurskorrektur beim Rennen zum Ball Zeit; es ist deshalb gelegentlich zweckmäßiger, ungebremst in die alte, nicht mehr ganz zutreffende Richtung weiterzulaufen.

Kooperation ergibt sich – wie in der Realität – aus dem Beobachten der Mannschaftskameraden: Wer den Ball führt, schießt ihn zu einem Mitspieler in aussichtsreicherer Position; dieser ist seinerseits darauf programmiert, das Leder schnell anzunehmen und gegebenenfalls wiederum weiterzuleiten. Unterschiedliche Rollenvorgaben sorgen für die Bevorzugung bestimmter Verhaltensweisen, was zum Beispiel ein effektives Operieren über die Flügel gewährleistet.

Virtueller Fußball ist für uns vor allem eine Möglichkeit, die Aspekte des agentenorientierten Programmierens zu erforschen. Dabei geht es uns ganz allgemein um den Entwurf von Programmen, die als Software-Assistenten vorgegebene Aufträge eines Benutzers situationsgerecht ausführen. Heute gängige Benutzerschnittstellen stehen noch auf einem sehr niedrigen Niveau: Man führt den Mauszeiger auf ein Symbol und klickt, woraufhin unabhängig von der Gesamtsituation im wesentlichen immer dasselbe geschieht. Ein Agent muß sehr viel flexibler reagieren können. Die Benutzung mentaler Begriffe wie Überzeugungen, Ziele, Absichten und Fähigkeiten soll die Strukturen solcher "intelligenten" Programme transparenter machen.

Wünschenswert ist auch, daß Software-Agenten Handlungen selbständig erlernen können. Das läßt sich gleichfalls im Umfeld des Roboter-Fußballs studieren. Als nächstes wollen wir unsere Spieler deshalb mit Methoden des maschinellen Lernens trainieren und ihnen mit Verfahren des fallbasierten Schließens beibringen, sich an gegnerische Taktiken anzupassen. Nachdem wir die in Nagoya eingesetzten Programme veröffentlicht haben, müssen wir sie deutlich verbessern, um beim RoboCup'98 im Juli dieses Jahres in Paris bestehen zu können.

Kasten 1: Tor!

Beim Stande von 3:3 zwischen den Mannschaften Gelb und Rot stürmen die Gelben aufs rote Tor zu. In dieser Situati-on (Bild unten) erhält der rote Torwart zur Zeit 1979 (Maßeinheit Zehntelsekunden) vom Soccerserver folgende Nachricht:

Receive: (see 1979 ((flag c t) 60.3 -19)

((flag l t) 107.8 -36) ((flag r t) 35.2 40) ((flag p l t) 87.4 -41) ((flag p r t) 24.8 3) ((ball) 8.2 17 -0.164 5.4) ((player) 81.5 -42) ((player) 60.3 -44) ((player GELB) 36.6 -17) ((player ROT 2) 10 -18 0 0) ((player ROT 3) 22.2 -24 0 0) ((player GELB 11) 14.9 -23 -0.298 0.2) ((player) 73.7 -38) ((line t) 42.5 -55))

Er kann daraus unter anderem folgendes entnehmen:

Die linke obere Eckfahne (flag l t) ist in 107,8 Meter Entfernung im Winkel von -36 Grad zu sehen. Die erste Zahl hinter einem Objekt bezeichnet stets die Entfernung, die zweite den Winkel im Uhrzeigersinn relativ zur eigenen Blickrichtung.

Der Ball befindet sich 8,2 Meter vor ihm im Winkel von 17 Grad. Er ist in Bewegung und wäre eine Zeiteinheit später in einer um 0,164 Meter geringeren Distanz und einem um 5,4 Grad vergrößerten Winkel zu sehen. Die dritte und vierte Zahl geben bei bewegten Objekten an, wie sich Entfernung und Winkel ändern; dabei wird auch die Eigenbewegung des Spielers berücksichtigt.

Der (gegnerische) gelbe Spieler Nummer 11 (player GELB 11) ist 14,9 Meter entfernt und kommt näher. Bei weiter ent-fernten Spielern fehlen Angaben zur Bewegung. Sie sind auch nicht mehr zu identifizieren: Es fehlen die Nummer und bei sehr großen Entfernungen auch die Angabe der Mannschaft.

Der Torwart entschließt sich, den Ball abzufangen. Dazu dreht er sich um ungefähr 55 Grad nach rechts und läuft mit maximaler Kraft. Er sendet dazu folgende Nachrichten im Ab-stand von jeweils einer Zehntelsekunde an den Soccerserver:

Send: (turn 54.724716) Send: (dash 100.000000) Send: (dash 100.000000)

Nach Ausführung dieser Aktionen hat sich sein Blickfeld geändert, und er erhält nach drei Zeiteinheiten die folgende Nachricht vom Soccerserver:

Receive: (see 1982 ((flag r t) 34.5 -10) ((ball) 6.7 -3 -0.402 5.4) ((line r) 12.3 -15))

Die Spieler sind jetzt außerhalb seines Blickfeldes. Die Entfernung zum Ball ist geringer geworden, und der Ball kommt noch weiter auf ihn zu (Entfernungsänderung -0,402 Meter). Er korrigiert seine Laufrichtung und läuft weiter:

Send: (turn 25.853629) Send: (dash 100.000000) Send: (dash 100.000000)

Da er sich aus der Bewegung heraus drehen wollte, ist die Drehung nur unvollkommen gelungen (vergleiche die Winkelangaben zur Eckfahne flag r t):

Receive: (see 1986 ((flag r t) 30.6 -26) ((ball) 3 -3 0.12 5.8) ((line r) 4.3 -30))

Er sucht den Ball noch zu erreichen und wegzuschlagen:

Send: (dash 100.000000) Send: (dash 100.000000) Send: (kick 100.000000, -134.373864)

Jedoch vergeblich:

Receive: (hear 1989 referee goal_l_4)


Kasten 2: Simulierter Fußball im Internet

Allgemeine Informationen finden sich unter http://www.RoboCup.org/RoboCup/RoboCup.html

sowie unter

http://www.ki.informatik.hu-berlin.de/RoboCup97/.

Die Programme Soccerserver und Soccermonitor sind unter

http://ci.etl.go.jp/~noda/soccer/server.html

abrufbar. Die Spielerprogramme schreibt man am besten selbst. Es gibt aber auch Beispielprogramme auf den genannten Web-Seiten. Allerdings benötigen 24 Programme (Soccerserver, Soccermonitor und 22 Spielerprogramme) schon eine beträchtliche Rechenleistung, wie sie nur eine größere Workstation bietet.

Zum Betrachten der RoboCup-Spiele genügt dagegen ein PC. Den Logplayer, das Programm, das ein aufgezeichnetes Match abspielt, bekommt man zusammen mit dem Soccerserver und dem Soccermonitor, während die Protokolle (log-files) der Spiele selbst unter

ftp://ci.etl.go.jp/pub/soccer/log/RoboCup97/

zum Herunterladen bereitstehen.



Aus: Spektrum der Wissenschaft 1 / 1998, Seite 20
© Spektrum der Wissenschaft Verlagsgesellschaft mbH
1 / 1998

Dieser Artikel ist enthalten in Spektrum der Wissenschaft 1 / 1998

Lesermeinung

Beitrag schreiben

Wir freuen uns über Ihre Beiträge zu unseren Artikeln und wünschen Ihnen viel Spaß beim Gedankenaustausch auf unseren Seiten! Bitte beachten Sie dabei unsere Kommentarrichtlinien.

Tragen Sie bitte nur Relevantes zum Thema des jeweiligen Artikels vor, und wahren Sie einen respektvollen Umgangston. Die Redaktion behält sich vor, Leserzuschriften nicht zu veröffentlichen und Ihre Kommentare redaktionell zu bearbeiten. Die Leserzuschriften können daher leider nicht immer sofort veröffentlicht werden. Bitte geben Sie einen Namen an und Ihren Zuschriften stets eine aussagekräftige Überschrift, damit bei Onlinediskussionen andere Teilnehmer sich leichter auf Ihre Beiträge beziehen können. Ausgewählte Lesermeinungen können ohne separate Rücksprache auch in unseren gedruckten und digitalen Magazinen veröffentlicht werden. Vielen Dank!