Hallo Leute!

Ich möchte ein Spiel programmieren, bei dem beide Spieler abwechselnd, ähnlich wie bei Tic-Tac-Toe, auf eine Fläche (Panels) klicken, um einen Spielstein zu setzen. Das Spielbrett hat 25 Felder. Anfangs besitzt jeder Spieler 5 Steine, die man wie die Bauern beim Schach bewegt. Ziel ist es, einen Stein auf die gegnerische Grundlinie zu bringen. Hier ein Beispiel:
fuzzy.cs.uni-magdebu...900.html#Streichholz
... nur dass ich eben 5x5 Felder möchte.
Nun gibt es eine Menge zum Thema KI, Tic-Tac-Toe usw. zu lesen, aber irgendwie kann ich es nicht umsetzen. Mir fehlt ein Anfang.

Wie bringe ich ein Programm hin, dass sinnvolle Züge berechnet und dabei auch die Spielsteine des Gegners berücksichtigt? Alles mit if oder case abzufragen würde irgendwann (vielleicht) halbwegs funktionieren, aber so will ich das nicht. Das wäre doch nur unprofessioneller Spaghetticode!

Kann mir jemand ein paar Ansätze und Denkhilfen geben?

Ich habe in diesem Zusammenghang von dem Minimax-Algorithmus gehört. Dieser rechnet alle mgölichen Züge durch und wählt den günstigsten aus. Aber von der Umsetzung habe ich keine Ahnung.

Marco D. hat folgendes geschrieben:

Aber von der Umsetzung habe ich keine Ahnung.

Ich auch nicht! Vielleicht könnte mir diesen Algorithmus jemand erkären!

wiki roxx^^

Die Idee ist einfach, das du dir von deiner Spielposition auds (du bist jetzt der Computer) einen Spielbaum aufbaust, also alle möglichen Spielverläufe. Da gibt es prinzipiell 2 Varianten:
1.) Du hast einen vollständigen Spielbaum (von der Startposizion an alle Spielverläufe. Die Anzahl explodiert aber in den meisten Fällen (4 gewinnt war auf ner normalen Festplatte schon nicht mehr speicherbar) Müsste man durchrechnen ob das bei dir klappt.
2.) Du baust dir an deiner aktuellen Spielposition nen Spielbaum bis zur ner bestimmten Tiefe auf. Um ddas etwas eleganter zu gestalten, kommt der MinMax-Algorythmus. Du wirst immer den Zug machen, der dir am meisten Gewinn bringt -> MAX. Der Gegner wird versuchen, sein Ergebnis zu maximieren... deins also zu minimieren -> MIN. Wenn man da immer die 3 besten/schlechtesten nimmt, bleibt es noch im überschaubaren Rahmen. (die 3 ist willkürlich gewählt )

Das Problem ist, das du bei der zweiten Variante eine Bewertungsfunktion brauchst. Du rechnest ja nicht bis zum Ende sondern brichst ab. Die Stellung, die da erreicht wurde, muss bewertet werden und geht in den MinMax-Algorythmus ein. Zu Bewerten währen unter anderen schon erreichte Punkte, strategische Stellung, etc.... Mit Büchern kann man da auch was machen. Einige (viele) Stellungen werden ausgibieg berrechnet und gespeichert. Wenn Später diese Situation auftritt, weiß man schon bescheid. Google mal nach WZebra, ist zwar Reversi, spart abr nicht an Informationen...

PS: Forensuche;)

MfG

zemy hat folgendes geschrieben:

Die Idee ist einfach, das du dir von deiner Spielposition auds (du bist jetzt der Computer) einen Spielbaum aufbaust, also alle möglichen Spielverläufe. Da gibt es prinzipiell 2 Varianten: 1.) Du hast einen vollständigen Spielbaum (von der Startposizion an alle Spielverläufe. Die Anzahl explodiert aber in den meisten Fällen (4 gewinnt war auf ner normalen Festplatte schon nicht mehr speicherbar) Müsste man durchrechnen ob das bei dir klappt.

Jetzt bin ich so schlau wie vorher! Das mit dem Baum ist mir klar, aber WIE schreibe ich den? Was soll das für ein Baum sein, beinhaltet der Spielstellungen:

Da gibt es so nette grafische Darstellungen über Bäume, aber was das ist, steht nirgendwo so genau!

zemy hat folgendes geschrieben:

PS: Forensuche;)

Siehe oben "Jetzt bin ich so schlau wie vorher!"!

REKURSION ist das stichwort und zwar INDIREKTE REKURSION

Die Oberfläache, die Zug-Regeln (gerade ziehen, schräg schlagen), die Option Spieler/Computer beginnt und die Spielaufstellung habe ich. Der 1. Zug des Computers erfolgt mit Random. Also alles nur keine KI!

