Spiele-KI: Wie teste ich Optimierungs-Algorithmen?

Hallo allerseits,

ich bin gerade dabei, für mein kleines Spiel BattleSimulator einen ernstzunehmenden Computergegner zu implementieren. Da sich die Spielregeln nur wenig vom Schachspiel unterscheiden, hab ich dabei auf Algorithmen der Schachprogrammierung zurückgegriffen. Unterschiede gibt es vor allem in den Funktionen zur Zug-Generierung und zur Bewertung einer bestimmten Spielsituation. Die Suche nach dem bestmöglichsten Zug funktioniert aber prinzipiell wie in jedem anderen Schachprogramm auch.

Dazu wird jeder theoretisch mögliche Zug bis zu einer bestimmten Anzahl von Zügen simuliert und dann das Spiel neu bewertet. Um den Zug mit der bestmöglichsten Bewertung zu finden, muß man dann den so entstandenden Baum durchsuchen und dabei das Spiel immer aus der Sicht des jeweiligen Spielers bewerten. Ich verwende dazu eine NegaMax-Suche mit Alpha-Beta-Pruning, um sowenig Knoten wie möglich auswerten zu müssen, und eine iterative Tiefensuche, um so schnell wie möglich ein (vorläufiges) Ergebnis zurückgeben zu können.

Die Details sind aber nicht so wichtig, mir geht es darum, daß die eigentliche Implementierung wesentlich komplexer ist als der Pseudocode bei Wikipedia. Man kann da letztendlich eine Menge schwerwiegender Fehler einbauen, ohne daß diese sich an einer anderen Stelle bemerkbar machen würden. Ich verbringe also eine Menge Zeit damit, gegen meine KI zu spielen, und dann herauszufinden, warum die KI in einer bestimmten Situation "gut" oder "schlecht" gespielt hat.

Hat man z.B. irgendwo ein falsches Vorzeichen gesetzt, dann führt das nicht zu einem Fehler oder zu einer falschen Spielweise. Bemerkbar macht sich das dann evtl. dadurch, daß die KI bei der Eröffnung besonders gut spielt, und im Endspiel eher schlecht (oder umgekehrt). Das läßt sich aber nur durch wiederholtes und aufmerksames Spielen / Debuggen herausfinden.

Im Gegensatz zu der Zug-Generierung oder den Bewertungsfunktionen komme ich nämlich hier mit Unit-Tests nicht besonders weit. Die Suche nach dem "richtigen" Zug ist keine Funktion, die für bestimmte Eingabedaten bestimmte Ausgabedaten zurückgibt, die man im Unit-Test validieren könnte. Einen "richtigen" (also korrekten) Zug gibt es ja nie, sondern immer nur einen "guten" (also optimalen) Zug. Das einzige Kriterium, von dem man auf eine "gute" oder "richtige" Suchfunktion schließen kann, ist meiner Meinung nach, ob die KI überdurchschnittlich viele Spiele gegen einen Zufallsgegner gewinnt oder nicht. Aber diese Erkenntnis hat mir bisher bei meiner Teststrategie und meiner gezielten Fehlersuche nicht besonders viel weiter geholfen, und bringt mich zu meiner eigentlichen Frage:

Welche Strategien und Herangehensweisen gibt es eigentlich um sicherstellen, daß Implementationen solcher komplexen Algorithmen (besonders aus dem Bereich der künstlichen Intelligenz) fehlerfrei und wie erwartet funktionieren?

Danke schonmal!
Christian

Fehlerfreiheit wirst du nie beweisen können. 😉

Ein geeignetes Bewertungskriterium wirst du am ende wohl selbst bestimmen müssen.

Eine idee währe die Zuge in Aquivalenzklassen einzuteilen. z.B. Schlecht, Ok, Gut. Dann könntest du schonmal Testen in welche Klasse deine KI fällt. Wenn du da dann mehr Arbeit reinsteken willst. kannst du die Zuge auch dynamisch gewichten und dir merken welche zug im endefekt zum Sieg/Niederlage geführt hat. Wichtig währe hier vielleicht Zuge auszuschließen die einfach nicht sein sollen. (Z.B. KI macht immer den gleichen zug hin und her.)

Du kanst die KI auch gegen unterschiedliche Versionen von sich selbst antreten lassen. Dann hast du schon mal einen vergleich der KIs untereinander. Die beiden stärksten kannst du die vieleicht zur grundlage der weiter Entwicklung heranziehen.

Die grundlegende Funktionsweise, der Algoritmen kannst du ja mit UnitTest testen. Für Parameter Y/X/Z sollte ja immer das gleiche Ergebnis raus kommen.

MFG
Björn

Hallo,

