KI-Programmierung Teil 07: Lernen durch Erfahrung

“Aus Fehlern wird man klug!” Diese so wichtige Aussage wird Dreh- und Angelpunkt des gesamten Kapitels sein. Wie bringt man eine KI-Einheit dazu, aus ihren Fehlern zu lernen.
Zunächst einmal müssen wir definieren, aus welchen Fehlern die Einheit überhaupt etwas lernen soll. Im aktuellen Programmbeispiel machen wir die Sache nicht unnötig kompliziert und legen fest, dass die KI immer dann einen Fehler macht, wenn sie sich unnötigerweise einem Risiko aussetzt. Die Betonung liegt auf unnötig, denn es gibt auch Situationen, da lässt sich ein Risiko einfach nicht vermeiden.

Damit eine KI-Einheit ihr Verhalten ändern kann, muss sie sich die Anzahl der kritischen Situationen „merken“ können, in die sie durch eine falsche Entscheidung geraten ist. Weiterhin muss überprüft werden, ob überhaupt eine kritische Situation vorliegt. An dieser Stelle kommt die Check_AIEntity_AttackBehaviour()-Funktion ins Spiel. Zunächst wird überprüft, ob sich eine Einheit im Angriffs- bzw. Jagdzustand befindet. Sollte dies der Fall sein, wird überprüft, ob die gejagte Einheit ebenfalls auf der Jagd ist. Gefährlich wird es erst dann, wenn sich beide Einheiten gegenseitig jagen. In diesem Fall wird für beide Einheiten die Membervariable NumCriticalSituations um den Wert eins erhöht.

void Check_AIEntity_AttackBehaviour(CAIEntity* pAIEntity, long NumEntities)
{
    long i, j;

    for(i = 0; i < NumEntities; i++)
    {
        if(pAIEntity[i].BehaviourState_Chase == true)
        {
            j = pAIEntity[i].IDOfSelectedEnemy;

            if(pAIEntity[j].BehaviourState_Chase == true)
            {
                // beide Einheiten jagen sich gegenseitig:
                if(pAIEntity[j].IDOfSelectedEnemy == i)
                {
                    pAIEntity[i].NumCriticalSituations++;
                    pAIEntity[j].NumCriticalSituations++;
                }
            }
        }
    }
}

Erfolgreiches Lernen für dazu, dass sich unser Verhalten ändert. Genauer gesagt, das Verhalten in Situationen, in denen man die Wahl zwischen verschiedenen Verhaltensweisen hat. Auf unsere KI-Einheiten übertragen bedeutet das, dass sich mit der Zeit die Verhaltensprofile verändern. Eigens zu diesem Zweck wurde die CAIEntityBehaviourProfile-Klasse um die Replace_ProfileValue()-Methode erweitert.
Ersetzen wir zur Übung einfach mal einen Profilwert für Jagd durch einen für Flucht, damit sich die KI-Einheit in Zukunft vorsichtiger verhält:

// Flucht (1) statt Angriff (0):
AIEntityBehaviourProfile->Replace_ProfileValue(0, 1);

Jede KI-Einheit macht mit der Zeit ihre eigenen Erfahrungen und entwickelt daher ihr individuelles Verhaltensprofil. Aus Sicht des Programmierers muss also jede CAIEntity-Instanz mit einer eigenen CAIEntityBehaviourProfile-Instanz arbeiten. Die CAIEntityBehaviourProfile-Methode Clone() ermöglicht nun die Vervielfältigung eines einmal erstellten Verhaltensprofils. Aufgerufen wird diese Methode ihrerseits durch die Clone_AIEntityBehaviourProfile()-Methode der CAIEntity-Klasse beim Anlegen eines eigenen Verhaltensprofils. Dabei wird ein zuvor angelegtes Profil geklont und für die zukünftige Verwendung in der CAIEntity-Instanz gespeichert.

class CAIEntityBehaviourProfile
{
public:

    long  ProfileSize;
    long* Profile;

    CAIEntityBehaviourProfile();
    ~CAIEntityBehaviourProfile();

    // neu hinzugekommene Methode:
    void Clone(CAIEntityBehaviourProfile* pAIEntityBehaviourProfile)
    {
        SAFE_DELETE_ARRAY(Profile)

        ProfileSize = pAIEntityBehaviourProfile->ProfileSize;

        Profile = new long[ProfileSize];

        for(long i = 0; i < ProfileSize; i++)
            Profile[i] = pAIEntityBehaviourProfile->Profile[i];
    }

    void Set_ProfileSize(long size);
    void New_ProfileEntry(long entry, long IDOfProfileElement);

    // neu hinzugekommene Methode:
    void Replace_ProfileValue(long oldValue, long newValue)
    {
        for(long i = 0; i < ProfileSize; i++)
        {
            if(Profile[i] == oldValue)
            {
                Profile[i] = newValue;
                return;
            }
        }
    }
};