Werde mich mal mit dem Minimax-Thread näher beschäftigen und versuchen, die KI zu verstehen. Aber momentan stehe ich an...

galagher hat folgendes geschrieben:

zemy hat folgendes geschrieben: Die Idee ist einfach, das du dir von deiner Spielposition auds (du bist jetzt der Computer) einen Spielbaum aufbaust, also alle möglichen Spielverläufe. Da gibt es prinzipiell 2 Varianten: 1.) Du hast einen vollständigen Spielbaum (von der Startposizion an alle Spielverläufe. Die Anzahl explodiert aber in den meisten Fällen (4 gewinnt war auf ner normalen Festplatte schon nicht mehr speicherbar) Müsste man durchrechnen ob das bei dir klappt. Jetzt bin ich so schlau wie vorher! Das mit dem Baum ist mir klar, aber WIE schreibe ich den? Was soll das für ein Baum sein, beinhaltet der Spielstellungen: markieren Delphi-Quelltext     1: 2: 3: if [...] then [...] else  if then [...] else   if then [...] //usw.? Da gibt es so nette grafische Darstellungen über Bäume, aber was das ist, steht nirgendwo so genau!

Die Darstellung von Bäumen passt ziemlich genau. Der Unterschied ist, das sich auf deiner Festplatte kein Grünzeug befindet, sondern da nur ein paar Bytes rumliegen. Trotzdem gibts Wurzeln Äste und Blätter. Der ganze Trick dabei ist: Die Äste verweisen über Pointer zu den untergestellten Blättern oder Ästen

galagher hat folgendes geschrieben:

zemy hat folgendes geschrieben: PS: Forensuche;) Siehe oben "Jetzt bin ich so schlau wie vorher!"!

War nur, weil ich nen Thread "MinMax" gesehen habe, den du wohl auch schon gefunden hast

MfG

Ich glaube, da habe ich mir zu viel vorgenommen! Wenn ich nicht wirklich alles mit if oder case abfragen will, komme ich nicht weiter. Ich habe keine Ahnung, wie ich einen Algorithmus schreiben soll.

Folgende Anforderungen muss er erfüllen (der Computer spielt immer von oben nach unten):
1. Das Feld unterhalb der jeweiligen Ausgangsstellung besetzen, wenn dieses leer ist
2. Die "Figur" auf dem Feld schräg links oder rechts unterhalb der jeweiligen Ausgangsstellung schlagen
3. Dabei noch strategisch vorgehen und die Stellung des Spielers berücksichtigen (seinen Sieg verhindern).

Hier mal ein Screenshot:

Kannst ja auch erst mal schritt für Schritt vorgehen und nicht gleich bei Punkt 27 Anfangen. Schreib doch erst mal ne "dumme" Ki:

Schritt 1: Dumme KI:
1) Wenn ein gegnerischer Stein schmeißbar, dann schmeiße ihn. (da brauchst du ifs und vieleicht ne For-Schleife^^)
2) Wenn mehrere Steine schmeißbar sind, suche dir zufällig einen aus
3) Wenn nichts zum schmeißen ist, dann zieh zufällig einen Stein vor (bei dem es möglich ist)
4) Wenn nichts möglich ist, stürze ab oder setze aus... je nach dem

Diese KI ist dann zwar sehr einfach zu schlagen aber immerhin ein Anfang

Schritt 2: Schon KIiger
1. Geh ALLE Zugvarianten durch. Bewerte die Position, die sich daraus ergibt und speichere diese ab
2. Wähle die Variante aus, die am günstigsten ist. Wenn mehrere Variante den gleichen Zahlenwert haben, wähle zufällig eine