entschuldigung, aber ich bin nicht der Meinung, das bei bestimmten Parametern das gleiche Ergebnis kommen muss. Das würde eher eine schlechte KI ergeben, und ist für einen Spieler/Gegner ziemlich leicht auszurechnen.
Das Problem besteht vielmehr darin, das sich ein als gut gewerteter Spielzug im Nachhinein als grober Fehler herausstellen kann. Hier könnte eine Art Bibliothek helfen, auf welche die KI zurückgreift um Fehler dieser Art nur einmal zu machen.
Ich kenne das Spielprinzip jetzt nicht, aber jede gute Schachsoftware verwendet inzwischen mehrere "Datenbanken" um praktisch selbst zu lernen.
Über einstellbare Spielstärken wird die Berechnungstiefe und die Nutzung dieser Daten eingeschränkt, was idR zu mehr Fehlern führt.
Wenn ich aber wenig Erfahrung im Schach habe, gewinne ich trotzdem nicht.

Zum Test noch ein Tipp:
schaffe eine definierte Ausgangssituation, zeichne die Lösung(en) der KI auf und vergleiche mit Deiner gedachten Lösung. So kommst Du am schnellsten auf Fehler (die der KI und die eigenen!). Gleichzeitig kannst Du auch testen, ob es tatsächlich eine KI oder ein reiner "Logikkasten" ist. Die KI sollte bei (nicht zu einfacher Ausgangssituation) auf unterschiedliche Lösungen kommen.

Gruß
schnelleHelga

KI und Optimierungsalgorithmen wirst Du immer mit statistischen Mitteln testen müssen.
Dein Design sollte Dir erlauben, dass Du sowohl die Bewertung einer Position als auch den errechneten Zug nachspielen kannst.
Dann brauchst Du eine Datenbank mit diesen Werten und vergleichst vorher nachher mit statistischen Massgrößen, wie sehr sich die Werte auf Deine Datenbank verändern und schaust, dann im Detail vielleicht die Positionen an, wo die Veränderung signifikant ist.

hm.. keine leichte Fragestellung.

Ich könnte mir jetzt schon einige automatisierte Tests vorstellen, um deine Logik abzusichern (ich spreche aber explizit nicht von UnitTests). Du hast doch sicherlich verschiedene KI stärken? Sprich: Leichte KI findet schlechtere Lösung als eine Schwere KI. In einem automatisierten Tests könntest du virtuell KI gegen KI antreten lassen und davon ausgehen, dass KI mit geringerer Schwierigkeitsstufe immer gegen eine KI höherer Schwierigkeitsstufe verlieren müsste.. alles andere sollte ja rein theoretisch nicht möglich sein, zumindest, wenn die Bewertungs-Logik sauber ist.

Eine Prüfung in der Testautomatisierung kann auch sein, dass bei einem solchen automatischen Lauf eine utopische Anzahl X an Zügen nicht überschritten werden darf.
.. oder ähnliche andere Prüfungen, welche man per Code ausdrücken kann.

Alles solche Sachen, welche ärgerlich wären, diese auf manuellem Weg zu finden.

Wie aber auch die vorredner schon schreiben... ob eine schwere KI wirklich schwer ist, lässt sich auch in meinen Augen deutlich schwieriger verifizieren. Es ist ja auch irgendwo subjektiv, denn der Schwierigkeitsgrad hängt ja immer von der Erfahrung des Spielers ab. Da würde ich jetzt eher wieder empfehlen, ab einem gewissen Stand viel mit anderen möglichen Spielern zu testen.

Hoffe, das hilft etwas weiter..

Viele Grüße
Roland

Hallo miteinander,

danke für die vielen Tips.

Ein geeignetes Bewertungskriterium wirst du am ende wohl selbst bestimmen müssen.

Da liegt meiner Meinung nach das Hauptproblem. Wenn man einen beliebigen Zug als "gut" oder "schlecht" (bzw. "besser" oder "schlechter" als einen beliebigen anderen Zug) qualifizieren könnte - dann bräuchte man keine KI mehr.

Es ist ja selbst dort gar nicht so einfach, einen geeigneten Bewertungsmaßstab zu finden. Ein Zug ist z.B. "gut", wenn er:* Den eigenen Bewegungsspielraum erweitert oder den des Gegners einschränkt (kurzfristig)

• Zu Materialgewinn bzw. gegnerischen Materialverlust führt (kurzfristig)
• Das selbst kontrollierte Gebiet auf dem Spielfeld erweitert bzw. das des Gegners einschränkt (mittelfristig)
• Schneller zum eigenen Sieg bzw. später zum gegnerischen Sieg führt (langfristig)