Die meisten Erweiterungen im Vergleich zum vorangegangenen Kapitel hat die CAIEntity-Klasse erfahren. Die erste wichtige Änderung wurde ja bereits erwähnt – die AIEntityBehaviourProfile-Membervariable speichert ein individuelles Verhaltensprofil, das sich mit der Zeit durch Lernprozesse weiterentwickelt. Erzeugt wird das individuelle Profil mittels der Clone_AIEntityBehaviourProfile()-Methode, welche ein bereits existierendes Verhaltensprofil klont.

Für die Verhaltensbeurteilung sind zwei weitere Variablen hinzugekommen. Die Variable NumCriticalSituations speichert die Anzahl der kritischen Situationen, in die sich eine Einheit durch ihr Fehlverhalten gebracht hat, und die Variable NumCriticalSituationsTolerated speichert die Anzahl der tolerierbaren Fehlverhalten, bis sich diese letztlich auf das Verhaltensprofil auswirken. Je größer die Anzahl ist, umso langsamer erfolgt der Lernprozess. Festgelegt werden kann der Toleranzwert mithilfe der Set_BehaviourEvaluationParameter()-Methode.

Der eigentliche Lernprozess verbirgt sich hinter der Evaluate_Behaviour()-Methode und ist erstaunlich simpel. Wird die Anzahl der tolerierbaren Fehlverhalten überschritten, dann wird der Wert der NumCriticalSituations-Variable auf null zurückgesetzt und ein Profilelement im Verhaltensprofil von Angriff/Jagd auf Flucht umgestellt, wodurch sich die KI-Einheit in Zukunft weniger aggressiv verhalten wird:

if(NumCriticalSituations > NumCriticalSituationsTolerated)
{
    NumCriticalSituations = 0;

    // Flucht (1) statt Angriff (0):
   
AIEntityBehaviourProfile->Replace_ProfileValue(0, 1);
}

Des Weiteren wurde die Klasse um eine zusätzliche Update_BehaviourStates()-Methode erweitert. Im Unterschied zur ersten Methode arbeitet die neue intern mit dem individuellen Verhaltensprofil AIEntityBehaviourProfile. Bis auf eine einzige Codezeile sind beide Methoden völlig identisch:

neue Methode :
// Verhalten "überdenken"
ProfileValue = AIEntityBehaviourProfile->Profile[
               lrnd(0, AIEntityBehaviourProfile->ProfileSize)];
anstelle von:
// Verhalten "überdenken"
ProfileValue = pAIEntityBehaviourProfile->Profile[
               lrnd(0, pAIEntityBehaviourProfile->ProfileSize)];

class CAIEntity
{
public:

    bool BehaviourState_RandomWalk;
    bool BehaviourState_Chase;
    bool BehaviourState_Evade;

    long SavedBehaviorDecision;

    bool EntityIsChased;
    bool EntityIsChasing;

    long IDOfSelectedEnemy;

    D3DXVECTOR3 WorldSpacePosition;
    D3DXVECTOR3 Velocity;
    D3DXVECTOR3 MovementDirection;
    D3DXVECTOR3 ViewDirection;

    // Rundum Wahrnehmung
    float AllAroundPerceptionDistanceMax;
    float AllAroundPerceptionDistanceMaxSq;

    // Jede Einheit kann separat wahrgenommen werden.
    // Der Arrayindex entspricht dem Index der wahrgenommenen
    // Einheit:
    bool*        AllAroundPerception;
    D3DXVECTOR3* AllAroundPerceptionPos;

    // gerichtete Wahrnehmung
    float CosFieldOfView;
    float DirectedPerceptionDistanceMax;
    float DirectedPerceptionDistanceMaxSq;

    // Jede Einheit kann separat wahrgenommen werden.
    // Der Arrayindex entspricht dem Index der wahrgenommenen
    // Einheit:
    bool*        DirectedPerception;
    D3DXVECTOR3* DirectedPerceptionPos;

    // Anzahl der wahrnehmbaren Objekte:
    long NumPerceptionObjects;

    // eigenes Verhaltensprofil:
    CAIEntityBehaviourProfile* AIEntityBehaviourProfile;

    // Verhaltensbeurteilung:
    long NumCriticalSituations;
    long NumCriticalSituationsTolerated;

    CAIEntity();
    ~CAIEntity();

    // neu hinzugekommene Methode:
    void Clone_AIEntityBehaviourProfile(
         CAIEntityBehaviourProfile* pAIEntityBehaviourProfile)
    {
        SAFE_DELETE(AIEntityBehaviourProfile)

        AIEntityBehaviourProfile = new CAIEntityBehaviourProfile;

        AIEntityBehaviourProfile->Clone(pAIEntityBehaviourProfile);
    }

    // Wahrnehmungen zurücksetzen:
   
void Reset_Perceptions(void);

    // neu hinzugekommene Methode:
    void Set_BehaviourEvaluationParameter(
         long numCriticalSituationsTolerated)
    {
        NumCriticalSituationsTolerated = numCriticalSituationsTolerated;
    }

