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:

wer hat schon eine ki für tictactoe geschrieben?

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



Anmeldungsdatum: 28.10.2004
Beiträge: 109
Wohnort: Stuttgart

BeitragVerfasst am: 31.10.2004, 13:52    Titel: wer hat schon eine ki für tictactoe geschrieben? Antworten mit Zitat

Hallo,
Ich bin auf der Suche nach einer TicTacToe KI, die übersichtlich und verständlich geschrieben ist und einigermaßen stark sein sollte. Wer so etwas kennt (TicTactoe mit KI) kann den Quelltext mir schicken (paranoia71[ad]web.de) oder in diesen Thread posten.

Ich benötige eine solche KI, da ich selbst eine experimentelle KI für ein TicTacToe Spiel geschrieben hat, die den jeweiligen Zug berechnet, indem der Computer 10000 mal gegen sich selbst spielt und dann den "erfolgreichsten" Zug auswählt. Das Problem: Bisher bestehen die Spiele, in denen der PC gegen sich selbst spiel nur aus Zufallszügen (hier würde ich wenn jemand es erlaubt vielleicht seine KI einbauen), daher ist die Spielstärke OK, sie denkt aber nur 1 Zug voraus.

Danke im voraus, RESK
Wer sich das bisherige Spiel anschauen will: www.geocities.com/iroshdown/tictacto.bas
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden Website dieses Benutzers besuchen
MisterD



Anmeldungsdatum: 10.09.2004
Beiträge: 3071
Wohnort: bei Darmstadt

BeitragVerfasst am: 31.10.2004, 14:25    Titel: Antworten mit Zitat

Also bei sonenm simplen Spiel bringt ne KI garnix wenn ich das mal so sagen darf.

Ich hatte mir das durchgedacht und wenn jeder den besten Zug macht den er machen kann kommt am Ende ein unentschieden raus.

Bei dem Spiel gibts so wenige Mögichkeiten an Zügen, dass man die eigentlich alle definieren kann. Eine KI ist also nicht wirklich Sinnvoll..


Mal ein Beispielspiel:
1. Zug: setzt in eine Ecke da dass der Beste Anfang ist.
2. Zug: Gegner setzt in die Mitte da er sonst verliert.
3. Zug: der erste Spieler setzt in irgendein freies Feld was mit der von ihm besetzten Ecke in einer Linie steht um eine Chance auf eine dreierreihe zu haben.
4. Zug: Der Gegner blockiert die Reihe und bekommt dadurch selber die Chance auf eine eigene Reihe.
5. Zug: Der erste Spieler blockt ab.
6. Zug: Der Gegner versucht eine neue Reihe oder muss blocken
das geht dann bis zum 9. so weiter.....
->Unentschieden

Der Zweite Zug ist hier entscheidend. Legt der Gegner nicht in die Mitte kann der erste Spieler eine Zwickmühle aufbauen womit er gewonnen hat. Daher muss dieser auch im ersten Zug in die Ecke legen.
Legt der erste Spieler am Anfang nicht in die Ecke besteht das ganz Spiel nur aus Abblock-Zügen und führt ebenfalls zum Unentschieden.
_________________
"It is practically impossible to teach good programming to students that have had a prior exposure to BASIC: as potential programmers they are mentally mutilated beyond hope of regeneration."
Edsger W. Dijkstra
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden
REZK



Anmeldungsdatum: 28.10.2004
Beiträge: 109
Wohnort: Stuttgart

BeitragVerfasst am: 31.10.2004, 14:36    Titel: re Antworten mit Zitat

ja, mister d, du hast schon recht, eigentlich lohnt es sich nicht eine ki für ttt zu programmieren, aber ich wollte meinen oben schon erläuterten ansatz einmal in einem beispiel ausprobieren und da kam mir ttt gerade recht...

da er schon mit zufälligen zügen so schlecht nicht rechnet, denke ich, dass der ansatz auch für größere projekte nicht einmal so unsinnig ist.

vielleicht hat ja trotzdem einer eine ki...
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden Website dieses Benutzers besuchen
Tomtitom



Anmeldungsdatum: 20.09.2004
Beiträge: 308

BeitragVerfasst am: 01.11.2004, 14:59    Titel: Antworten mit Zitat

Also es hat mal jemand gesagt, eine gute KI besteht aus sehr sehr vielen If-Abfragen, dementsprechend ein Code http://www.jordanautomations.com/tictactoe.html (Tipp: auch mal Googeln)
hups, irgendwie funktioniert der Code nicht, dann nimm z.B. den http://www.qbasic.com/files/ttt.zip

Und zu deiner Methode an sich, also das ist schon interessant, was du machst, denn es hat schon einen Ansatz von evolutionären KI, aber ich vermute mal, du speicherst nicht die Ergebnisse.
Falls du aber mal doch sowas machen willst, würde mich dein Fortschritt interessieren. Möglichst aber für etwas komplexere Spiele wie 4gewinnt
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden
REZK



