Game-AITutorial

Programmieren von KIs für 4×4 TicTacToe – Part 2 – Heuristik-Basierte KI


Im letzten Post haben wir uns das Framework selbst angesehen so wie eine relativ dumme KI. Heute wollen wir jedoch einen ersten Schritt in Richtung ernst zu nehmenden Gegner machen, indem wir so genannte “Heuristiken” benutzen.
Heuristiken kann man umschreiben als “Algorithmen/Methoden, die in kurzer Zeit eine ziemlich gute Lösung berechnen”. Heuristiken kann man auch heranziehen, um abzuschätzen wie gut eine Lösung/Aktion ist. Das mag sich etwas theoretisch und schwammig anhören, aber wenn wir Heuristiken mit “Daumenregeln” vergleichen, sollte das Prinzip relativ klar werden.

Daumenregeln im Allgemeinen bieten eine Vereinfachung von Problemen oder Lösungen an. Ein paar Daumenregeln sind dabei etwa:

  • Zwischen 7-9h zu schlafen ist gesund
  • 1000ml Wasser wiegen 1000g

Die erste Daumenregel besagt, dass für jede Person 7-9h zu schlafen gesund ist. Dabei ist “für jede” Person sicherlich eine Verallgemeinerung. Für ein paar wenige Menschen reichen vielleicht auch 6h Schlaf und wieder andere brauchen vielleicht 12h Schlaf. Diese Daumenregel passt sicherlich in 95% der Fälle, aber eben nicht in jedem erdenklichen Fall. Dasselbe gilt für die Regel, dass ein Kilogramm Wasser genau 1 Liter ist. Diese Formel ist zwar im Allgemeinen und in erster Annäherung richtig, jedoch nicht für jede Situation. Für eine exakte Berechnung müsste man den Luftdruck, die Temperatur etc. mit reinrechnen. Trotzdem reicht diese Daumenregel für uns in den meisten Fällen aus.

Offensichtlich sind Daumenregeln genau so wie Heuristiken Annäherungen der realen Welt und vielen Fällen sind diese Annäherungen gut genug, um damit gute Entscheidungen zu treffen. Dennoch darf man nicht vergessen, dass Daumenregeln und Heuristiken lediglich Annäherungen der Realität sind!

In der KI sind Heuristiken also vereinfacht gesagt Daumenregeln. Für unser TicTacToe-Spiel könnten wir demnach folgende Heuristiken aufstellen:

  • Falls der Gegner nur noch ein X braucht, um zu gewinnen, blockiere das Feld sofort mit einem O
  • Platziere dein O immer dort wo die meisten O pro Zeile/Spalte/Diagonale sind

Diese einfachen Heuristiken decken bereits viele Fälle ab. Natürlich nicht alle möglichen Fälle, aber genug, um eine fortgeschrittene KI zu basteln. Eine KI, die Heuristiken benutzt ist demnach nicht mehr als eine KI, die verschiedene Daumenregeln anwendet, um zu spielen. Dieser Ansatz scheint erst einmal ziemlich dumm zu sein, funktioniert aber ziemlich gut für den begrenzten Implementierungsaufwand.

In der Regel benutzt man bei KIs Heuristiken nicht in Form von hundert Ifs/Whiles. Sondern man berechnet für jede nächste Aktion ein “Qualitätsmaß” bzw. “Gütemaß” für diese Aktion, auch oft Fitness genannt. Das heißt man möchte für jede mögliche Aktion eine Zahl haben, die ausdrückt wie gut oder schlecht es ist diese Aktion auszuführen. Diese Zahl (= Fitness) berechnet die KI für jede möglichen nächsten Aktion und wählt am Ende diejenige Aktion aus, die die höchste Fitness verspricht. Schauen wir uns das kurz einmal als Pseudo-Code an, dann wird das Prinzip relativ schnell klar.

Stellen wir uns einmal vor, wir sind in folgender Situation:

und wir benutzen diese Heuristiken:

  • Je mehr Os in einer Reihe/Spalte/Diagonale, desto besser
  • Wenn die Mitte frei ist, versuche sie zu bekommen
  • Wenn nur ein X vom Gegner nötig ist, um zu gewinnen, blocke das fehlende Feld

Als Pseudo-Code könnte man das so implementieren:

Jetzt berechnen wir für jede freie Zelle die Fitness und wählen dann im nächsten Schritt die Zelle mit der höchsten Fitness aus.

Die entstehende KI haben wir hier auch einmal eingepflegt. Es wird sofort klar, dass diese KI deutlich besser spielt als die Zufalls-KI und das obwohl der Aufwand eigentlich relativ gering war. Im nächsten Schritt werden wir dann endlich unsere KI zu einem Experten ausbauen, indem wir Heuristiken und “Suche” kombinieren, aber dazu später mehr!

Open in new window

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.

Diese Website verwendet Akismet, um Spam zu reduzieren. Erfahre mehr darüber, wie deine Kommentardaten verarbeitet werden.