Vorheriges Thema anzeigen :: Nächstes Thema anzeigen |
Autor |
Nachricht |
Haubitze
Anmeldungsdatum: 14.10.2009 Beiträge: 132
|
Verfasst am: 04.09.2017, 14:23 Titel: KI fuer ein 5x5 dame aehnliches brettspiel? |
|
|
hallo leute,
ich versuche eine selbstlernende KI zu kreieren fuer mein koreanisches brettspiel. dabei besteht das spielfeld aus einem 5x5 grid und jeweils 7 spielsteinen, die 2 spieler duerfen nur diagonal ziehen und nicht springen.
man darf vorwaaerts und rueckwaerts setzen da es vorkommen kann das man nicht vorwaerts kann. ziehl ist es seine steine in die gegnerische "basis" zu stellen.
nun frage ich mich was wohl die beste moeglichkeit waere die KI zu implementieren, MinMax hab ich schon gehoert nur versteh ich das nich wirklich.
streichholzschachtel computer wuerde selbst lernen aber da waere der daten aufwand wohl zu arg.
hatt da evtl jemand erfahrung und koennte mir auf die spruenge helfen.
danke und salute |
|
Nach oben |
|
|
Jojo alter Rang
Anmeldungsdatum: 12.02.2005 Beiträge: 9736 Wohnort: Neben der Festplatte
|
Verfasst am: 04.09.2017, 14:36 Titel: |
|
|
Hast du dir denn z.B. mal die Wikipedia-Artikel zur Alpha-Beta-Suche bzw Minimax mal durchgelesen? Woran scheitert das Verständnis?
Dort findest du ja sogar schon Pseudocode, den du quasi als Rahmen für deinen eigenen Computergegner kopieren kannst. _________________ » Die Mathematik wurde geschaffen, um Probleme zu lösen, die es nicht gäbe, wenn die Mathematik nicht erschaffen worden wäre.
|
|
Nach oben |
|
|
Haubitze
Anmeldungsdatum: 14.10.2009 Beiträge: 132
|
Verfasst am: 05.09.2017, 03:54 Titel: |
|
|
Jojo antwort unbefriedigend, bitte nochmal lesen und neu versuchen |
|
Nach oben |
|
|
nemored
Anmeldungsdatum: 22.02.2007 Beiträge: 4597 Wohnort: ~/
|
Verfasst am: 05.09.2017, 09:24 Titel: |
|
|
Hmm, die Antwort Jojos bestand eigentlich hauptsächlich in der Bitte, genauer zu spezifizieren, wo das Verständnisproblem liegt. Wenn diese Antwort unbefriedigend ist, wird es schwierig zu helfen.
In meinem OpenBook zur 2D-Spieleprogrammierung habe ich auch ein Kapitel zu Minimax dabei. Im Großen und Ganzen steht da natürlich inhaltlich auch nicht viel mehr als bei Wikipedia, aber vielleicht hilft es ja weiter. Es ist auch eine konkrete Implementierung für ein (sehr) einfaches Spiel dabei.
Die Hauptaufgabe bei der Verwendung von Mnimax besteht eigentlich darin, alle verfügbaren Züge zu finden (das ist bei deinem Spiel gut überschaubar) und eine gute Bewertungsfunktion zu erstellen. _________________ Deine Chance beträgt 1:1000. Also musst du folgendes tun: Vergiss die 1000 und konzentriere dich auf die 1. |
|
Nach oben |
|
|
Jojo alter Rang
Anmeldungsdatum: 12.02.2005 Beiträge: 9736 Wohnort: Neben der Festplatte
|
Verfasst am: 05.09.2017, 12:31 Titel: |
|
|
Haubitze hat Folgendes geschrieben: | Jojo antwort unbefriedigend, bitte nochmal lesen und neu versuchen |
Toll, jetzt weiß ich immer noch nicht was dein Problem ist. Was ist dein konkretes Problem? Vielleicht das Erstellen einer Bewertungsfunktion? Oder was der Algorithmus überhaupt genaut tut? usw... _________________ » Die Mathematik wurde geschaffen, um Probleme zu lösen, die es nicht gäbe, wenn die Mathematik nicht erschaffen worden wäre.
|
|
Nach oben |
|
|
Haubitze
Anmeldungsdatum: 14.10.2009 Beiträge: 132
|
Verfasst am: 05.09.2017, 13:54 Titel: |
|
|
oh da hab ich dich wohl nicht richtig verstanden Jojo.
genau letzteres versteh ich nicht, also was macht er.
danke nemored schau ich mal rein
gruesse |
|
Nach oben |
|
|
Marc Bonus
Anmeldungsdatum: 19.11.2016 Beiträge: 43
|
Verfasst am: 05.09.2017, 14:02 Titel: Re: KI fuer ein 5x5 dame aehnliches brettspiel? |
|
|
Haubitze hat Folgendes geschrieben: |
ich versuche eine selbstlernende KI zu kreieren fuer mein koreanisches brettspiel. dabei besteht das spielfeld aus einem 5x5 grid und jeweils 7 spielsteinen, die 2 spieler duerfen nur diagonal ziehen und nicht springen.
|
Ich würde so vorgehen, dass ich ein zweidimensionales Array mit 5 X 5 Feldern erstelle. Dann würde ich meine "KI" damit ihre Berechnungen anstellen lassen. "Selbstlernend" würde sie aber nicht sein, da die Möglichkeiten doch begrenzt sind. |
|
Nach oben |
|
|
Haubitze
Anmeldungsdatum: 14.10.2009 Beiträge: 132
|
Verfasst am: 05.09.2017, 14:38 Titel: |
|
|
okay also ich hab mir den abschnitt bei nemoreds openbook mal angeschaut.
wenn ich das richtig verstehe hab ich eine bewertungs funktion die einen einzelnen zug bewertet. zum beispiel ob der zug zum ziehl fuehrt, ob
ich den gegner blocken kann und ob die neue position der des letzten zuges
entspricht.
dann hab ich den minmax der geht nun, in meinem fall, 7*7*4*suchtiefe schritte durch und addiert die bewertungsfunktion auf. das ergebniss. vergleicht er mit allen anderen moeglichkeinten und waehlt den zug mit dem niedrigsten wert.
is das so in etwa richtig und kann man das modifizieren, ich haette halt gern was, was mit der anzahl an spielen besser wird. |
|
Nach oben |
|
|
Affemitwaffel
Anmeldungsdatum: 02.06.2011 Beiträge: 39
|
Verfasst am: 05.09.2017, 22:33 Titel: |
|
|
Ein einfacherer KI Ansatz wäre eine Monte-Carlo-KI. Bei einer Monte-Carlo KI simulierst du für jeden Zug x Spiele(in den simulierten Spielen führst du nur zufällig gewählte, gültige Züge aus) und wählst dann den Zug aus, der am häufigsten zum Sieg geführt hat. Wenn du das x ausreichend hoch wählst, führt diese KI ein optimales Spiel aus.
Wenn du allerdings wirklich eine KI haben willst die selbständig lernt, würde ich mir das Q-Learning angucken und die Q-Table mit einem machine learning algorithmus realisieren. Wenn du dafür ein neuronales Netz nimmst wird das ganze dann deep q learning genannt. Es spricht allerdings nicht gegen andere ml Algorithmen für das Q-Learning(z.B. könnte je nach Komplexität des Spiels auch logistische Regression zu akzeptablen Ergebnissen führen). |
|
Nach oben |
|
|
nemored
Anmeldungsdatum: 22.02.2007 Beiträge: 4597 Wohnort: ~/
|
Verfasst am: 06.09.2017, 00:40 Titel: |
|
|
Ich bewerte bei Minimax in der Regel nicht den Zug selbst, sondern das Ergebnis, das danach auf dem Feld steht. Also z. B.: Stehen bereits viele meiner Steine in Endposition (sehr gut), hat der Gegner gewonnen (nicht so toll), wie viel Bewegungsfreiheit habe ich, wie viel der Gegner, usw. Selbstlernend ist Minimax zunächst aber nicht. Man kann das sicher kombinieren, aber ich würde mich für den Anfang entweder auf Minimax/Alpha-Beta oder selbstlernend beschränken.
Selbstlernend kann man auch nach Trial and Error ganz von Null anfangen. Die Anzahl der möglichen Spielstände müsste unter 61 Milliarden liegen; da ich das Spiel nicht genauer kenne (außer die 25 Felder und 2x7 Spielsteine) kann ich nichts genaueres sagen, aber ich denke mal, die Anzahl liegt deutlich darunter, vermutlich höchstens im Millionen-Bereich. Das ist zwar nicht wenig, aber überschaubar, und es sind Spiegelungen dabei; man kann also noch reduzieren.
Man könnte jetzt für jeden der Spielstände drei Zustände definieren: angenommen, alle beiden Spieler spielen perfekt, und ich komme mit diesem Spielstand an den Zug, habe ich
- bereits verloren
- bereits gewonnen
- noch keine Ahnung, wer gewinnt.
Zu Beginn steht natürlich überall Zustand (3) außer bei den Sieg-Stellungen.
Ich mache nun alle möglichen Züge. Wenn daraus ein Spielstand entsteht, mit dem der Gegner bereits verloren hat (1), mache ich diesen Zug, und der vorige Spielstand bekommt den Zustand (2). Wenn, egal welchen Zug ich ausführe, für den Gegner der Zustand (2) entsteht, bekommt mein Ausgangs-Stand den Zustand (1); ich kann ja nur noch verlieren.
Wie gut das System funktioniert, hängt allerdings davon ab, wie stark das Spiel terminiert. _________________ Deine Chance beträgt 1:1000. Also musst du folgendes tun: Vergiss die 1000 und konzentriere dich auf die 1. |
|
Nach oben |
|
|
Haubitze
Anmeldungsdatum: 14.10.2009 Beiträge: 132
|
Verfasst am: 06.09.2017, 11:11 Titel: |
|
|
also ich komm mit der materie garnich klar, daher anbei mal mein
projekt als 7z.
evtl koennt ihr mir das ja dann nochmal besser erklaeren.
zZ schaue ich fuer jeden stein eines spielers ob er nach
vorn oder hinten ziehen kann, ist das der fall schaue ich ob er
in der neuen position einen gegnerischen stein blocken koennte.
danach schau ich noch ob die neue position eine der endpositionen ist.
dann suche ich mir den stein mit dem hoechsten endergbniss und ziehe.
naja bissl doof erklaert.
so na gut evtl wollt ihr euch ja mal anschaun, zum besseren verstaendniss wie das spiel gespielt wird hilfts allemal.
http://users.freebasic-portal.de/haubitze/O-Pat-Kono.7z
gesteuert wird mit ASDW Leertaste und Tab, spaeter soll noch joystik dazu kommen.
PS: das project ist einen ~1:1 umsetzung meine C64 spiels, da war ich ueberhaupt froh das die "KI" irgenwas macht. der PC sollte das aber besser koenn.
@nemored es giebt fuer 3 von sieben steinen insgesammt 13 positionen
fuer die andern 4 nur 12 da kommen dann noch abzuege da ja andere steine schon auf feldern stehn koenn (meine oder die des gegners) |
|
Nach oben |
|
|
nemored
Anmeldungsdatum: 22.02.2007 Beiträge: 4597 Wohnort: ~/
|
Verfasst am: 06.09.2017, 15:39 Titel: |
|
|
Zitat: | @nemored es giebt fuer 3 von sieben steinen insgesammt 13 positionen
fuer die andern 4 nur 12 da kommen dann noch abzuege da ja andere steine schon auf feldern stehn koenn (meine oder die des gegners) |
Ok, dann komme ich auf (theoretisch) etwas unter 1,2 Mrd. Stellungsmöglichkeiten einschließlich Spiegelungen; das könnte man also noch auf 300 Mio. drücken. Unmögliche Stellungen (beide Spieler befinden sich in Siegposition) könnte man zwar auch noch eliminieren, aber das ist vernachlässigbar.
Da ich den Namen des Spiels jetzt kenne, konnte ich mal suchmaschineln* und kann mir jetzt ein Bild vom Spiel machen**.
*) Ich will Schleichwerbung für spezielle Suchmaschinen vermeiden.
**) Die alten Völker hatten also doch recht - wer den Namen kennt, hat die Macht. *harhar* _________________ Deine Chance beträgt 1:1000. Also musst du folgendes tun: Vergiss die 1000 und konzentriere dich auf die 1. |
|
Nach oben |
|
|
Haubitze
Anmeldungsdatum: 14.10.2009 Beiträge: 132
|
Verfasst am: 06.09.2017, 21:13 Titel: |
|
|
hehe nemored, die frage is hast du eine moeglichst kleine feine loesung fuer mein problem? ;D |
|
Nach oben |
|
|
nemored
Anmeldungsdatum: 22.02.2007 Beiträge: 4597 Wohnort: ~/
|
Verfasst am: 07.09.2017, 07:32 Titel: |
|
|
Ja, die steht oben.
"Klein" ist aber so eine Sache; für Tic-Tac-Toe habe ich so ein komplett selbstlernendes System schon einmal erfolgreich umgesetzt, beim L-Spiel habe ich mal angefangen, habe mich aber bisher nicht aufraffen können, es durchzuziehen (allerdings sind die möglichen Züge da deutlich kompliizierter als bei O-Pat-Kono). An sich würde ich in deinem Fall Minimax vorziehen; da die Anzahl der Zugmöglichkeiten ja doch ziemlich begrenzt ist, kann man da einiges an Zugtiefe herausholen, denke ich. _________________ Deine Chance beträgt 1:1000. Also musst du folgendes tun: Vergiss die 1000 und konzentriere dich auf die 1. |
|
Nach oben |
|
|
Haubitze
Anmeldungsdatum: 14.10.2009 Beiträge: 132
|
Verfasst am: 07.09.2017, 12:05 Titel: |
|
|
hm okay nemored, dann muss ich mich nochmal ins thema MinMax einlesen.
ich danke eucht allen soweit.
gruesse |
|
Nach oben |
|
|
Haubitze
Anmeldungsdatum: 14.10.2009 Beiträge: 132
|
Verfasst am: 17.09.2017, 22:56 Titel: |
|
|
hm also so recht geht mir das einfach nich in die birne.
1. wie sollte den eine gute bewertungsfunktion aussehn.
ich berechne ja fuer jeden stein des spieler der gerade dran ist
einen gesamtscore und 4 teilscores fuer die jeweiligen richtungen.
kann man das ueberhaupt fuer minmax nutzen?
2. was ist mit "generiere alle zuege" gemeint bei meinem spiel waeren das
wenn beide spieler perfekt spielen annaehernd unendlich zuege,
da man den gegner wohl kaum zugunfaehig stellen kann.
oder ist damit gemeint fuer jeden stein eines spielers alle moeglichen
zuege zu erstellen? waeren das dann pro min und max zyklus
2(spieler)*7(steine)*4(richtungen)=56zuege*max_tiefe?
zZ hab ich noch keine minmax KI (wegen fehlendem verstaendniss) aber
zumindest schon was was bewertet und zieht. die DUMMHEIT spielt
zwar aber ab einem bestimmten fortschritt ziehen beide spieler einen
stein immer wieder vor und zurueck. eher suboptimal ne |
|
Nach oben |
|
|
nemored
Anmeldungsdatum: 22.02.2007 Beiträge: 4597 Wohnort: ~/
|
Verfasst am: 18.09.2017, 09:26 Titel: |
|
|
Wenn du an der Reihe bist, hast du maximal 7*4 Zugmöglichkeiten, weil du dir sieben Steine aussuchen und mit jedem davon in vier verschiedene Richtungen ziehen kannst. Tatsächlich sind es natürlich deutlich weniger, weil ja viele Züge blockiert sind.
Und zur Bewertungsfunktione - Ich habe oben schon geschrieben, dass du nicht den Zug, sondern die Stellung bewertest, die aus dem Zug resultiert. Üübertragen gesprochen schaust du dir das Brett an und überlegst, wie gut die aktuelle Stellung ist. Als möglicher Vo4schlag: Jeder eigene Stein bekommt +X Punkte für jede seiner Zugmöglichkeiten (Bewegungsfreiheit), jeder gegnerische Stein -X. Für jedes Feld, das ein Stein näher an einer Zielposition liegt, bekommt er +Y Punkte (ein gegnerischer Stein -Y). Wenn die Steine in Zielposition stehen, gibt es pauschal &hfffffff Punkte (beim Gegner negativ).
Ob diese Bewertung tragfähig ist oder nicht, musst du ausprobieren. Bei einem Sieg muss aber eine weitere Verschachtelung abgebrochen werden, sonst hebt sich möglicherweise ein Sieg beider Spieler gegenseitig auf und der Zug-Wert sinkt, obwohl ich mit ihm gewinne.
Nochmal kurzgefasst:
* Wenn Rekursionsstufe = 0 dann gib dei Bewertung des Feldes zurück.
Sonst:
* Erstelle eine Liste aller Züge; das sind weniger als 28.
* Führe der Reihe nach alle Züge durch. Das bedeutet:
- Zug durchführen
- Spiel an den Gegner übergeben (Rekursionsstufe - 1) und seine Bewertung entgegennehmen
- Wenn diese Bewertung (für dich) besser ist als die des bisher gemerkten Zuges, merke dir diesen Zug
- Zug wieder rückgängig machen
* Führe den gemerkten Zug aus. Es ist der, bei dem der Gegner das schlechteste Ergebnis erzielt.
Ich würde dir ehrlich gesagt vorschlagen, mal ein Minimax für ein sehr einfaches Spiel zu schreiben (z. B. Nim oder Tic-Tac-Toe), damit du siehst, wie es funktioniert. Danach ist es leicht, ihn auf andere Situationen zu übertragen. _________________ Deine Chance beträgt 1:1000. Also musst du folgendes tun: Vergiss die 1000 und konzentriere dich auf die 1. |
|
Nach oben |
|
|
|