Anmeldungsdatum: 28.10.2004
Beiträge: 109
Wohnort: Stuttgart

BeitragVerfasst am: 04.11.2004, 09:46    Titel: 4 gewinnt mit ergebnisse speichern Antworten mit Zitat

@tomtitom

ich hab mir gestern überlegt, ob ich so ein Projekt wie von dir vorgeschlagen beginnen soll (4 gewinnt mit evolutionärer KI, die durch speichern d. ergebnisse von spiel zu spiel stärker wird).
Aber ich habe ausgerechnet, dass die datei, in der alle spielzüge gescheichert sein müssten so um die 20 Petabyte gross wäre. Aber ich werd mir noch was überlegen...
REZK
_________________
Meine sämtlichen QB Projekte findet ihr hier
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden Website dieses Benutzers besuchen
Skilltronic



Anmeldungsdatum: 10.09.2004
Beiträge: 1148
Wohnort: Köln

BeitragVerfasst am: 04.11.2004, 13:28    Titel: Antworten mit Zitat

Hallo !

Ich finde, mit dem Begriff der KI wird oft etwas groszügig umgegangen.

Eine Datei anzulegen, in der bereits dagewesene Spielzüge und deren Folgen gespeichert werden reicht noch nicht aus. Das sieht man schon daran, dass ein halbwegs intelligenter Mensch dem die Regeln von 4 Gewinnt zum ersten mal erklärt werden, sofort spielen kann ohne vorher eine 20 Petabyte-Bibliothek angelegt zu haben.

Bei solchen Brett- und Kartenspielen ist es die einfachste Lösung, so vorzugehen wie man es selber in diesem Fall auch tut. Man geht im Geiste mehrere Spielzüge im Voraus durch und versucht so, die beste Möglichkeit zu finden. Da der Rechner dies sehr schnell und präzise tun kann, reicht das eigentlich auch schon aus, um mit uns Menschen mithalten zu können. Auch wenn man dabei dann nicht unbedingt von KI sprechen kann.

Natürlich lernt ein Spieler und wird mit der Zeit immer besser. Das ist auch der Grund, warum wir überhaupt noch gegen ein gutes Programm gewinnen können. Dieses intellligente Verhalten besteht aber nicht nur darin, eine Datenbank anzulegen und dann nachzusehen, ob man schonmal dieselbe Entscheidung treffen musste bzw. wenn ja, bei welcher Reaktion kam es zu welchem Ergebnis.

Ein Wesenselement der Intelligenz ist es, auch auf ganz neue Umstände noch eine angemessene Antwort zu finden. Das geschieht, indem eigentlich alle früheren Spielsituationen in die Bewertung miteinbezogen werden. Wie stark sie berücksichtigt werden, hängt dabei davon ab, wie "ähnlich" sie der neuen sind. Und ganau da liegt der Knackpunkt.

Letztendlich geht es dabei - wie so oft wenn von KI die Rede ist - um eine Mustererkenung. Das sieht man schon beim TicTacToe. Ein nicht unwichtiger Teil eines solchen Programms besteht ja darin, Reihen zu finden, die mit einem der nächsten Züge vervollständigt werden können. Dazu testet der Rechner Reihe für Reihe, Zeile für Zeile und die Diagonalen. Bei 4 Gewinnt wird das schnell unübersichtlich. Der Mensch geht anders vor. Er erkennt sozusagen "intuitiv" das Muster einer angefangenen Reihe. Egal wo und wie diese im Spielfeld liegt - man sieht sie eben einfach (meisstens). So wie wir einen Tisch erkennen, egal ob es ein runder aus Plastik mit einem Bein an einer Imbissbude ist, oder ein schwerer Wohnzimmertisch mit 4 Beinen. Ohne darüber nachzudenken. Das einem Bilderkennungsprogramm beizubringen ist nicht einfach.

Die Leistung hängt zwar von der Grösse der Wissensbasis ab, aber eben auch - wenn nicht vor allem von deren Auswertung. Sonst könnte niemand von einem Spieler mit weniger Erfahrung geschlagen werden. Und die Auswertung durch das Programm so gut zu machen, dass sie an die menschliche herankommt ist sehr, sehr schwierig. Schliesslich sind das Gehirn und die Augen seit ein paar hundert Millionen Jahren auf genau eine solche Mustererkennung und -auswertung getrimmt. Der Rechner dagegen ist von seiner ganzen Architektur nicht darauf ausgelegt, mit Begriffen wie ähnlich oder ungefähr umzugehen.

Speziell beim TicTacToe könnte so eine Datenbank doch ganz sinvoll sein. Selbst wenn man von allen Drehungen und Spiegelungen (Mustererkennung !) absieht, gibt es nur 10862 gültige Spielstände, von denen 6326 Siegstellungen sind.

