|
www.jobo2000.de - delphi |
|
| Home - Delphi - Video - Art - Render - Texte - Spiele - Download - Links - Mail | |
| Tipps:
Texte: |
Das Schreiben "intelligenter" Spiele - Zafer Barutcuoglu
============================================================ Jahrzehnte sind vergangen seit der Ersterscheinung von Schach Computern bis zu den listigen Strategien von Warcraft II, und es sieht so aus, als ob die kuenstliche Intelligenz auch in der Zukunft genau so gefragt sein wird. Besonders durch den juengsten Kampf zwischen Kasparov und Deep Blue, hat dieses Thema erst wieder weltweite Popularitaet genossen. Da Kuenstliche Intelligenz (AI) eines der aeltesten und groessten Forschungsgebiete in der Computer Wissenschaft ist, ist es mir nicht moeglich, ein Lies-das-weiss-alles Tutorial hier zu bieten. Nun, wie nur wenige Hausfrauen die eine Waschmaschine benutzen auch wirklich wissen wie sie funktioniert, brauchen auch wir nicht zu tief in unser Thema hineintauchen ; nur tief genug um es in unseren Spielen zu nutzen. Was ist Intelligenz? Amuesant ist nur, dass sich diese einzige Frage eine ganze Menge der wissenschaftlichen Texte ueber AI zum Thema gemacht haben. In unserem Fall, wuerde die Antwort, die Moeglichkeit den Spieler wirklich herauszufordern, sein. Aber lassen Sie uns nicht in diese Kontroverse gelangen und usere Zeit der richtigen Frage widmen: Wie? So, wie koennen wir AI erreichen? Auch dies muss wieder zum aktuellen
Fall beruecksichtigt werden, und sogar noch spezieller zu dem zu
prorammierenden Spiel. Es gibt vielzaehlige Varianten, geschaffen fuer die
verschiedensten Aufgaben. Ein Schach Algorhythmus ist keineswegs gleich
dem eines Fussballspieles, oder eines "GO", einem anderen
Spiels. Dafuer basieren unsere Methoden voellig auf der Natur des
Programms. Da ich hier nicht AI fuer jedes einzelne Spiel beschreiben
kann, werde ich versuchen die meistens angewandten Hauptschritte zu
beschreiben. Der einfachste Level ===================== Wenn Sie jehmals ein Arcade Spiel mit Computergegnern geschrieben haben, dann basierten diese auf dem Was-ist-wenn Prinzip. Dies ist dann der einfachste Level der AI. Doch es ist ja noch nicht mal klar das dies tatsaechlich AI ist, aber wie ich schon erwaehnte, werde ich das hier nicht weiter dikutieren. Denken Sie immer nur daran dass ein grosser Teil der AI Wissenschaft, Systeme fuer Experten genannt, nur auf solch einem Grundprinzip basiert, auf einem Was-ist-wenn Frage-Antwort Kasten. Jedoch fuer schwerwiegendere Probleme braucht man irgend etwas besseres. Spielbaeume und Schach ======================= Schach, wie kompliziert es als Strategiespiel zu sein scheint, ist eines der am einfachsten zu analysierenden Spiele. Das kommt daher, dass es ein Brettspiel ist, endlich viele moegliche Positionen ( alles in allem 64), und auch endlich viele Spielsteine(32) hat. Auf allen Positionen hat man als Spieler nur begrenzte und wirklich nicht viele Moeglichkeiten sich zu bewegen. Auf dieser Grundlage koennen wir sagen, dass auf der ganzen Welt nur eine endliche Anzahl von Schach Sequenzen existiert. Ueberall auf dem Schachbrett koennen wir dann alle moeglichen Zuege auflisten. Darueber hinaus koennen wir nach jedem dieser Zuege bestimmen, wie das Spielbrett aussehen wird. Auf diesem Wege koennen wir einen Spielbaum konstruieren. Die Wurzel ist die Ausgangsposition, die Aeste und Zweige Auf diese Art können wir das konstruieren was wir einen Spielbaum nennen, deren Wurzel unsere aktuelle Position ist, dessen Verzweigungspunkte sind Zwischenbrettfälle und dessen Blätter Spielenden sind. Wenn wir diesen Baum einmal am Anfang konstruieren, gewinnen wir praktisch das Spiel EGAL WAS. Wirklich verlieren wir nur, wenn wir schwarz spielend sind und gegen jemanden spielen der ebenfalls den kompletten Spielbaum besitzt. Jedoch praktisch gesehen, ist dieser Baum sehr groß. Sehr sehr sehr groß. Es ist praktisch unmöglich einen vollständigen Spielbaum zu erstellen, auch nicht wenn man die weltbesten Computer der heutigen Zeit benutzt. Bevor wir den ersten Schritt gehen, konstruieren wir den Spielbaum, der am aktuellen Fall, mit einer örtlich festgelegten Tiefe verwurzelt wird. So sind die Blätter notwendigerweise nicht mehr Spielenden. Jetzt muessen wir uns entscheiden in welcher Richtung wir die einzelnen Blaetter entwickeln wollen. Das heißt, welches Blatt ist das vorteilhaftere fuer uns? Für dieses Problem konstruieren wir eine zählende Funktion, die einen Brettfall als Input nimmt, und geben eine numerische Kerbe aus, die anzeigt, welche Seite in einer besseren Position ist und wieviel besser diese Position ist. Diese Funktion hängt gewöhnlich von der Zahl und Art der Stücken die auf jeder Seite uebrig geblieben sind ab, ebenfalls von der Mobilität(Zahl der Bewegungen möglich), der Fähigkeit zu castseln und anderen Faktoren. Dies wird Ihrer Erfahrung des Schachspielens überlassen. Wenn wir diese Funktion haben, zählen wir die Blattpositionen. Dann, annehmend, daß unser Konkurrent seinen besten Zug machen wird und daß wir unser bestes machen werden, rücken wir den Baum vor. Dieses wird der minimaxalgorithmus genannt weil, wenn der Konkurrent am Zug ist, werden wir Minimums nehmen, da er versucht unsere Punktzahl zu minimieren, und wenn wir am Zug sind, werden wir das maximale nehmen. Jeder Knotenpunkt nimmt das Mini-oder Maximum seiner Kinder, und wenn wir die Stufe unterhalb der Wurzel erreichen, haben wir eine Liste von moeglichen Zuegen, bei den jeder Zug eine bestimmte Punkteanzahl hat die von den Blaettern kommt. Dann alles was wir machen muessen, ist den Zug mit der hoechsten Punktanzahl zu machen. So einfach ist das. Die sogenannte Tiefenschicht, zu der wir den Baum konstruieren ist sehr wichtig, da Zeit und Raum exponential ansteigt. Vier Schichten werden als Minimum akzeptiert, aber ich konnte kaum bis 3 in meinem ersten Schach- programm gehen. Andere Methoden existierenen, die die Tiefe bedingt erhöhen, wie zum Beispiel eine Sicherung am Blatt. Dieses, auch wenn sehr einfach und ursprünglich, ist die allgemeine Grundlage für ein Schach- programm, auch wenn es einfach zu gewinnen ist, kann man ein Schachprogramm bekommen, das Anfänger herausfordern wird. Ich tat es. Es waren ungefähr 600 Pascal Zeilen und brachte mir mehr als 600 Seiten von KI bei, weil diese Methode, der Spielbaum, keineswegs auf Schach eingeschränkt wird. In der Tat bildet sie das Skelett von vielen KI-Maschinen herum. Und dennoch tun sie sich ein gefallen!!! Schreiben Sie ein Schachprogramm!!!
Heuristik ========== Beobachten Sie, daß wir die Suchtiefe verringerten haben, um sie anwendbarer zu machen. Dieses ist ein Beispiel der häufig angetroffenen Kompromisse in der Technik. In der Tat ist das wo der Trick bei der Sache liegt, weil jeder weiss wie man die Arbeit erledigt, aber nur der Schnellste gewinnt. Heuristik ist der Name für das Bilden der klugen Kompromisse. Stellen Sie sich ein heuristischen Tour Guide vor, der sie zu den besten Plätzen in der kürzesten Zeit bringt. Ein anderes Beispiel würde ein Auto beim Parken sein. Der Fahrer parkt sein Auto auf den ersten Platz, den er findet, wenn er nahe genug zu seinem Zielpunkt ist, obwohl der andere Plaetze viel naeher am Ziel sein koennten. Ähnlich können Sie Ihren Spielbaum von wirklich dummen Bewegungen entledigen bevor sie sich in ganzer Tiefe auszubreiten, und obgleich diese Bewegung eine äußerst gescheite Falle sein koennte, sind die Vorteile sehr hoch das es keine ist, und dann Ihr Programm läuft nur schneller. Dieses wird alpha- beta-beschneidung oder Beschneidung um es kurz zu sagen. Was auch immer, beachten Sie Ihre Heuristik. Fortgeschrittene Methoden: Planung =================================== Wenn Ihr Problem für einen groben Spielbaum zu schwierig ist, haben Sie sich wirklich ein Problem geschaffen. Wenn Sie zu diesem Punkt kommen, dann entweder Ihre Zeit oder Platz, oder beide, sind nicht getrennt. OK, selbstverständlich ist alles für den Computer getrennt, aber wir wissen, das uns das nicht viel hilft, wenn wir ein Spielbrett von 640x500 Pixel haben, anstelle von den 8x8 Quadraten eines Schachbretts. Ein illustratives Beispiel ist das japanische Spiel Go. Es wird auf einem Rasterfeld von 19x19 grid system mit gespielt und das mit identischen Spielstücken. Und Sie können NICHT mehr als 2 oder 3 Spielzuege voraussehen, weil Sie naemlich nach 3 Spielzuegen 391*391*391=59776471 moegliche Spielkombinationen haben. Zusätzlich, infolge der Natur des Spieles, hängt das Resultat schwer von den Anfangszuegen ab und normalerweise braucht man zwischen 200 und 350 Zuege um ein Spiel zu beenden. In diesen Dimensionen können Sie sich wahrscheinlich leicht vorstellen, daß es unmöglich ist, dieses Spiel auf einem Mikrocomputer zu machen. Glücklicherweise ist dieses nicht so. Unter solchen schweren Problemen können wir nicht mehr auf niedrigen Stufen wie Spielbäumen denken. Wir verwenden hochentwickelte KI-Techniken, wie Planung in diesem Fall. Planung ist der Prozeß des Teilens einer Aufgabe in kleinere Aufgaben, d.h. das sie entsprechend ihrer Natur und Abhängigkeiten geordnet werden und fuehren sie dann in dieser Reihenfolge aus. In unserem Spiel Go, heisst das vielleicht das entscheiden ob man z.B. die Ecken in Angriff nimmt oder die Mitte beherrschen möchte. Ich nehme an, daß Sie das Spiel nicht kennen, aber beachte den Unterschied zwischen dieser Entscheidung und der von, ob man den Ritter oder den Bishop bewegt. Wenn Sie ein wenig darueber nachdenken, werden Sie bemerken, daß real-life Entscheidungen wie Befehlen einer Armee oder Bankbeteiligungen häufig in dieser ausgedehnten Natur sind. Das ist auch, wie Sie ihre eigenen Spiele spielen. So, warum wendeten wir dieses nicht an allen unsere Spiele seit dem Anfang an? Einfach. Was wir benutzten, arbeitete fuer uns. Wenn Sie sich hinsitzen, etwas hands-on Programmierung machen und diese Methoden einführen, werden Sie entdecken wie Sie intelligentere Methoden erhalten und Ihr Code in zunehmendem Maße umfangreich und schwieriger zu handhaben wird. Außerdem sind Spiel-Bäume zum Beispiel leistungsfähiger als Planung beim Schachspielen gewesen. Dieses ist nicht sehr ueberraschend, wenn Sie sich daran erinnern, daß Sie intelligenter als Ihr Computer sind, aber der Computer dafuer schneller rechnen kann. So verwenden Sie einfachere Methoden, wenn Sie können. Coda ===== Obgleich es noch viel mehr ueber KI gibt, worueber ich sprechen möchte, begrenze ich mich auf das programmieren von Spielen, und ich nehme an, das alles sollte euch Programmierern zum weitermachen bewegen. Das Codieren von irgendwas intelligenten bereitet Ihnen ein Vergnügen, das wenige andere Sachen können. Sei es Tic-Tac-Toe oder Warcraft XXI, versuchen Sie es. Lesen Sie, lesen Sie den Code, codieren Sie. Diese drei Wege zahlen sich immer aus. |