spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

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:

1. 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
2. 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
3. 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.

Vielen Dank für Eure Antworten! Ich habe meine Bewertungsfunktion dem entsprechend angepasst.

Zitat von »BlueCobold«

Zitat von »Codechaos«

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?

Unter der Annahme, dass der Gegner "optimal spielt" und die KI ebenfalls ergibt das in jedem möglichen Fall ein Unentschieden als finaler Ausgang und keinen "sicheren Verlust". Den Rest hat TGGC ja schon geklärt.

Bei TicTacToe ist das natürlich so, das Projekt sollte allerdings auch nur als Einstieg gedacht sein. Daher ging meine Überlegung eher in die Allgemeine Richtung: Was wäre wenn und wie reagiert man darauf am Besten.

Zitat von »Legend«

Also keiner!

Nein. Der Minimax gibt den Wert des Pfades zurück, der für den Gegner am besten läuft.
Es geht hier ja darum, dass unser Algorithmus für den Gegner einen Weg gefunden hat uns in jedem Fall zu besiegen. Nicht dass alle verbleibenden Wege zu unserer Niederlage führen. Da wir aber nicht wissen, ob der Gegner diesen Pfad ebenfalls kennt, sollten wir das "kleinste Übel" wählen und meine Frage bezog sich darauf, wie wir dieses effizient finden.

Die nächste Frage ist hier natürlich, wie man die Bewertungsfunktion aufbaut, damit sie nicht zu rechenintensiv ist, aber gleichzeitig ein relativ komplexes Regelwerk gut umsetzt. Aber bevor ich Euch damit nerve, werde ich Google etwas bemühen