Logik für Computerspieler
0 0
0 
dedlfix
Logik für Computerspieler
Hallo zusammen und ein frohes neues Jahr,
wie vielleicht der eine oder andere hier im Forum gesehen hat, ich schreibe gerade an einem kleinen Spiel, das auch schon wunderbar funktioniert, wenn 2 menschliche Spieler gegeneinander spielen.
Jetzt bin ich neugierig geworden, ob ich es auch hinbekomme, dass der Computer spielt. Natürlich soll er schon besser sein, als nur einfach durch Zufall zu setzen.
Da ich denke, dass das Spiel und die Spielregeln relevant sind, hier nochmal kurz zur Erläuterung das Spielprinzip:
Es wird abwechselnd gespielt. Mit jedem Zug kann ein Eimer um eine Einheit gefüllt werden. Das Fassungsvermögen hängt von der Anzahl der Nachbar-Eimer ab. (Ein Eck-Eimer hat 2, ein Rand-Eimer 3 und alle anderen 4 Nachbarn) Ist ein Eimer voll, entleert er sich auf seine Nachbarfelder. Ziel ist es, alle Felder zu übernehmen.
Kann man prinzipiell formulieren, wie ein Computer-Spieler vorgehen wird/sollte? Ich habe versucht, meine eigenen Entscheidungen, welchen Zug ich durchführe, zu abstrahieren und bin dabei auf bestimmte Muster gestoßen, die ich selber versuche zu erzeugen bzw. beim Gegner zu verhindern. Stellt sich die Frage, wie ein Computer überhaupt Muster erkennen kann und wie man bestimmte Muster speichern kann. Ein Muster kann ja hier gedreht 4 Mal auftreten (z.B. die 4 Ecken). Ich würde dann auch gerne prüfen können, ob ein bestimmtes Muster erfolgreich war und diese Muster würde der Computer dann häufiger probieren als andere. Vielleicht sogar ein neues Muster speichern? Erfolg könnte man wohl kurzfristig einfach prüfen, indem man nach dem Zug Anzahl der übernommenen Felder zählt. Wobei das aber nur dann geprüft werden sollte, wenn sich Eimer entleeren, da ja sonst erstmal nichts passiert.
Oder bin ich vielleicht komplett auf einem Holzweg?
Euer Marvin
-
hi,
Es wird abwechselnd gespielt. Mit jedem Zug kann ein Eimer um eine Einheit gefüllt werden. Das Fassungsvermögen hängt von der Anzahl der Nachbar-Eimer ab. (Ein Eck-Eimer hat 2, ein Rand-Eimer 3 und alle anderen 4 Nachbarn) Ist ein Eimer voll, entleert er sich auf seine Nachbarfelder. Ziel ist es, alle Felder zu übernehmen.
Kann man prinzipiell formulieren, wie ein Computer-Spieler vorgehen wird/sollte?
In diesem Fall leider ja: Der Computer wird immer gewinnen, wenn er selbst das Spiel beginnt und der Algorithmus richtig implementiert wurde.
-
Hi
Kann man prinzipiell formulieren, wie ein Computer-Spieler vorgehen wird/sollte?
In diesem Fall leider ja: Der Computer wird immer gewinnen, wenn er selbst das Spiel beginnt und der Algorithmus richtig implementiert wurde.
Auch wenn mir das jetzt wirklich weiterhilft, denn man könnte später ja auch verschiedene Spielstärken einbauen, versuche ich die Grundlagen zu begreifen, wie ein Computer analysieren kann, welches der vermeintlich beste nächste Zug ist. Es kann übrigens womöglich auch sein, dass der Computer nur dann immer Erfolg hat, wenn er eben nicht anfängt. (Wenn ich z.B. annehme, dass keiner einen Überlauf provozieren möchte, da der Gegenzug dann gewinnen würde, dann wird der Spieler, der angefangen hat, verlieren.)
Marvin
-
Lieber Marvin,
die "dümmste" Intelligenzstufe wählt zufällig eine Handlungsmöglichkeit aus.
Die "zweit dümmste" Intelligenzstufe bestünde darin, die möglichen Züge daraufhin zu filtern, dass keiner einen Überlauf ergibt. Aus der Restmenge an Möglichkeiten wird zufällig eine ausgewählt.
Jetzt kannst Du optimieren, um "schlauere" Intelligenzen zu bauen. Sehr wahrscheinlich wirst Du die Möglichkeiten und ihre Ergebnisse daraufhin testen müssen, inwiefern sie Deinem Ziel näher kommen. Je mehr Züge Du im Voraus berechnest, desto "schlauer" sollte Dein Algorithmus werden.
Liebe Grüße,
Felix Riesterer.
-
Hallo Felix,
die "dümmste" Intelligenzstufe wählt zufällig eine Handlungsmöglichkeit aus.
Die "zweit dümmste" Intelligenzstufe bestünde darin, die möglichen Züge daraufhin zu filtern, dass keiner einen Überlauf ergibt. Aus der Restmenge an Möglichkeiten wird zufällig eine ausgewählt.
Jetzt kannst Du optimieren, um "schlauere" Intelligenzen zu bauen. Sehr wahrscheinlich wirst Du die Möglichkeiten und ihre Ergebnisse daraufhin testen müssen, inwiefern sie Deinem Ziel näher kommen. Je mehr Züge Du im Voraus berechnest, desto "schlauer" sollte Dein Algorithmus werden.
Die dümmste und zweitdümmste Stufe sind wohl die schnell am wenigsten genutzten Stufen. Gerade bei den "schlaueren Intelligenzen" fehlt es mir aber an einer umsetzbaren Logik. Wie geschrieben, versuche ich ja selber bestimmte Muster zu erzeugen, sodass ich z.B. einen nicht direkt ersichtlichen Überlauf erzeuge, wenn zwei über-Eck liegende Felder überlaufen, füllt sich ein Feld 2 Mal und läuft vielleicht dadurch erst über. Im unten gezeigten einfachen Beispiel laufen alle Felder mit einer "2" über. Die Randfelder ja sowieso schon, aber die Mittel-Felder werden 2 Mal aufgefüllt und laufen daher auch über. Mir fehlt eine Idee für einen Algorithmus, wie der Computer nach solchen Mustern suchen kann, sowohl auf seiner Seite als auch auf der Gegnerseite. Die einzige Idee ist alles zu Fuß nach dem Schema,
- ist Feld 1 eine 1 und Feld 2,7 und 8 eine 2, dann ... und das 4 Mal, für jede Ecke.
1 2 2 2oder
1 2 2 2 2 2 2 2Bei solchen Mustern in der Mitte kommen da sehr viele Varianten zusammen, daher dachte ich, ob es nicht möglich wäre einen allgemeineren, mathematischen Weg zu finden, um bestimmte Muster zu erkennen.
Ist vielleicht etwas weit hergeholt, aber wie funktioniert bei Kameras die Gesichtererkennung, sogar ob das Gesicht lächelt oder nicht. Oder wie bei den Navigationsgeräten, die schon Schilder mit Tempolimits erkennen.
Marvin
-
-
-
-
Tach!
Kann man prinzipiell formulieren, wie ein Computer-Spieler vorgehen wird/sollte?
Ja, nach dem implementierten Algorithmus. Das war die Antwort auf das "wird". Das "sollte" hängt davon ab, was man erreichen möchte. Der Computer macht ja von sich aus keine Fehler. Die musst du selbst in den Algorithmus einbauen, wenn du nicht nur eine auf Gewinn ausgelegte Strategie haben möchtest.
Ich habe versucht, meine eigenen Entscheidungen, welchen Zug ich durchführe, zu abstrahieren und bin dabei auf bestimmte Muster gestoßen, die ich selber versuche zu erzeugen bzw. beim Gegner zu verhindern.
Mathematiker haben auch Spaß daran, abseits eines konkreten Spieles in Ruhe Wege zu finden, die aus rein logischen Beweggründen zielführend sind. Normalsterbliche Menschen arbeiten hingegen gern auch mal mit dem Bauchgefühl, weil das Durchrechnen im Kopf anstrengend ist, besonders wenn man die weitere Entwicklung in die Zukunft betrachten will und sich jede Menge Wege auftun, die man alle beachten muss. Für einen Computer ist es jedoch ein leichtes, mit deutlich größeren Datenmengen umzugehen, als es der Mensch kann. Er braucht nur ein richtig geschriebenes Programm. (Selbst wenn sich irgendwann ein Performance-Problem ergibt, hat er immer noch weitaus mehr Daten berechnet, als es der Mensch könnte.)
Eine andere Vorgehensweise ist das Lernen. Das beginnt ganz grob gesehen mit zufälligem Setzen und schauen, ob das zum Gewinn führt. Die Schwierigkeit ist, die Situation zu definieren, so dass gleiche Situationen erkannt werden können. Dabei ist auch der Fortschritt im Spiel nicht ganz unwichtig. Wobei sich der in deinem Spiel automatisch anhand der Füllung des Brettes ergibt. Du kannst das aber auch vereinfachen, dass du dir das Brett als ganzes merkst und dann x mal y Züge dazu. Allerdings klingt das nur einfach, da werden sich ganz schnell immense Datenmengen ansammeln. Zudem muss man den Computer sehr oft spielen lassen, damit sich ein Lerneffekt einstellen kann. Am Ende ist der Computer aber wieder unschlagbar. Irgendwo dazwischen sollte er agieren, wenn er mit einem menschlichen Gegner spielt, sonst wird das für den Menschen schnell langweilig, wenn da gar keine Chance auf Erfolg sichtbar ist.
Ich würde dann auch gerne prüfen können, ob ein bestimmtes Muster erfolgreich war und diese Muster würde der Computer dann häufiger probieren als andere. Vielleicht sogar ein neues Muster speichern?
Es ist ja nicht nur der Füllstand eines Feldes, sondern auch der darumliegenden zu beachten. Und eigentlich kann man das gar nicht einschränken, weil der gesamte Brettinhalt relevant ist. Selbst wenn da eine Schneise das Brett in Teile teilt, kann die sich ja im Verlauf des Zuges füllen und der Funke überspringen.
Erfolg könnte man wohl kurzfristig einfach prüfen, indem man nach dem Zug Anzahl der übernommenen Felder zählt.
Das täuscht. Solange noch Züge übrig sind, kann sich das Blatt schlagartig wenden. Das geht am Ende mitunter ziemlich aufregend hin und her.
dedlfix.