Hallo Leute,
für die Uni sollen wir ein kleines Spieleprojekt entwickeln. Ein Teil davon ist natürlich ein Computergegner, weshalb ich angefangen habe, mich ein wenig mit der KI Entwicklung zu beschäftigen. Da ich noch keine große Erfahrung in der Materie habe und meine Programmierkenntnisse für einen Informatikstudenten mehr als peinlich sind, sollte es für den Einstieg
TicTacToe mit einem Minimax-Algorithmus sein.
Als Grundgerüst diente der Pseudocode bei Wikipedia und als Bewertungsfunktion habe ich mich daran gehalten, dass ein unentschieden 0 zurück gibt, gewinnen 1 und verlieren eine -1.
Eine der Eigenschaften des Minimax' ist, dass es annimmt, der Gegner spielt optimal. Aber genau da liegt der Hund begraben, wenn er das nicht tun sollte, hat der Spieler trotzdem noch die Möglichkeit zu gewinnen, nutzt diese allerdings nicht, sondern nimmt einfach den ersten möglichen Zug, da die Bewertung mit -1 der Bewertung aller anderen Züge entspricht.
Wie optimiert man das Spiel der KI dahingehend, dass sie selbst unter der Bedingung des sicheren Verlust (bei optimalem Spiel des Gegners) noch einen einigermaßen sinnvollen Zug wählt?
Drei Ansätze sind mir auf Anhieb eingefallen:
- Das Anpassen der Komplexität der Bewertungsfunktion, sodass man das "kleinere Übel" erkennen kann, was allerdings trotzdem zu gleichen Ergebnissen bei der Situationsbewertung führen kann
- Sobald man sich in einer Situation befindet, bei der die sichere Niederlage droht, wird der Suchalgorithmus dahingehend geändert, dass man den Pfad wählt, bei dem die meisten Wege zum Erfolg führen würden
- Man schaut, wie stark sich der Gegner im bisherigem Spiel, an der optimalen Strategie orientiert hat und weiß dem entsprechend, wie der Gegner sich wahrscheinlich entwickeln wird. Aber wie implementiert man das vernünftig?
Meine Frage ist nun, ob ihr vielleicht ein paar Tipps und Tricks habt, um sich auf das Spiel eines nicht optimalen Gegners einzustellen.