Das deutsche QBasic- und FreeBASIC-Forum Foren-Übersicht Das deutsche QBasic- und FreeBASIC-Forum
Für euch erreichbar unter qb-forum.de, fb-forum.de und freebasic-forum.de!
 
FAQFAQ   SuchenSuchen   MitgliederlisteMitgliederliste   BenutzergruppenBenutzergruppen  RegistrierenRegistrieren
ProfilProfil   Einloggen, um private Nachrichten zu lesenEinloggen, um private Nachrichten zu lesen   LoginLogin
Zur Begleitseite des Forums / Chat / Impressum
Aktueller Forenpartner:

KI fuer ein 5x5 dame aehnliches brettspiel?

 
Neues Thema eröffnen   Neue Antwort erstellen    Das deutsche QBasic- und FreeBASIC-Forum Foren-Übersicht -> Allgemeine Fragen zu FreeBASIC.
Vorheriges Thema anzeigen :: Nächstes Thema anzeigen  
Autor Nachricht
Haubitze



Anmeldungsdatum: 14.10.2009
Beiträge: 132

BeitragVerfasst am: 04.09.2017, 13:23    Titel: KI fuer ein 5x5 dame aehnliches brettspiel? Antworten mit Zitat

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
Benutzer-Profile anzeigen Private Nachricht senden
Jojo
alter Rang


Anmeldungsdatum: 12.02.2005
Beiträge: 9736
Wohnort: Neben der Festplatte

BeitragVerfasst am: 04.09.2017, 13:36    Titel: Antworten mit Zitat

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
Benutzer-Profile anzeigen Private Nachricht senden Website dieses Benutzers besuchen
Haubitze



Anmeldungsdatum: 14.10.2009
Beiträge: 132

BeitragVerfasst am: 05.09.2017, 02:54    Titel: Antworten mit Zitat

Jojo antwort unbefriedigend, bitte nochmal lesen und neu versuchen happy
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden
nemored



Anmeldungsdatum: 22.02.2007
Beiträge: 4594
Wohnort: ~/

BeitragVerfasst am: 05.09.2017, 08:24    Titel: Antworten mit Zitat

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. lächeln

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
Benutzer-Profile anzeigen Private Nachricht senden
Jojo
alter Rang


Anmeldungsdatum: 12.02.2005
Beiträge: 9736
Wohnort: Neben der Festplatte

BeitragVerfasst am: 05.09.2017, 11:31    Titel: Antworten mit Zitat

Haubitze hat Folgendes geschrieben:
Jojo antwort unbefriedigend, bitte nochmal lesen und neu versuchen happy

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
Benutzer-Profile anzeigen Private Nachricht senden Website dieses Benutzers besuchen
Haubitze



Anmeldungsdatum: 14.10.2009
Beiträge: 132

BeitragVerfasst am: 05.09.2017, 12:54    Titel: Antworten mit Zitat

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 lächeln

gruesse
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden
Marc Bonus



Anmeldungsdatum: 19.11.2016
Beiträge: 43

BeitragVerfasst am: 05.09.2017, 13:02    Titel: Re: KI fuer ein 5x5 dame aehnliches brettspiel? Antworten mit Zitat

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. lächeln
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden
Haubitze



Anmeldungsdatum: 14.10.2009
Beiträge: 132

BeitragVerfasst am: 05.09.2017, 13:38    Titel: Antworten mit Zitat

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
Benutzer-Profile anzeigen Private Nachricht senden
Affemitwaffel



Anmeldungsdatum: 02.06.2011
Beiträge: 39

BeitragVerfasst am: 05.09.2017, 21:33    Titel: Antworten mit Zitat

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
Benutzer-Profile anzeigen Private Nachricht senden
nemored



Anmeldungsdatum: 22.02.2007
Beiträge: 4594
Wohnort: ~/

BeitragVerfasst am: 05.09.2017, 23:40    Titel: Antworten mit Zitat

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
  1. bereits verloren
  2. bereits gewonnen
  3. 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
Benutzer-Profile anzeigen Private Nachricht senden
Haubitze



Anmeldungsdatum: 14.10.2009
Beiträge: 132

BeitragVerfasst am: 06.09.2017, 10:11    Titel: Antworten mit Zitat

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
Benutzer-Profile anzeigen Private Nachricht senden
nemored



Anmeldungsdatum: 22.02.2007
Beiträge: 4594
Wohnort: ~/

BeitragVerfasst am: 06.09.2017, 14:39    Titel: Antworten mit Zitat

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**. happy


*) 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
Benutzer-Profile anzeigen Private Nachricht senden
Haubitze



Anmeldungsdatum: 14.10.2009
Beiträge: 132

BeitragVerfasst am: 06.09.2017, 20:13    Titel: Antworten mit Zitat

hehe nemored, die frage is hast du eine moeglichst kleine feine loesung fuer mein problem? ;D
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden
nemored



Anmeldungsdatum: 22.02.2007
Beiträge: 4594
Wohnort: ~/

BeitragVerfasst am: 07.09.2017, 06:32    Titel: Antworten mit Zitat

Ja, die steht oben. lächeln
"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
Benutzer-Profile anzeigen Private Nachricht senden
Haubitze



Anmeldungsdatum: 14.10.2009
Beiträge: 132

BeitragVerfasst am: 07.09.2017, 11:05    Titel: Antworten mit Zitat

hm okay nemored, dann muss ich mich nochmal ins thema MinMax einlesen.
ich danke eucht allen soweit.

gruesse
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden
Haubitze



Anmeldungsdatum: 14.10.2009
Beiträge: 132

BeitragVerfasst am: 17.09.2017, 21:56    Titel: Antworten mit Zitat

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 grinsen
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden
nemored



Anmeldungsdatum: 22.02.2007
Beiträge: 4594
Wohnort: ~/

BeitragVerfasst am: 18.09.2017, 08:26    Titel: Antworten mit Zitat

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
Benutzer-Profile anzeigen Private Nachricht senden
Beiträge der letzten Zeit anzeigen:   
Neues Thema eröffnen   Neue Antwort erstellen    Das deutsche QBasic- und FreeBASIC-Forum Foren-Übersicht -> Allgemeine Fragen zu FreeBASIC. Alle Zeiten sind GMT + 1 Stunde
Seite 1 von 1

 
Gehe zu:  
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.

 Impressum :: Datenschutz