Wenn du das bewerten nur nach der Figurenzahl machst, hast du wieder Variante eins. Ist ganz gut beim testen (einfach mal ca. 100'000* durchspielen, 50:50 müsste rauskommen), bringt einen aber nicht viel weiter. Also muss die strategische Stellung mit rein. Eventuell, ob der Stein nach dem Zug nicht mehr geschmissen werden kann oder ob so ein gegnerischer Stein davon abgehalten werden kann, durchzubrechen. Spiel am besten das Spiel ne Weile gegen einen Menschen (oder gegen ein Programm, das das Spiel schon realisiert hat) und beobachte dich selbst: Worauf achtest du? Die Gewichte kannste erstmal nur schätzen (also wie stark sowas eingeht). Kann man testen gegen die Dumme KI aus (1)

Schritt 3: MinMax
Einfach bis zur ner bestimmten Tiefe vorrausrechen (siehe anderen Thread) Die Bewertungsfunktunktion hast du schon. Dadurch kannst du einen Zug nicht nur nach der nächsten Stellung bewerten, sondern auch nach den daraus vollgenden. Da müsste natürlich das Save-Bekommen der eigenen Steine extra bewertet werden um brauchbare Resultate zu bekommen

Schritt 4..27:
Verbessern der bewertungsfunktion über hinzufügen weiterer Parameter. Verbessern der Gewichte (eventuell was genetisches). Anlegen von Büchern. Vieleicht ein bischen mit neuronalen Netzen spielen, etc. Performance steigern, ...

Schritt 1 müsste auch für einen Anfänger zu machen sein. Solange man Arrays und For-Schleifen kennt, ist das kein großes Problem. Schritt 2 ist das komplizierteste die Bewertungsfunktion. Die ist schon etwas komplizierter zu programmieren aber man brauchs nicht gleich zu übertreiben Schritt 3 ist nach (2) dann auch kein Problem mehr und danach kannst du dir überlegen ob du es darauf beruhen lässt oder mehr Energie reinsetzt. Weiß ja nicht, wie intensiv du das hier betreiben willst...

MfG

zemy hat folgendes geschrieben:

Kannst ja auch erst mal schritt für Schritt vorgehen und nicht gleich bei Punkt 27 Anfangen. Schreib doch erst mal ne "dumme" Ki:

Danke für deine Hilfe - manchmal sieht man den Wald vor lauter Bäumen nicht! Es spielt schon recht agressiv - aber nicht wirklich intelligent!

Hier mal ein Tic-Tac-Toe mit 'MiniMax'-Algorithmus. So hingerotzt.

alzaimar hat folgendes geschrieben:

Hier mal ein Tic-Tac-Toe mit 'MiniMax'-Algorithmus. So hingerotzt.

Super, spielt sehr gut! Aber ich kann den MiniMax-Algorithmus einfach nicht umsetzen. Irgendwie kapiere ich das nicht...

warum ist dein bewertungsalgorithmus so wie er ist ? reicht es nicht zb -1 zurückzugeben wenn der pc gewonnen hat, 0 bei unentschieden und 1 wenn der spieler gewinnt ?

das lustige ist, dass die ki wenn sie die chance hat zu gewinnen, sie nicht nutzt, wenn sie bei ihrem nächsten zug ohnehin gewinnt (erzeugen einer zwickmühle), ich denke mal weil sie die ergebnisse tief unten von suchbaum nimmt.

Also,

@Fear: Stimmt, solange der Minimax einen Gewinnzug hervorbringt, ist es egal, wann die Maschine gewinnt. Dazu müsste man die Stellungs/Zugbewertung erweitern, um die Vorschautiefe zu berücksichtigen, in der eine Gewinnstellung erkannt wird. So kann man den Rechner auch dazu bringen, seine Gegner zu braten, wenn nämlich Gewinnzüge, die erst später zum Erfolg führen, höher bewertet werden, also die Züge, die unmittelbar zum Gewinn führen (Gesellschaftskritisch betrachtet ist also Sadismus nichts anderes als ein verdammt dummer Automatismus).

Die Funktion zur Bewertung einer Stellung ist etwas allgemeiner geraten. Sie zählt die Anzahl der 3er. Ist ja klar, das schon ein 3er zum Sieg reicht. Wenn Du nun einige Kleinigkeiten an der Implementierung änderst (Stellungsbewertung, nächsten Zugkandidaten suchen) und an z.B. Reversi, Dame, Schach etc. anpasst, funktioniert es genau so. Ich hab mal angefangen, das in eine Klasse zu packen (TBoard, TPlayer, TEngine). Dann müsste man nur einige Methoden ableiten (TBoard.GetAvailabelMoves, TBoard.Score) und man hätte eine allgemeingültige Minimax/NegaMax/NegaScout-Engine für beliebige rundenbasierte Nullsummen-Spiele mit vollständiger Information.

Der Kern ist immer die Bewertungsfunktion für die Stellung, sowie, falls der NegaScout-Algorithmus (Alpha-Beta-Pruning) verwendet wird, eine Bewertungsfunktion für den Zug. Beim Optimieren des Suchbaumes ist es von entscheidender Bedeutung, die vermutlich guten Züge zuerst auszuführen.

@galagher: Wo ist denn dein Problem? Da kann man bestimmt helfen. Der Minimax-Algorithmus sucht den Besten Zug aus Sicht des 'Spielers'. Der beste (MAX) Zug des Spielers ist der, der die schlechteste (MIN) Antwort des Gegners als Antwort hat. Der Algo ruft sich -mit umgekehrten Vorzeichen- selbst auf.

ja bei XXO funzts aber auch wunderbar mit sieg niederlage unentschieden
spart ein paar zeilen

alzaimar hat folgendes geschrieben:

@galagher: Wo ist denn dein Problem? Da kann man bestimmt helfen. Der Minimax-Algorithmus sucht den Besten Zug aus Sicht des 'Spielers'. Der beste (MAX) Zug des Spielers ist der, der die schlechteste (MIN) Antwort des Gegners als Antwort hat. Der Algo ruft sich -mit umgekehrten Vorzeichen- selbst auf.

Die Umsetzung ist das Problem. Was ist, wenn es mehrere gleich gute Züge gibt? Im Grunde habe ich keine Ahnung, nicht mal ansatzweise, wie ich den Minimax-Algorithmus für mein Programm umsetzen soll!

Ich habe 25 Panels und im Moment ist die ganze "KI" eine Reihe von if's. Genau das wollte ich aber nicht - aber ich weiss nicht, wie ich es sonst machen kann.

Ich weiss einfach nicht, wie.

Praktisches Beispiel:

alzaimar hat folgendes geschrieben:

Der Minimax-Algorithmus sucht den Besten Zug aus Sicht des 'Spielers'

Wie?
//Edit: Ich meine nicht, "wie logisch", sondern "wie programmtechnisch". Wie schreibe ich das für ein Programm, das im Prinzip das Bauernspiel im Schach ist? Kannst du mir vielleicht Pseudocode o.ä. dazu geben?

der code ist der gleiche, aber die bewertungsfunktion ist ein ganz eigenes problem, da gibts bei schach noch keine perfekte lösung, die wird es wohl erst geben wenn der komplette spielbaum analysiert werden kann dann braucht man die auch nicht mehr

galagher hat folgendes geschrieben:

Die Umsetzung ist das Problem. Was ist, wenn es mehrere gleich gute Züge gibt? Im Grunde habe ich keine Ahnung, nicht mal ansatzweise, wie ich den Minimax-Algorithmus für mein Programm umsetzen soll!

Klar, die Umsetzung ist immer das Problem (wie bei mir). Wenn es mehrere Gleiche Züge gibt, dann... kann man doch würfeln, welchen man denn nun nimmt. Oder: Man analysierte diese Züge nochmals, aber eingehender.

Ich hatte doch irgendwo mal einen Pseudocode für Minimax gepostet... Na egal, im Prinzip sieht es so aus:
Die Funktion 'FindeBestenZug' liefert den besten Zug sowie die 'Punktzahl' des Zuges.


Hier ist natürlich noch nicht dabei, das der Spieler 'passen' muss, oder das die suche abgebrochen wird, wenn eine Gewinnstellung erreicht wurde. Dann ist die Bewertung der Spielstellung natürlich (z.B.) MaxInt. Wenn ich einen Zug gefunden habe, der zu einer Gewinnstellung führt, brauch ich gar nicht erst weiter zu suchen. Bei einem 'Passe' muss ich rekursiv absteigen. Passt dann auch der Gegner, ist eine 'Endstellung' erreicht, die -je nach Spiel- auch zu bewerten ist.

Ich habe mir wochenlang Einen abgebrochen, als ich mich mit Spieleprogrammierung beschäftigt habe. Das ist nun schon fast 30 Jahre her (sabber)... Aber ich war damals extra an der Uni (mit 15) und habe mir die Bücher und Artikel (Journal of the ACM) über Spieletheorie reingezogen. Die ersten Artikel darüber sind immerhin von 1959 (glaub ich zumindest).

Ich bin grad zu faul zum suchen, aber welches Spiel willst Du programmieren?

[quote="alzaimar"]

galagher hat folgendes geschrieben:

Ich bin grad zu faul zum suchen, aber welches Spiel willst Du programmieren?

Im Grunde nichts anderes als das Bauernspiel beim Schach, müssen nicht unbedingt 16 Figuren sein; momentan sind es je 10. Die Idee habe ich von da:
fuzzy.cs.uni-magdebu...900.html#Streichholz

Vielleicht so, dass der gewonnen hat, der die meisten "Figuren" in der gegnerischen Grundlinie hat. Das wäre interessanter, da man sich nun nicht mehr Figuren um den Preis des Weiterkommens schlagen lassen kann.

Aber mir fehlt es an Grips, das zu realisieren. Momentan spielt mein Programm auf Basis von if [...] then. Es prüft, ob mit dem nächsten Zug die gegnerische Grundlinie erreicht ist, ob eine Figur geschlagen werden kann usw. Aber es ist eben bloss if und while; mit exit und break, wenn's passt. Fazit: Ich kann es nicht...

Aber wenn du mir helfen willst, ein Bauernspiel zu basteln - wäre toll!