    void Set_NumPerceptionObjects(long numObjects);

    void Set_AllAroundPerceptionParameter(float distance);

    void Set_DirectedPerceptionParameter(float distance,
                                         float cosFieldOfView);

    void Set_Random_WorldSpacePosition(float minX, float maxX,
                                       float minY, float maxY,
                                       float minZ, float maxZ);

    // PossibilityOfBehaviourProfileUsage: Legt die Wahrscheinlichkeit
    // für die Nutzung des gewählten Verhaltensprofils fest.
   
// PossibilityOfSavedBehaviorDecisionUsage: Legt die Wahrscheinlichkeit
    // fest, wie häufig die zuletzt gewählte Verhaltensweise neu
    // "überdacht" werden soll.
    // Viele Änderungen in schneller Folge wirken unnatürlich!!

   
void Update_BehaviourStates(float PossibilityOfBehaviourProfileUsage,
         float PossibilityOfSavedBehaviorDecisionUsage,
         CAIEntityBehaviourProfile* pAIEntityBehaviourProfile);

    // Die zweite Methode arbeitet mit dem in der Klasse gespeicherten
    // Verhaltensprofil "AIEntityBehaviourProfile", dass sich zur Laufzeit
    // durch Lernprozesse und Erfahrungen verändert.
   
// Ansonsten sind beide Update_BehaviourState()-Methoden identisch.

    // neu hinzugekommene Methode:
    void Update_BehaviourStates(float PossibilityOfBehaviourProfileUsage,
         float PossibilityOfSavedBehaviorDecisionUsage);

    // neu hinzugekommene Methode:
    void Evaluate_Behaviour(void)
    {
        // Verhaltensbeurteilung:

       
if(NumCriticalSituations > NumCriticalSituationsTolerated)
        {
            NumCriticalSituations = 0;

            // Flucht (1) statt Angriff (0):
           
AIEntityBehaviourProfile->Replace_ProfileValue(0, 1);
        }
    }

    void Chase(float velocity);
    void Evade(float velocity);
    void RandomWalk(long DirectionChangeFactor, float minVelocity,
                    float maxVelocity);
};

Abschließend möchte ich ihnen noch zeigen, wie sie KI-Klassen in ein eigenes Testprogramm integrieren können:

Initialisierungsarbeiten…

Schritt 1: Initialisierung der Verhaltensprofile

NumBehaviourProfiles = 2;
AIEntityBehaviourProfile = new CAIEntityBehaviourProfile[
                               NumBehaviourProfiles];

for(i = 0; i < NumBehaviourProfiles; i++)
{
    AIEntityBehaviourProfile[i].Set_ProfileSize(100);

    // Zufälliges Verhaltensprofil erzeugen:e
    for(j = 0; j < AIEntityBehaviourProfile[i].ProfileSize; j++)
        AIEntityBehaviourProfile[i].Profile[j] = lrnd(0, 2);
}

Schritt 2: Initialisierung der KI-Einheiten

NumAIEntities = 12;

AIEntity = new CAIEntity[NumAIEntities];

for(i = 0; i < NumAIEntities; i++)
{
    AIEntity[i].Set_Random_WorldSpacePosition(-8.0f, 8.0f,
                                              -8.0f, 8.0f,
                                              50.0f, 50.0f);

    AIEntity[i].Set_AllAroundPerceptionParameter(6.0f);
    AIEntity[i].Set_DirectedPerceptionParameter(10.0f, 0.8f);

    AIEntity[i].Set_NumPerceptionObjects(NumAIEntities);

    AIEntity[i].Clone_AIEntityBehaviourProfile(
                &AIEntityBehaviourProfile[lrnd(0, NumBehaviourProfiles)]);

    AIEntity[i].Set_BehaviourEvaluationParameter(10);
};

In der Spielschleife…

Schritt 1: Bewegung der KI-Einheiten

for(i = 0; i < NumAIEntities; i++)
{
    AIEntity[i].RandomWalk(150, 0.004f, 0.008f);
    AIEntity[i].Chase(0.010f);
    AIEntity[i].Evade(0.005f);
}


Schritt 2: Wahrnehmungen der KI-Einheiten ermitteln

Check_AIEntity_DistancesAndPerception(AIEntity, NumAIEntities);

Schritt 3: Verhaltensweise der KI-Einheiten aufgrund ihrer Wahrnehmungen festlegen

for(i = 0; i < NumAIEntities; i++)
    AIEntity[i].Update_BehaviourStates(100.0f, 80.0f);

Schritt 4: Anzahl der kritischen Situationen zählen, die sich aufgrund von Fehlverhalten ergeben

Check_AIEntity_AttackBehaviour(AIEntity, NumAIEntities);

Schritt 5: lernen

for(i = 0; i < NumAIEntities; i++)
    AIEntity[i].Evaluate_Behaviour();