Das bedeutet halt auch, daß ein Zug, der kurzfristig zu einem hohen Materialverlust führt, langfristig zum eigenen Sieg beitragen kann, bzw. umgekehrt. Aber all diese Entscheidungen werden innerhalb des (rekursiven) Such-Algorithmus getroffen, und der ist eine Art Blackbox für mich, wenn ich Unit-teste.

Meine Idee für die Test-Strategie war daher, die KI vor eine Entscheidung zu stellen, die sehr eindeutig ist. Hier ein paar Beispiele, um das Prinzip zu verdeutlichen:* In einer Spielsituation, bei dem ein einziger Zug zum sofortigen Sieg führt, erwarte ich von der Suche, daß sie diesen Zug findet.

• Umgekehrt erwarte ich in einer Spielsiuation, bei der der Gegner mit einem Zug das Spiel gewinnen kann, daß die KI sich für einen Zug entscheidet, der genau das verhindert.
• In Situationen, wo es die Möglichkeit zum Angriff und die Möglichkeit zum Ausweichen gibt, immer die überlegene Einheit angreifen und die unterlegene Einheit ausweichen läßt.

Alle diese Szenarien lasse ich mit unterschiedlichen Suchtiefen berechnen, d.h. die Anzahl der Züge bzw. die Anzahl der Ebenen im Suchbaum. Dabei erwarte ich immer das gleiche Ergebnis, aber es gibt auch andere Varianten, bei denen ein "besserer" Zug erst nach einer bestimmten Suchtiefe gefunden wird. Auch das teste ich erfolgreich.

KI und Optimierungsalgorithmen wirst Du immer mit statistischen Mitteln testen müssen.

Dieser Gedanke hat mich dann dazu gebracht, die KI mit immer höheren Suchtiefen (Spieler) gegen sich selbst in der geringsten Suchtiefe (Gegner) spielen zu lassen. Meine Erwartung, daß zufällig gewählte Spiele mit steigender Suchtiefe nach immer weniger Spielzügen gewonnen werden, ist dabei bestätigt worden.

Da das soweit alles funktioniert hat, habe ich daraus geschlossen, daß meine Implementierung des Such-Algorithmus funktionsfähig war. Also hab ich mich an die Optimierung der Performance gemacht und u.a. die von schnelleHelga vorgeschlagenen Datenbanken (sogenannte Transposition Tables) eingebaut.

Und dabei hab ich durch Zufall bemerkt, daß irgendwo in der Suchfunktion ein falsches Vorzeichen gesetzt war. Das führte dazu, daß bestimmte Züge falsch bewertet wurden, also "gut" statt "schlecht" und umgekehrt.

Allerdings laufen alle meine Unit-Tests erfolgreich durch, und zwar vor und nach der Vorzeichenänderung. Daraus schließe ich, daß meine Tests die Suchfunktion nur unzureichend auf ihre eigentliche Funktionalität überprüfen.

Jetzt habe ich halt in meinem bisherigen Berufsleben noch keine Erfahrung mit künstlicher Intelligenz oder Optimierungs-Algorithmen gemacht. Aber ich vermute, daß es sich hierbei um ein allgemeines Problem handelt, das bei Algorithmen auftritt, deren Aufgabe es ist, ein "optimales" Ergebnis zurückzugeben anstatt ein "richtiges". Und ich gehe mal davon aus, daß andere Leute vor mir bereits vor diesem Problem standen und die eine oder andere Möglichkeit gefunden haben, die Funktionsfähigkeit solcher Algorithmen sicherzustellen.

Christian

Deine Bewertung Kriterien fürs gesammte wirst du sicher mit der Zeit immer weiter Anpassen müssen.

Was gut ist ist meist wirklich schwer zu sagen, was schlecht ist geht da meist schon einfacher. Wenn ich beim Schach einen Zug mache mit dem ich nicht gewinnen kann, aber im nächsten dadurch Schach Matt bin, ist es ein Schlechter. Also kann ich schon mal Relative einfach eine Klasse von Schlechten Zügen festlegen. Und darauf testen.

@schnelleHelga
Mir ging es hier um die Teil Algorithmen, wenn in denen keine "Zufallszahlen" erzeugt werden, sollte bei gleichen Parrametern immer das gleiche herauskommen.

Computer würfeln nicht. Da kann ich mich aber auch irre, dann bin ich wenigstens in prominenter Begleitung. Bei der gelegenheit heute schon nach der Katze geschaut. 😉

live long and prosper
Björn

Hallo allerseits,

wenn wir davon reden, die KI gegen sich selbst in unterschiedlichen Spielstärken antreten zu lassen, dann reden wir eigentlich über Integrations-Tests, und nicht über Unit-Tests. Unit-Tests sind deterministisch und sollten eine eindeutige Aussage dazu treffen, ob der Rückgabewert einer getesteten Funktionalität der erwartete Wert ist, oder nicht.

