Diesem Artikel folgt eventuell eine neue Serie, eine Serie über (Browser)Gamebots, deren Verhalten und natürlich Künstliche Intelligenz. Denn Spiele zu “brechen” kann nicht nur über Hacks geschehen; Es kann auch durch ein gut gesteuertes Programm welches dem Spieler Arbeit abnimmt passieren!

Konkret geht es in diesem Artikel um eine sog. Finite State Machine. Dieses ist ein Grundansatz der KI-Programmierung. Diese beschränke KI kann auf bestimme Situationen reagieren, wenn diese nur festgelegt sind. Dadruch ergibt sich ein mehr oder weniger komplexes Netz aus Statii und Verhaltensweisen. Erklären kann man das am besten an dem Verhalten von Tieren: Fressen, schlafen und weg rennen sind solche Grundzustände, dabei wird jeweils in dem aktuellen Zustand entschieden was weiter gemacht wird bzw. in welchen Zustand als nächstes gewechselt wird.

In der Botprogrammierung ist das ganz ähnlich. Unser Bot reagiert auf verschiedene Parameter (Input) und erwiedert der Situation dementsprechend durch ein Zustandswechsel (Output). Wenn ein Bot für einen der vielen Farmvilleklons bemerkt, dass genügend Früchte vorhanden sind, so werden sie geerntet. Oder wie man auch so schön sagt: Aktion -> Reaktion.

Eine solche Finite State Machine wird im folgenden anhand eines Beispiels implementiert. Dabei ist lediglich Logik, Verständnis für abstrakte Klassen sowie der Umgang von Templateklassen vonnöten. Aber los geht es mit der Basisklasse, die einen State repräsentiert.

// Eine abstrakte Klasse welche einen Zustand repräsentiert
    public abstract class State<T> where T : class
    {
        // Jeder Zustand bekommt einen eindeutigen Namen
        public String Name = typeof(T).Name + "_NOT_DEFINED";
 
        // Eine abstrakte Funktion welche das Verhalten des Zustands beinhaltet
        public abstract void Run(T Parent);
    }

Eigentlich nur 3 Zeilen, aber diese Zeilen haben es in sich: Die abstrakte Klasse State bekommt ein Template <T> zugewiesen, wobei T jeden Type annehmen kann. Dabei kann man sich T, wenn einmal definiert, als einfachen Type vorstellen. Eine List<T> ist nichts anderes. Warum wir das machen klärt sich spätenstens bei dem Beispiel auf.

Um die States beim Debuggen zu unterscheiden ist es nützlich ein eindeutigen Namen mit anzugeben. Die letzte abstrakte Funktion Run wird einfach den “Ablaufcode” des Zustand enthalten. Dabei erwartet Run einen Parameter “Parent”. Parent (auch Elternteil, in diesem Fall Besitzer) wird ein von uns vordefinierten Type sein. Dabei wird dieser Parameter verwendet um auf den Bot (bzw. Zustandhalter, Tier, Whatever) zugreifen zu können. Keine Sorge, das sollte später noch klarwerden =)

Die Managerklasse ist entwas länger, dafür fast selbsterklärend:

public class StateEngine<T> where T : class
    {
        // Wenn wir zwischen vorherigem und aktuellem State umschalten wollten ganz nützlich
        public State<T> PreviousState;
        public State<T> CurrentState;
 
        // Der Besitzer der Stateengine und somit auch der Zustände
        public T StateEngineOwner;
 
        // Der Konstruktur setzt einfach den Parent vom generischen Type T
        public StateEngine(T Parent)
        {
            this.StateEngineOwner = Parent;
        }
 
        // Ändert den aktuellen Zustand in einen neuen
        // Der zweite Parameter gibt an ob der neue Zustand aufgerufen werden soll
        public void ChangeState(State<T> NewState, bool RunNewState)
        {
            this.PreviousState = CurrentState;
            this.CurrentState = NewState;
 
            if (RunNewState)
                this.RunCurrentState();
        }
 
        // Ruft den aktuell gesetzen Zustand auf
        public void RunCurrentState()
        {
           this.CurrentState.Run(StateEngineOwner);
        }
    }

Diese (wieder) generische Klasse StateEngine<T> verwaltet die Statii, schaltet zwischen den Zuständen hin und her und ruft diese auf. Dabei ist der “Besitzer” der StateEngine wieder vom festgelegten Type T, die States werden hier auch mit dem selben Type deklariert.

Soweit zum theoretischen Teil, in einem angewandten Beispiel wird das ganze viel klarer: Das Beispiel ist zugegebenermaßen nicht komplett selbst erfunden, sondern aus diesem hervorragenden Buch etwas abgeschaut und vereinfacht. Aber Beispiel ist Beispiel

Ein imaginärer Bergarbeiter sucht in Karlifonien nach Gold. Dabei kennt er folgende Zustände: Schlafen, Gold schürfen und trinken. Dabei bestimmt die Zeit (Input) welche Aktion (Output) er durchführt und wann die Zustände gewechselt werden. Eine finale Ausgabe des Beispiels zu Beginn:

Die Miner-Klasse zu erstellen ist auch schon der schwierigste Teil des Beispiels:

// Eine Testklasse für die FSE
// Eine Testklasse für die FSE
    public class TestMiner
    {
        // Die Zeit bestimmt was vor sich geht
        public int iTime; // From 0 - 24
        // Die Anzahl der Goldnuggets die er besitzt
        public int iGoldGained;
 
        // Die StateEngine des Miners vom TYPE TestMiner -> So kann man die Klasse ansprechen
        public StateEngine<TestMiner> StateMachine;
 
        // Der Konstruktor setzt einfach Grundwerte
        // und übergibt der StateEngine als Parent sich selbst (this).
        // Danach wird ein Grundstatus "SleepState" gesetzt.
        public TestMiner()
        {
            this.iTime = 0;
            this.iGoldGained = 0;
 
            this.StateMachine = new StateEngine<TestMiner>(this);
            this.StateMachine.ChangeState(new SleepState(), false);
        }
 
        // Beim Aufruf der Update-Funtkion wird die Zeit erhöht
        // und der aktuelle Zustand ausgeführt.
        public void Update()
        {
            this.iTime++;
            this.StateMachine.RunCurrentState();
        }
    }

Die Engine und der Konstruktor der Engine sollten die einzigen Verständnisprobleme darstellen. Um später von den einzelnen States auf die Miner Klasse zugreifen zu können, brauchen wir der Engine zu sagen, dass der Besitzer der Engine auch ein Miner ist. Dadurch bekommen wir Zugriff auf die Variablen des Miners die wir brauchen werden. Dann wird im Konstruktur ein this-Pointer übergeben, welcher die StateEngine mit der Miner-Instanz “verlinkt”.

Soweit sogut, der Schlafensstate ist der wohl einfachste, daher gibts ihn hier direkt abgedruckt:

public class SleepState : State<TestMiner>
    {
        public override void  Run(TestMiner Parent)
        {
            if (Parent.iTime <= 6 || Parent.iTime > 20)
            {
                Console.WriteLine(String.Format("[Time: {0}:00] Miner is sleeping and dreaming of catz <3",Parent.iTime));
            }
            else
            {
                Console.WriteLine(String.Format("[Time: {0}:00] The alarm rings at 7 o'clock, Miner gets up and goes to work",Parent.iTime));
                Parent.StateMachine.ChangeState(new WorkState(), false);
            }
        }
    }

Zu beachten ist dass Run nicht mehr mit dem Parameter T überschrieben wird, sondern direkt TestMiner eingesetzt wird. Toll, nicht? SleepState erbt von State<TestMiner>, also wird statt T direkt TestMiner verwendet.

Sobald die Zeit größer wie 6:00 wird, steht der Miner auf und der aktuelle State setzt über den Parent und dessen StateEngine einen neuen State, den WorkState. Dieser sieht natürlich ganz ähnlich aus:

public class WorkState : State<TestMiner>
    {
        public override void Run(TestMiner Parent)
        {
            if (Parent.iTime < 14)
            {
                Parent.iGoldGained++;
                Console.WriteLine(String.Format("[Time: {0}:00] Miner works hard, he gained 1 gold! He total got {1} nuggets", Parent.iTime, Parent.iGoldGained));
            }
            else
            {
                Console.WriteLine(String.Format("[Time: {0}:00] Miner is tired, he goes home to relax", Parent.iTime));
                Parent.StateMachine.ChangeState(new ChillingAtHomeState(), false);
            }
        }
    }

Zur Vollständigkeit noch der letze State, es sollte allerdings kein Vorbild sein 5 Stunden am Stück allein zu trinken

public class ChillingAtHomeState : State<TestMiner>
    {
        public override void Run(TestMiner Parent)
        {
            if (Parent.iTime < 20)
            {
                Console.WriteLine(String.Format("[Time: {0}:00] Miner is drinking beer and vodka", Parent.iTime));
            }
            else
            {
                Console.WriteLine(String.Format("[Time: {0}:00] Miner is drunken enough, he's going to sleep reeealy deep now...", Parent.iTime));
                Parent.StateMachine.ChangeState(new SleepState(), false);
            }
        }
    }

Der Code wird im Beispiel folgendermaßen verwendet, sollte auch selbsterklärend sein:

TestMiner Miner = new TestMiner();
 
            while (Miner.iTime < 24)
            {
                Miner.Update();
                System.Threading.Thread.Sleep(500);
            }
 
            Console.ReadLine();

Das Ganze war jetzt relativ simple gehalten, im echten Anwendungsfall ist mit mehreren tausenden Zeilen Code zu rechnen um möglichst viele und komplexe Situationen abzudecken. Dabei werden die States ineinandergreifen, Unterstates entstehen (z.B. auf der Flucht jemanden fressen ) und vieles mehr. Umsetzen kann man dieses State-Prinzip allerdings nicht nur für KIs, sondern auch für weitere Zustandssituationen wie z.B. in einem Tic-Tac-Toe-Spiel. Dabei wären die Zustände entsprechend “Spieler1AmZug, Spieler2AmZug und Spielresultat anzeigen”.

Diese einfache Form kann nun erweitert werden. Denkbar wäre es Message-System, damit mehrere “KIs” miteinander Interagieren können. Im o.g. Buch hat die Frau des Miners ihn über eine Message zum Mittagessen gerufen, welches einen Statewechsel zufolge hatte.

Greez Easy

6 people like this post.

Like

Unlike