Für kompliziertere Spiele ist es besser, einfach für mehrere Spielzüge im Vorraus alle Möglichkeiten durchzutesten. Da der Rechenaufwand dabei schnell ansteigt, muss man nur einen Kompromiss finden zwischen Spielgeschwindigkeit und der Zahl der Spielrunden, die vorberechnet werden sollen.

Wen's interessiert, dem schicke ich auf gerne mal ein 4-gewinnt, das ich selbst nach diesem Prinzip geschrieben habe. Der Code ist zwar gruselig und wird ausdrücklich nicht zur Nachahmung empfohlen, aber es läuft so einigermassen.

Gruss
Skilltronic
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden Website dieses Benutzers besuchen
REZK



Anmeldungsdatum: 28.10.2004
Beiträge: 109
Wohnort: Stuttgart

BeitragVerfasst am: 04.11.2004, 15:16    Titel: Antworten mit Zitat

@skill

ja, dein 4gewinnt kenne ich ja schon, du meines soweit ich weiss auch...
Eine Frage: Wie kommst du auf die 10862 Spielstände?? Ich werde sobald ich Zeit habe wahrscheinlich so ein TicTacToe mit einer Zugdatenbank, die sich mit jedem Spiel selbst erweitert programmieren.....

Im alten Forum habe ich noch etwas zu diesem Thema gefunden
http://212.168.28.138/cgi-bin/forum/forum.pl?session=&Imsg=34669


REZK
_________________
Meine sämtlichen QB Projekte findet ihr hier
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden Website dieses Benutzers besuchen
Skilltronic



Anmeldungsdatum: 10.09.2004
Beiträge: 1148
Wohnort: Köln

BeitragVerfasst am: 04.11.2004, 21:35    Titel: Antworten mit Zitat

REZK hat Folgendes geschrieben:
@skill

ja, dein 4gewinnt kenne ich ja schon, du meines soweit ich weiss auch...
Eine Frage: Wie kommst du auf die 10862 Spielstände??


Du kennst mein 4gewinnt schon? Ich habe es doch erst an ein oder zwei Leute geschickt und das ist schon ewig her? Hm, dann bist du wohl einer davon. Mein Gedächtnis ist auch nicht mehr das beste...


Auf die 10862 Spielstände komme ich so. Die neun Felder konnen drei Zustände annehmen - leer, Kreuz und Kreis. Das macht maximal 3^9 = 19683 Möglichkeiten. Davon sind aber viele ungültig, die noch aussortiert werden müssen. Ich habe das so gemacht:

Code:

CLS
GOSUB rechnen
DIM z%(19683)
FOR a = 0 TO 19682
w = a
FOR f = 0 TO 8
t(f) = FIX(w / q(f))
w = w - t(f) * q(f)
NEXT
s(1) = 0
s(2) = 0
FOR f = 0 TO 8
s(t(f)) = s(t(f)) + 1
NEXT
IF s(2) > s(1) OR s(1) - 1 > s(2) THEN z%(a) = -1
IF z%(a) = 0 THEN GOSUB test
IF k > 1 THEN z%(a) = -1
IF k = 1 THEN z%(a) = g
IF z%(a) = -1 THEN ung = ung + 1
IF z%(a) = 0 THEN gos = gos + 1
IF z%(a) = 1 THEN sga = sga + 1
IF z%(a) = 2 THEN sgb = sgb + 1
NEXT
PRINT "ungueltige      : "; ung
PRINT "gueltige o. Sieg: "; gos
PRINT "Sieger 1        : "; sga
PRINT "Sieger 2        : "; sgb
PRINT "----------------------"
PRINT "Gesamt          :"; ung + gos + sga + sgb
END

test:
g = 0
k = 0
FOR r = 0 TO 6 STEP 3
IF t(r) = t(r + 1) AND t(r) = t(r + 2) AND t(r) > 0 THEN g = t(r): k = k + 1
NEXT
FOR r = 0 TO 2
IF t(r) = t(r + 3) AND t(r) = t(r + 6) AND t(r) > 0 THEN g = t(r): k = k + 1
NEXT
IF t(0) = t(4) AND t(4) = t(8) AND t(4) > 0 THEN g = t(4): k = k + 1
IF t(2) = t(4) AND t(4) = t(6) AND t(4) > 0 THEN g = t(4): k = k + 1
RETURN

rechnen:
FOR a = 0 TO 8
q(a) = 3 ^ (8 - a)
NEXT
RETURN




Gruss
Skilltronic
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden Website dieses Benutzers besuchen
Beiträge der letzten Zeit anzeigen:   
Neues Thema eröffnen   Neue Antwort erstellen    Das deutsche QBasic- und FreeBASIC-Forum Foren-Übersicht -> Allgemeine Fragen zu QBasic. 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