Der NegaMax-Algorithmus hat auch keine Zufallsfunktionen, die das Testen erschweren könnten. D.h., auch wenn es sich nur um ein optimales Ergebnis handelt, ließe sich dieses Ergebnis vorher bestimmen, und der Algorithmus sollte jedesmal das gleiche Ergebnis zurückliefern.

Es sind eigentlich alle Voraussetzungen gegeben, die Implementierung mit Unit-Tests auf Herz und Nieren zu prüfen. Man muß nur geeignete Testfälle wählen. Die Aufgabe der Suchfunktion ist es nämlich nicht, ein Spiel zu gewinnen o.ä., sondern eine baumartige Datenstruktur zu durchsuchen.

Eigentlich muß ich in meinen Tests nur solche Bäume erstellen, bei denen ich das bestmögliche Suchergebnis bereits im Voraus kenne, und dann überprüfen, ob die Suchfunktion diesen Knoten auch findet.

Die Herausforderung ist dabei eigentlich nur, die Testfälle so zu konstruieren, daß die Suchfunktion möglichst vollständig getestet ist.

Christian

Das Ergebnis des Baums zu testen, ist kein Unit Test.
Aus meiner Sicht hast Du schnell den Effekt, dass das Pflegen der Tests aufwändiger wird, als die eigentliche Code-Anpassung, insbesondere wenn Du eine Änderung machst, die das Ergebnis für jeden Baum minimal verändert.

Hi weismat,

wie würdest du denn dabei vorgehen?

Es geht ja nicht darum, die gesamte KI zu testen oder gar zu optimieren. Es geht erstmal nur darum, die Suchfunktion zu testen.

Meine Analogie dazu ist: Wenn ich eine Funktion testen will, die mir ein Zeichen in einer Zeichenkette finden soll, dann übergebe ich in der Testfunktion eine Test-Zeichenkette mit einem bestimmten Test-Zeichen an die Suchfunktion und überprüfe, ob das Ergebnis das korrekte Test-Zeichen gefunden hat.

Wenn ich jetzt anstatt einer Zeichenkette einen Baum durchsuchen lassen will, dann würde ich genauso vorgehen. Es gibt ja wie gesagt keinen Zufallseinfluß, und wenn der Algorithmus korrekt implementiert ist, muß auch immer das gleiche Ergebnis gefunden werden.

Christian

Der Ansatz ist schon richtig.

Wichtig ist aber auch das Verhalten zu was Passiert wenn bedingungen nicht erfüllt sind. Bei der Suchfunktion wäre also die Frage was Passiert wenn der Zeichen nicht in der Zeichenkette ist.

Randwerte sind auch immer ein Punkt an dem man Testen kann. Wenn du z.B. irgendwas in der Form Zahl < 10 hat. Sind 9 und 10 schon mal gute Test kandidaten. -1, 0 und 1 würden sich da auch noch Abbieten, da sich mit -1 und 0 das verhalten der Zahlen ändert.

Ohne den Code jetzt zu kennen ist es aber schwer da gute Tipps zu geben.

Hi Palin,

was Passiert wenn der Zeichen nicht in der Zeichenkette ist.

Den Sonderfall hab ich bewußte außer Acht gelassen. Bei der Suche im Baum soll ja das beste Ergebnis zurückgegeben werden, also gibt es immer einen Rückgabewert (außer der Baum ist leer, aber dann ist das Spiel zu Ende).

Randwerte sind auch immer ein Punkt an dem man Testen kann. Wenn du z.B. irgendwas in der Form Zahl < 10 hat. Sind 9 und 10 schon mal gute Test kandidaten. -1, 0 und 1 würden sich da auch noch Abbieten, da sich mit -1 und 0 das verhalten der Zahlen ändert.

Das habe ich nicht verstanden, liegt aber evtl. daran:

Ohne den Code jetzt zu kennen ist es aber schwer da gute Tipps zu geben.

Hier ist die prinzipielle Funktionsweise gut erkennbar:

function negamax(node, depth, color)
    if depth = 0 or node is a terminal node
        return color * the heuristic value of node
    bestValue := -
    foreach child of node
        val := -negamax(child, depth - 1, -color)
        bestValue := max( bestValue, val )
    return bestValue

Initial call for Player A's root node
rootNegamaxValue := negamax( rootNode, depth, 1)
rootMinimaxValue := rootNegamaxValue

Der Pseudo-Code ist aus dem Wikipedia-Artikel zum NegaMax-Algorithmus. Dort gibt es auch ein animiertes GIF, das den Algorithmus noch besser veranschaulicht: